1

我正在寻找一个3 到 9 位数字的自恋号码。我有工作代码，但使用嵌套循环很麻烦。我想我可以使用递归，如何？

#include "stdafx.h"
#include <time.h>

int power(int a,int b)
{
    int t=1,i;
    for (i=0;i<b;i++)
        t*=a;
    return t;
}

int _tmain(int argc, _TCHAR* argv[])
{
    double t0=clock();
    int a,b,c,d,e,f,g,h,i;
    int len=9;
    for (a=1;a<=9;a++)
        for (b=0;b<=9;b++)
            for (c=0;c<=9;c++)
                for (d=0;d<=9;d++)
                    for (e=0;e<=9;e++)
                        for (f=0;f<=9;f++)
                            for (g=0;g<=9;g++)
                                for (h=0;h<=9;h++)
                                    for(i=0;i<=9;i++)
                                {
                                    int num=10*(10*(1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g)+h)+i;
                                    if (num==power(a,len)+power(b,len)+power(c,len)+power(d,len)+power(e,len)+power(f,len)+power(g,len)+power(h,len)+power(i,len))
                                        printf(" %d ",num);
                                }
                                printf("\n耗时： %f s",(clock()-t0)/CLOCKS_PER_SEC);

    return 0;
}
4

3 回答 3

2

您num只是简单地遍历从0(See Edit 2) 到 的所有数字999,999,999。所以你真的不需要迭代每个数字。一种做你想做的事情的简单方法，即使可能不再有效是这样的：

unsigned int num;
for (num = 0; num < 1000000000; ++num)      // will take long
{
    char digits[15];
    unsigned int i, other_num;
    sprintf(digits, "%09u", i);             // division used here
    other_num = 0;
    for (j = 0; j < 9; ++j)
        other_num += power(digits[j] - '0', len);
    if (num == other_num)
        printf(" %d ",num);
}

请注意，您可以power以更有效的方式完成您的功能。看到这个问题。

编辑1：（注：见Edit 2）

我正在阅读维基百科页面，事实证明你不应该设置len为 9，因为如果你有例如153，other_num应该是1^3 + 5^3 + 3^3（来自维基百科的例子）。

所以你应该通过以下方式调整循环：

unsigned int num;
for (num = 0; num < 1000000000; ++num)
{
    char digits[15];
    unsigned int i, other_num, len;
    len = snprintf(digits, 10, "%u", i);    // len returned by snprintf
    other_num = 0;
    for (j = 0; j < len; ++j)               // changed 9 to len
        other_num += power(digits[j] - '0', len);
    if (num == other_num)
        printf(" %d ",num);
}

编辑2：

我刚注意到你的号码是从 开始的100,000,000，所以你真的不需要关注Edit 1。不过，我相信如果您需要更改数字的范围，了解它是件好事。

于 2012-09-12T09:27:58.433 回答
1

美妙的循环。那这个呢：

for( num = 100000000; num <= 999999999; num++ ) {
    int compare = 0;
    for( k = 0; k < 10; k++ ) {
        int position = pow(10, k+1);
        int s = num%position;
        compare += pow(s, 9);
    }
    if( num == compare ) {
        printf("%d\n", num);
    }
}

当然，检查边界:)

于 2012-09-12T09:32:11.427 回答
0

实际上，如果我没记错的话，您正在检查num从 1 到 的所有值 ( ) 。10^len因此，从 1 到 的简单for循环10^len就足够了。然后您可以从中获取数字num并计算功率值。

我强烈建议先计算幂 1^len, 2^len ... 9^len 并将它们放入一个数组中。它将大大提高性能。

于 2012-09-12T09:30:06.543 回答