Project Euler 问题 14(Collat​​z 问题) [英] Project Euler Question 14 (Collatz Problem)

问题描述

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

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

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

n ->n/2 (n is even) n ->3n + 1 (n is odd)

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

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

13 40 20 10 5 16 8 4 2 1可以看出，这个序列(从13开始到1结束)包含10项.虽然还没有被证明(Collat​​z 问题)，但认为所有的起始数都以 1 结束.

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.

100 万以下的哪个起始数字产生最长的链?

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

注意:一旦链开始，条款就可以超过一百万.

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

我尝试使用蛮力方法在 C 中编写解决方案.但是，我的程序在尝试计算 113383 时似乎卡住了.请指教 :)

I tried coding a solution to this in C using the bruteforce method. However, it seems that my program stalls when trying to calculate 113383. Please advise :)

#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
", value);
 while(value!=1)
 {
  value=iteration(value);
  //printf("%d
", 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
", i);
  iteration_count=count_iterations(i);
  if (iteration_count>max)
   {
   max=iteration_count;
   count=i;
   }

 }

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

}

推荐答案

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

The reason you're stalling is because you pass through a number greater than 2^31-1 (aka INT_MAX); try using unsigned long long instead of int.

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

I recently blogged about this; note that in C the naive iterative method is more than fast enough. For dynamic languages you may need to optimize by memoizing in order to obey the one minute rule (but this is not the case here).

糟糕，我又做了一次(这个时间检查使用 C++ 进一步可能的优化).

Oops I did it again (this time examining further possible optimizations using C++).

这篇关于Project Euler 问题 14(Collat​​z 问题)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！