Problem2『Even Fibonacci numbers』

Fibonacci / OndasDeRuido

projecteuler.net

問題

　フィボナッチ数列において、400万以下の偶数項の総和を求めよ。

とりあえずフィボナッチ数列ぶん回すか！

using System;
using System.Diagnostics;

namespace Problem2
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(EF1(4000000));
        }

        static int EF1(int max)
        {
            int f1, f2;
            int sum = 0;

            f1 = 1;
            f2 = 1;
            while(true)
            {
                int f3 = f1 + f2;

                if (f3 > max) break;

                if (f3 % 2 == 0) sum += f3;

                f1 = f2;
                f2 = f3;
            }

            return sum;
        }
    }
}

　いつも通りフィボナッチ数列の項を1つ1つ判定して足していくプログラムです。

偶数の出かたとか

　フィボナッチ数列は
\( 0,1,1,2,3,5,8,13,21,34,\cdots \)
と続きます。
前の2項を足したものが次の項、という形ですね。
漸化式としてはこんなの。
\(a_{n+2} = a_{n+1} + a_{n} \)

　数列をよく見ればわかりますが、規則正しい間隔で偶数が出現してます。
最初の0を抜かせば、
\(奇数、奇数、偶数、奇数、奇数、偶数、\cdots \)
という形になっています。
つまり、約2/3が奇数なので全部奇数偶数チェックする必要はないってこと。

　じゃぁ偶数項だけ算出できないかなと考えて、偶数項だけ抜き出してみました。
\( 2, 8, 34, 144, 610, 2584, \cdots \)
じっと見てると「なんとなく4倍くらい…？」と感じたので(直感派)いじくると、こんな式になりました。
\( a_{n+2} = 4 \cdot a_{n+1} + a_{n} \)
例えば、偶数第4項の値を求めるには、
\( a_{4} = 4 \cdot a_{3} + a_{2} \)
\( a_{4} = 4 \cdot 34 + 8 \)
\( a_{4} = 136 + 8 = 144 \)
と、こんな感じ。
これを使えばフィボナッチ数列から偶数項だけを取り出せる。

　…まぁ、フィボナッチ数列の一般項使えばいいんですけどね。

偶数列でやってみる

using System;
using System.Diagnostics;

namespace Problem2
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(EF2(4000000));
        }

        static int EF2(int max)
        {
            int sum = 0;

            int f2 = 2;
            int f1 = 0;

            sum += f2;

            while (true)
            {
                int fnext = f2 * 4 + f1;

                if (fnext > max) break;

                sum += fnext;

                f1 = f2;
                f2 = fnext;
            }

            return sum;
        }
    }
}

フィボナッチ―自然の中にかくれた数を見つけた人

波紋と螺旋とフィボナッチ

不思議な数列フィボナッチの秘密

『バッドビート！～辻堂真夏のポーカー戦線～ 4th Bet ,5th Bet』を読んだ

comic-walker.com
　気づいたら4話と5話が出てた。

三行感想

・『人を殺せる、容易に』まぁ、じゃんけんで即死するし……
・制限時間みたいなものが無いのなら、四天王最強に対して総当たりも手だよな
・本当に確率の問題なのか？

バッドビート! ~辻堂真夏のポーカー戦線~ 1 (MFコミックス フラッパーシリーズ)

ガットショット ： 1 (アクションコミックス)

賭博堕天録カイジ ワン・ポーカー編(1) (ヤンマガKCスペシャル)

Project Euler : Problem1『Multiples of 3 and 5』

iPam - Jim! / marc kjerland

　projecteuler.net
数学的問題をプログラムで解きましょうね、というサイト。
週1で新しい問題が追加されるのかな？

問題1『3および5の倍数』

　英語じゃなくて日本語がいいです(本音)

問題の内容は、「1000未満の自然数のうち、3および5の倍数の総和を求めよ」という問題。

ループぶん回せばいいんでしょ？

　という考えで作ったのがこちらになります。

using System;
using System.Diagnostics;

namespace Problem1
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(solv1());
        }

        static int solv1()
        {
            int sum = 0;

            for (int i = 1; i < 1000; i++)
            {
                if ((i % 3 == 0) | (i % 5 == 0))
                {
                    sum += i;
                }
            }

            return sum;
        }
    }
}

　単純に1000までの数字を1つ1つ見ていき、「あ、これ3(または5)の倍数や！」と気づいたら足していくという処理。
答え出すだけなら別にこれでもいいんだけど。

より良い方法

　Wikipediaを見て、より良い方法があるのを知った。
プロジェクト・オイラー - Wikipedia
　包除原理や閉形式総和なんて難しい言葉使ってるけど、要は
3の倍数の総和と5の倍数の総和を足して、ダブルカウント状態にある15の倍数、その総和を引く。
ということ。

Wikipediaの方法

　何かもう、見るからに計算量少なくて済むのがわかりますよね。

using System;
using System.Diagnostics;

namespace Problem1
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(solv2());
        }

        static int solv2()
        {
            return SumM(1000, 3) + SumM(1000, 5) - SumM(1000, 15);
        }

        static int SumM(int MaxValue, int MultipleNumber)
        {
            int n = (MaxValue - 1) / MultipleNumber;

            return MultipleNumber * ((n * (n + 1)) / 2);
        }
    }
}

感想

　なるほど感がある。

オイラーの公式がわかる (ブルーバックス)

Project Euler

Project Euler

蝙蝠動画

　動画を見るまであまり気にしてなかったんですが、どうにもこうにも犬っぽくて可愛い。

コウモリ観察ブック―ニッポン里山探検隊シリーズ〈2〉 (ニッポン里山探検隊シリーズ (2))

身近で観察するコウモリの世界―町を飛ぶ不思議な野生動物 (子供の科学★サイエンスブックス)

MAFEX マフェックス ARMORED BATMAN アーマードバットマン 『バットマン vs スーパーマン』ノンスケール ABS&ATBC-PVC塗装済みアクションフィギュア