相同数字组成的平方数

无心人

考虑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以内最长的链，代码如下：

1. 
   
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. }
    

复制代码

无心人

回楼上，多谢你的参与

此问题确实比较简单
看的就是穷举的策略和检测的算法