4个平方数问题（C/C++算法）

Question

由0-9组成的4个平方数，它们必须分别是一位、二位、三位、四位的数字，要求数位不重复（即0-9只能在这四个数字中出现一次）且这四个数字要是某个数的平方。这是个有趣的问题，求C/C++算法思路或代码，谢谢！
例如：1 36 784 9025
     9 16 784 3025
     9 81 324 7056
     9 81 576 2304

Answer 1

谁给验证一下，要去赶飞机了~~#include <stdio.h>int main(void) 
{ 
int arr[100] = {1, 0};
int num[100] = {0};
for(int i=1; i<100; i++)
{
int k = num[i] = num[i-1]+((i-1)<<1)+1;
int nBitTmp = 0;
bool bOK = true;
while(k>0)
{
int t = k%10;
k/=10;
if ((nBitTmp | (1<<t)) == nBitTmp)
{
bOK = false;
break;
}
nBitTmp |= 1<<t;
}
bOK ? arr[i] = nBitTmp:0;
}
   
for(i=0; i<4; i++)
{
for(int j=4; j<10; j++)
{
if (arr[i] & arr[j]) continue; int two = arr[i] | arr[j];
for(int k=10; k<34; k++)
{
if (arr[k] == 0) continue;
if (two & arr[k]) continue;
int three = two | arr[k];
for(int m=34; m<100; m++)
{
if (arr[m] == 0) continue;
if (three & arr[m]) continue;
printf("%d\t%d\t%d\t%d\n", num[i], num[j], num[k], num[m]);
}
}
}
}
    return 0;
}
0       16      784     5329
0       25      784     1369
0       25      784     1936
0       25      841     7396
0       36      729     5184
0       81      324     7569
0       81      576     3249
0       81      729     4356
1       36      784     9025
9       16      784     3025
9       81      324     7056
9       81      576     2304

Answer 2

觉得这个问题有点意思，写了段代码，由于计算量不大，没有考虑优化：
WORD MakeCode(int n)
{
WORD code = 0;
char str[5];
sprintf(str, "%d", n*n);
for (int i=0; i<sizeof(str); i++)
{
if (str[i] == 0) break;
code |= 1<<(str[i]-'0');
}
return code;
}void main()
{
WORD c[100];
for (int i=1; i<100; i++)
{
c[i] = MakeCode(i);
}
for (int n1=1; n1<4; n1++)
{
for (int n2=4; n2<10; n2++)
{
for (int n3=10; n3<32; n3++)
{
for (int n4=32; n4<100; n4++)
{
if ((c[n1]|c[n2]|c[n3]|c[n4]) == 1023)
{
printf("%d %d %d %d\n", n1*n1, n2*n2, n3*n3, n4*n4);
}
}
}
}
}
}
结果：
1 36 784 9025
9 16 784 3025
9 81 324 7056
9 81 576 2304

Answer 3

cnzdgs：请问你一下，
 code |= 1<<(str[i]-'0');
 ........
 if ((c[n1]|c[n2]|c[n3]|c[n4]) == 1023)这两句什么意思？非常感谢 

Answer 4

解释一下我的做法，先把100以内每个数的平方计算出来，每个值用一个WORD（实际上只用10位）来表示其中包含那些数字，第0位为1表示有“0”，第1位为1表示有“1”，第N位为1表示有“N”……。然后再按照平方后的十进制位数把数分为4组，用4重循环穷举各种组合，检查每种组合的4个数和起来是否包含了0~9之间的所有数字。
code|=1<<(str[i]-'0')就是把字符串中的第i个数字对应的位设置为1；if((c[n1]|c[n2]|c[n3]|c[n4])==1023)是把4个数用“或”合并，然后看结果的低10位是不是都为1，如果低10位都是1，则说明4个数中包含了0~9之间的所有数字（因为4个数一共只有10位，如果10个数字都包含则肯定不会有重复）。

Answer 5

那个WORD还不是很明白，程序里没有定义？

Answer 6

danxuezx ：
    感谢你给出你的经典算法的思路和code。据我了解程序运行的结果还不正确，可否帮忙想下问题出在哪儿？谢谢!

Answer 7

楼主弄错了。那个经典算法的思路和code是满天星前辈写的，不是我写的。
另外，您说程序运行结果不正确可否说出不正确的地方？

Answer 8

cnzdgs前辈：
       据我了解你给的算法的运行结果不是很正确，能否帮忙看看问题出在哪儿，谢谢！

Answer 9

能不能麻烦lz说一下，我在4楼贴的代码有什么问题？？结果不正确？思路和5楼cnzdgs是一模一样的，只是多了些剪枝判断，不知道lz的给分标准是怎样的，谁分多就给谁？0不算完全平方数？我以为0*0=0,所以也计算在内了。抛去0打头的，剩下的4组就是cnzdgs给的程序的结果。PS: cnzdgs大牛在5楼贴的代码并没有问题，是正确的。

Answer 10

python客串一下：
import mathN = 10  
lst = range(N)
beginZeroEnable = Falsedef isSquare(n):
    r = int( math.sqrt(n) )
    return r*r == ndef dfs(level):
    n1 = lst[0]
    n2 = lst[1]*10 + lst[2]
    n3 = lst[3]*100 + lst[4]*10 + lst[5]
    n4 = lst[6]*1000 + lst[7]*100 + lst[8]*10 + lst[9]
    if level==N-1 :
        if isSquare(n4) :
            if beginZeroEnable :
                print "%d %d%d %d%d%d %d%d%d%d" % tuple(lst)
            elif lst[0] and lst[1] and lst[3] and lst[6]:
                print "%d %d%d %d%d%d %d%d%d%d" % tuple(lst)
        return
    if level==1 and (  not isSquare(n1)  ):
            return
    if level==3 and( not isSquare(n2)  ):
            return     
    if level==6 and( not isSquare(n3)  ):
            return              
    for i in range(level,N):
        lst[i],lst[level] = lst[level],lst[i]
        dfs(level+1)  
        lst[i],lst[level] = lst[level],lst[i]        
            
if __name__ == '__main__':
    dfs(0)