平方数数字和

无心人

另外，GxQ的代码完全不用事后计算平方阿
当时填充结果的时候就可以复制过去的

或者说，是否根本不用记录平方的根
就闷头搜索平方就可以了

gxqcn

原帖由 无心人 于 2008-7-10 21:07 发表
另外，GxQ的代码完全不用事后计算平方阿
当时填充结果的时候就可以复制过去的

这个想法是不错，甚至可以考虑直接存储输出的字符串。

但我那个程序，主要是想直接存平方根，仅4Bytes，比较节省内存，
而后期展开的运算代价很小。

无心人

超过2^32再存平方根就比较麻烦了阿
另外在这个程序里
内存节约的很
呵呵

无心人

157     28979978999958969889
20位内无更高的结果了
要对GxQ代码动大手术
去掉很多无用的代码
呵呵明天抽时间做下

呵呵，计算出145消耗的时间缩小到48秒
如果是GxQ机器还快吧

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. 
   
5. 
   
6. #define TEN_POW2    100UL
   
7. #define TEN_POW4    10000UL
   
8. 
   
9. int main( void )
   
10. {
    
11.     unsigned long table[ TEN_POW4 ];
    
12.     unsigned long mark[ 9*32 + 1 ];
    
13.     unsigned long value[ 8 ], delta[ 8 ];
    
14.     unsigned long * p = table;
    
15. 
    
16.     unsigned long i, j, k, m, s;
    
17.     long t;
    
18.     unsigned long i2, i3, i4, s2, s3;
    
19. 
    
20.     for ( i4 = 0; i4 < 10; ++i4 )
    
21.     {
    
22.         for ( i3 = 0; i3 < 10; ++i3 )
    
23.         {
    
24.             s3 = i4 + i3;
    
25.             for ( i2 = 0; i2 < 10; ++i2 )
    
26.             {
    
27.                 s2 = s3 + i2;
    
28.                 for ( i = 0; i < 10; ++i )
    
29.                 {
    
30.                     *p++ = s2 + i;
    
31.                 }
    
32.             }
    
33.         }
    
34.     }
    
35. 
    
36.     for (i=0; i < 8; i ++)
    
37.     {
    
38.        value[i] = 0;
    
39.        delta[i] = 0;
    
40.     }
    
41. 
    
42.     for (i = 0; i < 9*32 + 1; i ++)
    
43.       mark[i] = 0;
    
44. 
    
45.     value[ 0 ] = 0;
    
46.     delta[ 0 ] = 1;
    
47.     m = 1;
    
48.     for ( ; ; )
    
49.     {
    
50.         s = 0;
    
51.         for ( i = 0; i < m; ++i )
    
52.         {
    
53.             value[ i ] += delta[ i ];
    
54.             if ( value[ i ] >= TEN_POW4 )
    
55.             {
    
56.                 value[ i ] -= TEN_POW4;
    
57.                 ++value[ i + 1 ];
    
58.             }
    
59. 
    
60.             s += table[ value[ i ] ];
    
61.         }
    
62.         
    
63.         if (value[m])
    
64.         {
    
65.           m++;
    
66.           s++;
    
67.         }
    
68. 
    
69.         if ( 0 == mark[ s ])
    
70.         {
    
71.         mark[s] = 1;
    
72.         printf("%d    ", s);
    
73.         for (t=7;t>=0;t--)
    
74.           printf("%04d", value[t]);
    
75.         printf("\n");
    
76.         }
    
77. 
    
78.         if (m >= 9)
    
79.            break;
    
80. 
    
81.         delta[ 0 ] += 2;
    
82. 
    
83.         i = 0;
    
84.         while ( delta[ i ] >= TEN_POW4 )
    
85.         {
    
86.             delta[ i ] -= TEN_POW4;
    
87.             ++delta[ ++i ];
    
88.         }
    
89.     }
    
90. 
    
91.     s = 0;
    
92.     i = 0;
    
93.     printf( "\n" );
    
94. 
    
95.     return 0;
    
96. }

复制代码

[ 本帖最后由 无心人 于 2008-7-11 07:37 编辑 ]

无心人

GxQ代码存在一个隐含的Bug
计算数位和没计算进位

就是说如果恰好进位到高位产生
他没加进位到s

结果10000会被计算到mark[0]中
但因为mark[0]不输出
所以看不到
呵呵

mathe

现在证明了猜想:
那么请问,是否对于每个9的倍数或模3余1的正整数,都存在一个完全平方数,数字之和是这个正整数

我们考虑
$(10^n-1)^2, (10^n-2)^2, (10^n-3)^2, (10^n-5)^2$
它们的结果非常规律,在$n>=2$时，数字和分别为$9n,9n+1,9n+4,9n-2$
所以我们只要在找到数字和为$1,4,7,9,10,13$的平方数，就完全证明了这个问题。

无心人

gxqcn

原帖由 无心人 于 2008-7-11 07:41 发表
GxQ代码存在一个隐含的Bug
计算数位和没计算进位

就是说如果恰好进位到高位产生
他没加进位到s

结果10000会被计算到mark[0]中
但因为mark[0]不输出
所以看不到
呵呵

mark[] 并未采用 10000 进制，应该没有你说的 bug 吧？

无心人

呵呵
你看看你程序的mark的全部输出
而不是部分结果哦

无心人

153    00000000000005899989587897999889
151    00000000000006979497898999879969
154    00000000000008899988895999696889
157    00000000000028979978999958969889
160    00000000000078897999969769888996
162    00000000000087989899898866889889
163    00000000000199989299899788979969
166    00000000000449998999899988698769