相同数字组成的平方数
考虑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，且列出其对应的平方数么 难道我这个题目有问题？
咋没人说话呢？ 穷举吧。不重复的n个数字组成的平方数一共才611个 呵呵，是的，不重复的有限的 有时间我看看我能不能求出来。。。 我写了一个弱弱的程序，得到了一些相关的结果，不过跟题目有点不一样，得到了下面的链：
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以内最长的链，代码如下：
/*
169 = 13^2
196 = 14^2
961 = 31^2
数码位置不对的平方数组合测试。
winxos 2009-6-19
*/
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int isLike(int a,int b)
{
int t={0};
while(a)
{
t+=10;
t+=1;
a/=10;
b/=10;
}
for (int i=0;i<10;i++)
if (t%10 != t/10)
return 0;
return 1;
}
int main()
{
int i,maxlen=0,max=40000;
int *table=new int;
vector<int> chains; //记录链长
for (i=1;i<max;i++)
{
table=i*i;
}
for (i=1;i<max;i++)
{
chains.clear();
chains.push_back(table); //第一个数
for (int j=i+1;j<max;j++)
{
if ((int)(log(table)/log(10)) > (int)(log(table)/log(10)))
break; //位数不同，提前跳出循环
if (table == 0)
continue; //已经访问过，进入下一步
if (isLike(table,table))
{
chains.push_back(table);
table=0; //将访问过的数划掉
}
}
if (chains.size() > maxlen)
{
maxlen=chains.size();
for (int j=0;j<maxlen;j++)
cout<<chains<<"->";
cout<<"LENS:"<<maxlen<<endl;
}
}
return 0;
}
回楼上，多谢你的参与
此问题确实比较简单
看的就是穷举的策略和检测的算法
页:
[1]