java - Project Euler 14(Collat​​z Conjecture)，问题在 Java 中实现缓存

Question

我正在解决 Project Euler 问题，但我卡在了第 14 个位置，我确实设法使用蛮力解决了它，问题是: http://projecteuler.net/problem=14

The following iterative sequence is defined for the set of positive integers:

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

Using the rule above and starting with 13, we generate the following sequence:

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

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

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

由于 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);


}
}

但是它不起作用，我哪里出错了？是long转int的原因吗？

Answer 1

在这一行:

counter=collatzCache[(int) number];

你覆盖了与缓存值相反的内容，因此失去了额外的链步骤。