项目欧拉问题14(Collat​​z问题)

Question

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

n - > n/2(n是偶数)n - > 3n + 1(n是奇数)

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

13 40 20 10 5 16 8 4 2 1可以看出,这个序列(从13开始,1完成)包含10个术语.虽然尚未证实(Collat​​z问题),但据认为所有起始数字都是1.

哪个起始编号低于一百万,产生最长的链？

注意:链条启动后,条款允许超过一百万.

我尝试使用bruteforce方法在C中编写解决方案.但是,似乎我的程序在尝试计算113383时失速.请指教:)

#include <stdio.h>
#define LIMIT 1000000

int iteration(int value)
{
 if(value%2==0)
  return (value/2);
 else
  return (3*value+1);
}

int count_iterations(int value)
{
 int count=1;
 //printf("%d\n", value);
 while(value!=1)
 {
  value=iteration(value);
  //printf("%d\n", value);
  count++;
 }
 return count;
}

int main()
{
 int iteration_count=0, max=0;
 int i,count;


 for (i=1; i<LIMIT; i++)
 {
  printf("Current iteration : %d\n", i);
  iteration_count=count_iterations(i);
  if (iteration_count>max)
   {
   max=iteration_count;
   count=i;
   }

 }

 //iteration_count=count_iterations(113383); 
 printf("Count = %d\ni = %d\n",max,count);

}

Answer 1

你拖延的原因是你通过了一个大于2^31-1(又名INT_MAX)的数字; 尝试使用unsigned long long而不是int.

我最近在博客上写过这个 ; 请注意,在C中,天真的迭代方法足够快.对于动态语言,您可能需要通过记忆来优化以遵守一分钟规则(但这不是这里的情况).

哎呀我再次这样做(这次使用C++进一步检查可能的优化).

Answer 2

请注意,您的暴力解决方案通常会一遍又一遍地计算相同的子问题.例如,如果你开始10,你会得到5 16 8 4 2 1; 但如果你开始20,你得到20 10 5 16 8 4 2 1.如果您10一次缓存该值,则计算该值,然后不必再次计算它.

(这称为动态编程.)