0

当我遇到这个问题时，我正忙于 projecteuler 的问题 151，http ://projecteuler.net/problem=151。

我正在尝试使用 ArrayList envelope（仅包含 2 的幂）和 intindex作为参数进行简单的递归。它首先用它下面的所有 2 的幂替换包络位置的整数index（例如，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

所以第一次选择 A5 的几率是1 in 4，所以如果A5在第一次选择中找不到 A5，我们会得到A2你的信封，如下所示： 

2 A3  
2 A4  
2 A5

现在第三批有2 in 6（三分之一）的机会选择一个A5。

让我知道这个澄清是否需要更多解释。

于 2013-01-25T15:03:31.860 回答