首页 > 代码库 > 整数划分问题
整数划分问题
描述
Given two positive integers N and M, please divide N into several integers A1, A2, ..., Ak (k >= 1), so that:
1. 0 < A1 < A2 < ... < Ak;
2. A1 + A2 + ... + Ak = N;
3. A1, A2, ..., Ak are different with each other;
4. The product of them P = A1 * A2 * ... * Ak is a multiple of M;
How many different ways can you achieve this goal?
输入
Two integers N and M. 1 <= N <= 100, 1 <= M <= 50.
输出
Output one integer -- the number of different ways to achieve this goal, module 1,000,000,007.
样例提示
There are 4 different ways to achieve this goal for the sample:
A1=1, A2=2, A3=4;
A1=1, A2=6;
A1=2, A2=5;
A1=3, A2=4.
7 2
4
#include <iostream> using namespace std; int N=0; //用于打印(输出)的函数 //result为存储某划分结果的数组,length为此划分所占长度-1(从0开始) void display(int *result,int length) { for(int i=0;i<length;i++) cout<<result[i]<<" "; cout<<endl; } bool noRepeat(int *result,int length){ int a[1000]={0}; for(int i=0;i<length;i++){ if(a[result[i]]!=0){ return false; } else{ a[result[i]]++; } } return true; } bool isMultipleRight(int *result,int length,int m){ int a=1; for(int i=0;i<length;i++){ a*=result[i]; } if(a%m == 0){ return true; } return false; } //主划分函数q(int n,int m,int *result,int length) //n为待划分整数,m为最大加数上限,result和length意以同display函数 //将q分成五种情况分类讨论,其中包含递归调用 int q(int n,int m,int *result,int length,int multiple) { //当n>=1并且m=1时,q(n,m,result,length)=q(n-1,m,result,length) if(n>=0&&m==1) { //直至n=0并且m=1时,输出 if(n==0) { display(result,length); if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){ N++; } } else { result[length]=1; q(n-1,m,result,length+1,multiple); } return 1; } // 当 n=1并且m>1 时,分解已经完成,进行输出 else if(n==1&&m>1) { result[length]=n; display(result,length+1); if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){ N++; } return 1; } //当n<m时,q(n,m,result,length)=q(n,n,result,length) else if(n<m) { return q(n,n,result,length,multiple); } //当n=m时,q(n,m,result,length)=q(n,m-1,result,length)+1(划分数目) else if(n==m) { result[length]=m; display(result,length+1); if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){ N++; } return q(n,m-1,result,length,multiple)+1; } //当n>m>1时,//q(n,m,result,length)=q(n-m,m,result,length+1)+q(n,m-1,result,length) else { result[length]=m; return q(n-m,m,result,length+1,multiple)+q(n,m-1,result,length,multiple); } } int main() { int n,m; int result[100]={0},length=0; cout<<"please input the integer:"; cin>>n>>m; cout<<"整数"<<n<<"的划分个数为"<<q(n,n,result,length,m)<<endl; cout<<"合格的划分个数是"<<N<<endl; return 0; }
整数划分问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。