首页 > 代码库 > 编程题 -- 分组问题,输出公式.
编程题 -- 分组问题,输出公式.
编程题:
命令行输入两个整数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 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
编程题 -- 分组问题,输出公式.