平方数问题一则

无心人

我那个算法还是做了点优化的 就是在判定是否平方数上 你用开方算是不对的 另外，穷举平方数用累加 计算数字和用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

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