get_product_contenthtml
第5章精巧求解剖析
精巧求解，包括高精度计算，是吸引力的亮点，也是让人望而却步的难点。
本章从互积和与嵌套根式和的巧算、同码数的整除及同码数求和规律的探索，到建模统计、分类统计、游戏中的素数概率求解，突出一个“巧”字。同时，从探索小01串积、指定多码串积与尾数前移问题等，突显一个“精”字。
探讨并拓展著名的梅齐里亚克砝码问题与伯努利装错信封的排列问题，是“巧”与“精”结合的典范。飘逸于数学殿堂的两个“幽灵”e和π，凝聚着数学的精华，彰显出编程的卓越。5.1和与积巧算
本节探讨简单的互积和与根式和，不存在难点，但求解技巧颇具启发性。
5.1.1互积和
探求已知整数组的互积和是涉及和与积的常规题，有较强的技巧性，常常作为数学奥赛的培训题或测试题。
有9个整数: -3，-2，-1，0，1，2，4，8，16，对这9个整数求任意2个数之积，任意3个数之积，……，直至所有9个数之积。把所有这些积之和称为这些整数的互积和。
【问题】试求这9个整数的互积和m。
【分类求解】把互积和分类是简化求解的关键。
可忽略0，因凡含有0的积结果均为0，对后结果没有影响。
注意到所有正数和为31，分以下5类情形考虑。
（1） 所有正数互积和，设为s1（不含单个正数）。
（2） 所有负数互积和: s2=2 3 6-6=5。
（3） 含1个负数的互积和: s3=(-1-2-3)×(s1 31)=-6s1-6×31。
（4） 含2个负数的互积和: s4=11×(s1 31)=11s1 11×31。
（5） 含3个负数的互积和: s5=-6×(s1 31)=-6s1-6×31。
以上5项求和，巧妙消去其中尚未算出的s1，得到互积和m。m=s1 s2 s3 s4 s5=5-31=-26 【妙思巧解】巧妙构造多项式化互积为多项式积。
记8个非零整数为a1，a2，…，a8，构造多项式f(x)=(x a1)(x a2)…(x a8)=x8 p1x7 p2x6 … p7x p8（1）其中，p1为8个数之和25；p2为任意2个数积之和；p3为任意3个数积之和；……；p8为所有8个数之积。显然，所求互积和m=p2 … p8
令x=1，由式（1）左边知f(1)=0（因有一整数为-1）；同时，由式（1）右边有f(1)=1 p1 p2 … p8=1 25 m，因而所求结果为m=p2 … p8=-26。
给出的整数中有-1，即得和f(1)=0，这是减少计算量的关键所在。
即使给出的8个整数中没有-1，计算式（1）左边的8个数之积也远比计算“互积”来得简单。
【概括】以上两个求解都颇具启发性。如果按“互积”的定义，具体实施每2个数求积，每3个数求积，……，这一思路并不可行。而分类的思想和建多项式的思想，就是化解“互积”这一难点的巧妙突破点。
如果对于指定的一般n个整数，如何求取其互积和？
【编程拓展】 拓展至一般情形，探求n个整数的互积和。
对给出的n个整数，计算任意2个数之积，任意3个数之积，……，直到所有n个数之积。定义所有这些积之和为这n个整数的互积和m。
从键盘输入n个整数，探求并输出这n个整数的互积和m。
（1） 设计要点。
按上述巧妙构造多项式，化“互积”为多项式积。
设置存储n个整数的a数组，从键盘输入的n个整数存储在a［1］，a［2］，…，a［n］。
同时构造关于这n个整数的n次多项式y(x)=(x a1)(x a2)…(x an)=xn p1xn-1 p2xn-2 … pn-1x pn（2）其中，p1为n数之和；p2为任意2个数积之和；……；pn-1为任意n-1个数积之和；pn为所有 n个数之积。显然，m=p2 … pn。
令x=1，按式（2）左边通过循环求积，可简单得出y(1)；按式（2）右边有y(1)=1 p1 p2 … pn-1 pn；同时在循环中求出n个整数之和p1，显然所求互积和m为m=y(1)-p1-1（3）循环结束，即按式（3）输出所求n个整数的互积和m。
（2） 程序设计。//求n个整数的互积和m
#include <stdio.h>
void main()
{longk,m,n,s,y,a\[100\];
printf("请确定整数的个数n:");scanf("%ld",&n);
s=0;y=1;
for(k=1;k<=n;k )//逐个输入n个整数
{printf("请输入第%ld个整数:",k);
scanf("%ld",&a\[k\]);
s =a\[k\]; y=(1 a\[k\]); //计算整数和s及f(1)
}
m=y-1-s;//计算互积和m
printf("输入的%ld个整数为:%ld",n,a\[1\]);
for(k=2;k<=n;k )//集中输出n个整数
printf(", %ld",a\[k\]);
printf("\\n以上%ld个整数的互积和m=%ld。 \\n",n,m);//输出结果
}（3） 程序运行示例与说明。请确定整数的个数n:8
输入的8个整数为:-5, -3, -2, 3, 5, 8, 10, 13
以上8个整数的互积和m=-266142。
运行程序时，输入n个整数的先后顺序对互积和结果没有影响。
以上程序把求互积（若干积）转化为求一个积，是简化复杂运算的技巧所在。
同时，程序设置在输入循环中输入与计算（和与积）同步进行，输入循环结束，计算也随之完成。
如果运行程序，输入9个整数-3，-2，-1，0，1，2，4，8，16，即可得到互积和为-26，其中的整数-1是一个简化因子。
即使没有-1这一简化整数,以上程序实现把“互积”难点转化为在循环中求一个积,也非常精巧。
5.1.2嵌套根式和
试求以下两个嵌套根式和s1=1 2 3 … n(4)
s2=5 3 5 3 … 5 3(式中有n个5与n个3)(5)输入正整数n,输出根式和s1与s2(精确到小数点后8位)。
1. 设计要点
对于给定的正整数n,在s1中涉及n层开方,而s2涉及2n层开方,新颖少见。
根式和(4)与(5)存在根号嵌套,处理根号嵌套这一难点是设计的关键。
按通常由起点1到终点n设置循环,不便于处理根号嵌套这一难点。但若反过来逆向设置循环,解决根号嵌套就顺理成章。
(1) 实现s1求和。
设置a(n-1～1)循环枚举整数a,循环外赋初值s1=n; 循环内求累加和。s1=a sqrt(s1);赋值表达式中的sqrt(s1),即可实现s1的根号嵌套。
当a=n-1时,s1=(n-1) sqrt(n); 实现内1层根号。
当a=n-2时,s1=(n-2) sqrt((n-1) sqrt(n)); 实现内2层根号。
……
当a=1时,s1实现式(4)除外层之外的其他所有n-1层根号。
后一层根号在输出结果时完成。
(2) 实现s2求和。
同样设置a(n-1～1)循环,循环外赋初值s2=5 sqrt(3); 循环n-1次。s2=5 sqrt(3 sqrt(s2));赋值表达式中的sqrt(s2)即可实现s2的根号嵌套。
当a=n-1时,s2=5 sqrt(3 sqrt(5 sqrt(3))); 实现内3层根号。
当a=n-2时,s2=5 sqrt(3 sqrt(5 sqrt(3 sqrt(5 sqrt(3))))); 实现内5层根号。
……
当a=1时,s2实现式(5)除外层之外的其他所有2n-1层根号。
后一层根号在输出结果时完成。
2. 程序设计//探求两个根式和
#include <stdio.h>
#include <math.h>
void main()
{double a,n,s1,s2;
printf("请输入正整数n(n>1): "); scanf("%lf",&n);
s1=n;s2=5 sqrt(3);
for(a=n-1;a>=1;a--)//枚举n-1至1的整数a
{s1=a sqrt(s1);
s2=5 sqrt(3 sqrt(s2));
}
printf("s1=%.8f\\n",sqrt(s1));//后的和s1与s2需开平方
printf("s2=%.8f\\n",sqrt(s2));
}3. 程序运行示例与变通请输入正整数n(n>1): 100
s1=1.75793276
s2=2.71870969
在所设置的a循环中,应用s1=a sqrt(s1);及s2=5 sqrt(3 sqrt(s2));是实现根号嵌套的技巧所在。
变通: 容易修改以上程序,探求区间［c,d］中的根式和s1=c (c 1) (c 2) … d（6)
s2=c (c 1) c (c 2) … c d（7)输入区间上下限正整数c,d(c<d),输出根式和s1与s2。
5.2同码数汇趣
由同一个数码组成的数称为同码数。
例如,555,0.7777都是同码数,前者是同码整数,而后者则是同码小数。
如果说优美数要求数字不重复体现和谐美,那么同码数强调数码相同则是奇异美的象征。本节探讨同码数整除问题,探求同码整数与同码小数之和。从同码整数之和与同码小数之和可发现一些有趣的规律与特点。
5.2.1同码数整除
先看一个简单的同码数整除问题。
【命题】存在正整数n≤2019,使得n个1组成的同码整数m能被2019整除。
【证明】根据余数的抽屉原理来证。
分别由n=1～2019个由1组成的同码整数除以2019,其余数r不外乎0,1,…,2018。
如果存在某一n值,n个1组成的同码数除以2019,余数r=0,则命题成立。
假设分别由n=1～2019个由1组成的同码数除以2019,余数中不存在0,这2019个余数r不外乎1,…,2018。根据抽屉原理,2019个余数中必存在至少两个余数是相同的。
不妨设1≤n1<n2≤2019,由n1个1组成的整数m1与由n2个1组成的整数m2,这两个同码数除以2019的余数相同。于是其差m=m2-m1能被2019整除,注意到m=m2-m1=11…1n2-n100…0n1=11…1n2-n1×100…0n1（1)整数m是2个整数之积,后者只有2与5因数,不能被2019整除,只有前者被2019整除。注意到1≤n2-n1<2019,即存在n2-n1个1 组成的同码数能被2019整除,与假设矛盾。
因而证得存在正整数n≤2019,使得n个1组成的同码数m能被2019整除。
【问题】至少需要多少个1组成的同码整数m能被2019整除。
【求解】试实施竖式除法实验探求。
探求由1组成的同码整数,至少需要多少个1才能被2019整除,可实施竖式除法,如图51所示。图51实施竖式除法示意图
只要有一定的耐心与时间,总可以把竖式除法做下去,找到小的整数n,使得n个1组成的同码数m能被2019整除。
可以肯定地告诉你,除法不可能无限制地进行下去,因为有n≤2019。至于n至少为多大,则必须要等以上图示的试商结果出炉。
【编程探求】探求同码数能被p整除。
给定正整数p(约定整数p为个位数字不是5的奇数),探求小的正整数n,使得n个1组成的同码数能被p整除。
为什么要约定整数p为个位数字不是5的奇数呢?因为偶数的积只能是偶数,个位数字为5的奇数的乘积个位数字只能是0或5,都不可能为1。
(1) 竖式除法模拟设计要点。
设整数竖式除法每次试商的被除数为a,除数为p(即给定正整数),每次试商余数为c。
以余数c≠0作为条件设置条件循环,循环外赋初值: c=1,n=1;或c=11,n=2等。
被除数a=c10 1,试商余数c=a%p。每商一位,设置统计1个数的变量n增加1。
若余数c=0,结束循环,输出结果。
否则,继续下一轮试商,直到c=0为止。
(2) 程序设计。//探求整数至少多少个1能被指定整数p 整除
#include <stdio.h>
void main()
{int a,c,p,n;
printf("请输入整数p: "); scanf("%d",&p);
if(p%2==0 || p%10==5)
{ printf("不存在同码数整除%d。",p); return; }
n=1; c=1;//确定初始值n,c
while(c!=0)
{ a=c10 1; c=a%p; n ;}//实施除乘竖式计算模拟
printf("至少需%d个1的整数才能被%d整除。\\n",n,p);
}(3) 程序运行示例与说明。请输入整数p: 2019
至少需672个1的整数才能被2019整除。
输出结果是至少需672个1才能被2019整除,靠人工实施竖式除法,想得出这一结果还是比较繁复的。
这还不算,试试“至少需多少个1才能被2017整除”,就更能切身体会到人工计算与程序计算的效益差别。
5.2.2同码数求和
本节探索n个同码数求和,包括同码整数求和与同码小数求和。设和式s(d,n)=d dd ddd … dd…d(n个d)（2)
f(d,n)=0.d 0.dd 0.ddd … 0.dd…d(小数点后n个d)（3)式(2)为n个同数码d整数之和,和式中第k项有k位数字d(d=1,2,…,9)。
例如,s(3,5)=3 33 333 3333 33333。
式(3)为n项同数码d小数之和,其中第k项小数点后有连续k个数字d(d=1,2,…,9)。
例如,f(7,4)=0.7 0.77 0.777 0.7777。
【问题1】试求同码整数和s(3,30)。
【求解】引入中间量s(9,30)用以简化求和。
引入中间量s(9,30)是有趣的,因为s(9,30)与s(3,30)直接相关,而s(9,30)可以直接算出。事实上,由s(3,30)=s(9,30)/9×3=s(9,30)/3（4)而s(9,30)=9 99 … 99…9
=(10-1) (100-1) … (1030-1)
=11…10-30=11…1080 (后数中28个1)
s(3,30)=11…1080/3(被除数中28个1)
注意到1111/3=370,余数1;1080/3=360,因而得S(3,30)=370…3709个370360（5)有趣的是,以上s(3,30)的结果(5)中出现9个370重复节,耐人寻味。
【问题2】试求同码小数和f(6,30)。
【求解】引入中间量f(9,30)用以简化求和。
同样引入中间量f(9,30),因为f(9,30)与f(6,30)直接相关,而且f(9,30)可以直接算出。由f(6,30)=s(9,30)/9×6=s(9,30)×2/3（6)而f(9,30)=0.9 0.99 … 0.99…9=30-0.11…1(后项小数共连续30个1)则f(6,30)=(30-0.111…)×2/3=(60-0.222…)/3因而f(6,30)=59.77…78/3=19 2.77…78/3 (其中后项小数有连续29个7)注意到2777/3=925,余数为2;而2778/3=926,因而得f(6,30)=19.925…9259个925926（7)同样耐人寻味的是,f(6,30)的结果(7)中出现9个重复节925。
【编程拓展】探求同码整数和s(d,n)与同码小数和f(d,n)。
输入整数d(1≤d≤9),及整数n(1<n≤100),输出s(d,n)与f(d,n)。
1. 设计要点
设置s数组存储和s(d,n),s［1］存储个位数字,s［2］存储十位数字,以此类推。
设置f数组存储和f(d,n),f［0］存储小数和的整数部分,f［1］存储小数点后第1位,f［2］ 存储小数点后第2位,……,f［n］存储小数点后第n位。
(1) 整数求和。
整数和式中共有n位数求和,第i个数有i位(i=1,2,…,n),每一位数字为d。
设置i(1～n)循环,循环n次,实施n个数相加: i=1时,个位有n个d相加,其值为n×d;i=2时,十位有n-1个d相加,其值为(n-1)×d;一般第i位,有n-i 1个d相加,其值为(n-i 1)×d。
完成相加后,还需从个位开始,逐位实施进位:s\[j 1\]=s\[j 1\] s\[j\]/10;s\[j\]=s\[j\]%10; (j=1~n-1)整数输出当然是从高位开始,逐位向低位输出。
(2) 小数求和。
同样设置i(1～n)循环,循环n次,实施n个数相加: i=1时,小数点后第1位有n个d相加,其值为n×d;i=2时,小数点后第2位有n-1个d相加,其值为(n-1)×d;一般小数点后第i位,有n-i 1个d相加,其值为(n-i 1)×d。
以上相加就在一个循环中实现。完成n个相加后,还需从小数点后第n位开始,逐位实施进位。f\[j-1\]=f\[j-1\] f\[j\]/10;f\[j\]=f\[j\]%10; (j=n~1)后得到的f［0］即为小数和的整数部分,其值可能为1位,也可能为多位。
小数和输出,先输出整数部分f［0］加带小数点,然后从小数点第1位开始,逐位输出到小数点后第n位。
2. 同码数求和程序设计//求整数和s(d,n)=d dd ddd … dd…d(n个d)
//求小数和f(d,n)=0.d 0.dd 0.ddd … 0.dd…d(n个d)
#include <stdio.h>
void main()
{int d,i,j,n,s\[5000\],f\[5000\];
printf(" 请输入整数d,n: ");scanf("%d,%d",&d,&n);
for(j=0;j<=n;j ) s\[j\]=f\[j\]=0;
for(i=1;i<=n;i )
s\[i\]=f\[i\]=(n-i 1)d;//第i位共n 1-i个d之和
for(j=1;j<=n-1;j )//加完n个整数数后统一进位
{ s\[j 1\]=s\[j 1\] s\[j\]/10;s\[j\]=s\[j\]%10;}
printf("s(%d,%d)=",d,n);
for(j=n;j>=1;j--)//从高位开始逐位输出和s(d,n)
printf("%d",s\[j\]);
for(j=n;j>=1;j--)//加完n个小数数后统一进位
{ f\[j-1\]=f\[j-1\] f\[j\]/10;f\[j\]=f\[j\]%10;}
printf("\\nf(%d,%d)=%d.",d,n,f\[0\]);
for(j=1;j<=n;j )//从小数点后位开始逐位输出和
printf("%d",f\[j\]);
printf(" \\n");
}3. 程序运行示例与说明请输入整数d,n: 7,30
s(7,30)=864197530864197530864197530840
f(7,30)=23.246913580246913580246913580247
从上述整数求和结果看,864197530这一“重复节”在和中重复3次,只有后3位840不属于重复节。
从上述小数求和结果看,小数点后除了尾部3位247之外,其余是246913580这一“重复节”,重复3次。
同码数求和结果中的“重复节”与循环小数的“循环节”有类似之处,不同的是重复节往往在前面,而循环节通常在后面。
5.3统计的智慧
本节探讨巧妙建模、三角网格与交通方格网等3个有代表性的统计案例,其统计思路与方法颇为新颖。
5.3.1巧妙建模
本案例探求一个线性不定方程的解有多少组,应用建模简化了统计过程。
【问题】对于不定方程 x y z=15,试统计:
(1) x,y,z为非负整数解的组数;
(2) x,y,z为正整数解的组数;
(3) x,y,z满足x≥-3,y≥2,z≥5的整数解的组数。
【建模巧解】拟建立投球统计模型,转化为组合计算。
(1) 把问题转化为15个相同的小球投放到3个分别标有x,y,z标签的盒子中的不同的投放种数。然后,把3个盒子“抽象”为并排设置的2块隔板,这2块隔板划分的3个区域相当于3个盒子,即x,y,z变量。于是把15个小球与这2块隔板进行排列,每一种不同的排列对应一种投球结果,即对应不定方程x y z=15的一组解。排列种数等于15 2个位置中挑选出2块隔板位置的组合数C(15 2,2)。因而x,y,z为非负整数解的组数为C(17,2)=136。
(2) 若x,y,z为正整数,相当于每一个盒子至少要投放一个小球,不妨每一盒子先放一小球。然后15-3=12个小球与2块隔板进行排列,共有组数即为组合数C(12 2,2)。因而x,y,z为正整数解的组数为C(14,2)=91。
(3) 若x,y,z满足x≥-3,y≥2,z≥5,令a=x 3,b=y-2,c=z-5,则由x y z=15得a b c=11(a,b,c≥0),由上可知这一方程的非负整数解组数为组合数C(11 2,2)。因而x,y,z满足x≥-3,y≥2,z≥5的整数解的组数为C(13,2)=78。
【编程拓展】
对于给定的正整数和s,对于3个变量x,y,z的不定方程x y z=s,试统计x,y,z取自区间［c,d］(0≤c<d,3c≤s) 整数解的组数。
(1) 设计要点。
建立x,y,z循环枚举区间［c,d］上的所有整数,如果满足条件x y z=s即输出方程的解并用n实施统计。
注意到3个变量x,y,z没有大小约定,因而循环区间都是［c,d］。
(2) 程序设计。//不定方程x y z=s求解与统计
#include <stdio.h>
#include <math.h>
void main()
{int c,d,n,s,x,y,z;
printf("请确定各变量起点c与终点d:"); scanf("%d,%d",&c,&d);
printf("请确定和s(3c<s<3d): "); scanf("%d",&s);
n=0;
for(x=c;x<=d;x )//设置3重循环枚举x,y,z
for(y=c;y<=d;y )
for(z=c;z<=d;z )
if(x y z==s)//满足条件时统计并输出解
{n ;
printf(" x=%d,y=%d,z=%d",x,y,z);
if(n%3==0)printf("\\n");
}
printf("\\n 共%d组解。\\n",n);
}(3) 程序运行示例与说明。请确定各变量起点c与终点d: 5,9
请确定和s(3c<s<3d): 20
x=5,y=6,z=9 x=5,y=7,z=8 x=5,y=8,z=7
x=5,y=9,z=6 x=6,y=5,z=9 x=6,y=6,z=8
x=6,y=7,z=7 x=6,y=8,z=6 x=6,y=9,z=5
x=7,y=5,z=8 x=7,y=6,z=7 x=7,y=7,z=6
x=7,y=8,z=5 x=8,y=5,z=7 x=8,y=6,z=6
x=8,y=7,z=5 x=9,y=5,z=6 x=9,y=6,z=5
共18组解。
当输入c=0,d=15,s=15,即为上面建模所解x y z=15的136个非负整数解。
当输入c=1,d=15,s=15,即为上面建模所解x y z=15的91个正整数解。
区间［c,d］的起始整数c也可以取负整数。
