编程找出不同的四位平方数对,它们由相同的数字构成

缺乏、安全感 2022-08-07 04:50 95阅读 0赞

**问题重述：**

\[ 1024,2401; 1089,9801; 1296,2916; 1296,9216; 1369,1936; 1764,4761; 2916,9216; 4096,9604 \]

上述数对是1000~9999 的平方数，他们4个位数上所用到的数字是一样的。

**问题分析：**

1000~9999所有的平方数对应的平方根范围是32~99，二重遍历32~99，找出符合规则的数对\{x,y\}(x != y)，打印。

伪代码的框架可以简化为：

i : 32 -> 99

j : i+1 -> 99

//相应的规则符合即打印i ,j

**一个错误的想法：**

按照上述伪代码框架，找出规则为解题的关键：

最初的错误想法是：

将 平方数 的4位数每一位数的和&积(除去0)求出来，都相等的即为符合的规则

结果：

多出来这样的数对：

\{ 35(1225) , 71(5041) \}

\{ 47(2209) , 70(4900) \}

\{ 67(4489) , 94(8836) \}

后来仔细考虑发现 忽略了4平方位数的合数位的质因数或者因数 可能在另一4位平方数上占据多位（有点绕口，但看上述三个特例就清楚了）

为了交流学习，错误代码如下：

#include <stdio.h>
    
    int NumberSum(int num)
    {
    	int i=4;
    	int sum =0;
    	while (i--)
    	{
    		sum += num%10;
    		num /= 10;
    	}
    	return sum;
    }
    int NumberAdd(int num)
    {
    	int i=4;
    	int sum = 1;
    	int temp;
    	while (i --)
    	{
    		temp = num % 10;
    		if(temp != 0)
    			sum *= temp;
    		num /= 10;
    	}
    	return sum;
    }
    int main()
    {
    	int i;
    	int j;
    	int numI;
    	int numJ;
    	int numI1;
    	int numJ1;
    	for (i = 32 ;i <= 99 ; i ++)
    	//int key = -1;
    	{
    		numI = NumberSum(i*i);
    		numI1 = NumberAdd(i*i);
    		for(j = i + 1; j<= 99; j++)
    		{
    			numJ = NumberSum(j*j);
    			numJ1 = NumberAdd(j*j);
    			if (numI == numJ)
    			{
    				if(numI1 == numJ1)
    				{
    					printf("i = %d j = %d\r\n",i,j);
    				}
    			}
    		}
    	}
    	
    	return 0;
    }

**正确的思路：**

将平方数的每一位放入数组，并对数组按升序或者降序排序后，对两个数组按位比较。

代码如下：

#include <iostream>
    using namespace std;
    
    int cmp(const void*a,const void*b)
    {
    	return *(int*)a -*(int*)b;
    }
    
    
    //将每一位数字存入数组
    void getNumber(int num,int a[])
    {
    	int i = 4;
    	while (i)
    	{
    		a[--i] = num % 10;
    		num /= 10;
    	}
    }
    
    //按位比较两个数组的每一位数字
    int Compare(int a[],int b[])
    {
    	int i;
    	int count = 0;
    	for (i=0;i<4;i++)
    	{
    		if (a[i]==b[i])
    		{
    			count ++;
    		}
    		else
    			continue;
    	}
    	if(count == 4)
    		return 1;
    	else
    		return 0;
    }
    int main()
    {
    	int i;
    	int j;
    	int a[4];
    	int b[4];
    	for (i = 32 ;i < 100; i++)
    	{
    		getNumber(i*i,a);
    		qsort(a,4,sizeof(a[0]),cmp);//排序
    		for(j= i+1 ;j< 100; j++)
    		{
    			getNumber(j*j,b);
    			qsort(b,4,sizeof(b[0]),cmp);//排序
    			if(Compare(a,b))
    			{
    				cout << "{"<<i*i<<","<<j*j<<"}"<<endl;
    			}
    		}
    	}
    	return 0;
    }

运行结果如下：

![SouthEast][]

[SouthEast]: /images/20220805/75482abb623d4fff9162b7a466e94a3e.png