平方数数字和

无心人

另外，GxQ的代码完全不用事后计算平方阿 当时填充结果的时候就可以复制过去的 或者说，是否根本不用记录平方的根 就闷头搜索平方就可以了

gxqcn

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

这个想法是不错，甚至可以考虑直接存储输出的字符串。 但我那个程序，主要是想直接存平方根，仅4Bytes，比较节省内存， 而后期展开的运算代价很小。

无心人

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

无心人

157 28979978999958969889 20位内无更高的结果了 要对GxQ代码动大手术 去掉很多无用的代码 呵呵明天抽时间做下 呵呵，计算出145消耗的时间缩小到48秒 如果是GxQ机器还快吧

2. #include <stdlib.h>
3. #include <stdio.h>
6. #define TEN_POW2 100UL
7. #define TEN_POW4 10000UL
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;
16. unsigned long i, j, k, m, s;
17. long t;
18. unsigned long i2, i3, i4, s2, s3;
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. }
36. for (i=0; i < 8; i ++)
37. {
38. value[i] = 0;
39. delta[i] = 0;
40. }
42. for (i = 0; i < 9*32 + 1; i ++)
43. mark[i] = 0;
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. }
60. s += table[ value[ i ] ];
61. }
63. if (value[m])
64. {
65. m++;
66. s++;
67. }
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. }
78. if (m >= 9)
79. break;
81. delta[ 0 ] += 2;
83. i = 0;
84. while ( delta[ i ] >= TEN_POW4 )
85. {
86. delta[ i ] -= TEN_POW4;
87. ++delta[ ++i ];
88. }
89. }
91. s = 0;
92. i = 0;
93. printf( "\n" );
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