解题思路:
个人采用深度优先搜索(DFS)枚举所有0-9数字的排列。由于a和b都是五位数,共10位,所以枚举10个位置。前5位构成被除数a(divide),后5位构成除数b(dividen)。枚举过程中使用数组st记录数字是否被使用,以及用数组my_pow(表示万位、千位、百位、十位、个位的权重)来快速计算当前数字的值。
程序说明:
1. 定义全局变量:
* n:输入的整数
* flag:标记是否有解
* st[10]:标记0-9数字是否被使用
* divide:当前枚举的被除数a(由前5位数字构成)
* dividen:当前枚举的除数b(由后5位数字构成)
* my_pow[5]:权重数组,用于计算数字的值([10000, 1000, 100, 10, 1])
2. DFS函数:
* 参数pos:当前枚举的位置(09),其中04位置用于a,5~9位置用于b。
* 当pos>=10时,说明已经枚举完10个数字,检查条件:divide除以dividen的余数为0且商等于n,则输出(注意输出格式为5位,不足补0),并将flag置为true。
* 如果pos<5,说明当前在枚举a(被除数)的第pos位(0为最高位,4为最低位)。遍历0-9,如果数字i未被使用,则标记为已使用,并更新divide(加上i*my_pow[pos]),然后递归下一层。回溯时恢复divide和st。
* 如果pos>=5,说明当前在枚举b(除数)的第pos-5位(即b的第0位到第4位)。同样遍历0-9,标记后更新dividen,然后递归,回溯时恢复。
3. 主函数:
* 读入n
* 调用dfs(0)从位置0开始枚举
* 如果没有解(flag为false),输出"No answer."
代码:
缺点: dfs耗时大,可通过仅枚举被除数的方式,判断剩下的数字是否能够组成满足题目要求的除数,即可大量减少运算次数