2

我正在解决 Project Euler 问题，但我被困在第 14 位，我确实设法使用蛮力解决了它，问题指出： http ://projecteuler.net/problem=14

为正整数集定义了以下迭代序列：

   n → n/2 (n is even)
   n → 3n + 1 (n is odd)

使用上面的规则并从 13 开始，我们生成以下序列：

   13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出，这个序列（从 13 开始，到 1 结束）包含 10 个术语。尽管尚未证明（科拉茨问题），但人们认为所有起始数字都以 1 结束。

哪个起始数字（低于 100 万）产生最长的链？

注意：一旦链启动，条款允许超过一百万。

我想做的是实现一个缓存，我想使用一个整数数组作为缓存，索引将是数字，存储在每个单元格中的计数将是链的长度，当我们命中一个数字时缓存单元已经有一个正数我们跳过进一步检查（打破循环），从循环中获取现有的计数器数据并将其添加到当前计数器值，然后从下一个数字开始，所以这里是实现：

由于 Project Euler 政策而删除了工作蛮力代码，下面是错误代码。

public class Challenge14 {

public static void main(String[] args) {
    
    int[] collatzCache=new int[1000000]; //cache
    
    int count=0;
    long maxCount=0;
    int maxNumber=0;
    long number;
    
    int limit=1000000;
    
    for(int i=0;i<limit;i++)
    {
        int counter=0;
        number=i;
        while(number>1)
        {
            if(number%2==0)
            {
                number=number/2;
            }
            else 
            {
                number=3*number+1;
            }

            if(number<limit && collatzCache[(int)number]>0) //check
            {
                counter=collatzCache[(int) number];
                break;
            }
            counter++;
        }
        count=counter+1;
        collatzCache[i]=count;
    if(count>maxCount)
    {
        maxCount=count;
        maxNumber=i;
    }
    }
    System.out.println(maxNumber);


}
}

但它不起作用，我在哪里出错了？是因为长到 int 类型转换吗？

4

1 回答 1

2

At this line:

counter=collatzCache[(int) number];

you overwrite what was in counter with the cache value and so lose the extra chain steps.

于 2014-01-12T20:26:16.410 回答