首页 > 代码库 > 编程题 -- 分组问题,输出公式.

编程题 -- 分组问题,输出公式.

编程题:
命令行输入两个整数N 和 P. (N<=P). 程序输出满足以下条件的一系列公式:
公式为: A1*B1 + A2*B2 + ... + An*Bn
要求:
公式需同时满足:
A1*B1 + A2*B2 + ... + An*Bn = N
A1+A2+..+An = P
其中数列: A1 A2 ... An 为 >=1的整数数列.
B1 B2 ... Bn 为 >=1的整数数列,且 满足:Bn>Bn-1
多条公式为并列关系,无输出先后要求.
该程序命名为grouping(分组). 有一批多种颜色的球(数量无限)需装进一个N个格子的包装里.每个包装中只有P种颜色的球.请问这些组合里的重复情况.
比如有 A1个出现B1次+A2个出现B2次.

例如:
输入
grouping 7 5
4*1 + 1*3
3*1 + 2*2

解题思路:(不喜看思路者可直接看代码)
设计一个函数传入N P K S. 函数可递归调用.
N为剩余N值 P为剩余P值 K为最小的B值 S为传入字符串.

题设当输入 7 5时,函数调用为:

F(7,5,1,NULL)
函数尝试 :
5*1 P-5=0, 5*1 < 7 F(7,5,2,NULL) 继续下一个尝试.
4*1 P-4=1 调用 F(7-4*1,5-4,2,"4*1 ") ,递归返回后继续下一个尝试.
3*1 调用 F(4,2,2,"3*1 ")
2*1 调用 F(5,3,2,"2*1 ")
1*1 调用 F(6,4,2,"1*1 ")
返回.

调用: F(7-4*1,5-4,2,"4*1 ") 的解析
F(3,1,2,"4*1 ")
尝试
1*2 P-1=0 ,F(3,1,3,"4*1 ") ---> 输出 4*1 + 1*3

调用 F(4,2,2,"3*1 ")
尝试
2*2=4 ---> 输出 3*1 + 2*2

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4  5 void grouping(int N,int P,int K ,char* prestr) { 6 #define grouping_buf_size 128 7     // trying: N N-1 N-2 .... 8     char buf[grouping_buf_size]; 9     for(int i=P;i>0;i--) {10         if(prestr==NULL) {11             sprintf(buf,"%d*%d",i,K); 12         } 13         else {14             sprintf(buf,"%s + %d*%d",prestr,i,K); 15         }16         if(P-i==0) {17             if(N-i*K == 0) {18                 printf("%s\n",buf); 19             }20             else if(N-i*K > 0) {21                 grouping(N,P,K+1,prestr);22             }23             else if(N-i*K < 0) {24             }25         }26         else if(N-i*K>0){27 28             grouping(N-i*K,P-i,K+1,buf);29         }30 31     }32 33 #undef grouping_buf_size 34 }35 36 int main(int argc,char** argv) {37 int n=atoi(argv[1]);38 int p=atoi(argv[2]);39 grouping(n,p,1,NULL);40 41 return 1;42 }
grouping 代码

测试:

$ grouping 7 7
7*1
$ grouping 7 6
5*1 + 1*2
$ grouping 7 5
4*1 + 1*3
3*1 + 2*2
$ grouping 7 4
3*1 + 1*4
2*1 + 1*2 + 1*3
1*1 + 3*2

 

编程题 -- 分组问题,输出公式.