C语⾔程序设计100例之（35）：邮票组合
例35  邮票组合
问题描述
⼩明有四张3分的邮票和三张5分的邮票，⽤这些邮票中的⼀张或若⼲张可以得到多少种不同的邮资？
输⼊格式
⽆输⼊
输出格式
所有能得到的不同邮资。
输⼊样例
⽆
输出样例
…
…  （省略，共19个数）
（1）编程思路。
定义数组int a[28]，所有元素初始值全为0，a[i]=0表⽰邮资i不能得到。
设3分邮票和5分邮票所⽤张数分别为i、j。⽤循环对i、j进⾏穷举。
穷举范围为：0≤i≤4，0≤j≤3。
对穷举的每种组合，置a[i*3 +j*5]=1，表⽰邮资i*3 +j*5可得到。
穷举完成后，数组a中为值1的元素，其下标值所对应邮资可得到。
（2）源程序。
#include<stdio.h>
int main()
{
int a[28]={0};
int i,j;
for (i=0; i<=4; i++)      // 取3分邮票的张数
for (j=0; j<=3; j++)  // 取5分邮票的张数
a[i*3+j*5]=1;
for (i=1; i<=27; i++)
if (a[i]!=0) printf("%d ",i);
printf("\n");
return 0;
}
习题35
35-1  邮票问题
问题描述
⼈们在寄信时要贴邮票，在邮局有⼀些⼩⾯值的邮票，通过这些⼩⾯值邮票中的⼀张或⼏张的组合，可以满⾜不同邮件的不同邮资。现在，邮局有4种不同⾯值的邮票。在每个信封上最多能贴5张邮票，⾯值可以相同也可以不同。编程求出⽤这4种⾯值所能组成的从1开始连续邮资的最⼤值。
例如，假设有 1 分和 3 分的两种邮票，最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资（⽤ 1 分邮票贴就⾏了），接下来的邮资也不难：
6 = 3 + 3，当然还可以贴3+1+1+1，我们给出贴最少张数的⽅案。
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1
邮资14⽆法贴出，当然邮资15可以贴出（贴5张3分即可）。因此，求得的答案是13。
输⼊格式
4个正整数，代表4种⼩⾯值邮票的⾯值。
输出格式
⼀个正整数，表⽰⽤这4种⾯值可组成的连续邮资最⼤值。若邮资1不能得到，则输出“No one!”。
输⼊样例
1 3 5 10
输出样例
36
（1）编程思路。
设4种邮票的⾯值分别为a、b、c、d，贴邮资时所⽤张数分别为i、j、k、l。⽤循环对i、j、k、l进⾏穷举。
穷举范围为：0≤i≤5，0≤j≤5-i，0≤k≤5-i-j，0≤l≤5-i-j-k。
定义数组int hash[1001]，所有元素初始值全为0，hash[i]=0表⽰邮资i不能贴出。
对穷举的每种组合，执⾏ hash[a*i + b*j + c*k + d*l]加1，表⽰邮资a*i + b*j + c*k + d*l贴出的⽅案数加1。
穷举循环完成后，从1开始遍历数组hash，若hash[i]==0，表⽰邮资i被贴出的⽅案数为0，i不能贴出，所求答案为i-1。
（2）源程序。
#include<stdio.h>
int main()
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int hash[1001]={0};
int i, j, k, l;
for (i=0; i<=5; i++)
for (j=0; i+j<=5; j++)
for(k=0; k+i+j<=5; k++)
for(l=0; k+i+j+l<=5; l++)
hash[a*i+b*j+c*k+d*l]++;
for (i=1; i<1000; i++)
if (hash[i]==0)  break;
if (i==1) printf("No one!\n");
else  printf("%d\n", i-1);
return 0;
}
35-2  砝码碎⽚
问题描述
法国数学家梅齐亚克在他著名的《数字组合游戏》（1962）中提出了⼀个问题：⼀位商⼈有⼀个重40磅的砝码，⼀天不⼩⼼将砝码摔成了四块。后来商⼈称得每块的重量都是整磅数，⽽且发现这四块碎⽚可以在天平上称1⾄40磅之间的任意重量。请问这四块碎⽚各重多少？
其中，条件“在天平上”意味着：同⼀砝码既可以放在天平的左侧，也可以放在天平的右侧。
输⼊
⽆
输出
4个正整数，表⽰四块砝码碎⽚的重量。
（1）编程思路。
若规定重物只能放在天平的左侧，则当天平平衡时有：
重物重量+左侧砝码重量总和=右侧砝码重量总和
由此可得：
重物重量=右侧砝码重量总和-左侧砝码重量总和
编程时采⽤⼀种简单的⽅法来表⽰⼀个砝码是在天平的左侧还是在天平的右侧，或是根本没有使⽤。⽤整数1表⽰砝码放在天平右边，0表⽰不⽤该砝码，-1表⽰砝码放在天平的左边。
设4个砝码的重量分别为w1、w2、w3、w4，且w1<w2<w3<w4，其在天平上的放置⽅法分别为d1、d2、d3、d4，可称重值为
w1*d1+w2*d2+w3*d3+w4*d4。
程序中进⾏两重穷举。先穷举4个砝码的重量w1、w2、w3、w4，其中
1≤w1≤9，w1+1≤ w2≤ (40-w1)/3  w2+1≤w3≤(40-w1-w2)/2
W4=40-w1-w2-w3。
对每种穷举的砝码情况，再判断1~40的重量能否完全称出，在进⾏判断时，⼜对4个砝码每个砝码放置的3种情况（放左边、不放、放右边）进⾏穷举。
（2）源程序。
#include<stdio.h>
int main()
{
int w1,w2,w3,w4,d1,d2,d3,d4,x,flag;
for (w1=1; w1<=9; w1++)
for (w2=w1+1; w2<=(40-w1)/3; w2++)
for (w3=w2+1; w3<=(40-w1-w2)/2; w3++)
if ((w4=40-w1-w2-w3)>=w3)
{
for (flag=1,x=1; x<41 && flag; x++)  // 判断可否称出1~40
for (flag=0,d1=1; d1>-2 && !flag; d1--)
for (d2=1; d2>-2&&!flag; d2--)
for (d3=1; d3>-2&&!flag; d3--)
for (d4=1; d4>-2&&!flag; d4--)
if(x==w1*d1+w2*d2+w3*d3+w4*d4)
flag=1;
if (flag) printf("%d %d %d %d\n",w1,w2,w3,w4);
c语言游戏编程题经典100例}
}
35-3  5个正整数
问题描述
已知五个互不相同的正整数之和为N（15≤N≤31），且从这五个数中挑选若⼲个加起来可以表⽰从1到N之内的全部⾃然数。问这五个数是什么？
输⼊格式
⼀个正整数N。
输出格式
和为N的5个正整数，5个数按升序排列。每种可⾏⽅案占⼀⾏。
输⼊样例
23
输出样例
[1]: 1 2 3 5 12
[2]: 1 2 3 6 11
[3]: 1 2 3 7 10
[4]: 1 2 4 5 11
[5]: 1 2 4 6 10
[6]: 1 2 4 7 9
（1）编程思路。
设5个正整数分别为a、b、c、d、e，且a<b<c<d<e，且5个正整数在参与求和时的取舍分别为i、j、k、l、m（取值为0或1之⼀，0代表不参加求和，1代表参加求和），可表⽰和值为a*i+b*j+c*k+d*l+e*m。
程序中进⾏两重穷举。先穷举5个正整数a、b、c、d、e，其中
1≤a≤n/5，1+a ≤b≤(n-a)/4，1+b≤c≤(n-a-b)/3，1+c≤d≤(n-a-b-c)/2，
e=n-a-b-c-d
对每种穷举的5个正整数的情况，再判断1~n的和值能否完全表⽰出来，在进⾏判断时，⼜对5个正整数每个数的取舍情况进⾏穷举。
（2）源程序。
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0;
for(a=1; a<=n/5; a++)
for(b=1+a; b<=(n-a)/4; b++)
for(c=1+b; c<=(n-a-b)/3; c++)
for(d=1+c; d<=(n-a-b-c)/2; d++)
{
f=1;
if ((e=n-a-b-c-d)>d)
for (f=0,x=1; x<=n &&!f; x++)
for (f=1,i=0; i<2&&f; i++) // 穷举5个数的全部取舍
for (j=0; j<2&&f; j++)
for (k=0; k<2&&f; k++)
for (l=0; l<2&&f; l++)
for (m=0; m<2&&f; m++)
if (x==a*i+b*j+c*k+d*l+e*m) f=0;
if(!f) printf("[%d]: %d %d %d %d %d\n",++count,a,b,c,d,e);          }
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。