76.小明買書
小明假期同爸爸一起去書店，他選中了六本書，每本書的單價分別為：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只帶了十幾塊錢，為了讓小明過一個愉快的假期，爸爸扔然同意買書，但提郵購一個要求，要小明從六本書中選出若干本，使得單價相加所得的和同10最接近。你能夠幫助小明解決這個問題嗎？
*問題分析與算法設(shè)計
分析題意，可將題目簡化為：從六個數(shù)中選出若干個求和，使得和與10的差值最小。
題目中隱含兩個問題，其一是怎樣從六個數(shù)中選出若干個數(shù)；其二是求與10的差。
從六個數(shù)中選出若干個數(shù)實(shí)質(zhì)是從六個數(shù)中選出若干個進(jìn)行組合。每個數(shù)在組合過程中只有兩種情況：要么是選中參加求和，要么是沒選中不參加求和。這樣就可以使用六重循環(huán)對每個數(shù)是否參加求和進(jìn)行全部可能情況的組合。
關(guān)于求與10的差值應(yīng)當(dāng)注意的是：差值的含義是指差的絕對值。例如：“9-10=-1"和"11-10=1",但9和11這兩者與10的差值都是1。若認(rèn)為”9“與”10的差值為-1就錯了。
*程序與程序注釋
#include
#include
void 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]); /*輸入六個浮點(diǎn)數(shù)*/
for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*建立六個數(shù)的全部組合并處理*/
for(d[1]=0;d[1]<2;d[1]++) /*i:差值具有min組合的數(shù)量*/
for(d[2]=0;d[2]<2;d[2]++) /*min:與10的最小差值*/
for(d[3]=0;d[3]<2;d[3]++) /*d[]:組合時是否取該數(shù)的標(biāo)志*/
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:將六個數(shù)的組合用對應(yīng)的一個十進(jìn)制位表示 x:對應(yīng)六個數(shù)組合的和*/
{
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進(jìn)行處理*/
b[i++]=flag; /*b[]:有相同的min的flag的數(shù)組 i:b[]數(shù)組的下標(biāo)*/
}
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 {
printf("10(+ -)%.2f=",min);
for(flag=b[m],j=0;flag>0;j++,flag/=10)
if(flag%10) /*將b[]中存的標(biāo)記flag還原為各個數(shù)的組合*/
if(flag>1) printf("%.2f+",c[j]);
else printf("%.2f\n",c[j]);
}
}
*運(yùn)行結(jié)果
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
*思考題
可以看出，程序中求六個數(shù)所能產(chǎn)生全部組合的算法并不好，使用六重循環(huán)進(jìn)行處理使程序顯得不夠簡潔。可以設(shè)計出更通用、優(yōu)化的算法產(chǎn)生全部組合。
小明假期同爸爸一起去書店，他選中了六本書，每本書的單價分別為：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只帶了十幾塊錢，為了讓小明過一個愉快的假期，爸爸扔然同意買書，但提郵購一個要求，要小明從六本書中選出若干本，使得單價相加所得的和同10最接近。你能夠幫助小明解決這個問題嗎？
*問題分析與算法設(shè)計
分析題意，可將題目簡化為：從六個數(shù)中選出若干個求和，使得和與10的差值最小。
題目中隱含兩個問題，其一是怎樣從六個數(shù)中選出若干個數(shù)；其二是求與10的差。
從六個數(shù)中選出若干個數(shù)實(shí)質(zhì)是從六個數(shù)中選出若干個進(jìn)行組合。每個數(shù)在組合過程中只有兩種情況：要么是選中參加求和，要么是沒選中不參加求和。這樣就可以使用六重循環(huán)對每個數(shù)是否參加求和進(jìn)行全部可能情況的組合。
關(guān)于求與10的差值應(yīng)當(dāng)注意的是：差值的含義是指差的絕對值。例如：“9-10=-1"和"11-10=1",但9和11這兩者與10的差值都是1。若認(rèn)為”9“與”10的差值為-1就錯了。
*程序與程序注釋
#include
#include
void 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]); /*輸入六個浮點(diǎn)數(shù)*/
for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*建立六個數(shù)的全部組合并處理*/
for(d[1]=0;d[1]<2;d[1]++) /*i:差值具有min組合的數(shù)量*/
for(d[2]=0;d[2]<2;d[2]++) /*min:與10的最小差值*/
for(d[3]=0;d[3]<2;d[3]++) /*d[]:組合時是否取該數(shù)的標(biāo)志*/
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:將六個數(shù)的組合用對應(yīng)的一個十進(jìn)制位表示 x:對應(yīng)六個數(shù)組合的和*/
{
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進(jìn)行處理*/
b[i++]=flag; /*b[]:有相同的min的flag的數(shù)組 i:b[]數(shù)組的下標(biāo)*/
}
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
printf("10(+ -)%.2f=",min);
for(flag=b[m],j=0;flag>0;j++,flag/=10)
if(flag%10) /*將b[]中存的標(biāo)記flag還原為各個數(shù)的組合*/
if(flag>1) printf("%.2f+",c[j]);
else printf("%.2f\n",c[j]);
}
}
*運(yùn)行結(jié)果
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
*思考題
可以看出，程序中求六個數(shù)所能產(chǎn)生全部組合的算法并不好，使用六重循環(huán)進(jìn)行處理使程序顯得不夠簡潔。可以設(shè)計出更通用、優(yōu)化的算法產(chǎn)生全部組合。