平方数问题一则

无心人

我那个算法还是做了点优化的
就是在判定是否平方数上

你用开方算是不对的

另外，穷举平方数用累加
计算数字和用Cache法

kofeffect

原帖由 无心人 于 2009-1-31 22:37 发表


我那个算法还是做了点优化的
就是在判定是否平方数上

你用开方算是不对的

另外，穷举平方数用累加
计算数字和用Cache法

开方算为什么不对啊

穷举平方数用累加
计算数字和用Cache法

请教这两招怎么用

无心人

因为，数字和的范围是很小的
比如24*9内的数字就能表示24位以内整数的数字和
只要预先把这个数字范围的数中的数字标上是否平方数就可以了

累加的算法看平方数数字和问题的GxQ的分析
具体是$(N + 1)^2 = N^2 + 2N + 1$

Cache法是预先计算4位数（0-9999）的数字和
然后，你用10000进制表示你的数字就可以节约分解数字的计算了

当然1000000进制也可以， 不过预先计算的工作量多些

kofeffect

再修改下：

1. Clear[a, s, i, j, k, len, lst, squareLst];
   
2. k = 1;
   
3. a = 0;
   
4. len = 0;
   
5. squareLst = Table[i^2, {i, 1, 15}];(*初始化和为平方数的列表*)
   
6. For[i = 1, i < 10^5 + 1, i++,
   
7.     a += i + i - 1;(*使用累加(n + 1)^2 = n^2 + n + n + 1计算平方数*)
   
8.     (*二重平方数*)
   
9.     len = Length[IntegerDigits[a]];
   
10.     lst = IntegerDigits[a];
    
11.     s = 0;
    
12.     (*计算数字和*)
    
13.     For[j = 1, j < len + 1, j++,
    
14.       s += Part[lst, j];
    
15.       ];
    
16.     If[MemberQ[squareLst, s],(*PutAppend[NO : k | a | s, "2SquareNum.txt"];*)
    
17.       (*Print["NO.", k, "(", a, " ", s, ")"];*)k += 1, Continue[];];
    
18.     ] // Timing
    
19. Print["No.", k]

复制代码

无心人

恐怕你要承担查询的代价
怎么不直接用数组保存是否平方的信息?

kofeffect

无心人
怎么快速得到整数1~10000的各位数和？有没有直接的生成公式？

无心人

s[1000*i + 100*j + 10*k + l] = i + j + k + l

kofeffect

原来是这样

无心人

不是我想出来的

要归功于几个大哥哥大姐姐

kofeffect

呵呵，知道是很有规律的，可是就是理不清
果然简洁，天气大好