08.txt

CC++语言程序百例精解 非常经典的C

76.小明买书

小明假期同爸爸一起去书店，他选中了六本书，每本书的单价分别为：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只带了十几块钱，为了让小明过一个愉快的假期，爸爸扔然同意买书，但提邮购一个要求，要小明从六本书中选出若干本，使得单价相加所得的和同10最接近。你能够帮助小明解决这个问题吗？

*问题分析与算法设计
分析题意，可将题目简化为：从六个数中选出若干个求和，使得和与10的差值最小。
题目中隐含两个问题，其一是怎样从六个数中选出若干个数；其二是求与10的差。
从六个数中选出若干个数实质是从六个数中选出若干个进行组合。每个数在组合过程中只有两种情况：要么是选中参加求和，要么是没选中不参加求和。这样就可以使用六重循环对每个数是否参加求和进行全部可能情况的组合。
关于求与10的差值应当注意的是：差值的含义是指差的绝对值。例如：“9-10=-1"和"11-10=1",但9和11这两者与10的差值都是1。若认为”9“与”10的差值为-1就错了。

*程序说明与注释
#include<stdio.h>
#include<math.h>
int main()
{
int d[6],m,i,j;
long b[63],flag;
float c[6],min,x;
printf("Please enter the prices of 6 books:");
for(i=0;i<6;i++) scanf("%f",&c[i]); /*输入六个浮点数*/
for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*建立六个数的全部组合并处理*/
for(d[1]=0;d[1]<2;d[1]++) /*i:差值具有min组合的数量*/
for(d[2]=0;d[2]<2;d[2]++) /*min:与10的最小差值*/
for(d[3]=0;d[3]<2;d[3]++) /*d[]:组合时是否取该数的标志*/
for(d[4]=0;d[4]<2;d[4]++)
for(d[5]=0;d[5]<2;d[5]++)
{
for(flag=0,x=0,j=5;j>=0;j–)
/*flag:将六个数的组合用对应的一个十进制位表示 x:对应六个数组合的和*/
{
x+=c[j]*d[j]; flag=flag*10+d[j];
}
x=((x-10>0)? x-10:10-x); /*x: 组合的和与10的差*/
if(min<0)
{
min=x; /*对第一次计算出的差min进行处理*/
b[i++]=flag; /*b[]:有相同的min的flag的数组 i:b[]数组的下标*/
}
else if(min-x>1.e-6) /*对新的min的处理*/
{
min=x; b[0]=flag; i=1;
}
else if(fabs((double)x-min)<1.e-6)
b[i++]=flag; /*对相等min的处理*/
}
for(m=0;m<i;m++) /*输出全部i个与10的差值均为min的组合*/
{
printf("10(+ -)%.2f=",min);
for(flag=b[m],j=0;flag>0;j++,flag/=10)
if(flag%10) /*将b[]中存的标记flag还原为各个数的组合*/
if(flag>1) printf("%.2f+",c[j]);
else printf("%.2f\n",c[j]);
}
}

*运行结果
Please enter the prices of 6 books:3.1 1.7 2.0 5.3 0.9 7.2
10(+ -)0.10=2.00+0.90+7.20
10(+ -)0.10=1.70+2.00+5.30+0.90
10(+ -)0.10=3.10+1.70+5.30

*思考题
可以看出，程序中求六个数所能产生全部组合的算法并不好，使用六重循环进行处理使程序显得不够简洁。可以设计出更通用、优化的算法产生全部组合。

 

77.波松瓦酒的分酒趣题

法国著名数学家波瓦松在表年时代研究过一个有趣的数学问题：某人有12品脱的啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和5品脱的容器，怎样倒才能将啤酒分为两个6品脱呢？

*问题分析与算法设计
将12品脱酒 8品脱和5品脱的空瓶平分，可以抽象为解不定方程：
8x-5y=6
其意义是：从12品脱的瓶中向8品脱的瓶中倒x次，并且将5品脱瓶中的酒向12品脱的瓶中倒y次，最后在12品脱的瓶中剩余6品脱的酒。
用a,b,c代表12品脱、8品脱和5品脱的瓶子，求出不定方程的整数解，按照不定方程的意义则倒法为：
a -> b -> c ->a
x y
倒酒的规则如下：
1) 按a -> b -> c ->a的顺序；
2) b倒空后才能从a中取
3) c装满后才能向a中倒
按以上规则可以编写出程序如下：

*程序说明与注释
#include<stdio.h>
void getti(int a,int y,int z);
int i; /*最后需要分出的重量*/
int main()
{
int a,y,z;
printf("input Full a,Empty b,c,Get i:"); /*a 满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/
scanf("%d%d%d%d",&a,&y,&z,&i);
getti(a,y,z); /*按a -> y -> z -> a的操作步骤*/
getti(a,z,y); /*按a -> z -> y -> a的步骤*/
}
void getti(int a,int y,int z) /*a:满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/
{
int b=0,c=0; /* b:第一瓶实际的重量 c:第二瓶实际的重量*/
printf(" a%d b%d c%d\n %4d%4d%4d\n",a,y,z,a,b,c);
while(a!=i||b!=i&&c!=i) /*当满瓶!=i或另两瓶都!=i*/
{
if(!b)
{ a-=y; b=y;} /*如果第一瓶为空，则将满瓶倒入第一瓶中*/
else if(c==z)
{ a+=z; c=0;} /*如果第二瓶满，则将第二瓶倒入满瓶中*/
else if(b>z-c) /*如果第一瓶的重量>第二瓶的剩余空间*/
{ b-=(z-c);c=z;} /*则将装满第二瓶，第一瓶中保留剩余部分*/
else{ c+=b; b=0;} /*否则，将第一瓶全部倒入第二瓶中*/
printf(" %4d %4d %4d\n",a,b,c);
}
}

*思考题
上面的程序中仅给出了两种分酒的方法，并没有找出全部的方法。请设计新的算法，找出全部的分酒方法，并找出一种倒酒次数最少的方法。

78.求π的近似值

请利用“正多边形逼近”的方法求出π的近似值

*问题分析与算法设计
利用“正多边形逼近”的方法求出π值在很早以前就存在，我们的先人祖冲之就是用这种方法在世界上第一个得到精确度达小数点后第6位的π值的。
利用圆内接正六边形边长等于半径的特点将边数翻番，作出正十二边形，求出边长，重复这一过程，就可获得所需精度的π的近似值。
假设单位圆内接多边形的边长为2b，边数为i，则边数加倍后新的正多边形的边长为：
x=√──────
2-2*√───
1-b*b
──────
2
周长为：
y=2 * i * x i:为加倍前的正多边形的边数

*程序说明与注释
#include<stdio.h>
#include<math.h>
int main()
{
double e=0.1,b=0.5,c,d;
long int i; /*i: 正多边形边数*/
for(i=6;;i*=2) /*正多边形边数加倍*/
{
d=1.0-sqrt(1.0-b*b); /*计算圆内接正多边形的边长*/
b=0.5*sqrt(b*b+d*d);
if(2*i*b-i*e<1e-15) break; /*精度达1e-15则停止计算*/
e=b; /*保存本次正多边形的边长作为下一次精度控制的依据*/
}
printf("pai=%.15lf\n",2*i*b); /*输出π值和正多边形的边数*/
printf("The number of edges of required polygon:%ld\n",i);
}

*运行结果
pai=3.141592653589794
The number of edges of required polygon:100663296

*思考题
请用外切正多边形逼近的方法求π的近似值。

79.求π的近似值(2)

利用随机数法求π的近似值

*问题分析与算法设计
随机数法求π的近似值的思路：在一个单位边长的正方形中，以边长为半径，以一个顶点为圆心，在政权方形上作四分之一圆。随机的向正方形内扔点，若落入四分之一圆内则计数。重复向正方形内扔足够多的点，将落入四分之一圆内的计数除以总的点数，其值就是π值四分之一的近似值。
按此方法可直接进行编程，注意：本方法求出的π值只有统计次数足够多时才可能准确。

*程序说明与注释
#include<time.h>
#include<stdlib.h>
#include<stdio.h>
#define N 30000
int main()
{
float x,y;
int c=0,d=0;
randomize();
while(c++<=N)
{
x=random(101); /*x:坐标。产生0到100之间共101个的随机数*/
y=random(101); /*y:坐标。产生0到100之间共101个的随机数*/
if(x*x+y*y<=10000) /*利用圆方程判断点是否落在圆内*/
d++;
}
printf(" pi=%f\n",4. *d/N); /*输出求出的π值*/
}

*运行结果
多次运行程序，可能得到多个不同的对口果，这是因为采用的是统计规律求出的近似值，只有当统计的次数足够大时，才可能逼近π值。运行四次，可能的结果是：
3.122267
3.139733
3.133733

80.奇数平方的一个有趣性质

编程验证“大于1000的奇数其平方与1的差是8的倍数”。

*问题分析与算法设计
本题是一个很容易证明的数学定理，我们可以编写程序验证它。
题目中给出的处理过程很清楚，算法不需要特殊设计。可以按照题目的叙述直接进行验证(程序中仅验证到3000)。

*程序说明与注释
#include<stdio.h>
int main()
{
long int a;
for(a=1001;a<=3000;a+=2)
{
printf("%ld:",a); /*输出奇数本身*/
printf("(%ld*%ld-1)/8",a,a); /*输出(奇数的平方减1)/8*/
printf("=%ld",(a*a-1)/8); /*输出被8除后的商*/
printf("+%ld\n",(a*a-1)%8); /*输出被8除后的余数*/
}

}