1

数字 1 と 2 だけを使用して、合計 (1000000 など) になる方法の数を見つける必要があります。順序が重要です。組み合わせを使用してソリューションを作成しました：

ここに画像の説明を入力

n合計はどこですか。

例：

には、方法n=7があり21ます。

1111111、111112、111121、111211、112111、121111、211111、11122....1222、2122、2212、2221

数は非常に大きくなる可能性があり、いくつかの大きな素数を法として見つけなければなりません。（はい、オンラインコーディングコンテストの小さな問題です）。もっとコンピュータにやさしい式が必要です。何か助けてください。それとも、再帰と行列累乗を作成することで実行できますか?

4

4 に答える 4

1

見つけようとしている数は、n 番目のフィボナッチ数です。最良の方法 (n は非常に大きくなる可能性があるため) は、この再帰O(log n)式を実装することです (これらは 2x2 の行列です。見苦しい形式で申し訳ありません)。

[F(n+2)] = [1 1] [F(k+1)]
[F(n+1)]   [1 0] [F (k) ]

おそらく、再帰的な形式よりも明示的な形式の方が適しているでしょう:

[1 1]^n = [F(k+1)   F(k) ]
[1 0]     [ F(k)   F(k-1)]

フィボナッチ数を計算するのは、私が知っている最速の方法です。出力は非常に急速に大きくなるため、大きな n の結果をキャッシュできないことに注意してください。

于 2013-02-03T10:44:09.620 に答える
1

これを行う方法の数は、簡単に計算できる n 番目のフィボナッチ数 F(n) に等しくなります。

帰納法による証明。n について true と仮定します。長さ n+1 のシーケンスを考えてみましょう。これは、合計 n のシーケンスに 1 を追加するか、合計 n-1 のシーケンスに 2 を追加することによって形成できます。これは明確であり、すべての可能性を表しています。

したがって、F(n+1) = F(n) + F(n-1) F(1) = 1

いいですね。

于 2013-02-03T05:13:02.743 に答える
0

これが私が思いついたものです：

def onesAndTwos(num):
    if num <= 0:
        return set()
    elif num == 1:
        return set([(1, 0)])
    elif num == 2:
        return set([(2,0), (0, 1)])
    else:
        setA = set([(1 + x[0], x[1]) for x in onesAndTwos(num-1)])
        setB = set([(x[0], 1 + x[1]) for x in onesAndTwos(num-2)])
        setA.update(setB);
        return setA

print onesAndTwos(10)
print len(onesAndTwos(10))

最初の要素が 1 の数で、2 番目の要素が 2 の数である一連のタプルを使用します。したがって、 で合計 3 を生成できますset[(3,0), (1,1)]。組み合わせがいくつあるかを調べるには、セット内のタプルを数えます。10 の出力:

set([(8, 1), (6, 2), (0, 5), (4, 3), (10, 0), (2, 4)])
6

これは幾分動的プログラミングのアプローチであり、一連の繰り返し発生するサブ問題と同様の構造が全体にあり、以前のソリューションに基づいて構築することができます。これは、2 つのブランチ (1 を取り除くときの 1 つ目と 2 を取り除くときの 2 つ目) で以前に計算された値を再利用していないため、最適ではありません。

于 2013-02-03T03:25:48.990 に答える
0 
public class Fibonacci {
    public static int magic(int input) {
        if (input == 1) {
            return 1;
        } else if (input == 2) {
            return 2;
        } else {
            return magic(input-1) + magic(input-2);
        }
    }

    public static void main(String args[]) {
        int input = 7;
        int numberOfCombinations = magic(input);
        System.out.println("The total number of combinations for the given integer "+input+" is "+numberOfCombinations);
    }
}

完全で動作する Java コード。大会などにご自由にお使いください。コードが基礎となるアルゴリズムを自明であるといいのですが。幸運を！

于 2013-02-03T05:02:38.090 に答える