4

我正在尝试用 c++ 完成 Project Euler Problem 14，但我真的被卡住了。现在，当我运行问题时，它卡在 So Far：计数最高的数字：113370，计数为 155 So Far：计数最高的数字，但是当我尝试将 i 值更改为超过 113371 时，它可以工作。到底是怎么回事？？

问题是：

为正整数集定义了以下迭代序列： n → n/2（n 为偶数） n → 3n + 1（n 为奇数）

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 可以看出，这个序列（从 13 开始，到 1 结束）包含 10 个项。虽然尚未证明（科拉茨问题），但认为所有起始数字都以 1 结束。100 万以下的哪个起始数字产生最长的链？

#include<stdio.h>
int main() {
    int limit = 1000000;
    int highNum, number, i;
    int highCount = 0;
    int count = 0;
    for( number = 13; number <= 1000000; number++ )
    {
        i = number;
        while( i != 1 ) {
            if (( i % 2 ) != 0 ) {
                i = ( i * 3 ) + 1;
                count++;
            }
            else {
                count++;
                i /= 2;
            }
        }
        count++;
        printf( "So Far: the number with the highest count: %d with the count of %d\n",
                     number, count );
        if( highCount < count ) {
            highCount = count;
            highNum = number;
        }
        count = 0;
        //break;
    }
    printf( "The number with the highest count: %d with the count of %d\n",
            highNum, highCount );
}
4

4 回答 4

3

你得到整数溢出。像这样更新您的代码并自己查看：

if (( i % 2 ) != 0 ) {
    int prevI = i;
    i = ( i * 3 ) + 1;
    if (i < prevI) {
        printf("oops, i < prevI: %d\n", i);
        return 0;
    }
    count++;
}

您应该将类​​型更改i为long long或unsigned long long以防止溢出。

（是的，缓存中间结果）

于 2014-10-24T22:17:00.747 回答
3

记住所有中间结果（直到某个适当高的数字）。
另外，使用足够大的类型：

#include <stdio.h>

static int collatz[4000000];
unsigned long long collatzmax;

int comp(unsigned long long i) {
  if(i>=sizeof collatz/sizeof*collatz) {
      if(i>collatzmax)
        collatzmax = i;
      return 1 + comp(i&1 ? 3*i+1 : i/2);
  }
  if(!collatz[i])
      collatz[i] = 1 + comp(i&1 ? 3*i+1 : i/2);
  return collatz[i];
}

int main() {
  collatz[1] = 1;
  int highNumber= 1, highCount = 1, c;
  for(int i = 2; i < 1000000; i++)
    if((c = comp(i)) > highCount) {
      highCount = c;
      highNumber = i;
    }
  printf( "The number with the highest count: %d with the count of %d\n",
        highNumber, highCount );
  printf( "Highest intermediary number: %llu\n", collatzmax);
}

关于大肠杆菌： http ://coliru.stacked-crooked.com/a/773bd8c5f4e7d5a9

运行时间较小的变体：http: //coliru.stacked-crooked.com/a/2132cb74e4605d5f

The number with the highest count: 837799 with the count of 525
Highest intermediary number: 56991483520

BTW：遇到的最高中介需要 36 位来表示为无符号数。

于 2014-10-24T22:18:52.680 回答
0

使用您的算法，您可以计算几个时间相同的序列。您可以缓存以前数字的结果并重复使用它们。

就像是：

void compute(std::map<std::uint64_t, int>& counts, std::uint64_t i)
{
    std::vector<std::uint64_t> series;
    while (counts[i] == 0) {
        series.push_back(i);
        if ((i % 2) != 0) {
            i = (i * 3) + 1;
        } else {
            i /= 2;
        }
    }
    int count = counts[i];
    for (auto it = series.rbegin(); it != series.rend(); ++it)
    {
        counts[*it] = ++count;
    }
}

int main()
{
    const std::uint64_t limit = 1000000;

    std::map<std::uint64_t, int> counts;
    counts[1] = 1;
    for (std::size_t i = 2; i != limit; ++i) {
        compute(counts, i);
    }
    auto it = std::max_element(counts.begin(), counts.end(),
        [](const std::pair<std::uint64_t, int>& lhs, const std::pair<std::uint64_t, int>& rhs)
        {
            return lhs.second < rhs.second;
        });
    std::cout << it->first << ":" << it->second << std::endl;
    std::cout << limit-1 << ":" << counts[limit-1] << std::endl;
}

演示（10 秒）

于 2014-10-24T21:46:40.223 回答
0

不要一遍又一遍地重新计算相同的中间结果！

给定

typedef std::uint64_t num;  // largest reliable built-in unsigned integer type

num collatz(num x)
{
    return (x & 1) ? (3*x + 1) : (x/2);
}

那么 的值collatz(x)仅取决于x，而不取决于您何时调用它。（换句话说，collatz是一个纯函数。）因此，您可以记住的collatz(x)不同值的值x。为此，您可以使用 astd::map<num, num>或 a std::unordered_map<num, num>。

作为参考，这里是完整的解决方案。

它在Coliru上，有时间（2.6 秒）。

于 2014-10-24T21:54:00.837 回答