将0到9这十个数字分成n组，每一组的数字之和等于输入的数，输入的数的个数等于n。例如：输入：40 5则程序需要把这十个数字分成两组，第一组所有数字之和为40，第二组之和为5。所以有：输出：0 1 2 3 4 6 7 8 95 #include <iostream>using namespace std;int main(){ const int N_OF_DIGITS=9; const int TOTAL_COMBS=512; const int MAX_NUM_GROUP=9; int bin[N_OF_DIGITS]={0}; int digits_record[N_OF_DIGITS]={0}; int digits[]={1,2,3,4,5,6,7,8,9}; int sum_of_combs[TOTAL_COMBS]={0}; int groups_sums[MAX_NUM_GROUP]; int comb_indices[MAX_NUM_GROUP]={0}; int n_of_groups; int i,j,k; void dec2bin(int n,int *arr); int IsOverlap(int arr1[],int arr2[],int size); void SetRecord(int arr1[],int arr2[],int size); cout<<"input number of groups:\n"; cin>>n_of_groups; cout<<"input the sum of each group (in ascend order):\n"; for(i=0;i<n_of_groups;i++) cin>>groups_sums[i]; for(i=0;i<TOTAL_COMBS;i++) { for(j=0;j<N_OF_DIGITS;j++) bin[j]=0; dec2bin(i,bin); for(j=0;j<N_OF_DIGITS;j++) sum_of_combs[i]+=digits[j]*bin[j]; } for(i=0;i<n_of_groups;i++) { for(j=0;j<TOTAL_COMBS;j++) { if(sum_of_combs[j]==groups_sums[i]) { for(k=0;k<N_OF_DIGITS;k++) bin[k]=0; dec2bin(j,bin); if(!IsOverlap(digits_record,bin,N_OF_DIGITS)) { SetRecord(digits_record,bin,N_OF_DIGITS); comb_indices[i]=j; break; } } } } for(i=0;i<n_of_groups;i++) { cout<<"numbers in group "<<i+1<<":"<<endl; for(k=0;k<N_OF_DIGITS;k++) bin[k]=0; dec2bin(comb_indices[i],bin); for(k=0;k<N_OF_DIGITS;k++) { if(bin[k]==1) cout<<bin[k]*digits[k]<<' '; } putchar('\n'); } system("pause"); return 0;}void dec2bin(int n,int *arr){ if(n>0) { *arr=n%2; dec2bin(n/2,arr+1); }}int IsOverlap(int arr1[],int arr2[],int size){ for(int i=0;i<size;i++) if(arr1[i]==1 && arr2[i]==1) return 1; return 0;}void SetRecord(int arr1[],int arr2[],int size){ for(int i=0;i<size;i++) arr1[i]+=arr2[i];}要求输入的数据从小到大，数据有解，0可以在任意一组出现所以就没考虑就是1~9。没解的算不了。测试了下，应该没问题：input number of groups:4input the sum of each group (in ascend order):7 11 12 15numbers in group 1:1 2 4numbers in group 2:5 6numbers in group 3:3 9numbers in group 4:7 8
评论