算法题每日一练 --- 第 12 天：算式 900

一、问题描述

小明的作业本上有道思考题：

看下面的算式：

  (□□□□-□□□□)*□□=900

其中的小方块代表 0 ~ 9 的数字，这 10 个方块刚好包含了 0 ~ 9 中的所有数字。 注意：0 不能作为某个数字的首位。

小明经过几天的努力，终于做出了答案！如下：

(5012-4987)*36=900

用计算机搜索后，发现还有另外一个解，本题的任务就是：请你算出这另外的一个解。

注意：输出格式需要与示例严格一致； 括号及运算符号不要用中文输入法； 整个算式中不能包含空格。

二、题目要求

运行限制

• 最大运行时间：1s

• 最大运行内存: 128M

三、问题分析

题目要求使用 0~9 十个数字，不能重复使用每一个数字都需要用到，0 不能作为首元素完成一个等式。首先，问题规模不是很大，只有 10 个数字，排成不同的序列，判断是否满足上述条件。

所以，我们使用全排列来解决这个问题。定义一个数组 a[10]存储 10 个数字。

全排列公式：

do{
}while(next_permutation(a,a+10));

全排列公式头文件 algorithm，或者使用万能头文件 bits/stdc++.h

拓展

• 不足两位时补 0，可以使用 %02d，不足两位前面补 0，可以判断首位为 0 的情况

• %d 是 int 普通的存储，%2d 按宽度为 2，采用右对齐方式输出，若数据位数不到 2 位，则左边补空格

四、编码实现

#include<iostream>#include<algorithm>//全排列头文件 using namespace std;int main(){  int i,n=10,a[10];//初始化定义数组   for(i=0;i<10;i++)//循环给数组a赋值     a[i]=i;//赋值   do  {    int x=1000*a[0]+100*a[1]+10*a[2]+a[3];//第一个数     int y=1000*a[4]+100*a[5]+10*a[6]+a[7];//第二个数     int z=10*a[8]+a[9];//第三个数     if((x-y)*z==900)//if条件判断     {      printf("%04d   %04d  %02d \n",x,y,z);//输出符合条件的结果     }  }while(next_permutation(a,a+n));//全排列列出所有结果   return 0;}

五、输出结果

5012 4987 36

6048 5973 12

7153 6928 04 不满足条件，舍去