印尼大师赛次轮朴安河领先 詹世昌第二白老虎第七_综合体育_新浪竞技风暴_新浪网
印尼大师赛次轮朴安河领先 詹世昌第二白老虎第七
印尼赛激战正酣
　　新浪体育讯　北京时间4月24日消息，在新加坡居住的澳大利亚高尔夫球手朴安河今天与皇家雅加达高尔夫俱乐部的大风展开了苦斗，最终交出73杆(+1)之后，以一杆优势获得了总奖金75万美元的亚巡赛-联昌银行印尼大师赛第二轮的领先，28岁的中华台北球手詹世昌排在第2位，而前世界第一李-维斯特伍德则排在第7位。
　　联昌银行印尼大师赛第二轮的比赛遭遇了大风，全场只有4位球手打出低于标准杆的成绩。朴安河继续将自己放在夺取首个亚巡赛冠军的有利位置上，以140杆(-4)的总成绩上升至成绩榜第1位。首轮并列领先的詹世昌在自己的最后一个洞擒获老鹰，交出75杆(+3)，以141杆(-3)的总成绩跌至第2位。首轮的另外一位并列领先者托马斯-比约恩(76杆)、日本球手V田阳亮(Yosuke Tsukada，71杆)以及2名泰国球手奈彻库-塔提珀卡库(Namchok Tantipokhakul,73杆)、查普查-尼拉特(Chapchai Nirat，74杆)一道以142杆(-2)的总成绩排在并列第3位。两届印尼大师赛冠军维斯特伍德今天以74杆收杆，以143杆(-1)的总成绩位居第7位。
　　本轮比赛之前，朴安河排在并列第2位，从后9洞出发，一上来就陷入了挣扎，在自己的首个洞吞下柏忌，不过他很快在14号洞和16号洞分别抓下了小鸟。然而转场之后，他只添加了1只小鸟，吞下了3个柏忌，不过在大部分球手都遇到大麻烦的情况下，73杆的成绩还是确保朴安河获得了单独领先。
　　“今天是艰难的一天，我实际上觉得今天的风刮得更猛烈。我的击球不如昨天那样好，但我还是打出了一些好球，”41岁的朴安河甚至对自己占据着领先位置感到吃惊，不过也有信心拿下个人的首个亚巡赛冠军，“当我打得出色的时候，我总会给自己带来惊喜。今天，我就是坚持了下来，总体来说，进入到周末的比赛还是处于很棒的位置上。”
　　与此同时，詹世昌依靠在自己最后一洞切进的老鹰球，排到了第2位，同样有希望摘得职业生涯的亚巡赛首胜。“我需要最后一洞的老鹰，把我拉回到争夺冠军的行列里。这确实是一大安慰，因为我在转场的时候已经变成了+4的成绩，需要像那种老鹰球特别的东西来将我带回到竞争冠军的行列。我习惯了这种大风的比赛，因为这也跟我在家乡的球场状况相似，但是我今天在距离方面遇到了大问题，毕竟这是一座相当长的球场，我必须要打出非常远的击球。”
　　维斯特伍德今天也在狂风面前望而却步，但是仍有信心摘得第3个印尼大师赛的冠军。目前落后领先者三杆。“这是我在亚洲见过的最难打的比赛之一。天气状况真的很极端，我们在这种天气下没有时来运转。正常来说，早上的状况会较为风平浪静，但是从今天早晨一开始，风就刮得很大。”
　　“我觉得，打出低于标准杆的成绩就会让你进入到争冠的行列里，我目前就处于这样的位置上。我想，周日的冠军之争会是一场众人激战的乱战。”获得过2011年和2012年印尼大师赛冠军的维斯特伍德今天迎来了自己42周岁的生日，要是能够在周日加冕胜利，无疑是给其最好的礼物。
　　联昌银行印尼大师赛前两轮比赛过后，晋级线设为151杆(+7)的总成绩，总共有68名球手顺利获得晋级。
　　(米罗)
文章关键词：
&&|&&&&|&&&&|&&
您可通过新浪首页顶部 “”， 查看所有收藏过的文章。
请用微博账号，推荐效果更好！计算机算法课后习题总结 - LegendQi - 博客园
随笔 - 261
习题解答提要
1-1 分数分解算法描述
把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和：
（1） 寻找并输出小于a/b的最大埃及分数1/c；
（2） 若c&，则退出；
（3） 若c≤，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。
（4） 若a/b不为埃及分数，则继续（1）、（2）、（3）。
试描述以上算法。
解：设 (这里int(x)表示取正数x的整数)，注意到 ，有
算法描述：令c=d+1，则
input (a,b)
{c=int(b/a)+1;
{ print(1/c+);
b=bc; // a,b迭代，为选择下一个分母作准备
{ print(1/b);}
1-2 求出以下程序段所代表算法的时间复杂度
for(k=1;k&=n;k++)
for(j=k;j&=1;j--)
解：因s=1+2+…+n=n(n+1)/2
时间复杂度为O(n2)。
for(k=1;k&=n;k++)
for(j=1;j&=k/2;j++)
解：设n=2u+1，语句m=m+1的执行频数为
s=1+1+2+2+3+3+…+u+u=u(u+1)=(n-1)(n+1)/4
设n=2u，语句m=m+1的执行频数为
s=1+1+2+2+3+3+…+u=u2=n2/4
时间复杂度为O(n2)。
（3）t=1;m=0;
for(k=1;k&=n;k++)
for(j=1;j&=kt;j++)
解：因s=1+2×2!+ 3×3!+…+ n×n!=(n+1)!-1
时间复杂度为O((n+1)!).
（4）for(a=1;a&=n;a++)
for(b=a100-1;b&=a100-99;b-=2)
{for(x=0,k=1;k&=sqrt(b);k+=2)
if(b%k==0)
printf("%ld \n",a);}
解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环 次。因而k循环体的执行次数s满足
时间复杂度为O( )。
1-3 若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。
证：设m为正整数，p(n)=a1×nm+a2×nm-1+…+am×n，
取常数c&ma1+(m-1)a2+…+am, 则
log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×logn
因而有O(log(p(n)))=O(logn)。
1-4 构建对称方阵
观察图1-5所示的7阶对称方阵：
图1-5 7阶对称方阵
试构造并输出以上n阶对称方阵。
解：这是一道培养与锻炼我们的观察能力与归纳能力的案例，一个一个元素枚举赋值显然行不通，必须全局着眼，分区域归纳其构造特点，分区域枚举赋值。
（1） 设计要点
设方阵中元素的行号为i，列号为j。
可知主对角线：i=j；次对角线：i+j=n+1。两对角线赋值“0”。
按两条对角线把方阵分成上部、左部、右部与下部4个区,如图1-6所示。
图1-6 对角线分成的4个区
上部按行号i赋值；下部按行号函数n+1-i赋值。
左部按列号j赋值；右部按列号函数n+1-j赋值。
（2） 程序实现
#include &stdio.h&
void main()
{int i,j,n,a[30][30];
请确定方阵阶数n: ");
scanf("%d",&n);
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
{if(i==j || i+j==n+1)
a[i][j]=0;
// 方阵对角线元素赋值
if(i+j&n+1 && i&j)
a[i][j]=i;
// 方阵上部元素赋值
if(i+j&n+1 && i&j)
a[i][j]=j;
// 方阵左部元素赋值
if(i+j&n+1 && i&j)
a[i][j]=n+1-i;
// 方阵下部元素赋值
if(i+j&n+1 && i&j)
a[i][j]=n+1-j;
// 方阵右部元素赋值
%d阶对称方阵为:\n",n);
for(i=1;i&=n;i++)
{ for(j=1;j&=n;j++)
// 输出对称方阵
printf("%3d",a[i][j]);
printf("\n");
1-5 据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。
修改程序，求出 n至少为多大时，n个“1”组成的整数能被2013整除？
解：程序为
#include &stdio.h&
void main()
{ int a,c,p,n;
c=1111;n=4;
变量c与n赋初值
while(c!=0)
循环模拟整数竖式除法
{ a=c*10+1;
// 每试商一位n增1
由 %d 个1组成的整数能被 %d 整除。\n",n,p);
2-1 解不等式
设n为正整数，解不等式
解：上下限一般为键盘输入的a,b。
// 解不等式: a&1+1/(1+1/2)+...+1/(1+1/2+...+1/n)&b
#include &stdio.h&
#include&math.h&
void main()
{ long a,b,c,d,i;
double ts,s;
请输入a,b: ");
scanf("%d,%d",&a,&b);
i=0;ts=0;s=0;
while(s&a)
ts=ts+(double)1/i;
while(s&b)
ts=ts+(double)1/i;
printf("\n 满足不等式的正整数n为: %ld≤n≤%ld \n",c,d);
2-2 韩信点兵
韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。
按从1至5报数,记下最末一个士兵报的数为1；
再按从1至6报数,记下最末一个士兵报的数为5；
再按1至7报数,记下最末一个报的数为4；
最后按1至11报数,最末一个士兵报的数为10。
你知道韩信至少有多少兵?
设兵数为x，则x满足下述的同余方程组:
x=5y+1 即 x=1 (mod 5)
x=6z+5 x=5 (mod 6)
x=7u+4 x=4 (mod 7)
x=11v+10 x=10 (mod 11)
其中y,z,u,v都为正整数。试求满足以上方程组的最小正整数x。
应用枚举可得到至少的兵数。x从1开始递增1取值枚举当然可以，但不必要。事实上枚举次数可联系问题的具体实际大大缩减。
（1) 注意到x除11余10，于是可设置x从21开始，以步长11递增。此时，只要判别前三个条件即可。
（2) 由以上第2，4两方程知x+1为11的倍数，也为6的倍数。而11与6互素，因而x+1必为66的倍数。于是取x=65开始，以步长66递增。此时,只要判别x%5=1与x%7=4 两个条件即可。
这样可算得满足条件的最小整数x即点兵的数量。
include &stdio.h&
void main()
if(x%5==1 && x%7==4)
{ printf("至少有兵: %ld 个。",x);
分解质因数
对给定区间[m,n]的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。
例如, *503, 2011=(素数!)。
解：对区间中的每一个整数i(b=i)，用k(2——sqrt(i))试商：
若不能整除，说明该数k不是b的因数，k增1后继续试商。
若能整除，说明该数k是b的因数，打印输出"k*"；b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。
按上述从小至大试商确定的因数显然为质因数。
如果有大于sqrt(n)的因数(至多一个!),在试商循环结束后要注意补上，不要遗失。
如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。
若k是b的因数，按格式输出，然后b=b/k后继续试商k。
若k不是b的因数，则k增1后继续。
若上述试商完成后1&b&i，说明i有一个大于sqrt(i)的因数，要补上该因数。
若试商后b还是原来的i,则i是素数。
// 质因数分解乘积形式
include"math.h"
include &stdio.h&
void main()
{long int b,i,k,m,n,w=0;
printf("[m,n]中整数分解质因数（乘积形式）.\n");
printf("请输入m,n:");
scanf("%ld,%ld",&m,&n);
for(i=m;i&=n;i++) // i为待分解的整数
{ printf("%ld=",i);
while(k&=sqrt(i)) // k为试商因数
{if(b%k==0)
{printf("%ld*",k);
// k为质因数,返回再试
if(b==1) printf("%ld\n",k);
if(b&1 && b&i)
printf("%ld\n",b); // 输出大于i平方根的因数
{printf("(素数!)\n");w++;} // b=i,表示i无质因数
基于素数代数和的最大最小
(和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项取“-”，即为-25*27。)
求s(2011)。
设1&=n&=2011，当n为多大时，s(n)最大。
设1&=n&=2011，当n为多大时，s(n)最小。
解：代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：
若2k-1为素数，标注a[k]=1；
否则，若2k-1不是素数，a[k]=0。
设置k循环（1——n），循环中分别情况求和：
若a[k]+a[k+1]&=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”；
否则，若a[k]+a[k+1]==0，即(2k-1)与(2k+1)中没有素数，实施“-”。
同时，设置最大值变量smax，最小值变量smin。
在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。
// 基于素数的整数和
include&stdio.h&
include&math.h&
void main()
{ int t,j,n,k,k1,k2,a[3000]; long s,smax,
printf(" 请输入整数n: ");
scanf("%d",&n);
for(k=1;k&=n+1;k++) a[k]=0;
for(k=2;k&=n+1;k++)
{for(t=0,j=3;j&=sqrt(2k-1);j+=2)
if((2k-1)%j==0)
if(t==0) a[k]=1; // 标记第k个奇数2k-1为素数
s=3;smax=0;smin=s;
for(k=2;k&=n;k++)
{if(a[k]+a[k+1]&=1)
s+=(2k-1)(2k+1); // 实施代数和
s-=(2k-1)(2k+1);
if(s&smax){smax=s;k1=k;} // 比较求最大值smax
if(s&smin){smin=s;k2=k;} // 比较求最大值smin
printf("s(%d)=%ld \n",n,s);
printf("当k=%d时s有最大值: %ld\n",k1,smax);
printf("当k=%d时s有最小值: %ld\n",k2,smin);
特定数字组成的平方数
用数字2,3,5,6,7,8,9可组成多少个没有重复数字的7位平方数？
解：求出最小7位数的平方根b, 最大7位数的平方根c.
用a枚举[b，c]中的所有整数，计算d=a*a，这样确保所求平方数在d中。
设置f数组统计d中各个数字的个数。如果f[3]=2，即平方数d中有2个“3”。
检测若f[k]&1(k=0——9)，说明d中存在有重复数字，返回。
在不存在重复数字的情形下，检测若f[0]+f[1]+f[4]=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。
// 组成没有重复数字的7位平方数
include &math.h&
include &stdio.h&
void main()
{int k,m,n,t,f[10];
long a,b,c,d,w;
b=sqrt(2356789);c=sqrt(9876532);
for(a=b;a&=c;a++)
{d=a*a; w=d; // 确保d为平方数
for(k=0;k&=9;k++) f[k]=0;
while(w&0)
{ m=w%10;f[m]++;w=w/10;}
for(t=0,k=1;k&=9;k++)
if(f[k]&1) t=1; // 测试三个平方数是否有重复数字
if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4
printf(" %2d: ",n);
printf(" %ld=%ld^2 \n",d,a);
printf(" 共可组成%d个没有重复数字的7位平方数.\n",n);
写出例2-2中对称方阵的完整程序，并运行程序。
对称方阵程序：
include &stdio.h&
void main()
{int i,j,n,a[30][30];
printf(" 请确定方阵阶数n: ");
scanf("%d",&n);
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
{if(i+j&=n+1 && i&=j)
a[i][j]=(n+1)/2-i+1; // 方阵上部元素赋值
if(i+j&n+1 && i&j)
a[i][j]=(n+1)/2-j+1; // 方阵左部元素赋值
if(i+j&=n+1 && i&=j)
a[i][j]=i-n/2; // 方阵下部元素赋值
if(i+j&n+1 && i&j)
a[i][j]=j-n/2; // 方阵右部元素赋值
printf(" %d阶对称方阵为:\n",n);
for(i=1;i&=n;i++)
{ for(j=1;j&=n;j++) // 输出对称方阵
printf("%3d",a[i][j]);
printf("\n");
四则运算式
把数字1,2,...,9这9个数字填入以下含加减乘除的综合运算式中的9个□中,使得该式成立
□□×□+□□□÷□-□□=0
要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在数式的一位数中（即排除各式中的各个1位数为1这一平凡情形）。
（1） 求解要点
设式右的5个整数从左至右分别为a,b,c,d,e,其中a,e为二位整数，b,d为大于1的一位整数，c为三位整数。设置a,b,c,d循环，对每一组a,b,c,d,计算e=a*b+c/d。若其中的c/d非整数，或所得e非二位数，则返回。
然后分别对5个整数进行数字分离，设置f数组对5个整数分离的共9个数字进行统计，f(x)即为数字x(1—9)的个数。
若某一f(x)不为1，不满足数字1,2,...,9这九个数字都出现一次且只出现一次，标记t=1.
若所有f(x)全为1，满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。
设置n统计解的个数。
（2） 程序实现
// 四则运算式
include &stdio.h&
void main()
{int x,y,t,k,a,b,c,d,e,n=0;
int m[6],f[11];
for(a=12;a&=98;a++)
for(b=2;b&=9;b++)
for(c=123;c&=987;c++) // 对a,b,c,d 实施枚举
for(d=2;d&=9;d++)
{x=c/d;e=ab+x;
if(c!=xd || e&100)
m[1]=a;m[2]=c;m[3]=e;m[4]=b;m[5]=d;
for(x=0;x&=9;x++) f[x]=0;
for(k=1;k&=5;k++)
while(y&0)
{x=y%10;f[x]=f[x]+1;
y=(y-x)/10; // 分离数字f数组统计
for(t=0,x=1;x&=9;x++)
if(f[x]!=1)
{t=1;} // 检验数字0--9各只出现一次
if(t==0) // 输出一个解，用n统计个数
printf("%2d: %2d*%1d+%3d/%1d-%2d=0 \n",n,a,b,c,d,e);
printf(" n=%d.\n",n);
合数世纪探求
定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。
探索最早的合数世纪。
（1） 设计要点
应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。
对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。
（2） 合数世纪程序设计
// 合数世纪探求
include &stdio.h&
include &math.h&
void main()
{long a,b,k; int s,x;
{a++;s=0; // 检验a世纪
for(b=a100-99;b&=a100-1;b+=2) // 穷举a世纪奇数年号b
for(k=3;k&=sqrt(b);k+=2)
if(b%k==0)
if(x==0) // 当前为非合数世纪时，跳出循环进行下世纪的探求
s=s+x; // 年号b为合数时，x=1，s增1
if(s==50) // s=50，即50个奇数均为合数
{ printf("最早出现的合数世纪为 %ld 世纪!\n",a);
最小连续n个合数
试求出最小的连续n个合数。（其中n是键盘输入的任意正整数。）
（1）设计要点
求出区间[c,d]内的所有素数(区间起始数c可由小到大递增)，检验其中每相邻两素数之差。若某相邻的两素数m,f之差大于n，即m-f&n，则区间[f+1,f+n]中的n个数为最小的连续n个合数。
应用试商法求指定区间[c,d](约定起始数c=3，d=c+10000)上的所有素数。求出该区间内的一个素数m，设前一个素数为f,判别：
若m-f&n，则输出结果[f+1,f+n]后结束；
否则，作赋值f=m，为求下一个素数作准备。
如果在区间[c,d]中没有满足条件的解，则作赋值：c=d+2，d=c+10000，继续试商下去，直到找出所要求的解。
（2） 程序实现
求最小的连续n个合数
include &stdio.h&
include &math.h&
void main()
{ long c,d,f,m,j;
printf(" 求最小的n个连续合数.\n");
printf(" 请输入n:");
scanf("%d",&n);
c=3;d=c+10000;
{ for(m=c;m&=d;m+=2)
{ for(t=0,j=3;j&=sqrt(m);j+=2)
if(m%j==0) // 实施试商
if(t==0 && m-f&n) // 满足条件即行输出
{ printf("最小的%d个连续合数区间为:",n);
printf("[%ld,%ld]。 \n",f+1,f+n);
if(t==0) f=m; // 每求出一个素数m后赋值给f
{c=d+2;d=c+10000;} // 每一轮试商后改变c,d转下一轮
和积9数字三角形
求解和为给定的正整数s（s≥45）的9个互不相等的正整数填入9数字三角形，使三角形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。
图2-7 9数字三角形
（1）求解要点。
把和为s的9个正整数存储于b数组b(1)，…，b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即b(1)&b(7)&b(4)且b(2)&b(3)且b(6)&b(5)且b(9)&b(8)。
b数组分布示意图
可以根据约定对b(1)、b(7)和b(4)的值进行循环探索，设置：
b(1)的取值范围为1～(s-21)/3（因其他6个数之和至少为21）。
b(7)的取值范围为b(1)+1～(s-28)/2。
b(4)的取值范围为b(7)+1～(s-36)。
同时探索判断步骤如下：
1）若(s+b(1)+b(7)+b(4))%3≠0，则继续探索；否则，记s1=(s+b(1)+b(7)+b(4))/3。
2）根据约定对b(3)、b(5)和b(8)的值进行探索，设置：
b(3)的取值范围为(s1-b(1)-b(4))/2+1～s1-b(1)-b(4)。
b(5)的取值范围为(s1-b(4)-b(7))/2+1～s1-b(4)-b(7)。
b(8)的取值范围为(s1-b(1)-b(7))/2+1～s1-b(1)-b(7))。
同时根据各边之和为s1，计算出b(2)、b(6)和b(9)：
b(2)=s1-b(1)-b(4)-b(3)
b(6)=s1-b(4)-b(5)-b(7)
b(9)=s1-b(1)-b(7)-b(8)
3）若b数组存在相同正整数，则继续探索。
4）设s2=b(1)*b(2)*b(3)*b(4)，若另两边之积不为s2，则继续探索；否则探索成功，打印输出结果，接着继续探索直到所有数字组探索完毕为止。
（2）9数字三角形求解程序设计。
// 9数字三角形求解
include&stdio.h&
include&math.h&
void main()
int k,j,t,s,s1,s2,n,b[10];
printf(" 请输入正整数s：");
scanf("%d",&s);
for(b[1]=1;b[1]&=(s-21)/3;b[1]++)
for(b[7]=b[1]+1;b[7]&=(s-28)/2;b[7]++)
for(b[4]=b[7]+1;b[4]&=s-36;b[4]++)
if((s+b[1]+b[4]+b[7])%3!=0)
s1=(s+b[1]+b[4]+b[7])/3;
for(b[3]=(s1-b[1]-b[4])/2+1;b[3]&s1-b[1]-b[4];b[3]++)
for(b[5]=(s1-b[4]-b[7])/2+1;b[5]&s1-b[4]-b[7];b[5]++)
for(b[8]=(s1-b[1]-b[7])/2+1;b[8]&s1-b[1]-b[7];b[8]++)
b[2]=s1-b[1]-b[4]-b[3];
b[6]=s1-b[4]-b[7]-b[5];
b[9]=s1-b[1]-b[7]-b[8];
for(k=1;k&=8;k++)
for(j=k+1;j&=9;j++)
if(b[k]==b[j]) {t=1;k=8;}
s2=b[1]b[2]b[3]b[4];
if(b[4]b[5]b[6]b[7]!=s2)
if(b[1]b[9]b[8]*b[7]!=s2)
printf(" %3d：%2d",n,b[1]);
for(k=2;k&=9;k++)
printf(", %2d",b[k]);
printf(" s1=%d, s2=%d \n",s1,s2);
printf("共%d个解。",n);
递推求解b数列
已知b数列定义：
递推求b数列的第20项与前20项之和。
include &stdio.h&
void main()
{ int k,n; long b[3000],s;
printf(" 请输入n: ");
scanf("%d",&n);
b[1]=1;b[2]=2;s=3;
for(k=3;k&=n;k++)
{ b[k]=3*b[k-1]-b[k-2];
printf(" b(%d)=%ld \n",n,b[n]);
printf(" s=%ld \n",s);
双关系递推数列
集合M定义如下：
3）再无别的数属于M
试求集合M元素从小到大排列的第2011个元素与前2011 个元素之和。
解：（1）设计要点
设n个数在数组m中，2x+1与3x+1均作为一个队列，从两队列中选一排头（数值较小者）送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。
if(2*m(p2)&3*m(p3))
{ m(i)=2*m(p2)+1;p2++;}
if(2*m(p2)&3*m(p3))
{ m(i)=3*m(p3)+1;p3++;}
特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。
if(2*m(p2)==3*m(p3))
{ m(i)=2*m(p2)+1;
p2++; p3++;
// 为避免重复项，P2，p3均须增1
（2） 程序设计
双关系递推
include &stdio.h&
void main()
{int n,p2,p3,i;long s,m[3000];
m[1]=1;s=1;
p2=1;p3=1; // 排头p2,p3赋初值
printf(" 请输入n: ");
scanf("%d",&n);
for(i=2;i&=n;i++)
if(2m[p2]&3m[p3])
{ m[i]=2m[p2]+1; s+=m[i];
{ m[i]=3m[p3]+1; s+=m[i];
if(2m[p2]==3m[p3]) p2++; // 为避免重复项，P2须增1
printf(" m(%d)=%ld\n",n,m[n]);
printf(" s=%ld\n",s);
3-3 多幂序列
设x,y,z为非负整数，试计算集合
的元素由小到大排列的多幂序列第n项与前n项之和。
（1）递推算法设计
集合由2的幂、3的幂与5的幂组成，实际上给出的是3个递推关系。
显然，第1项也是最小项为1（当x=y=z=0时）。
从第2项开始，为了实现从小到大排列，设置3个变量a,b,c，a为2的幂，b为3的幂，c为5的幂，显然a,b,c互不相等。
设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;c=5;s=1;在k循环中通过比较赋值：
当a&b且a&c时，由赋值f[k]=a确定为序列的第k项；然后a=a*2，即a按递推规律乘2，为后一轮比较作准备；
当b&a且b&c时，由赋值f[k]=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。
当c&a且c&b时，由赋值f[k]=c确定为序列的第k项；然后c=c*5，即c按递推规律乘5，为后一轮比较作准备。
递推过程描述：
a=2;b=3;c=5;
// 为递推变量a,b,c赋初值
for(k=2;k&=n;k++)
{ if(a&b && a&c)
{ f[k]=a;a=a*2;}
// 用a给f[k]赋值
if(b&a && b&c)
{ f[k]=b;b=b*3;}
// 用b给f[k]赋值
{ f[k]=c;c=c*5;}
// 用c给f[k]赋值
在这一算法中，变量a,b,c是变化的，分别代表2的幂、3的幂与5的幂。
上述递推算法的时间复杂度与空间复杂度均为O(n)。
（2）多幂序列程序实现
// 多幂序列求解
include &stdio.h&
void main()
{int k,m,t,p2,p3,p5;
double a,b,c,s,f[100];
printf(" 求数列的第m项与前m项和,请输入m: ");
scanf("%d",&m);
f[1]=1;p2=0;p3=0;p5=0;
a=2;b=3;c=5;s=1;
for(k=2;k&=m;k++)
{ if(a&b && a&c)
{ f[k]=a;a=a2; // 用2的幂给f[k]赋值
t=2;p2++; // t=2表示2的幂，p2为指数
else if(b&a && b&c)
{ f[k]=b;b=b3; // 用3的幂给f[k]赋值
t=3;p3++; // t=3表示3的幂，p3为指数
{ f[k]=c;c=c*5; // 用5的幂给f[k]赋值
t=3;p5++; // t=5表示5的幂，p5为指数
printf(" 数列的第%d项为: %.0f ",m,f[m]);
if(t==2) // 对输出项进行标注
printf("(2^%d) \n",p2);
else if(t==3)
printf("(3^%d) \n",p3);
printf("(5^%d) \n",p5);
printf(" 数列的前%d项之和为：%.0f \n",m,s);
双幂积序列的和
由集合 元素组成的复合幂序列，求复合幂序列的指数和x+y≤n（正整数n从键盘输入）的各项之和
（1）设计要点
归纳求和递推关系:
当x+y=0时，s(1)=1；
当x+y=1时，s(1)=2+3；
当x+y=2时，s(2)=22+2×3+32=2*s(1)+ 32
当x+y=3时，s(3)=23+22×3+2×32+33=2*s(2)+ 33
一般地，当x+y=k时，s(k)=2*s(k-1)+3k
即有递推关系：
s(k)=2*s(k)+3k
其中3k可以通过变量迭代实现。这样可以省略数组，简化为一重循环实现复合幂序列求和。
（2）程序实现
// 复合幂序列求和
include &stdio.h&
void main()
{int k,n; long sum,t,s[100];
printf("请输入幂指数和至多为n:");
scanf("%d",&n);
t=1;s[0]=1; sum=1;
for(k=1;k&=n;k++)
{t=t3; // 迭代得t=3^k
s[k]=2s[k-1]+t; // 实施递推
sum=sum+s[k];
printf("幂指数和至多为%d的幂序列之和为:%ld\n",n,sum);
核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t秒时反应堆裂变产生的α粒子和β粒子数。
1. 算法设计
设在t秒时α粒子数为f(t)，β粒子数为g(t)，依题可知：
g(t)=3f(t-1)+2g(t-1)
f(t)=g(t-1)
g(0)=0,f(0)=1
由（2）得f(t-1)=g(t-2)
将式（3）代入（1）得
g(t)=2g(t-1)+3g(t-2) (t≥2)
g(0)=0,g(1)=3
以递推关系（4）与初始条件（5）完成递推。
2．粒子裂变C程序设计
// 粒子裂变
include&stdio.h&
void main()
{int t,k;long g[100];
printf(" input t:");
scanf("%d",&t);
g[0]=0; g[1]=3; // 确定初始条件
for(k=2;k&=t;k++)
g[k]=2g[k-1]+3g[k-2]; // 完成递推
printf("%d 秒时反应堆中β粒子数为:%ld \n",t,g[t]);
printf("%d 秒时反应堆中α粒子数为:%ld \n",t,g[t-1]);
m行n列逆转矩阵
图3-4所示为4行5 列逆转矩阵。
试应用递推设计构造并输出任意指定m行n列逆转矩阵。
解： 对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。
设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。
程序设计：'
// m×n数字逆转矩阵
#include &stdio.h&
void main()
{int i,j,c,d,h,v,m,n,s,a[30][30];
m行n列矩阵,请确定m,n: "); scanf("%d,%d",&m,&n);
if(m&n) c=m;
d=(c+1)/2;
for(i=1;i&=d;i++)
从外至内第d圈赋值
for(h=i;h&=m-i;h++)
// 一圈的左列从上至下递增
{ s++; a[h][v]=s;}
for(v=i;v&=n-i;v++)
// 一圈的下行从左至右递增
{ s++; a[h][v]=s;}
for(h=m+1-i;h&i;h--)
// 一圈的右列从下至上递增
{ s++; a[h][v]=s;
if(s==m*n) {h=i;}
for(v=n+1-i;v&i;v--)
// 一圈的上行从右至左递增
{ s++; a[h][v]=s;
if(s==m*n) {v=i;}
%d行%d列旋转矩阵为:\n",m,n);
for(i=1;i&=m;i++)
{ for(j=1;j&=n;j++)
// 按m行n列输出矩阵
printf("%4d",a[i][j]);
printf("\n");
3-7 猴子吃桃
有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了1个。第2天早上又将剩下的桃子吃掉一半，又多吃了1个。以后每天早上都吃了前一天剩下的一半后又多吃1个。到第10天早上想再吃时，见只剩下1个桃子了。
求第1天共摘了多少个桃子。
(1) 求解要点
第1天的桃子数是第2天桃子数加1后的2倍，第2天的桃子数是第3天桃子数加1后的2倍，…，一般地，第k天的桃子数是第k+1天桃子数加1后的2倍。设第k天的桃子数是t(k)，则有递推关系
t(k)=2*(t(k+1)+1) (k=1,2,…,9)
初始条件：t(10)=1
逆推求出t(1)，即为所求的第一天所摘桃子数。
(2) 程序设计
// 猴子吃桃程序 '
#include &stdio.h&
void main()
long t[1000];
// 确定初始条件
for(k=9;k&=1;k--)
// 逆推计算t(1)
t[k]=2*(t[k+1]+1);
第 1 天摘桃%ld个。\n",t[1]);
for(k=1;k&=9;k++)
{ printf("
第 %d 天面临%4ld个桃，",k,t[k]);
吃了%4ld+1=%4ld个，",t[k]/2,t[k]/2+1);
还剩%4ld个。\n",t[k]/2-1);
第10天早上还剩1个。");
3-8 拓广猴子吃桃
有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了m个。第2天早上又将剩下的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上想再吃时，见只剩下d个桃子了。
求第1天共摘了多少个桃子(m,n,d由键盘输入)？
解：递推关系
t(k)=2*(t(k+1)+m) (k=1,2,…,n-1)
初始条件：t(n)=d
逆推求出t(1)，即为所求的第一天所摘桃子数。
// 拓广猴子吃桃程序
#include &stdio.h&
void main()
{ int d,k,m,n;
long t[1000];
请确定正整数m,n,d: ");
scanf("%d,%d,%d",&m,&n,&d);
// 确定初始条件
for(k=n-1;k&=1;k--)
// 逆推计算t(1)
t[k]=2*(t[k+1]+m);
第 1 天摘桃%ld个。\n",t[1]);
for(k=1;k&=n-1;k++)
{ printf("
第 %d 天面临%4ld个桃，",k,t[k]);
吃了%4ld+%d=%4ld个，",t[k]/2,m,t[k]/2+1);
还剩%4ld个。\n",t[k]/2-m);
第%d天早上还剩%d个。",n,d);
3-9 据例3-1中求裴波那契数列的第40项与前40项之和的递推算法与迭代算法，写出完整的程序，并比较其运行结果。
(1) 应用递推求解
// 裴波那契数列递推程序
#include &stdio.h&
void main()
{ long s,f[50];
f[1]=1;f[2]=1;
s=f[1]+f[2];
// 数组元素与和变量赋初值
for(k=3;k&=40;k++)
{ f[k]=f[k-1]+f[k-2];
// 实施递推
// 实施求和
f数列第40项为: %ld \n",f[n]);
前40项之和为: %ld \n",s);
应用迭代求解
// 裴波那契数列迭代程序
#include&stdio.h&
void main()
{ long a,b,s;
a=1;b=1;s=a+b;
// 迭代变量a,b,s赋初值
while(k&=20)
// 控制迭代次数
// 推出a是f数列的第2k-1项
// 推出b是f数列的第2k项
// 推出s是f数列的前2k项之和
f数列的第40项为：%ld \n",b);
前40项之和为：%ld \n",s);
4-1 阶乘的递归求解
阶乘n!定义: n!=1(n=1)；n!=n*(n-1)! (n&1)
设计求n!的递归函数，调用该函数求
解： 定义n!的递归函数f(n),在求和的k(1——n)循环中实施求和
s+=(double)1/f(k);
程序设计：
#include &stdio.h&
long f(int n)
if(n==1) g=1;
else g=n*f(n-1);
return(g);
void main()
{ int k,n;
double s=1;
请输入n: ");scanf("%d",&n);
for(k=1;k&=n;k++)
s+=(double)1/f(k);
s=%f \n",s);
4-2 递归求解f数列
已知f数列定义：
建立f数列的递归函数，求f数列的第n项与前n项之和。
解：定义f数列的递归函数f(n),在求和的k(1——n)循环中实施求和 s+=f(k)。
程序设计：
#include &stdio.h&
long f(int n)
if(n==1 || n==2) g=1;
else g=f(n-1)+f(n-2);
return(g);
void main()
{ int k,n; long s=0;
请输入n: ");scanf("%d",&n);
for(k=1;k&=n;k++)
f(%d)=%ld \n",n,f(n));
s=%ld \n",s);
4-3 递归求解b数列
已知b数列定义：
建立b数列的递归函数，求b数列的第n项与前n项之和。
解：#include &stdio.h&
long b(int n)
if(n==1) g=1;
else if(n==2) g=2;
else g=3*b(n-1)-2*b(n-2);
return(g);
void main()
{ int k,n; long s=0;
请输入n: ");scanf("%d",&n);
for(k=1;k&=n;k++)
b(%d)=%ld \n",n,b(n));
s=%ld \n",s);
4-4 递归求解双递推摆动数列
已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数），试建立递归，求该数列的第n项与前n项的和。
// 摆动数列
#include &stdio.h&
int a(int n)
if(n==1) g=1;
else if(n%2==0) g=a(n/2)+1;
else g=a((n-1)/2)+a((n+1)/2);
return(g);
void main()
{ int k,n; long s=0;
请输入n: ");scanf("%d",&n);
for(k=1;k&=n;k++)
a(%d)=%d \n",n,a(n));
s=%ld \n",s);
4-5 应用递归设计输出杨辉三角。
// 杨辉三角递归设计
void c(int a[],int n)
if(n==0) a[1]=1;
else if(n==1)
{a[1]=1;a[2]=1;}
{c(a,n-1);
for(i=n;i&=2;i--)
a[i]=a[i]+a[i-1];
#include&stdio.h&
void main()
{ int i,j,k,n,a[100];
请输入杨辉三角的行数：");
scanf("%d",&n);
for(j=0;j&=n;j++)
for(k=1;k&=30-2*j;k++) printf(" ");
for(i=1;i&=j;i++)
printf("%4d",a[i]);
printf("%4d\n",1);
4-6 试把m×n顺转矩阵的递归设计转变为递推设计。
解： 对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。
设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。
程序设计：
// m×n数字旋转矩阵
#include &math.h&
#include &stdio.h&
void main()
{int i,j,c,d,h,v,m,n,s,a[30][30];
m行n列矩阵,请确定m,n: "); scanf("%d,%d",&m,&n);
if(m&n) c=m;
d=(c+1)/2;
for(i=1;i&=d;i++)
从外至内第d圈赋值
for(v=i;v&=n-i;v++)
{s++;a[h][v]=s;}
// d圈的首行从左至右赋值
for(h=i;h&=m-i;h++)
{s++;a[h][v]=s;}
// d圈的尾列从上至下赋值
for(v=n+1-i;v&=i+1;v--)
{ s++;a[h][v]=s;
// d圈的尾行从右至左赋值
if(s==m*n) {i=d;}
// 赋值完成即行退出
for(h=m+1-i;h&=i+1;h--)
{ s++;a[h][v]=s;
// d圈的首列从下至上赋值
if(s==m*n) {i=d;}
%d行%d列旋转矩阵为:\n",m,n);
for(i=1;i&=m;i++)
{ for(j=1;j&=n;j++)
// 按m行n列输出矩阵
printf("%4d",a[i][j]);
printf("\n");
4-7 试应用递归设计构造并输出任意指定逆转m×n矩阵。
解：在递归函数中，每圈4边按左列左列从上至下递增、下行从左至右递增、右列从下至上递增、上行从右至左递增给元素赋值。
程序设计：
// m×n逆转矩阵递归设计
#include &stdio.h&
int m,n,a[20][20]={0};
void main()
{ int h,v,b,s,d;
数阵为m行n列，请确定m,n：");
scanf("%d,%d",&m,&n);
if(m&n) s=n;
void t(int b,int s,int d);
// 递归函数说明
// 调用递归函数
%d×%d逆转矩阵: \n",m,n);
for(h=1;h&=m;h++)
{for(v=1;v&=n;v++)
printf(" %3d",a[h][v]);
printf("\n");
void t(int b,int s,int d)
// 定义递归函数
{ int j,h=b,v=b;
// 递归出口
for(j=1;j&=m+1-2*b;j++)
// 一圈的左列从上至下递增
{ a[h][v]=d;h++;d++;}
for(j=1;j&=n+1-2*b;j++)
// 一圈的下行从左至右递增
{ a[h][v]=d;v++;d++;}
for(j=1;j&=m+1-2*b;j++)
// 一圈的右列从下至上递增
{ a[h][v]=d;h--;d++;
for(j=1;j&=n+1-2*b;j++)
// 一圈的上行从右至左递增
{ a[h][v]=d;v--;d++;
// 另一递归出口
t(b+1,s-2,d);
// 调用内一圈递归函数
4-8 应用递归设计实现n个相同元素与另m个相同元素的所有排列。
解： 设置递归函数p(k)，1≤k≤m+n，元素a[k]取值为0或1。
当k=m+n时，作变量h统计“0”的个数。若h=m则打印输出一排列，并用s统计排列个数。然后回溯返回，继续。
当k&m+n时，还不足n+m个数,则调用p(k+1)探索下一个数。
主程序中调用p(1)。
// n个1与另m个0的排列
#include &stdio.h&
int m,n,r,a[30]; long s=0;
void main()
{ int p(int k);
printf(" input n,m: "); scanf("%d,%d",&n,&m);
%d个1与%d个0的排列:\n",n,m);
// 从第1个数开始
printf("\n s=%ld \n",s);
// 输出排列的个数
// 排列递归函数
#include &stdio.h&
int p(int k)
{ int h,i,j;
if(k&=m+n)
{ for(i=0;i&=1;i++)
// 探索第k个数赋值i
if(k==m+n)
// 若已到m+n个数则检测0的个数h
{ for(h=0,j=1;j&=n+m;j++)
if(a[j]==0) h++;
// 若0的个数为m个,输出一排列
{ s++; printf(" ");
for(j=1;j&=n+m;j++)
printf("%d",a[j]);
if(s%10==0) printf("\n");
// 若没到n+m个数,则调用p(k+1)探索下一个数
5-1 倒桥本分数式
把1,2,...,9这9个数字填入下式的9个方格中，数字不得重复,且要求1不得填在各分数的分母，且式中各分数的分子分母没有大于1的公因数，使下面的分数等式成立
这一填数分数等式共有多少个解?
解: 在桥本分数式回溯程序中修改
// 倒桥本分数式回溯实现
// 把1,2,...,9填入□□/□+□□/□=□□/□
#include &stdio.h&
void main()
{int g,i,k,u,t,a[10];
long m1,m2,m3;
i=1;a[1]=1;
for(k=i-1;k&=1;k--)
if(a[i]==a[k]) {g=0;}
// 两数相同,标记g=0
if(i==9 && g==1 && a[1]&a[4] && a[1]&1 && a[7]&1)
{m1=a[2]*10+a[3];
m2=a[5]*10+a[6];
m3=a[8]*10+a[9];
for(t=0,u=2;u&=9;u++)
{if(a[1]%u==0 && m1%u==0) t=1;
if(a[4]%u==0 && m2%u==0) t=1;
if(a[7]%u==0 && m3%u==0) t=1;
if(t==0 && m1*a[4]*a[7]+m2*a[1]*a[7]==m3*a[1]*a[4])
// 判断等式
%d/%ld+%d/%ld",m1,a[1],m2,a[4]);
printf("=%d/%ld
\n",m3,a[7]);
if(i&9 && g==1)
{i++;a[i]=1;}
// 不到9个数,往后继续
while(a[i]==9 && i&1) i--;
// 往前回溯
if(a[i]==9 && i==1)
else a[i]++;
// 至第1个数为9结束
5-2 两组均分
参加拔禾比赛的12个同学的体重如下：
48，43，57，64，50，52，18，34，39，56，16，61
为使比赛公平，要求参赛的两组每组6个人，且每组同学的体重之和相等。
请设计算法解决这 “两组均分”问题。
（1） 求解要点
一般地，对已知的2n(n从键盘输入)个整数，确定这些数能否分成2个组，每组n个数，且每组数据的和相等。
我们可采用回溯法逐步实施调整。
对于已有的存储在b数组的2n个数,求出总和s与其和的一半s1(若这2n个数的和s为奇数,显然无法分组)。把这2n个数分成二个组,每组n个数。为方便调整,设置数组a存储b数组的下标值，即a(i):1─2n。
考察b(1)所在的组,只要另从b(2)─b(2n)中选取n-1个数。即定下a(1)=1,其余的a(i)(i=2,…,n)在2─2n中取不重复的数。因组合与顺序无关,不妨设
2 ≤ a(2)&a(3)&...&a(n) ≤2n
从a(2)取2开始,以后a(i)从a(i-1)+1开始递增1取值,直至n+i为止。这样可避免重复。
当a(n)已取值,计算s=b(1)+b(a(2))+…+b(a(n)),对和s进行判别:
若s=s1,满足要求,实现平分。
若s≠s1,则a(n)继续增1再试。如果a(n)已增至2n,则回溯前一个a(n-1)增1再试。如果a(n-1)已增至2n-1,继续回溯。直至a(2)增至n+2时,结束。
二堆均分问题并不总有解。有解时,找到并输出所有解。没有解时,显示相关提示信息“无法实现平分”。
（2） 两组均分程序设计
// 两组均分程序设计
#define N 50
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
void main()
{int n,m,a[N],b[2*N],i,j,t;
long s1,s=0;
printf("把2n个整数分为和相等的两个组,每组n个数.\n");
t=time(0)%1000;srand(t);
随机数发生器初始化
printf(" input n :"); scanf("%d",&n);
for(s=0,i=1;i&=2*n;i++)
产生2n个不同的随机整数
{t=0;b[i]=rand()%(5*n)+10;
for(j=1;j&=i-1;j++)
if(b[i]==b[j])
if(t==1) {i--;}
// 出现相同数时，返回重新产生
s+=b[i]; printf("%d
if(s%2==0)
{printf("\n以上%d个整数总和为%d.\n",2*n,s);
printf("\n
和%ld为奇数,无法平分!\n",s);
a[1]=1;i=2;a[i]=2;
{for(s=0,j=1;j&=n;j++)
s+=b[a[j]];
// 满足均分条件时输出
{m++; printf("NO%d:
for(j=1;j&=n;j++)
printf("%d
",b[a[j]]);
{i++; a[i]=a[i-1]+1;}
while(a[i]==n+i) i--;
// 调整或回溯
if(i&1) a[i]++;
if(m&0) printf("共有以上%d种分法。",m);
printf(" 无法实现二堆均分. ");
5-3 指定低逐位整除数探求
试求出所有最高位为3的24位低逐位整除数（除个位数字为“0”外,其余各位数字均不得为“0”）。
// 最高位为3的n位右逐位整除
#include&stdio.h&
void main()
{ int i,j,n,r,t,a[100]; long s=0;
逐位整除n位，请确定n：");
scanf("%d",&n);
所求%d位最高位为3的右逐位整除数：\n",n);
for(j=1;j&=100;j++) a[j]=1;
t=0;a[1]=0;i=1;
while(a[1]&1)
{ if(t==0 && i&n) i++;
for(r=0,j=i;j&=1;j--)
// 检测i时是否整除i
{ r=r*10+a[j]; r=r%i; }
{ a[i]=a[i]+1;t=1;
// 余数r!=0时a[i]增1,t=1
while(a[i]&9 && i&1)
{ a[i]=1;i--;
a[i]=a[i]+1;
// 余数r=0时,t=0
if(t==0 && i==n)
{ if(a[n]==3)
{s++;printf("
%ld: ",s);
for(j=n;j&=1;j--)
printf("%d",a[j]);
printf("\n");
a[i]=a[i]+1;
最高位为3的%d位右逐位整除数共%ld个.",n,s);
未找到n位右逐位整除数.",n);
5-4 枚举求解8项素数和环，与回溯结果进行比较。
(1) 设计要点
为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。
环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数——中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。
为操作与判断方便，设置3个数组：
f数组统计8位数a中各个数字的频数。如f[3]=2，即a中有2个数字“3”。
g数组表示8位数a中每位数的数字。如g[4]=6，即a的从高位开始第4位数为数字“6”。
b数组标记整数x是否为素数。如b[13]=1，标识“1”表示13为素数，标识“0”为非素数。
枚举实施：
1） 注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。
2） 在8位数的a 循环中，对a实施8次求余分离出各个数字x，应用f[x]++统计数字x的频数，应用g[9-k]=x记录a的各位数字。
3） 设置k(1——8)判断循环：
若f[k]!=1 ，表明数字k出现重复或遗漏，返回。
若 b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。顺便说明，为判断方便，首项“1”先行赋值给g[9]，以与g[8]相邻，在k循环中一道进行判别。
4） 通过以上判断筛选的a，其各个数字即为所求的8项素数环的各项，打印输出。
(2) 枚举实现8项素数和环
// 8项素数和环枚举求解
#include&stdio.h&
#include&math.h&
void main()
{ int t,k,s,x,g[10],f[10],b[18];long a,y;
for(k=1;k&=15;k++) b[k]=0;
g[9]=1;s=0;
b[3]=b[5]=b[7]=b[11]=b[13]=1;
// 5个奇素数标记
8项素数和环：\n");
for(a=;a&=;a+=9)
// 步长为9枚举8位数
for(k=0;k&=9;k++) f[k]=0;
for(k=1;k&=8;k++)
{x=y%10;f[x]++;
分离a的8个数字,用f数组统计x的个数
用g数组记录a的第k位数字
for(k=1;k&=8;k++)
if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1;
有相同数字或相邻和非素，返回
%d: 1",s);
输出8项素数和环
for(k=2;k&=8;k++)
printf(",%d",g[k]);
printf("\n");
5-5 递归求解20项素数环
// 递归求解素数环问题
#include&stdio.h&
#include&math.h&
int n,a[2000],b[1000];long s=0;
void main()
{ int t,j,k;
int p(int k);
前n个正整数组成素数环，请输入整数n: ");
scanf("%d",&n);
for(k=1;k&=2*n;k++) b[k]=0;
for(k=3;k&=2*n;k+=2)
{for(t=0,j=3;j&=sqrt(k);j+=2)
if(k%j==0)
if(t==0) b[k]=1;
// 奇数k为素数的标记
a[1]=1;k=2;
前%d个正整数组成素数环，以上是其中3个。\n",n);
// 素数环递归函数p(k)
#include &stdio.h&
int p(int k)
{ int i,j,u;
{ for(i=2;i&=n;i++)
// 探索第k个数赋值i
for(u=0,j=1;j&=k-1;j++)
if(a[k]==a[j] || b[a[k]+a[k-1]]==0)
若出现重复数字
// 若第k数不可置i,则u=1
// 若第k数可置i,则检测是否到n个数
{ if(k==n && b[a[n]+a[1]]==1 && s&3) // 若已到n个数时打印出一个解
printf(" %ld:
for (j=2;j&=n;j++)
printf(",%d",a[j]);
printf("\n");
// 若没到m个数,则探索下一个数 p(k+1)
5-6 枚举探索6珠
所能覆盖的最大和s。
// 数码串珠探索
#include&stdio.h&
void main()
{int d,i,j,s,t,u,v,a[20],b[300];
for(s=31;s&=28;s--)
s=%2d： \n",s); v=0;
// v统计s时解的个数
a[0]=0;a[1]=1;a[6]=s;
for(a[2]=a[1]+1;a[2]&=s-4;a[2]++)
for(a[3]=a[2]+1;a[3]&=s-3;a[3]++)
for(a[4]=a[3]+1;a[4]&=s-2;a[4]++)
for(a[5]=a[4]+1;a[5]&=s-1;a[5]++)
{for(i=7;i&=11;i++)
a[i]=s+a[i-6];
for(t=0,i=0;i&=5;i++)
for(j=i+1;j&=i+5;j++)
{t++;b[t]=a[j]-a[i];}
// 除s外，产生30个部分和
for(d=1;d&=s-1;d++)
for(i=1;i&=30;i++)
if(b[i]==d)
// b有[1,s-1]中的一个数，u增1
{u+=1;i=30;}
if(u==s-1)
// u=s-1时为完全环覆盖
%2d",v,1);
for(i=1;i&=5;i++)
printf(",%2d",a[i+1]-a[i]);
if(v%2==0)
printf("\n");
5-7 枚举探索4阶德布鲁金环，并与德布鲁金环的回溯程序运行结果进行比较。
求解由16个0或1组成的环序列，形成的由每相连4个数字组成的16个二进制数恰好在环中都出现一次。
(1) 枚举设计要点
约定序列由0000开头，第5个数字与第16个数字显然都为1(否则会出现00000)。余下10个数字应用枚举探求。
设置一维a数组，由约定0000开头，即a(0)～a(3)均为0；a(4)=1,a(15)=1。其余10个数字a(5)～a(14)通过枚举探求。因为是环序列，a(16)～a(18)即为开头的0。
分析10个数字0、1组成的二进制数，高位最多2个0（否则出现重复），即循环的初值可定为n1=27。同时，高位不会超过4个1（否则出现11111超界），即循环的终值可定为n2=29+28+27+26。
对区间[n1,n2]中的每一个整数n(为不影响循环，赋值给b)，通过除以2取余转化为10个二进制数码。用变量i统计该二进制数中1的个数，若i≠6返回，确保16个数字中有8个1时转入下面的检验：计算m1,m2并通过比较，检验a(0)～a(18)中每4个相连数字组成的二进制数若有相同，显然不能满足题意要求，标记t=1退出。若所有由4个相连数字组成的16个二进制数没有相同的，满足德布鲁金环序列条件，作打印输出。
（2）4阶德布鲁金环序列枚举实现
#include &stdio.h&
void main()
int b,m,m1,m2,n,n1,n2,i,j,k,t,a[20];
n2=512+256+128+64;
// 确定枚举范围
for(n=n1;n&n2;n++)
{for(k=0;k&=18;k++) a[k]=0;
a[4]=1;a[15]=1;
for(i=0,k=14;k&=5;k--)
// 正整数n(即b)转化为二进制数
{a[k]=b%2; b=b/2;
// 确保8个1转入以下检验
for(t=0,k=0;k&=14;k++)
for(j=k+1;j&=15;j++)
// 计算并检验16个二进制数是否相同
{m1=a[k]*8+a[k+1]*4+a[k+2]*2+a[k+3];
m2=a[j]*8+a[j+1]*4+a[j+2]*2+a[j+3];
if(m1==m2)
// 若16个二进制数没有相同，输出结果
No(%2d): ",m);
for(j=0;j&=15;j++)
// 依次输出16个二进制数
printf("%1d",a[j]);
if(m%2==0) printf(" \n");
5-8 回溯实现组合C(n,m)
对指定的正整数m,n(约定1＜m≤n), 回溯实现从n个不同元素中取m个（约定1＜m＜n）的组合C(n,m)。
（1）回溯算法设计
注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。
设置一维数组a，a(i)(i=1,2,…,m)在1～n中取值。
首先从a(1)=1开始取值。以后各项从前一项增1取值：a[i]=a[i-1]+1。
若a(i)=n+i-m，则返回前一个数组元素a(i-1)。直到i=0，已无法返回，意味着已全部试毕，求解结束。
问题的解空间是由数字1～n组成的m位整数组，其约束条件是没有相同数字。
按以上所描述的回溯的参量：m,n(m≤n)
元素初值：a[1]=1，数组元素初值取1。
取值点：a[i]=a[i-1]+1，以保持升序。
回溯点：a[i]=n+i-m，各数组元素取值至n+i-m后回溯。
（2）回溯实现C(n,m)的C程序实现
// 实现组合C(n,m)
#include &stdio.h&
void main()
i,j,n,m,a[100];
printf(" input n
(n&10):"); scanf("%d",&n);
printf(" input m(1&m&=n):"); scanf("%d",&m);
i=1;a[i]=1;
for(j=1;j&=m;j++)
printf("%d",a[j]);
// 输出一个排列
if(s%10==0) printf("\n");
{i++;a[i]=a[i-1]+1;}
while(a[i]==n+i-m) i--;
// 回溯到前一个元素
if(i&0) a[i]++;
printf("\n 总数为:%ld \n",s);
// 输出C(n,m)的值
5-9 回溯实现复杂排列
应用回溯法探索从n个不同元素中取m（约定1＜m≤n）个元素与另外n-m个相同元素组成的复杂排列。
（1）算法设计要点
引入变量k来控制0的个数，当k＜n-m时，a[i]=0，元素需从0开始取值；否则，0的个数已达n-m个，a[i]=1，即从1开始取值。这样处理，使0的个数不超过n-m，减少一些无效操作，提高了回溯效率。
按以上所描述的回溯的参量：n,m(m≤n)
元素初值：a[1]=0，数组元素取初值0。
取值点：当k＜n-m时，a[i]=0，需从0开始取值；否则，a[i]=1，即从1开始取值。
回溯点：a[i]=n，各元素取值至n时回溯。
约束条件1：a[k]!=0 && a[i]=a[k] || a[i]*a[k]＞0 && fabs(a[i]-a[k])=i-k, (其中i＞k)，排除同一列或同对角线上出现2个皇后。
约束条件2：i=n && h=n-m && b[1-n][1-n]=1, 当取值达n个，其中n-m个零，且棋盘全控时输出一个解。
（2）复杂排列回溯优化设计
#include &stdio.h&
#define N 30
void main()
i,j,h,k,n,m,t,a[N];
printf(" input n
(n&10):"); scanf("%d",&n);
printf(" input m(1&m&=n):"); scanf("%d",&m);
i=1;a[i]=0; k=1;
for(j=1;j&i;j++)
if(a[j] && a[j]==a[i]) {t=0;}
// 非零元素相同，则返回
if(t && k==n-m && i==n)
// 已取n 个值且0的个数为n-m时输出解
for(j=1;j&=n;j++) printf("%d",a[j]);
if(s%10==0) printf("\n");
if(t && (k&n-m || i&n))
if(k&n-m){a[i]=0; k++;}
// 0的个数增加1
else a[i]=1;
// 若0的个数已达到n-m，则不再取0了
while(a[i]==n) i--;
// 调整或回溯或终止
{if(a[i]==0) k--;
// 改变取值为0的元素值前先把0的个数k减1
printf("\n s=%ld\n",s);
5-10 8对夫妇特殊的拍照
一对夫妇邀请了7对夫妇朋友来家餐聚，东道主夫妇编为0号，其他各对按先后分别编为1，2，…，7号。
餐聚后拍照，摄影师要求这8对夫妇男左女右站在一排，东道主夫妇相邻排位在横排的正中央，其他各对排位，1号夫妇中间安排1个人,2号夫妇中间安排2个人,依此类推。
共有多少种拍照排队方式？
在n组每组2个相同元素（相当于n对情侣），a数组从0取到2n-1不重复，对n同余的两个数为一对编号：余数为0的为0号（即东道主），余数为1的为1号，…，余数为n-1的为n-1号。
例如，n=4，数组元素为0与4，对4同余，为一对“0”； 1与5对4同余，为一对“1”；一般地， i与4+i对4同余，为一对i,(i=0,1,2,3)。
返回条件修改为（当j&i时）：
a(j)=a(i) or a(j)%n=a(i)%n and (a(j)&a(i) or a(j)+1!=i-j)
其中a(j)=a(i)，为使a数组的2n个元素不重复取值；
a(j)%n=a(i)%n and a(j)&a(i)，避免同一对取余相同的数左边大于右边，导致重复；
a(j)%n=a(i)%n and a(j)+1!=i-j，避免同一对数位置相差不满足题意相间要求。
例如，a(j)=0时，此时a(i)=n，为0号情侣，位置应相差1（即中间没有人），即i-j=1。
a(j)=1时，此时a(i)=n+1，为1号情侣，位置应相差2（即中间有1人），即i-j=2。
这些都应满足条件a(j)+1=i-j。如果a(j)+1!=i-j，不满足要求，返回。
设m=2n，若满足条件(g&0 and i=m and a(1)%n&a(m)%n)且a(n)=0(即东道主在正中央)，为一个拍照排列，用s统计解的个数。
// 8对夫妇拍照
#include &stdio.h&
#include &math.h&
void main()
i,j,g,n,m,s,a[20];
printf(" input n
(2&n): ");
scanf("%d",&n);
i=1;a[i]=0;s=0;
for(j=1;j&i;j++)
if(a[j]==a[i] || a[j]%n==a[i]%n && (a[j]&a[i] || a[j]+1!=i-j))
// 出现相同元素或同余小在后时返回
if(g && i==m && a[1]%n&a[m]%n)
// 满足统计解的个数条件
{if(a[n]==0)
// 满足输出解的条件
for(j=1;j&=m;j++)
printf("%d",a[j]%n);
// 输出一个排列
if(g && i&m)
{i++;a[i]=0;}
while(a[i]==m-1) i--;
// 回溯到前一个元素
if(i&0) a[i]++;
printf("\n 共有解s=%d个。\n",s);
6-1 n个矩阵连乘问题
设矩阵A为p行q列，矩阵B为q行r列，求矩阵乘积AB共需做pqr次乘法。
试求n（n&2）个矩阵 的乘积 的最少乘法次数。其中n与 的行、列数 均从键盘输入。
解：注意 是 的列数，也是 的行数，这样才能确保 与 能相乘。
多个矩阵相乘，满足乘运算结合律。
例如，求 ，先求前两个矩阵的乘积 ，还是先求后两个的乘积 ，都是可以的，但两者的乘法次数不一定相等，我们要求最少乘法次数。
设m(i,j)是求乘积 的最少乘法次数，则有递推关系
(i≤k≤j,i&j)
初始（边界）条件：m(i,j)=0 (i=j)
最优值为m(1,n).
程序设计：
为递推方便，设置d=i-j。显然，1≤d≤n-1。
// 矩阵连乘
#include &stdio.h&
void main()
{int d,n,i,j,k,t,r[100],m[100][100];
printf(" 请输入矩阵的个数 n :"); scanf("%d",&n);
printf(" 请输入第1个矩阵的行数 :"); scanf("%d",&r[1]);
for(i=1;i&=n-1;i++)
{printf(" 请输入第%d个矩阵的列数，也是第%d个矩阵的行数 :",i,i+1);
scanf("%d",&r[i+1]);
printf(" 请输入第%d个矩阵的列数 :",n); scanf("%d",&r[n+1]);
for(i=1;i&=n;i++)
m[i][i]=0;
for(d=1;d&=n-1;d++)
for(i=1;i&=n-d+1;i++)
m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1];
for(k=i+1;k&j;k++)
{t=m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1];
if(t&m[i][j]) m[i][j]=t;
%d个矩阵连乘的乘法次数的最小值为：%d \n",n,m[1][n]);
6-2 应用顺推实现动态规划求解点数值三角形的最优路径
在一个n行的点数值三角形中，寻找从顶点开始每一步可沿左斜（L）或右斜（R）向下至底的一条路径，使该路径所经过的点的数值和最小。
应用顺推实现动态规划求解从项到底的最小路程。
（1）建立递推关系
设点数值三角形的数值存储在二维数组a(n,n),数组b(i,j)为从顶点（1,1）到点(i,j)的最小数值和。b(i,j)与stm(i,j)(i=2,3,…,n)的值由b数组的第i-1行的第j-1个元素与第j个元素值的大小比较决定，即有递推关系：
b(i,j)=a(i,j)+b(i-1,j); （b(i-1,j)&b(i-1,j-1)）
b(i,j)=a(i,j)+b(i-1,j-1); （b(i-1,j)≥b(i-1,j-1)）
其中i=2,3,…,n
比较b(n,1),b(n,2),…,b(n,n)所得最小值min即为所求的最小路径。
边界条件：
b(1,1)=a(1,1);
b(i,1)=a(i,1)+b(i-1,1);
b(i,i)=a(i,i)+b(i-1,i-1); i=2,…,n。
（2）顺推计算最优值
b[1][1]=a[1][1];
for(i=2;i&=n;i++)
{ b[i][1]=a[i][1]+b[i-1][1];
b[i][i]=a[i][i]+b[i-1][i-1];
for(i=3;i&=n;i++) // 顺推得b[n][j]
for(j=2;j&=i-1;j++)
if (b[i-1][j]&b[i-1][j-1])
b[i][j]=a[i][j]+b[i-1][j];
b[i][j]=a[i][j]+b[i-1][j-1];
min=10000;
for(j=1;j&=n,j++) // 比较得最短路程
if(b[n][j]&min)
{ min=b[n][j];m=j;}
printf("%d",min);
6-3 应用顺推实现动态规划求解n行m列边数值矩阵最大的路程
已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。
动态规划算法设计：
设矩阵的行数n，列数m，每点为(i, j)，i=1,2,…,n；j=1,2,…,m。显然，该边数值矩阵每行有m-1条横向数值边，每列有n-1条纵向数值边。
从点(i,j)水平向右的边长记为r(i,j)(j&m)，点(i,j)向下的边长记为d(i,j)(i&n)。
（1）建立递推关系
设a(i,j)为左上角顶点(1,1)到点（i,j）的最大路程。
a(i,j)的值由a(i-1,j)+d(i,j)与a(i,j-1)+r(i,j)比较，取其较大者得到，即有递推关系：
a(i,j)=max(a(i-1,j)+d(i-1,j),a(i,j-1)+r(i,j-1))
其中i=2,…,n；j=2,…,m。
注意到左边纵列与上边横行只有惟一出口，因而有边界条件：
a(i,1)=a(i-1,1)+d(i-1,1); i=2,…,n
a(1,j)=a(1,j-1)+r(1,j-1); j=2,…,m
（2）逆推计算最优值
a[1][1]=0;
for(i=2;i&=n;i++)
a[i][1]=a[i-1][1]+d[i-1][1]; // 左边纵列初始化
for(j=2;j&=m;j++)
a[1][j]=a[1][j-1]+r[1][j-1]; // 上边横行初始化
for(i=2;i&=n;i++) // 顺推求解a(i,j)
for(j=2;j&=m;j++)
if(a[i-1][j]+d[i-1][j]&a[i][j-1]+r[i][j-1])
a[i][j]=a[i-1][j]+d[i-1][j];
a[i][j]=a[i][j-1]+r[i][j-1];
printf("%d",a[n][m]);
所求左上角顶点到右下角顶点的最大路程即最优值为a(n,m)。
6-4 求解边数值三角形的最短路径
已知边数值三角形每两点间距离如图7-4所示，每一个点可向左或向右两个去向，求三角形顶点到底边的最短路径。
图7-4 三角形边数值数据
1) 算法设计
设边数值三角形为n行(不包含作为边终止点的三角形底边)，每点为(i，j)，i=1,2,……，n；j=1,2,……，i.从点(i,j)向左的边长记为l(i,j)，点(i,j)向右的边长记为r(i,j)。记a(i,j)为点（i,j）到底边的最短路程。显然
a(i,j)=min(a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j))
st(i,j)={‘l’,’r’}
应用逆推求解，所求的顶点A到底边的最短路程为a(1,1).
2) 边数值三角形最短路径搜索C程序设计
// 边数值三角形最短路径搜索
#include "math.h"
#include &stdio.h&
void main()
{ int n,i,j,t,s;
int a[50][50],l[50][50],r[50][50];char st[50][50];
t=time()%1000;srand(t);
随机数发生器初始化
printf("请输入数字三角形的行数n:");
scanf("%d",&n);
for(i=1;i&n;i++) j=rand();
// 产生并输出数值边三角形
for(j=1;j&=33;j++) printf(" ");printf("
for(i=1;i&=n;i++)
{for(j=1;j&=37-4*i;j++) printf(" ");
for(j=1;j&=i;j++) printf("
"); printf("\n\n");
for(j=1;j&=36-4*i;j++) printf(" ");
for(j=1;j&=i;j++)
{l[i][j]=rand()/1000+1;printf("%4d",l[i][j]);
r[i][j]=rand()/1000+1;printf("%4d",r[i][j]);}
printf("\n");}
for(j=1;j&=37-4*(n+1);j++) printf(" ");
for(j=1;j&=n+1;j++) printf("
printf("底边\n\n");
for(i=n;i&=1;i--)
// 逆推求取最短路径
{for(j=1;j&=i;j++)
if(a[i+1][j]+l[i][j]&a[i+1][j+1]+r[i][j])
{a[i][j]=a[i+1][j]+l[i][j];st[i][j]='l';}
{a[i][j]=a[i+1][j+1]+r[i][j];st[i][j]='r';}
printf("\n 最短路程为：%d",a[1][1]);
printf("\n 最短路径为：顶点A ");
for(j=1,i=1;i&=n;i++)
if(st[i][j]=='l')
printf("L-%d-",l[i][j]);
{printf("R-%d-",r[i][j]);j++;}
printf("底边。");
6-5 求解点数值矩阵最小路径
随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。
1) 算法设计
应用动态规划，即从右下角逐行反推至左上角。确定n,m后，随机产生的整数二维数组a(n,m)作矩阵输出，同时赋给部分和数组b(n,m)。这里数组b(i,j)为点(i,j)到右下角的最小数值和，stm(i,j)是点(i,j)向右（R）或向下（D）或向右下（O）的路标字符数组。
注意到最后一行与最后一列各数只有一个出口,于是由b(n,m)开始向左逐个推出同行的b(n,j),(j=m-1,...,2,1);向上逐个推出同列的b(i,m),(i=n-1,...,2,1)。
b(i,j)与stc(i,j)(i=n-1,...,2,1,j=m-1,...,2,1))的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定:
首先,作赋值 b(i,j)=yb+b(i+ 1, j + 1): stc(i, j) = "O".(其中变量yb为原b(i,j)的值)。
然后,求 b(i+1,j) 与 b(i,j+1) 的最小值 min。
如果 b(i+1,j+1)&min ,说明前面为b(i,j)赋值不对,作修改:
b(i,j)=yb+min
若min 为 b(i+1,j),则 stc(i,j)="D",否则 stc(i,j)="R"
这样反推所得b(1,1)即为所求的最小路径数字和。
为了打印最小路径,利用c数组从上而下操作:先打印a(1,1),i=1,j=1.
若 stc(i,j)="R" 则j增1,即j=j+1,然后打印 "-R-"与右边整数a(i,j);
若 stc(i,j)="D" 则i增1,即i=i+1,然后打印 "-D-"与下面整数a(i,j);
若 stc(i,j)="O" 则i,j均增1,即i=i+1,j=j+1,然后打印 "-O-"与斜向右下整数a(i,j);
依此类推,直至打印到终点a(n,m)。
6-6 西瓜分堆
已知的n个西瓜的重量分别为整数，请把这堆西瓜分成两堆，每堆的个数不一定相等，使两堆西瓜重量之差为最小。
(1） 设计要点
两组数据之和不一定相等，不妨把较少的一堆称为第1堆。设n个整数b(i)之和为s，则第1堆数据之和s1≤[s/2]，这里[x]为x的取整。
问题要求在满足s1≤[s/2]前提下求s1最大值maxc，这样两堆数据和之差的最小值为mind=s-2*maxc。
为了求s1的最大值，应用动态规划设计，按分每一个瓜为一个阶段，共分为n个阶段。每一个阶段都面临两个决策：选与不选该瓜到第1组。
1） 建立递推关系
设m(i,j)为第1堆距离c1=[s/2]还差重量为j，可取瓜编号范围为：i,i+1,…,n的最大装载重量值。则
当0≤j&b(i)时，西瓜i号不可能装入。m(i,j)与m(i+1, j)相同。
而当j≥b(i)时，有两种选择：
不装入西瓜i，这时最大重量值为m(i+1, j)；
装入西瓜i，这时已增加重量b(i)，剩余重量为j-b(i)，可以选择西瓜i+1,…,n来装，最大载重量值为m(i+1,j-b(i))+b(i)。我们期望的最大载重量值是两者中的最大者。于是有递推关系
以上j与b(i)均为正整数，i=1,2,…,n,
所求最优值m(1,c1)即为s1的最大值maxc。因而得两组数据和之差的最小值为mind=s-2maxc=s-2m(1,c1)。
2） 递推计算最优值
for(j=0;j&b(n);j++) m(n,j)=0;
for(j=b(n);j&=c1;j++) m(n,j)=b(n); // 首先计算m(n,j)
for(i=n-1;i&=1;i--) // 逆推计算m(i,j)
for(j=0;j&=c1;j++)
if(j&=b(i) && m(i+1,j)&m(i+1,j-b(i))+b(i))
m(i,j)=m(i+1,j-b(i))+b(i);
m(i,j)=m(i+1,j);
printf("%d",m(1,c1));
3） 构造最优解
构造最优解即给出所得最优值时的分瓜方案。
if(m(i,cb)&m(i+1,cb)) （其中cb为当前的剩余量，i=1,2, n-1）
第1堆分b(i);
else 不分b(i);
if(m(1,c1)-sb=b(n)) 则第1堆分b(n)。
（2）求解两组数据和之差的最小值程序设计
// 求解两组数据和之差的最小值
#include &stdio.h&
#define N 40
void main()
{int n,c1,i,j,s,t,cb,sb,b[N],m[N][10*N];
printf(" input n: "); scanf("%d",&n);
for(i=1;i&=n;i++)
输入n个西瓜重量整数
请输入第%d个整数：",i);
scanf("%d",&b[i]); s+=b[i];
各个西瓜重量：");
for(i=1;i&=n;i++)
%d",b[i]);
printf("\n 总重量s=%d \n",s);
for(j=0;j&b[n];j++)
m[n][j]=0;
for(j=b[n];j&=c1;j++)
m[n][j]=b[n];
首先计算m(n,j)
for(i=n-1;i&=1;i--)
逆推计算m(i,j)
for(j=0;j&=c1;j++)
if(j&=b[i]
&& m[i+1][j]&m[i+1][j-b[i]]+b[i])
m[i][j]=m[i+1][j-b[i]]+b[i];
m[i][j]=m[i+1][j];
// 得最优值m(1,c1)
两堆之差最小值为：%d \n",s-2*m[1][c1]);
第1堆: ");
cb=m[1][c1];
for(sb=0,i=1;i&=n-1;i++)
构造最优解，输出第1堆的西瓜
if(m[i][cb]&m[i+1][cb])
{cb-=b[i];sb+=b[i];
printf(" %3d",b[i]);
// b(i)分后赋0,为输出第2堆作准备
if(m[1][c1]-sb==b[n])
{printf(" %3d",b[n]);
sb+=b[n]; b[n]=0;
(%d)\n",sb);
第2堆: ");
for(sb=0,i=1;i&=n;i++)
输出第2堆西瓜
if(b[i]&0)
{sb+=b[i];
printf(" %3d",b[i]);
(%d)\n",sb);
6-7 应用递推实现动态规划求解序列的最小子段和
应用递推实现动态规划求解：给定n个整数（可能为负整数）组成的序列 ，求该序列形如 段和的最小值。
递推实现动态规划求解：
1） 动态规划算法设计
设q[j]为序列前j项之和的最小值，即
由q[j]的定义,得q[j]的递推关系:
初始条件：
Q[0]=0 (没有项时，其值自然为0)。
（2） 动态规划程序实现
// 动态规划求最小子段和
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
void main()
{ int i,j,k,t,n,s,smin,q[1000],a[1000];
t=time(0)%1000;srand(t);
随机数发生器初始化
序列中n个正负项,请确定n:");
scanf("%d",&n);
序列的%d个整数为：\n
for(i=1;i&=n;i++)
{t=rand()%(4*n)+10;
// 随机产生n个整数
if(t%2==1) a[i]=-1*(t-1)/2;
// 把奇数变为负数，大小减半
else a[i]=t/2;
// 把偶数大小减半
printf("%d,",a[i]);
smin=1000;q[0]=0;
for(j=1;j&=n;j++)
{if(q[j-1]&=0) q[j]=a[j];
else q[j]=q[j-1]+a[j];
if(q[j]&smin)
//比较得最小值
{smin=q[j];k=j;}
printf("\n
最小子段和为：%ld\n",smin);
for(s=0,i=k;i&=1;i--)
// 反推最小和子段的首标i
{ s+=a[i]; if(s==smin) }
最小子段从序列的第%d项到第%d项。\n",i,k);
6-8 应用递归实现动态规划求解序列的最小子段和
应用递归实现动态规划求解：给定n个整数（可能为负整数）组成的序列 ，求该序列形如 段和的最小值。
递归实现动态规划求解：
1） 动态规划算法设计
设q(j)为序列前j项之和的最小值，即
由q(j)的定义,得q(j)的递推关系:
初始条件：
q(0)=0 (没有项时，其值自然为0)。
（2） 动态规划程序实现
// 动态规划(递归)求最小子段和
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
int j,a[1000];
void main()
{ int i,k,n,t,s,
int q(int j);
t=time(0)%1000;srand(t);
随机数发生器初始化
序列中n个正负项,请确定n:");
scanf("%d",&n);
序列的%d个整数为：\n
for(i=1;i&=n;i++)
{t=rand()%(4*n)+10;
// 随机产生n个整数
if(t%2==1) a[i]=-1*(t-1)/2;
// 把奇数变为负数，大小减半
else a[i]=t/2;
// 把偶数大小减半
printf("%d,",a[i]);
smin=1000;
for(j=1;j&=n;j++)
if(q(j)&smin)
// 调用递归函数,比较得最小值
{smin=q(j);k=j;}
printf("\n
最小子段和为：%ld\n",smin);
for(s=0,i=k;i&=1;i--)
// 反推最小和子段的首标i
{ s+=a[i];
if(s==smin) }
最小子段从序列的第%d项到第%d项。\n",i,k);
int q(int j)
// 定义递归函数q(j)
if(j==0) f=0;
{ if(q(j-1)&=0) f=a[j];
else f=q(j-1)+a[j];
6-9 插入加号求最小值
在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小。
1） 动态规划求解
设f(i,k)表示在前i位数中插入k个加号所得和的最小值，a(i, j)表示从第i个数字到第j个数字所组成的j-i+1(i≤j)位整数值。
为了求取f(i,k)，考察数字串的前i个数字，设前j（k≤j&i）个数字中已插入k-1个加号的基础上，在第j个数字后插入第k个乘号，显然此时的最小和为f(j,k-1)+a(j+1,i)。于是可以得递推关系式：
f(i,k)=min(f(j,k-1)+a(j+1,i)) （k≤j&i）
前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得边界值为：
f(j,0)=a(1,j) (1≤j≤i)
为简单计，在程序设计中省略a数组，用变量d替代。
2） 程序设计
// 在一个数字串中插入r个+号，使和最小
#include &stdio.h&
#include &string.h&
void main()
{ char sr[16];
int n,i,j,k,u,r,b[16],t[16],c[16][16];
f[17][17],d;
printf("请输入整数："); scanf("%s",sr);
n=strlen(sr);
printf("请输入插入的+号个数r：");
scanf("%d",&r);
输入的整数位数不够或r太大！ ");
printf("在整数%s中插入%d个+号，使和最小：\n",sr,r);
for(d=0,j=0;j&=n-1;j++)
b[j]=sr[j]-48;
// 把输入的数串逐位转换到b数组
for(i=1;i&=n;i++)
for(j=1;j&=r;j++)
f[i][j]=1e16;
for(d=0,j=1;j&=n;j++)
{d=d*10+b[j-1];
// 把b数组的一个字符转化为数值
f[j][0]=d;
// f[j][0]赋初始值
for(k=1;k&=r;k++)
for(i=k+1;i&=n;i++)
for(j=k;j&i;j++)
{for(d=0,u=j+1;u&=i;u++)
d=d*10+b[u-1];
if(f[i][k]&f[j][k-1]+d)
// 递推求取f[i][k]
{f[i][k]=f[j][k-1]+d;
c[i][k]=j;
t[r]=c[n][r];
for(k=r-1;k&=1;k--)
t[k]=c[t[k+1]][k];
// 逆推出第k个+号的位置t[k]
t[0]=0;t[r+1]=n;
for(k=1;k&=r+1;k++)
{for(u=t[k-1]+1;u&=t[k];u++)
printf("%c",sr[u-1]);
// 输出最优解
printf("+");
printf("=%.0f\n ",f[n][r]);
// 输出最优值
6-10 根据例6-1求解整币兑零不同的兑换种数的递推算法与例6-2 求解整币兑零的最少零币个数的动态规划算法，写出完整程序。
求解整币兑零不同的兑换种数程序设计
// 整币兑零递推求解
#include&stdio.h&
void main()
{ int p,i,j,m,n,k;static int t[12];
long b,s; static long a[12][1001];
printf("请输入整币值n(单位数):");
// 输入处理数据
scanf("%d",&n);
printf("请输入零币种数m:");
scanf("%d",&m);
printf("(从小至大依次输入每种零币值)\n");
for(i=1;i&=m;i++)
{ printf("第%d种零币值(单位数):",i);
scanf("%d",&t[i]);
for(j=0;j&=n;j++)
// 确定初始条件
if(j%t[1]==0) a[1][j]=1;
else a[1][j]=0;
for(s=a[1][n],i=2;i&=m;i++)
// 递推计算a(2,n),a(3,n),...
{ for(j=t[i];j&=n;j++)
{ p=j-t[i];b=0;
for(k=1;k&=i;k++) b+=a[k][p];
a[i][j]=b;
s+=a[i][n];
// 累加a(1,n),a(2,n),...
printf("整币兑零种数为:%ld\n",s);
// 输出兑零种数
求解整币兑零最少零币个数程序设计
// 整币兑零,最少零币个数动态规划求解
#include&stdio.h&
void main()
{ int i,j,m,n;
static int t[12],g[20][1001];
请输入整币值(单位数):");
// 输入处理数据
scanf("%d",&n);
请输入零币种数:");
scanf("%d",&m);
(从小至大依次输入每种零币值)\n");
for(i=1;i&=m;i++)
{ printf("
第%d种零币值(单位数):",i);
scanf("%d",&t[i]);
for(j=1;j&=n;j++)
if(j%t[1]!=0) g[1][j]=0;
else g[1][j]=j/t[1];
for(i=2;i&=m;i++)
for(j=1;j&=n;j++)
{ if(j&t[i] || j&t[i] && g[i][j-t[i]]==0)
g[i][j]=g[i-1][j];
g[i][j]=g[i][j-t[i]]+1;
最少零币个数为:%d\n",g[m][n]);
// 输出最少零币个数
7-1 删除数字求最小值
给定一个高精度正整数a, 去掉其中s个数字后按原左右次序将组成一个新的正整数。对给定的a,s寻找一种方案,使得剩下的数字组成的新数最小。
解：应用贪心算法设计求解
（1） 设计要点
操作对象为n位高精度数，存储在数组a中。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部降序或相等，则删除左边的大数字。
当k&1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n-k个数字即可（相当于删除了若干个最右边的数字）。
贪心算法程序设计
// 贪心删数字达最小
#include&stdio.h&
void main()
{ int i,j,k,m,n,x,a[200];
char b[200];
请输入整数：");
scanf("%s",b);
以字符串方式输入高精度整数
for(n=0,i=0;b[i]!='\0';i++)
{n++;a[i]=b[i]-48;}
删除数字个数:
");scanf("%d",&k);
以上%d位整数中删除%d个数字分别为: ",n,k);
i=0;m=0;x=0;
while(k&x && m==0)
if(a[i-1]&a[i])
// 出现递减, 删除左边的数字
{ printf("%d, ",a[i-1]);
for(j=i-1;j&=n-x-2;j++)// 删除一数字后，后面的数字前移
a[j]=a[j+1];
// x统计删除数字的个数
// 从头开始查递增区间
if(i==n-x-1) m=1;
// 已无递减区间,m=1脱离循环
删除后所得最小数: ");
for(i=1;i&=n-k;i++)
// 打印剩下的左边n-k个数字
printf("%d",a[i-1]);
printf("\n");
7-2 枚举求解埃及分数式
本章应用贪心算法构造了埃及分数式：3/11=1/5+1/15+1/165，试用枚举法求解分数3/11的所有3项埃及分数式，约定各项分母不超过200。
解：（1） 设计要点
设指定的分数m/d的三个埃及分数的分母为a,b,c (a&b&c)，最大分母不超过z，通过三重循环实施枚举。
确定a循环的起始值a1与终止值a2为:
(即把b,c全放大为z)
(即把b,c全缩减为a)
b循环起始取a+1,终止取z-1.
c循环起始取b+1,终止取z.
对于三重循环的每一组a,b,c,计算x=mabc,y=d(ab+bc+ca).
如果x=y 且 b,c不等于d，即满足分解为三个埃及分数的条件,打印输出一个分解式。然后退出内循环,继续寻求。
（2）构建指定分数的3个埃及分数式
// 构建三个埃及分数之和
#include &stdio.h&
void main()
{int a1,a2,a,b,c,d,m,n,z; double x,y;
确定分数m/d,请输入m,d: ");
scanf("%d,%d",&m,&d);
请确定分母的上界：");
scanf("%d",&z);
把分数%d/%d分解为三个埃及分数之和: \n",m,d);
(分母不得为%d,最大分母不超过%d) \n",d,z);
a1=d*z/(m*z-2*d); a2=d*3/m+1;
for(a=a1;a&=a2;a++)
for(b=a+1;b&=z-1;b++)
for(c=b+1;c&=z;c++)
{x=m*a*b*c;
// 计算x,y值
y=d*(a*b+b*c+c*a);
if(x==y && b!=d && c!=d)
输出分解式
%d/%d=1/%d",n,m,d,a);
printf("+1/%d+1/%d \n",b,c);
共上述%d个分解式.\n",n);
7-3 币种统计
单位给每个职工发工资（约定精确到元），为了保证不至临时兑换零钱，且使每个职工取款的张数最少，请在取工资前统计所有职工所需的各种票面（约定为100,50,20,10,5,2,1元共7种）的张数，并验证币种统计是否正确。
(1) 算法设计
各职工的工资额依次从键盘输入，同时用su统计工资总额。
为了确保各职工所得款的张数最少，应用“贪心”策略，优先取大面值币种，即首先付100元币；小于100元时，优先付50元币；依此类推。
设置b数组，存储7种票面的值，即b[1]=100,b[2]=50,…,b[7]=1。
设置s数组，存储对应票面的张数，即s[1]为100元的张数，…，s[7]为1元的张数。
最后验证：各种票面的总额su1是否等于su？ 若相等，验证正确。
（2） 程序实现
// 币种统计
#include&stdio.h&
void main()
{ int i,j,m,n, long su1,su=0;
int s[8]={0,0,0,0,0,0,0,0};
int b[8]={0,100,50,20,10,5,2,1};
请输入人数：");
scanf("%d",&n);
请依次输入各职工的工资：\n");
for(i=1;i&=n;i++)
{ printf("
输入第%d个职工工资：",i);
scanf("%d",&gz);
for(j=1;j&=7;j++)
{ m=gz/b[j];
s[j]=s[j]+m;
gz=gz-m*b[j];
单位工资总额为: %ld \n",su);
各面值币的统计结果:
for(j=1;j&=7;j++)
{ printf(" %3d---%3d \n",b[j],s[j]);
su1=su1+b[j]*s[j];
if(su==su1) printf("
经检验统计无误！\n");
7-4 只显示两端的取数游戏
A与B玩取数游戏：随机产生的2n个整数排成一排，但只显示排在两端的数。两人轮流从显示的两端数中取一个数，取走一个数后即显示该端数，以便另一人再取，直到取完。
胜负评判：所取数之和大者为胜。
A的取数策略：“取两端数中的较大数”这一贪心策略。
B的取数策略：当两端数相差较大时，取大数；当两端数相差为1时，随意选取。
试模拟A与B取数游戏进程，2n个整数随机产生。
（1） 算法要点
设置k循环（k=1——2n），当k%2=1时A取数，k%2=0时B取数，体现了A先取，A，B轮留取数。
每次显示排两端整数为d[k]与d[2*n]，通过比较其中较大者t为所取数，并分别加入A的得分sa。B的取数从键盘输入，所取数t加入B的得分sb。
特别地，当A、B所取数t=d[2*n]，则前面的数均需后移一位：
d[j]=d[j-1]; （j=2n,2n-1,…,k）
这样处理，为后续取数提供方便。
取数完毕，比较最后得分即可评定胜负。
算法操作为取数与移位，时间复杂度为O(n2)。
（2） 程序实现
模拟A,B取数游戏
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
void main()
{ int j,k,n,sa,sb,t,c[1000],d[1000];
t=time(0)%1000;srand(t);
随机数发生器初始化
序列中2n个整数, 请确定n:");
scanf("%d",&n);
for(j=1;j&=2*n;j++)
{c[j]=rand()%(2*n)+2;
// 随机产生2n个整数
d[j]=c[j];
序列的%d个整数已产生，每次只显示两端整数。\n
A先取，A，B轮流取，直到取完。\n");
for(k=1;k&=2*n;k++)
{if(k&2*n)
printf("\n
两端数为：%2d,%2d
",d[k],d[2*n]);
printf("\n
只剩下1个数：%2d
",d[2*n]);
if(k%2==1)
if(t&d[2*n])
{t=d[2*n];
for(j=2*n;j&=k+1;j--) d[j]=d[j-1];
sa=sa+t; printf("
A取数%2d; ",t);
{ printf("
B取数:");scanf("%d",&t);
if(t==d[k] || t==d[2*n])
{ sb=sb+t;
if(t==d[2*n])
{ for(j=2*n;j&=k+1;j--) d[j]=d[j-1];}
{ printf("
A取数有误，重新开始！");}
原序列的%d个整数为：",2*n);
for(j=1;j&=2*n;j++)
%d",c[j]);
printf("\n
最后得分为 A=%d, B=%d,",sa,sb);
printf(" 此游戏A胜！\n");
else if(sa&sb) printf(" 此游戏B胜！\n");
else printf(" 此游戏A,B平手！\n");
7-5 全显取数游戏 “先取不败”的实现
A与B玩取数游戏：随机产生的2n个整数排成一排，但只显示排在两端的数。两人轮流从显示的两端数中取一个数，取走一个数后即显示该端数，以便另一人再取，直到取完。
胜负评判：所取数之和大者为胜。
A说：还是采用贪心策略，每次选取两端数中较大者为好。虽不能确保胜利，但胜的几率大得多。
B说：我可以确保不败，但有两个条件：一是我先取；二是明码，即所有整数全部显示。
试模拟A、B的取数游戏。
（1） 算法要点
应用贪心策略每次取两端较大数不能确保B先取不败。
为确保B先取不败，建立数学模型：
设序列的2n个整数存储于a[1]——a[2*n],
1） 计算序列中奇数号整数之和s1与偶数号整数之和s2。
2） 如果s1&s2，B取所有奇数号整数：先取a[1]，则A必取偶数号（2或2n）上的整数；随后B“连号”取数，即A若取a[2]，B取a[3]； A若取a[2*n]，B取a[2*n-1]；…这样可确保B取完所有奇数号整数而获胜。
3） 否则，即s1≤s2，B取所有偶数号整数：先取a[2*n]，则A必取奇数号（1或2n-1）上的整数；随后B“连号”取数，即A若取a[1]，B取a[2]； A若取a[2*n-1]，B取a[2*n-2]；…这样可确保B取完所有偶数号整数而不败（当s1=s2时平手）。
4） A按贪心策略取数，即取两端数的较大者。
5） 算法操作为取数与移位，时间复杂度为O(n2)。
（2） 程序实现
所有数显示，B先取不败取数游戏
#include &stdio.h&
#include &stdlib.h&
#include &time.h&
void main()
{ int j,k,n,d1,d2,s1,s2,t,a[1000];
t=time(0)%1000;srand(t);
随机数发生器初始化
序列中2n个整数, 请确定n:");
scanf("%d",&n);
序列的%d个整数依次为：",2*n);
for(j=1;j&=2*n;j++)
{a[j]=rand()%(2*n)+2;
// 随机产生并显示2n个整数
printf(" %d",a[j]);
if(j%2==1) s1+=a[j];
else s2+=a[j];
printf("\n
B先取。");
d1=1;d2=2*n;
B取数%d; \n",a[d1]);
B取数%d; \n",a[d2]);
请在剩余项：");
for(j=d1;j&=d2;j++) printf(" %d",a[j]);
printf(" 的两端取数。\n");
for(k=2;k&=n;k++)
{ if(a[d1]&a[d2])
{ printf("
A取数: %d;",a[d1]);
B取数: %d; \n",a[d1+1]);
{ printf("
A取数: %d;",a[d2]);
B取数: %d; \n",a[d2-1]);
请在剩余项：");
for(j=d1;j&=d2;j++) printf(" %d",a[j]);
printf(" 的两端数取数。\n");
A最后取数: %d;\n",a[d2]);
{ printf("
最后得分为:B=%d, A=%d \n",s1,s2);
此游戏B胜！\n");
else if(s1&s2)
{ printf("
最后得分为:B=%d, A=%d\n",s2,s1);
此游戏B胜！\n");
{ printf("
最后得分为:B=%d, A=%d\n",s2,s1);
此游戏B与A平手！\n");
8-1 连写数探求
从1开始按正整数的顺序不间断连续写下去所成的整数称为连写数。要使连写数112…m（连写到整数m）能被指定的整数p（&1000）整除，m至少为多大？
（1）模拟除法设计要点
要使连写数1234...m能被键盘指定的整数n整除，模拟整数的除法操作:
设被除数为a，除数为n，商为b，余数为c，则
b=a/n, c=a-bn 或 c=a%n
当c≠0且m为1位数时,a=c10+m 作为下一轮的被除数继续。
当c≠0一般地m为一个t位数时,则分解为t次(即循环t次)按上述操作完成。
直至c=0时，连写数能被n整除，作打印输出增连数1234...m除以n所得的商。
在整个模拟除法过程中,m按顺序增1。
（2） 模拟除法程序设计
// 模拟除法求连写数
#include &math.h&
#include&stdio.h&
void main()
{ int c,d,e,j,k,t,w,m,n;
A给出整数n: ");
scanf("%d",&n);
{e=j/10;t=1;w=1;
while(e&0)
// 对每一个j,计算t
{e=e/10;t=t*10;w=w+1;}
for(k=1;k&=w;k++)
// 对每一个j,分位试商
{d=e/t;e=e%t;t=t/10;
a=c*10+d;c=a%n;}
B寻求的整数m：%d. \n",m);
连写数12...%d/%d=",m,n);
for(j=2;j&=m;j++)
{e=j/10;t=1;w=1;
while(e&0)
// 对每一个j,计算t
{e=e/10;t=t*10;w=w+1;}
for(k=1;k&=w;k++)
// 对每一个j,分位试商
{d=e/t;e=e%t;t=t/10;
a=c*10+d;c=a%n;
printf("%d",a/n);}
printf("\n");
8-2 01串积
程序设计爱好者A，B进行计算游戏：
B任给一个正整数b，A寻求另一个整数a, 使a 与b的积最小且全为0与1组成的数。
例如，B给出b=23，A找到a=4787, 其最小01串积为110101。
01串积问题相对前面的积全为“1”的乘数问题要复杂一些，我们应用求余数判别。
（1） 注意到01串积为十进制数，应用求余运算“%”可分别求得个位“1”，十位“1”，…，分别除以已给b的余数，存放在c数组中：c(1)为1,c(2)为10除以b的余数,c(3)为100除以b的余数，…。
（2） 要从小到大搜索01串，不重复也不遗漏，从中找出最小的能被b整除01串积。为此，设置k从1开始递增，把k转化为二进制，就得到所需要的这些串。不过，这时每个串不再看作二进制数，而要看作十进制数。
（3） 在某一k转化为二进制数过程中，每转化一位a(i)(0或1)，求出该位除以b的余数a(i)c(i)，通过累加求和得k转化的整个二进制数除以b的余数s。
（4） 判别余数s 是否被b整除：若s%b=0, 即找到所求最小的01串积。
（5） a 从高位开始除以b的商存储在d数组，实施整数除法运算：
x=e10+a[j]; // e为上轮余数，x为被除数
d[j]=x/b; // d为a 从高位开始除以b的商
e=x%b; // e为试商余数
去掉d数组的高位“0”后，输出d即为所寻求的数。
（6） 最后从高位开始打印a数组，即为01串积。
// 01串积C程序
#include&stdio.h&
void main()
{ int b,e,i,j,t,x,a[2000],d[2000],c[2000];
B给出整数 b:"); scanf("%d",&b);
for(i=2;i&200;i++)
c[i]=10*c[i-1]%b;
// c(i)为右边第i位1除以b的余数
{ k++;j=k;i=0;s=0;
while(j&0)
{i++;a[i]=j%2;
s+=a[i]*c[i];j=j/2; s=s%b; // 除2取余法转化为二进制
if(s%b==0)
{for(e=0,j=i;j&=1;j--)
{ x=e*10+a[j];
d[j]=x/b; e=x%b;
// a 从高位开始除以b的商为d
while(d[j]==0) j--;
// 去掉d数组的高位“0”
A寻求整数a：");
for(t=j;t&=1;t--)
printf("%d",d[t]);
printf("\n
a*b的最小01串积为：");
for(t=i;t&=1;t--)
printf("%d",a[t]);
printf("\n");
8-3 自然对数底e的高精度计算
自然对数的底数e是一个无限不循环小数, 是“自然律”的一种量的表达，在科学技术中用得非常多。学习了高数后我们知道，以e为底数的对数是最简的，用它是最“自然”的，所以叫“自然对数”。
试设计程序计算自然对数的底e，精确到小数点后指定的x位。
1．算法设计
（1）选择计算公式
计算自然对数的底e，我们选用以下公式：
（2）确定计算项数
其次，要依据输入的计算位数x确定所要加的项数n。显然，若n太小，不能保证计算所需的精度；若n太大，会导致作过多的无效计算。
可证明，式中分式第n项之后的所有余项之和 。因此，只要选取n，满足 即可。即只要使
于是可设置对数累加实现计算到x位所需的项数n。为确保准确，算法可设置计算位数超过x位（例如x+2位），只打印输出x位。
（3）竖式除模拟
设置a数组，下标预设5000，必要时可增加。计算的整数值存放在a(0)，小数点后第i位存放在a(i)中(i=1,2,…)。
依据公式（1），应用竖式除模拟进行计算：
数组除以n，加上1；再除以n-1，加上1；…。这些数组操作设置在j (j=n,n-1,…,2) 循环中实施。
按公式实施除竖式计算操作:被除数为c，除数d分别取n,n-1,……,2。商仍存放在各数组元素(a(i)=c/d)。余数(c%d)乘10加在后一数组元素a(i+1)上，作为后一位的被除数。
按数组元素从高位到低位顺序输出。因计算位数较多，为方便查对，每一行控制打印50位，每10位空一格。注意，在输出结果时，整数部分a(0)需加1。
（4） 模拟乘除竖式计算求解e，程序运行非常快捷。注意到其计算项数n小于计算e的位数x，该算法的时间复杂度为O(xn)。
2．自然对数的底e的程序实现
// 高精度计算自然对数的底e
#include &math.h&
#include&stdio.h&
void main()
{ int x,n,c,i,j,d,l,a[5000];
请输入精确位数:");
scanf("%d",&x);
for(s=0,n=2;n&=5000;n++)
// 累加确定计算的项数n
{ s=s+log10(n);
for(i=0;i&=x+2;i++)
for(c=1,j=n;j&=2;j--)
// 按公式分步计算
for(i=0;i&=x+1;i++)
// 各位实施除j
{a[i]=c/d;
c=(c%d)*10+a[i+1];
a[x+2]=c/d;
a[0]=a[0]+1;c=a[0];
// 整数位加1
printf("\n
e=%d.",a[0]+1);
// 遂位输出