相同数字组成的平方数

无心人

考虑1，6，9组成的三位数 169 = 13^2 196 = 14^2 961 = 31^2 现在有问题 1、假设有不重复的n个数字组成的集合A，由A中的不重复数字组成的n位平方数，对应A集合 1)对A的每种情况，对应的平方数都有多少个，比如A = {1, 6, 9}，对应有3个平方数 2)如何挑选A使得组成的平方数最多 2、假设有n个重复的数字组成的集合A，由A中的可重复数字组成的n位平方数，对应A集合，且要求所有平方数具有相同的数字组成 你能求出一个得到最多平方数的集合A，且列出其对应的平方数么

无心人

难道我这个题目有问题？ 咋没人说话呢？

northwolves

穷举吧。不重复的n个数字组成的平方数一共才611个

无心人

呵呵，是的，不重复的有限的

winxos

有时间我看看我能不能求出来。。。

winxos

我写了一个弱弱的程序，得到了一些相关的结果，不过跟题目有点不一样，得到了下面的链： 1->LENS:1 144->441->LENS:2 169->196->961->LENS:3 10404->14400->40401->44100->LENS:4 10609->16900->19600->61009->90601->96100->LENS:6 1006009->1060900->1690000->1960000->6100900->9006001->9060100->9610000->LENS:8 10278436->10837264->23078416->32478601->38204761->38427601->42367081->47623801-> 72148036->LENS:9 12348196->19324816->19412836->31281649->34916281->42981136->48219136->81234169-> 83192641->91623184->LENS:10 14243076->31270464->37601424->41370624->43046721->44076321->47032164->47320641-> 61027344->73410624->73462041->LENS:11 100240144->100420441->102414400->104244100->121044004->121440400->144024001->144 240100->201044041->400440121->404412100->441042001->441420100->LENS:13 100460529->104652900->104960025->105206049->120956004->169052004->169520400->194 602500->200165904->251000649->264095001->400520169->405216900->529046001->529460 100->605012409->621504900->624950001->659000241->964102500->LENS:20 102576384->105637284->158306724->176305284->180472356->183467025->187635204->208 571364->218034756->284057316->307265841->316057284->430728516->472801536->475283 601->560837124->570684321->576432081->734681025->783104256->825470361->853107264 ->LENS:22 139854276->152843769->157326849->215384976->245893761->254817369->326597184->361 874529->375468129->382945761->385297641->412739856->523814769->529874361->537219 684->549386721->587432169->589324176->597362481->615387249->627953481->653927184 ->672935481->697435281->714653289->735982641->743816529->842973156->847159236->9 23187456->LENS:30 1600000000以内最长的链，代码如下：

2. /*
3. 169 = 13^2
4. 196 = 14^2
5. 961 = 31^2
6. 数码位置不对的平方数组合测试。
7. winxos 2009-6-19
8. */
9. #include <iostream>
10. #include <vector>
11. #include <cmath>
12. using namespace std;
13. int isLike(int a,int b)
14. {
15. int t[10]={0};
16. while(a)
17. {
18. t[a%10]+=10;
19. t[b%10]+=1;
20. a/=10;
21. b/=10;
22. }
23. for (int i=0;i<10;i++)
24. if (t[i]%10 != t[i]/10)
25. return 0;
26. return 1;
27. }
28. int main()
29. {
30. int i,maxlen=0,max=40000;
31. int *table=new int[max];
32. vector<int> chains; //记录链长
33. for (i=1;i<max;i++)
34. {
35. table[i]=i*i;
36. }
37. for (i=1;i<max;i++)
38. {
39. chains.clear();
40. chains.push_back(table[i]); //第一个数
41. for (int j=i+1;j<max;j++)
42. {
43. if ((int)(log(table[j])/log(10)) > (int)(log(table[i])/log(10)))
44. break; //位数不同，提前跳出循环
45. if (table[j] == 0)
46. continue; //已经访问过，进入下一步
47. if (isLike(table[j],table[i]))
48. {
49. chains.push_back(table[j]);
50. table[j]=0; //将访问过的数划掉
51. }
52. }
53. if (chains.size() > maxlen)
54. {
55. maxlen=chains.size();
56. for (int j=0;j<maxlen;j++)
57. cout<<chains[j]<<"->";
58. cout<<"LENS:"<<maxlen<<endl;
59. }
60. }
61. return 0;
62. }

复制代码

无心人

回楼上，多谢你的参与 此问题确实比较简单 看的就是穷举的策略和检测的算法