史上最全的整数分解方法（包含经典的分苹果问题）
【华为OD机试真题 2022&2023】真题目录 @点这里@
【华为OD机试真题】信号发射和接收 &试读& @点这里@
【华为OD机试真题】租车骑绿道 &试读& @点这里@
整数分解方法总结
一、加法分解：
题目描述：
给定一个正整数，我们可以定义出下面的公式：
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
对于一个正整数，求解满足上面公式的所有算式组合 对于整数4：
4 = 4；
4 = 3+1；
4 = 2+2；
4 = 2+1+1；
4 = 1+1+1+1；
1.所有可能的分解输出（有重复）
方法一：
#include
using namespace std;
const int Size = 20;
int res_num;
// 拆分元素暂存在res数组中
int res[Size];
int a, p = 0;
// 将n进行拆分
void resolve(int n);
int main() {
while (1) {
cin >> a;
resolve(a);
cout << "total num of res: " << res_num << endl;
res_num = 0;
}
return 0;
}
void resolve(int n) {
if (n<=0) { // 出口
cout << a << "=";
for (int i=0; i cout << res[i] << "+"; cout << res[p-1] << endl; res_num++; } for (int i = 1; i <= n; i++) { res[p] = i; p++; // p ++来顺序存储各个拆分元素 resolve(n-i); p--; // 此行必须有，执行完这一行，下一次for循环才能回退 } } 方法二： #include #include using namespace std; int counts; void Backtrack(int n, vector { int tmpSum; for (int num = 1; num <= n; num++) { comb[cur] = num; tmpSum = sum + num; if (tmpSum > n) { break;//最好换成break(原来为continue),因为当tmpSum>n之后继续循环是没有意义的 } else if(tmpSum == n)//第一次输出前不断地递归，进入到最里面一层，当tmpSum==n时，通过for循环 //输出全1的拆分结果，随后看是一层一层退出，依次分别执行外部的for循环，使得通过num的增加，而使 //拆分的最后一位数字增加（中间可能涉及前进和后退的过程，通过tmpSum //之后num在原数值基础上继续增加，导致拆分的最后一位数字增加）回退到最外面一层for循环之后，num //增加使得输出拆分结果的第一个数字增加。 { cout << n << "="; for (int i = 1; i < cur; i++) cout << comb[i] << "+"; cout << comb[cur] << endl; counts++; } else { Backtrack(n, comb, cur + 1, tmpSum); } } } int main() { int n; vector while (cin >> n) { com.assign(n+1, 1); Backtrack(n, com, 1, 0); cout << "The total number is: " << counts << endl; } return 0; } 结果如下： 2.输出不重复的分解结果 方法一改： #include using namespace std; const int Size = 20; int res_num; // 拆分元素暂存在res数组中 int res[Size]; int a, p = 0; // 将n进行拆分 void resolve(int n, int flag); int main() { while (1) { cin >> a; resolve(a, 1); cout << "total num of res: " << res_num << endl; res_num = 0; } return 0; } void resolve(int n, int flag) { if (n<=0) { // 出口 cout << a << "="; for (int i=0; i cout << res[i] << "+"; cout << res[p-1] << endl; res_num++; } for (int i = flag; i <= n; i++) { res[p] = i; p++; // p ++来顺序存储各个拆分元素 resolve(n-i, i); p--; // 此行必须有，执行完这一行，下一次for循环才能回退 } } 方法二改： #include #include using namespace std; void Backtrack(int n, vector { int tmpSum; for (int num = comb[cur-1]; num <= n; num++) { comb[cur] = num; tmpSum = sum + num; if (tmpSum > n) { break;//最好换成break(原来为continue),因为当tmpSum>n之后继续循环是没有意义的 } else if(tmpSum == n)//第一次输出前不断地递归，进入到最里面一层，当tmpSum==n时，通过for循环 //输出全1的拆分结果，随后看是一层一层退出，依次分别执行外部的for循环，使得通过num的增加，而使 //拆分的最后一位数字增加（中间可能涉及前进和后退的过程，通过tmpSum //之后num在原数值基础上继续增加，导致拆分的最后一位数字增加）回退到最外面一层for循环之后，num //增加使得输出拆分结果的第一个数字增加，而由for循环的初始条件num=comb[cur-1]及comb[cur]=num， //决定了每次输出的拆分结果，后面的数字不小于前一位数字。 { cout << n << "="; for (int i = 1; i < cur; i++) cout << comb[i] << "+"; cout << comb[cur] << endl; } else { Backtrack(n, comb, cur + 1, tmpSum); } } } int main() { int n; vector while (cin >> n) { com.assign(n+1, 1); Backtrack(n, com, 1, 0); } return 0; } 输出结果： 二、触类旁通之乘法分解： 将一个数n的分解为因子的乘积形式，输出所有可能，并输出表达式。 12=2*2*3； 12=2*6； 12=3*4； 12=6*2； 12=12*1； 代码如下： #include using namespace std; int data_s[100]; // 存储因子的数组 int p=0; // 因子数组的指针 int num=0; // 记录分解因子的总数 int x; // 待分解的数 // 递归函数，用于分解因子 void resolve(int n,int minNum) { if(n<2) // 如果n小于2，说明已经分解完毕 { num++; // 记录分解因子的总数 cout<< x << "="; // 输出待分解的数 for(int j=0;j { cout<< data_s[j]; // 输出因子 if(j!=p-1) cout << "*"; // 输出乘号 if(data_s[j] == x) cout << "*1"; // 如果因子等于待分解的数，输出*1 } cout << endl; // 换行 return; } for(int i=minNum;i<=n;i++) // 从minNum开始枚举因子 { if(n%i==0) // 如果n能够整除i，说明i是n的因子 { data_s[p]=i; // 将i存储到因子数组中 p++; // 指针后移 resolve(n/i, i); // 递归分解n/i的因子，最小因子为i p--; // 回溯，指针前移 } } } int main() { while(cin >> x) // 循环读入待分解的数 { resolve(x, 2); // 分解因子 cout<< "The total numbers is " << num << endl; // 输出分解因子的总数 cout << "--------------------------" << endl; // 输出分隔符 num = 0; // 重置分解因子的总数 break; } return 0; } 下面的代码可以实现从小到大的顺序输出质数因子的乘积： #include const int Num = 100; using namespace std; int main() { int data[Num],n; // 定义一个数组data和一个整数n while (cin >> n) // 循环读入n的值 { int num = n,j = 0; // 定义一个整数num和一个计数器j for (int i = 2; i <= n; ++i) // 从2到n遍历每个数 { while (num % i == 0) // 如果num能被i整除 { num /= i; // 将num除以i data[j] = i; // 将i存入数组data中 j++; // 计数器加1 } } for (int i = 0; i < j; ++i) // 遍历数组data { cout << data[i]; // 输出数组元素 if (i != j - 1) cout << '*'; // 如果不是最后一个元素，输出乘号 } cout << '=' << n << endl; // 输出等号和n的值 } return 0; } 如果需要输出所有分解组合，只需要将resolve()的第二个参数去掉即可，如下面这段代码，输出所有因子组合（有重复）： #include using namespace std; int data_s[100]; // 存储因子的数组 int p=0; // 因子数组的指针 int num=0; // 记录分解因子的总数 int x; // 待分解的数 // 递归函数，用于分解因子 void resolve(int n) { if(n<2) // 如果n小于2，说明已经分解完毕 { num++; // 记录分解因子的总数 cout<< x << "="; // 输出待分解的数 for(int j=0;j { cout<< data_s[j]; // 输出因子 if(j!=p-1) cout << "*"; // 输出乘号 if(data_s[j] == x) cout << "*1"; // 如果因子等于待分解的数，输出*1 } cout << endl; // 换行 return; } for(int i=2;i<=n;i++) // 从minNum开始枚举因子 { if(n%i==0) // 如果n能够整除i，说明i是n的因子 { data_s[p]=i; // 将i存储到因子数组中 p++; // 指针后移 resolve(n/i); // 递归分解n/i的因子，最小因子为i p--; // 回溯，指针前移 } } } int main() { while(cin >> x) // 循环读入待分解的数 { resolve(x); // 分解因子 cout<< "The total numbers is " << num << endl; // 输出分解因子的总数 cout << "--------------------------" << endl; // 输出分隔符 num = 0; // 重置分解因子的总数 break; } return 0; } 输出结果： 三、分苹果相关问题 接下来是只需要输出组合数的代码： 将要拆的数n，当作n个苹果。拆成k个数，当作k个盘子。 k > n时，多出来的盘子必定是空的，拆分情况的数量和k==n没区别。 k < n时，两种情况： 1)至少有一个空盘子，则相当于少一个盘子的情况q(n, k) = q(n, k-1) 2)没有空盘子，分配完之后相当于每个盘子里都减少一个苹果的情况q(n, k) = q(n-k, k) 两种情况合起来就是：q(n, k) = q(n, k-1) + q(n-k, k) n的最大值为120，可以用空间换时间，用一个120*120的二维数组存储所有结果 #include using namespace std; int main() { int solution[121][121] = {0}; // 定义一个二维数组solution，用于存储结果 for (int n = 1; n <= 120; n++) // n表示苹果的个数，从1到120遍历 { for (int k = 1; k <= 120; k++) // k表示盘子的个数，从1到120遍历 { if (n == 1 || k == 1) // 如果苹果个数为1或盘子个数为1，那么只有一种放法 { solution[n][k] = 1; } else if (n > k) // 如果苹果个数大于盘子个数，那么可以分成两种情况 { // 第一种情况：至少有一个盘子不放苹果，即f(n-k,k) // 第二种情况：每个盘子都放至少一个苹果，即f(n,k-1) solution[n][k] = solution[n-k][k] + solution[n][k-1]; } else if(n == k) // 如果苹果个数等于盘子个数，那么只有一种放法 { // n个苹果，k-1个盘子只是比k个盘子少了一种全1的组合，即只少了一种情况 solution[n][k] = 1 + solution[n][k-1]; } } } int n; while (cin >> n) // 循环读入n { cout << solution[n][n] << endl; // 输出结果 } return 0; } 本题就是先建一个二维数组用以存储数据，然后根据前面的分析填充数据，然后使用输入的值查表就可以得到结果。 补充放苹果问题： 题目描述: 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 输入 每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。 样例输入: 7 3 样例输出: 8 解题分析： 设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论， 当m < n：则必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)当m >= n:不同的放法可以分成两类：含有0的方案数，不含有0的方案数 含有0的方案数，即有至少一个盘子空着，即相当于 f(m,n)=f(m,n-1);不含有0的方案数，即所有的盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即 f(m,n)=f(m-n,n)。 而总的放苹果的放法数目等于两者的和，即 f(m,n)=f(m,n-1)+f(m-n,n) 递归出口条件说明： 当n=1时，所有苹果都必须放在一个盘子里，所以返回1； 当m==0(没有苹果可放)时，定义为1种放法； 递归解法： #include using namespace std; int fun(int m,int n) { if(m==0||n==1) return 1; else if(m return fun(m,m); else return fun(m-n,n)+fun(m,n-1); } int main() { int a,b,num; while(cin >> a >> b) { cout << fun(a,b) << endl; } } //动态归划解法： #include using namespace std; int main() { int solution[11][11] = {0}; for (int n = 0; n <= 10; n++) { for (int k = 0; k <= 10; k++) { if (n == 0 || k == 1) { solution[n][k] = 1; } else if (n >= k) { solution[n][k] = solution[n-k][k] + solution[n][k-1]; } else if(n < k) { solution[n][k] = solution[n][n]; } } } int n, k; while (cin >> n >> k) { cout << solution[n][k] << endl; } return 0; } 问题描述：将整数N分成K个整数的和且每个数大于等于A小于等于B，求有多少种分法 #include using namespace std; int Dynamics(int n, int k, int min, int max) { //将n分为k个整数，最小的大于等于min,最大的不超过B if(n < min) return 0; //当剩下的比min小，则不符合要求，返回0 if(n <= max && k == 1)//原来只有k==1最后一个判断条件，下面k==0也没有， //现在做这样的修改是为了处理按照要求不能分配的特殊情况 return 1; if (k == 0)//在不能正确划分的情况下，防止k变为负值，提前终止！ { //cout << "The value of k is " << k << endl; return 0; } int sum = 0;//sum直到最后把n划分完才会得到返回值1，否则递归过程中每段都返回0；如果划分成功，则最后就得到0+...+0+1等于1 for(int t = min; t <= max; t++) { sum += Dynamics(n-t, k-1, t, max);//为了避免重复，所以第三个参数用t,说明t是每次递归完成后是动态变化的 } return sum; } int main() { int a, b, mins, maxs; while (cin >> a >> b >> mins >> maxs) { cout << Dynamics(a, b, mins, maxs) << endl;//最开始函数的min由这里控制， //随后的min由函数内的for循环控制 } } 问题拓展：前面的放苹果问题，如果每个盘子都不能为空，则有多少种放法？ 思路，先把每个盘子都放一个苹果，这样问题就转化为：m-n个苹果放进n个盘子里，盘子允许空，即为前面的问题。