以下の様な、「階段の上り方」の問題です。

それぞれの段に行くまでに何通りあるか、というのを考えます。

0段目はスタート地点なので、1通り、

1段目は0段目からでしか行けないので1通り、

2段目は0段目から来るケースと1段目からケースがあるから、0段目と1段目の合計値、

それ以降はi段目はi-1段目とi-2段目の合計値となります。

最終的にN段目の合計値を出力すればOKです。

        public int UpsideStairs(int N)
        {
            int[] dp = new int[45];

            for(int i = 0; i <= N; i++)
            {
                if(i <= 1)
                {
                    dp[i] = 1;
                }
                else
                {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            }

            return dp[N];
        }

カエルの移動というのはこんな感じの問題です。

アルゴリズムのテキストから抜粋しました。

これを計算するのに動的計画法を使用します。

動的計画法とは、数列の漸化式のように問題を小さな問題（一つ前の）計算結果を使用して解くアルゴリズムで、

では漸化式とは？というと、例えばフィボナッチ数列のように、1+1=2、1+2=3、2+3=5、3+5=8のような数列です。

一般化すると、H[i-1]を使用して計算した値と、H[i-2]を使用して計算した値を比較して、適用する値を決定、それを繰り返していく、というやりかたですな。（現時点での理解）

        public int FrogMove(int[] H)
        {
            int[] dp = new int[H.Length];

            for(int i = 0; i < H.Length; i++)
            {
                if(i == 0)
                {
                    dp[i] = 0;
                }
                if(i == 1)
                {
                    dp[i] = Math.Abs(H[i - 1] - H[1]);
                }
                if(i >= 2)
                {
                    int v1 = dp[i - 1] + Math.Abs(H[i - 1] - H[i]);
                    int v2 = dp[i - 2] + Math.Abs(H[i - 2] - H[i]);
                    dp[i] = Math.Min(v1, v2);
                }
            }
            return dp[H.Length - 1];
        }

テキストに書いてあったマージソートのアルゴリズムです。

        public void MargeSort(List<int> A)
        {
            List<int> C = new List<int>();
            for(int i = 0; i < A.Count; i++)
            {
                C.Add(0);
            }
            MargeSortSub(A, C, 0, A.Count);
        }

        public void MargeSortSub(List<int> A, List<int> C, int l, int r)
        {
            if(r - l == 1)
            {
                return;
            }

            int m = (l + r) / 2;
            MargeSortSub(A, C, l, m);
            MargeSortSub(A, C, m, r);

            int c1 = l;
            int c2 = m;
            int cnt = 0;

            while(c1 != m || c2 != r)
            {
                if (c1 == m)
                {
                    C[cnt] = A[c2];
                    c2++;
                }else if (c2 == r)
                {
                    C[cnt] = A[c1];
                    c1++;
                }else
                {
                    if(A[c1] <= A[c2])
                    {
                        C[cnt] = A[c1];
                        c1++;
                    }else
                    {
                        C[cnt] = A[c2];
                        c2++;
                    }
                }
                cnt++;
            }

            for(int i = 0; i < cnt; i++)
            {
                A[l + i] = C[i];
            }
        }

nCr=n! / r!(n – r)!なので、nPr / r!で求められるはず。

        /**
         * nCrを求める
         * 
         * @param n 
         * @param r 
         * @return nCr
         */
        public long C(long n, long r)
        {
            return P(n, r) / Factorial(r);
        }

        /**
         * nの階乗を求める
         * 
         * @param n 
         * @return nPr
         */
        public long Factorial(long n)
        {
            long ret = 1;
            if(1 < n)
            {
                ret = n * Factorial(n - 1);
            }
            return ret;
        }

nPr = n!/(n-r)! = n × (n – 1) × (n – 2) ×･･･× (n – (r + 1))なので、

        /**
         * nPrを求める
         * 
         * @param n 
         * @param r 
         * @return nPr
         */
        public long P(long n, long r)
        {
            long ret = 1;
            if(0 < n - r)
            {
                ret = n * P(n - 1, r);
            }
            return ret;
        }

これで求められるはず。

二つの値の最大公約数を求めるアルゴリズムです。

まともに計算すると時間が掛かるので、ユークリッドの互除法というアルゴリズムを使用します。

        /**
         * AとBの最大公約数を求める(ユークリッドの互除法)
         * 
         * @param A 最大公約数を求める対象の値A
         * @param B 最大公約数を求める対象の値B
         * @return AとBの最大公約数
         */
        public long GreatestCommonDivisor(long A, long B)
        {
            while(A >= 1 && B >= 1)
            {
                if(A < B)
                {
                    B = B % A;
                }
                else
                {
                    A = A % B;
                }
            }
            if(A >= 1)
            {
                return A;
            }
            return B;
        }

ポイントは、

・大きい方の数を「大きい方を小さい方で割った余り」に書き換える処理を繰り返す

・片方が0になったら操作を終了する。もう片方の数が最大公約数

というところ。

値Nが持つ約数を列挙するアルゴリズムです。

        /**
         * 引数Nの約数をリストで返す
         * 
         * @param N 約数を求める値
         * @return Nの約数のリスト
         */
        public List<long> CalculateIsprimeList(long N)
        {
            List<long> list = new List<long>();
            for (long i = 2; i * i <= N; i++)
            {
                if (N % i != 0)
                {
                    continue;
                }
                list.Add(i);
                if(i != N / i)
                {
                    list.Add(N / i);
                }
            }

            list.Sort();
            return list;
        }

前回の素数判定のコードと似ています。

【C#】【アルゴリズム】素数かどうかを判定するアルゴリズム

小さい値から、Nの約数を求めていき、約数だった場合、その値と商も約数として出力します。

値Nが素数かどうかを判定するには、2~√Nで割り切れなければ素数らしい。

        /**
         * 引数Nが素数かどうかを判定する
         * 
         * @oaram N 素数判定する値
         * @return 素数:true/素数でない:false
         */

        public bool isprime(long N)
        {
            for(long i = 2; i * i <= N; i++)
            {
                if(N % i == 0)
                {
                    return false;
                }
            }
            return true;
        }