蓝桥杯练习题四 - 排它平方数（c++）

「爱情、让人受尽委屈。」 2023-09-30 15:11 7阅读 0赞

> 题目如下

203879 \* 203879 = 41566646641

这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。

具有这样特点的6位数还有一个，请你找出它！

再归纳一下筛选要求：

1.  6位正整数

1.  每个数位上的数字不同

1.  其平方数的每个数位不含原数字的任何组成数位

以下程序实现了这一功能，请你补全以下空白处内容：

#include <iostream>
    using namespace std;
    
    int main()
    {
        int num[10], flag;
        for (long long i = 123456; i <= 987654; i++)
        {
            long long a = i;
            long long b = i * i;
            memset(num, 0, sizeof(num));
            flag = 1;
            while (a)
            {
                _________________;
            }
            if (flag)
            {
                while (b)
                {
                    if (num[b % 10])
                    {
                        flag = 0;
                        break;
                    }
                    b /= 10;
                }
                if (flag)
                    cout << i << endl;
            }
        }
        return 0;
    }

提示：

0的平方为0
    1的平方为1
    5的平方为5
    6的平方为6
    以上这4个数字都不能作为原数字的最后一位，可以在最后一位排除
    且第一位不能为0

> 最终代码如下：

#include <iostream>
    using namespace std;
    
    int main()
    {
        int num[10], flag;
        for (long long i = 123456; i <= 987654; i++)
        {
            long long a = i;
            long long b = i * i;
            memset(num, 0, sizeof(num));
            flag = 1;
            while (a)
            {
                if (num[a % 10])
                {
                    flag = 0;
                    break;
                }
                num[a % 10]++ 
                a /= 10;
            }
            if (flag)
            {
                while (b)
                {
                    if (num[b % 10])
                    {
                        flag = 0;
                        break;
                    }
                    b /= 10;
                }
                if (flag)
                    cout << i << endl;
            }
        }
        return 0;
    }

> 解析如下：

**1.for (long long i = 123456; i <= 987654; i++)**

i的起始值和结束值，起始值应该为最小的不重复的数字，结束值应该为最大的不重复的数字，有些人代码直接就写成了起始值为100000，结束值为999999，这样也行，只不过会增加运算的次数，但这里给出的123456明显也不太符合六位数不重复且最小值的定义，我认为应该是102345，这个才是最小值。

**2.memset(num, 0, sizeof(num));**

memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。

这条语句是把num中中所有字节换做字符“0”，常用来对指针或字符串的初始化。

sizeof可设置从0开始的长num的替换区间，但必须从第0位开始，同时0也可以替换成其他的字符。

**3.第一个while循环**

while (a)
    {
        if (num[a % 10])
        {
            flag = 0;
            break;
        }
        num[a % 10]++ 
        a /= 10;
    }

全篇最难理解的来了，大家要认真仔细的看了。

while(a)不难理解，a不为0

num\[a % 10\]这个有点难理解了，需要上道具，结合2中的**memset**来说明，**memset(num, 0, sizeof(num));**之后,num是下面这样的：

num = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

a % 10是什么呢？假设a为123456，a % 10 = 6，num\[6\]是多少呢？num是个数组，里面全是0，num\[6\] = 0，此时if (num\[a % 10\])就是if(0)，条件不成立，num\[a % 10\]++，它等价于num\[6\]++,num\[6\]是0，num\[6\]++后就是1，这时的num是多少呢？看下面：

num = [0, 0, 0, 0, 0, 0, 1, 0, 0, 0];

以上是第一次循环，之后，a /= 10，a = 12345， 我们继续：

第二次循环时if里面是num\[5\],num\[5\]是0，条件不成立，num\[5\]++,num\[5\]是0，num\[5\]++后就是1，这时的num是多少呢？看下面：

num = [0, 0, 0, 0, 0, 1, 1, 0, 0, 0];

此时，a /= 10，a = 1234， 我们继续：

第三次循环时if里面是num\[4\],num\[4\]是0，条件不成立，num\[4\]++,num\[4\]是0，num\[4\]++后就是1，这时的num是多少呢？看下面：

num = [0, 0, 0, 0, 1, 1, 1, 0, 0, 0];

此时，a /= 10，a = 123， 我们继续：

第四次循环时if里面是num\[3\],num\[3\]是0，条件不成立，num\[3\]++,num\[3\]是0，num\[3\]++后就是1，这时的num是多少呢？看下面：

num = [0, 0, 0, 1, 1, 1, 1, 0, 0, 0];

此时，a /= 10，a = 12， 我们继续：

第五次循环时if里面是num\[2\],num\[2\]是0，条件不成立，num\[2\]++,num\[2\]是0，num\[2\]++后就是1，这时的num是多少呢？看下面：

num = [0, 0, 1, 1, 1, 1, 1, 0, 0, 0];

此时，a /= 10，a = 1， 我们继续：

第六次循环时if里面是num\[1\],num\[1\]是0，条件不成立，num\[1\]++,num\[1\]是0，num\[1\]++后就是1，这时的num是多少呢？看下面：

num = [0, 1, 1, 1, 1, 1, 1, 0, 0, 0];

此时，a /= 10，a = 0， 继续

这时候while（a）条件不成立，直接走到下面去了。

这里解释下为什么要这么做：

> 它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字

注意这段话，数字每一位不重复，平方后每一位数字和平方前不重复。

我们得到了满足条件的a之后，就可以用和a同样的方式来在num中取值，如果取出来不为0，则说明b和a重了，那么这个a就不满足题目中我们需要的答案。

如果a中数字重复，那么直接就进入if中执行，flag=0，也就没有后面b啥事了。

**4.flag中第二个for循环**

if (flag)
    {
        while (b)
        {
            if (num[b % 10])
            {
                flag = 0;
                break;
            }
            b /= 10;
        }
        if (flag)
            cout << i << endl;
    }

a满足条件，flag就不会变为0，进入i+1的下一个for循环。

有没有发现两个for循环特别的像？没错，几乎一样，注意，这里要敲黑板了，很重要的一点：

第二个for循环中只通过num\[b % 10\]去取值，但是没有进行赋值操作，也就是第一个for循环中num\[a % 10\]++的操作，这里只做了取值来判断num中对应的数字下标位置是否有值，有值，说明重复，flag=0，跳出循环，继续下一个值，没有值，说明不重复，直到验证完每一位的值之后，输出i。

每一次的循环和3里面是一样的，只是没有num的赋值操作，只做了效验，博主就不再赘述了，能耐心看到这里，恭喜你，相信你已经基本掌握了排它平方数。

**5.提示内容**

0的平方为0
    1的平方为1
    5的平方为5
    6的平方为6
    以上这4个数字都不能作为原数字的最后一位，可以在最后一位排除
    且第一位不能为0

这个不可不看，关系到效率问题，可以在for循环中提前判断最后一位数是不是提示中存在的数字，可直接跳过，可以减少绝大部分无效运算，提高程序的运行效率，所以，把下面这段代码加进for循环中，最先执行。

if (i % 10 == 1 || i % 10 == 5 || i % 10 == 6 || i % 10 == 0) 
    {
        continue;
    }

到这里，也到了跟大家说再见的时候，分析完了，有问题，欢迎评论区留言讨论，咱们下篇再见。