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

一、问题描述

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

看下面的算式：

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

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

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

(5012-4987)*36=900

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

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

二、题目要求

考察

考察：全排列、数学思想
建议用时15~25min

三、问题分析

题目要求使用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    不满足条件，舍去