0

この問題に遭遇したとき、私はprojecteuler の問題 151 ( http://projecteuler.net/problem=151 )で忙しかったです。

envelopeArrayList (2 の累乗のみを含む) と intindexをパラメーターとして使用して単純な再帰を作成しようとしています。最初に、エンベロープの位置にある整数をindex、その下のすべての 2 の累乗に置き換えます (たとえば、16 は 8,4,2,1 になります)。次に、インデックスを 0 から新しいものの終わりまでループenvelopeし、新しいエンベロープと新しいインデックスをパラメータとして使用して同じ再帰を適用し、エンベロープが {1} に等しくなるまで続けます。これを行う方法の数を数えているとしましょう。これはコードです：

import java.util.ArrayList;

public class Prob151 {

public static void main(String[] args) {
    totalCount = 0;
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(8);
    recursion(list,0,1);
    System.out.printf("%d",totalCount);
}

public static int totalCount;

public static void recursion(ArrayList<Integer> envelope, int index, int batch) {
    int number = envelope.get(index); 
    if (envelope.size() == 1 && number == 1) {

        totalCount += 1;

    } else {

        // Updates the envelope
        envelope.remove(index);
        while (number > 1) {
            number /= 2;
            envelope.add(number);
        }
        batch += 1;

        for (int i = 0; i < envelope.size(); i++) {
            // Displays current information
            System.out.printf("batch = %d, envelope = {",batch);
            for (int j : envelope) {
                System.out.printf("%d,",j);
            }
            System.out.printf("}, i = %d\n",i);

            recursion(envelope,i,batch);
        }

    }
}

}

これは私が得た出力でした：

batch = 2, envelope = {4,2,1,}, i = 0
batch = 3, envelope = {2,1,2,1,}, i = 0
batch = 4, envelope = {1,2,1,1,}, i = 0
batch = 5, envelope = {2,1,1,}, i = 0
batch = 6, envelope = {1,1,1,}, i = 0
batch = 7, envelope = {1,1,}, i = 0
batch = 8, envelope = {1,}, i = 0
1

インデックス i = 1 でバッチ 7 に戻る代わりに、エンベロープ = {1} の最初のインスタンスに遭遇した後に停止します。必要な結果を得るには何を変更すればよいですか?

前もって感謝します！

4

1 に答える 1

0

ここで役立ついくつかのこと:

1) 間違ったデータ構造を使用しています。問題は明らかに、彼がエンベロープをランダムに取得していることを示しています。の使用を強くお勧めしますBag。

2) 最初のバッチが実行されると、エンベロープには次の要素が含まれます。 

1 A2    
1 A3  
1 A4  
1 A5

1 in 4したがって、最初のパスでA5 を選択するA5確率A2は 

2 A3  
2 A4  
2 A5

これで、3 番目のバッチは2 in 6(3 分の 1) の確率でA5.

この説明にさらに説明が必要な場合はお知らせください。

于 2013-01-25T15:03:31.860 に答える