100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式从标准输入读入一个正整数N (N<1000*1000)
输出格式程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1 100 样例输出1 11 样例输入2 105 样例输出2 6 #include <iostream> using namespace std; int n; int count=0; int a[9]; //记录排序后的数字串 int sum; int fenzi, fenmu; //自己定义乘方函数，避免大量的浮点运算 int chengfang(int mi) { int num = 1; for(int i = 0; i < mi; i++) num *= 10; return num; } int Pailie(int pos) { for(int i = 0; i < pos - 1; i++) //新放入的数字是否与原有数字重复 { if(a[pos - 1] == a[i]) return 0; //如果重复则回溯 } //得到一个全排列以后，则尝试在不同的位置插入加号和除号 if(pos == 9) //pow的返回值为double类型，会减慢速度，所以自定义乘方函数 { //1 2 3 4 5 6 7 8 9 for(int i = 0; a[0] * chengfang(i) < n; i++) //i表示+号的位置，整数部分必须小于目标数字 { sum = 0; for(int m = 0; m <= i; m++) sum += a[m] * chengfang(i - m); if(sum >= n) //如果i走到某一位置后，整数部分比n大，那么后面也不必再看了 return 0; //回溯 for(int j = 4 + i / 2; j <= 7; j++) //j表示除号的位置，从剩余部分的中间开始向后移动 { fenzi=0; fenmu=0; for(int k = i + 1; k <= j; k++) fenzi += a[k] * chengfang(j - k); for(int h = j + 1; h <= 8; h++) fenmu += a[h] * chengfang(8 - h); if(fenzi <= fenmu) //分子小于分母无法得到整数，除号继续向后移动 continue; if((n - sum) * fenmu == fenzi) //对原式进行变化，避免产生浮点数 { count++; cout<<"第"<<count<<"个："<<sum<<" + "<<fenzi<<" / "<<fenmu<<endl; } } } return 0; } for(int i = 1; i <= 9; i++) { a[pos]=i; //放数字 Pailie(pos + 1); //放下一个数字 } } int main() { cin>>n; Pailie(0); cout<<count; return 0; } 要点： 1、尽早作出判断，结束循环/递归，避免无意义的运算。 2、在多重循环/递归中应尽量避免浮点运算。 3、pow函数的返回值是double类型。