《算法设计与分析实用教程》习题参考解答

《算法设计与分析实用教程》参考解答

1-1 加减得1的数学游戏

西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。

例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。

（1） 若输入两个不同的正整数a,b均为偶数，显然不可能得到1。

设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2） 算法描述

// 两数若干次加减结果为1的数学游戏 #include void main()

{long a,b,d,n,x,y;

printf(\" 请输入整数a,b: \"); scanf(\"%ld,%ld\ if(a%2==0 && b%2==0)

{ printf(\" -1\\n\");return;} n=0; while(1) { n++;

for(x=1;x<=n;x++)

{ y=n+1-x;d=x*a-y*b;

if(d==1 || d==-1) // 满足加减结果为1 { printf(\" n=%ld\\n\} } }

请输入整数a,b: 2012,19 961

请输入整数a,b: 101,2013 606

1-2 埃及分数式算法描述

分母为整数分子为“1”的分数称埃及分数，试把真分数a/b分解为若干个分母不为b的埃及分数之和。

（1） 寻找并输出小于a/b的最大埃及分数1/c； （2） 若c>900000000，则退出；

（3） 若c≤900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。

（4） 若a/b不为埃及分数，则继续（1）、（2）、（3）。 试描述以上算法。

解：设dint(b) (这里int(x)表示取正数x的整数)，注意到dbd1，有

aa a1a(d1)bbd1b(d1)

算法描述：令c=d+1，则 input (a,b) while(1)

{c=int(b/a)+1;

if(c>900000000) return; else

{ print(1/c+); a=a*c-b;

b=b*c; // a,b迭代，为选择下一个分母作准备 if(a==1)

{ print(1/b);return;} } }

1-3 求解时间复杂度

求出以下程序段所代表算法的时间复杂度。 （1）m=0;

for(k=1;k<=n;k++) for(j=k;j>=1;j--) m=m+j;

解：因s=1+2+…+n=n(n+1)/2

2

时间复杂度为O(n)。 （2）m=0; for(k=1;k<=n;k++) for(j=1;j<=k/2;j++)

m=m+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的执行频数为

22

s=1+1+2+2+3+3+…+u=u=n/4

2

时间复杂度为O(n)。 （3）t=1;m=0;

for(k=1;k<=n;k++) {t=t*k;

for(j=1;j<=k*t;j++)

m=m+j; }

解：因s=1+2×2!+ 3×3!+…+ n×n!=(n+1)!−1 时间复杂度为O((n+1)!). （4）for(a=1;a<=n;a++) {s=0;

for(b=a*100−1;b>=a*100−99;b−=2) {for(x=0,k=1;k<=sqrt(b);k+=2) if(b%k==0)

{x=1;break;} s=s+x; } if(s==50)

printf(\"%ld \\n\}

解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环b/2次。因而k循环体的执行次数s满足

s＜25(99199L100n1)＜250(12Ln)4n3＜250n＜250nn6

算法的时间复杂度为O(nn)。

1-4 时间复杂度的一个性质

若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。

mm-1

证：设m为正整数，p(n)=a1×n+a2×n+…+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-5 统计n!中数字“0”的个数

修改1.3.2计算n!的算法，统计并输出n!中数字“0”的个数及其尾部连续“0”的个数（n<10000）。

解：计算n!完成后，在j（1——m）循环过 if(a[j]==0) p++; 统计n!中数字“0”的个数p。

应用q=1; while(a[q]==0) q++;统计尾部连续“0”的个数q-1。 // 统计n!中0的个数及尾部连续0的个数（n<10000）

#include #include void main()

{ int g,j,k,m,n,p,q,t,a[40000];double s; printf(\" 请输入正整数n(n<10000): \"); scanf(\"%d\ // 输入n s=0;

for(k=2;k<=n;k++)

s+=log10(k); // 对数累加确定n!的位数m m=(int)s+1;

for(k=1;k<=m;k++)

a[k]=0; // 数组清零 a[1]=1;g=0;

for(k=2;k<=n;k++)

for(j=1;j<=m;j++)

{ t=a[j]*k+g; // 数组累乘并进位 a[j]=t%10; g=t/10; } p=0;

for(j=m;j>=1;j--) if(a[j]==0) p++; // p统计n!中0的个数 q=1;

while(a[q]==0) q++; // q尾部连续0的个数 printf(\" p=%d,q=%d\\n\输出结果 } 数据测试：

请输入正整数n(n<10000): 1000 p=472,q=249

请输入正整数n(n<10000): 2013 p=1032,q=501

1-6 构建斜折对称方阵

图1-4是一个7阶斜折对称方阵，试观察斜折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（奇数）阶斜折对称方阵。

图1-4 7阶斜折对称方阵

（1） 构造规律与赋值要点

对n阶方阵中的每一个元素都必须赋值，但不可能逐行逐列地一个个赋值，有必要分析方阵的构造特点，分块或分片实施。

斜折对称方阵的构造特点：两对角线上均为“0”，依两对角线把方阵分为4个区域，每一区域表现为同数字依附两对角线折叠对称，至上下左右正中元素为n/2。

同样设置2维a[n][n]数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j列元素。

令m=(n+1)/2, 按m把方阵分成的4个小矩形区如图1-5所示。

图1-5 按m分成的4个小矩形

注意到方阵的主对角线（从左上至右下）上元素为：i=j，则左上区与右下区依主对角线赋值：a[i][j]=abs(i-j);

注意到方阵的次对角线（从右上至左下）上元素为：i+j＝n+1，则右上区与左下区依次对角线赋值：a[i][j]=abs(i+j-n-1);

(2) 程序设计 // 斜折对称方阵 #include #include void main()

{int i,j,m,n,a[30][30];

printf(\" 请确定方阵阶数(奇数)n: \"); scanf(\"%d\if(n%2==0)

{ printf(\" 请输入奇数！\");return;} m=(n+1)/2;

for(i=1;i<=n;i++) for(j=1;j<=n;j++)

{ if(i<=m && j<=m || i>m && j>m)

a[i][j]=abs(i-j); // 方阵左上部与右下部元素赋值 if(i<=m && j>m || i>m && j<=m)

a[i][j]=abs(i+j-n-1); // 方阵右上部与左下部元素赋值 }

printf(\" %d阶对称方阵为:\\n\ for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++) // 输出对称方阵 printf(\"%3d\ printf(\"\\n\"); } }

1-7 构建横竖折对称方阵

试观察图1-6所示的横竖折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（奇数）阶横竖折对称方阵。

图1-6 7阶横竖折对称方阵

（1） 构造规律与赋值要点

观察横竖折对称方阵的构造特点，方阵横向与纵向正中有一对称轴。两对称轴所分4个小矩形区域表现为同数字横竖折递减，至4顶角元素为1。

设阶数n（奇数）从键盘输入，对称轴为m=(n+1)/2。

设置2维a数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j列元素。 可知主对角线（从左上至右下）有：i=j； 次对角线（从右上至左下）有：i+j=n+1。

按两条对角线把方阵分成上部、左部、右部与下部4个区,如图1-7所示。

图1-7 对角线分成的4个区

对角线上元素可归纳到上、下部，即上、下部区域带等号即可。 上、下部按列号j的函数m-abs(m-j)赋值：

if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j) a[i][j]=m-abs(m-j);

左、右部按行号i的函数m-abs(m-i)赋值： if(i+jj || i+j>n+1 && i// 横竖折对称方阵

#include // 调用2个头文件

#include void main()

{int i,j,m,n,a[30][30]; // 定义数据结构

printf(\" 请确定方阵阶数(奇数)n: \"); scanf(\"%d\ if(n%2==0)

{printf(\" 请输入奇数！\");return;} m=(n+1)/2;

for(i=1;i<=n;i++) for(j=1;j<=n;j++) {

if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j)

a[i][j]=m-abs(m-j); // 方阵上、下部元素赋值 if(i+jj || i+j>n+1 && ia[i][j]=m-abs(m-i); // 方阵左、右部元素赋值 }

printf(\" %d阶对称方阵为:\\n\ for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++) // 输出对称方阵 printf(\"%3d\ printf(\"\\n\"); } }

1-8 应用定义求最大公约与最小公倍数

应用定义求n个正整数的最大公约数与最小公倍数, 给出算法设计。 为方便表述，记

(a1,a2,...,an)为n个正整数a1,a2,...,an的最大公约数。 {a1,a2,...,an}为n个正整数a1,a2,...,an的最小公倍数。 （1）设计要点

求3个或3个以上正整数的最大公约数与最小公倍数，可通过反复运用求两个正整数的最大公约数与最小公倍数的方法来实现。

对于3个或3个以上正整数，最大公约数与最小公倍数有以下性质：

(a1,a2,a3)=((a1,a2),a3)

(a1,a2,a3,a4)=((a1,a2,a3),a4),... {a1,a2,a3}={{a1,a2},a3}

{a1,a2,a3,a4}={{a1,a2,a3},a4},...

应用这一性质，要求n个数的最大公约数，先求出前n-1个数的最大公约数b，再求第n个数与b的最大公约数。要求n个数的最小公倍数，先求出前n-1个数的最小公倍数b，再

求第n个数与b的最小公倍数。

程序设计求最大公约数时变量b的值：开始b=m[0]，即输入的第一个数；进入循环后，每次把输入的数赋值给a，求得a、b的最大公约数c，同时赋值给b，为下一轮循环作准备。

求最小公倍数时变量b的值：开始b=m[0]，即输入的第一个数；进入循环后，每次把输入的数赋值给a，求得a、b的最小公倍数c，同时赋值给b，为下一轮循环作准备。 （2）算法描述

// 求n个正整数的最大公约数与最小公倍数 #include void main() { int k,n;

long a,b,c,m[100];

printf(\"请输入正整数个数n: \"); scanf(\"%d\

printf(\"请依次输入%d个正整数: \ for(k=0;k<=n-1;k++)

{ printf(\"\\n请输入第%d个正整数： \ scanf(\"%ld\// 输入原始数据 } b=m[0];

for(k=1;k<=n-1;k++) {a=m[k]; if(a{c=a;a=b;b=c;} // 交换a、b，确保a>b for(c=b;c>=1;c--)

if(a%c==0 && b%c==0) // 计算最大公约数 break; b=c; }

printf(\"(%ld\ // 输出最大公约数结果 for(k=1;k<=n-1;k++) printf(\ printf(\")=%ld\\n\ b=m[0];

for(k=1;k<=n-1;k++) {

a=m[k]; if(a{c=a;a=b;b=c;} for(c=a;c<=a*b;c=c+a)

if(c%b==0) // 计算最小公倍数

break; b=c; }

printf(\"{%ld\ // 输出最小公倍数结果 for(k=1;k<=n-1;k++) printf(\ printf(\")=%ld\\n\}

（3）数据测试

请输入正整数个数n：3 请依次输入3个正整数: 请输入第1个正整数： 238 请输入第2个正整数： 782 请输入第3个正整数： 646 (238,782,646)=34 {238,782,646}=104006

2-1 广义同码小数之和

s(d,n)=0.d+0.dd+0.ddd+...+0.dd...d (n个d) 其中正整数d,n从键盘输入（1例如：s(301,4)=0.301+0.301301+0.301301301+0.1 依次输入整数d，n（11) 求出输入的整数d的位数k及d的各位数字p[k]（p[1]为个位数字）。 2) 枚举小数点后各位（共n*k位）求和。 3) 设置n*k次循环，从后往前进位。 (2) 枚举描述

// 求和s(d,n)=0.d+0.dd+0.ddd+...+0.dd...d (n个d) #include void main()

{ int a,d,i,j,k,m,n,p[10];long s[50000]; printf(\" 请输入整数d,n: \"); scanf(\"%d,%d\ a=d;k=0; while(a>0)

{ k++;p[k]=a%10;a=a/10;}

for(j=0;j<=k*n;j++) s[j]=0; // s[0]为整数部分 for(i=0;i<=n-1;i++)

for(j=1;j<=k;j++)

s[i*k+j]=(n-i)*p[k+1-j]; // 小数点后各位求和

for(j=k*n;j>=1;j--) // 加完n个数从后往前统一进位 { s[j-1]=s[j-1]+s[j]/10;s[j]=s[j]%10;} printf(\" s(%d,%d)=%ld.\ m=k*n;

if(m>10) m=10; for(j=1;j<=m;j++) printf(\"%ld\}

数据测试：

输入整数d,n: 2014,2013

s(2014,2013)=405.4587257305

2-2 解不等式

设n为正整数，解不等式

201311112014 11/211/21/311/21/n解：上下限一般为键盘输入的a,b。

分两段求和：应用条件s #include void main()

{ long a,b,c,d,i; double ts,s;

printf(\" 请输入a,b: \"); scanf(\"%d,%d\ i=0;ts=0;s=0; while(sts=ts+(double)1/i; s=s+1/ts; } c=i;

while(sts=ts+(double)1/i;

s=s+1/ts;

} d=i-1;

printf(\"\\n 满足不等式的正整数n为: %ld≤n≤%ld \\n\}

数据测试：

请输入a,b: 2013,2014

满足不等式的正整数n为: 18642≤n≤18652

2-3 解不定方程

试求解三元不定方程

111abcabc

满足条件 xa,b,cy,bc 的所有正整数解。

（1）枚举设计要点

1） 为了扩大求解围，所涉变量设置为double型。 2） 注意a,b,c的取值围，在区间[x,y]中取值：

a与b,c没有限制，只限制b3） 另外，原三元不定方程为分数形式，转化为以下的整数形式

(abc)bca((abc)bc) 在枚举循环中应用以上整式进行筛选是可行的。 （2） 枚举描述

// 解不定方程 #include #include void main()

{ double a,b,c,s,x,y,m;

printf(\" 请输入正整数x,y: \"); scanf(\"%lf,%lf\ m=0;

for(a=x;a<=y;a++) // 设计三重循环实现枚举 for(b=x;b<=y-1;b++) for(c=b+1;c<=y;c++) { s=a+b+c;

if(b*c*s!=a*(b*c+s)) // 应用方程式实施筛选 continue;

m++; // 统计解的个数并输出解 printf(\" %.0f: a=%.0f,b=%.0f,c=%.0f \\n\}

}

数据测试：

请输入正整数x,y: 10,100 1: a=50,b=10,c=15 2: a=90,b=15,c=21

2-4 合数世纪探索

定义：一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。

试探索第m（约定m<100）个合数世纪。 （1） 枚举要点

应用枚举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。

对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为合数世纪，用n统计合数世纪的个数。当n=m时打印输出a 世纪。

当n=m时退出循环结束。 （2） 枚举描述

// 探求第m个合数世纪 #include #include void main()

{long a,b,k; int m,n,s,x;

printf(\" 请确定m: \"); scanf(\"%d\ a=1;n=0;

while (1)

{a++;s=0; // 检验a世纪

for(b=a*100-99;b<=a*100-1;b+=2) // 穷举a世纪奇数年号b {x=0;

for(k=3;k<=sqrt(b);k+=2) if(b%k==0)

{x=1;break;}

if(x==0)break; // 当前为非合数世纪时，跳出循环进行下一个世纪的探求 s=s+x; // 年号b为合数时，x=1，s增1 }

if(s==50) // s=50，即50个奇数均为合数

{ n++; if(n==m) printf(\" 第%d个合数世纪为：%ld 世纪。\\n\

}

if(n==m) break; }

}

数据测试： 请确定m: 10

第10个合数世纪为：58453 世纪。

2-5 分解质因数

对给定区间[m,n]的正整数分解质因数,•每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。

例如, 2012=2*2*503, 2011=(素数!)。 （1） 设计要点

对区间中的每一个整数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// 质因数分解乘积形式 #include\"math.h\" #include void main()

{long int b,i,k,m,n,w=0;

printf(\"[m,n]中整数分解质因数（乘积形式）.\\n\"); printf(\"请输入m,n:\"); scanf(\"%ld,%ld\

for(i=m;i<=n;i++) // i为待分解的整数

{ printf(\"%ld=\ b=i;k=2;

while(k<=sqrt(i)) // k为试商因数 {if(b%k==0) {b=b/k;

if(b>1)

{printf(\"%ld*\

continue; // k为质因数,返回再试 }

if(b==1) printf(\"%ld\\n\}

k++;

}

if(b>1 && bprintf(\"%ld\\n\输出大于i平方根的因数 if(b==i)

{printf(\"(素数!)\\n\");w++;} // b=i,表示i无质因数 } }

数据测试：

[m,n]中整数分解质因数（乘积形式）. 请输入m,n:5845201,5845300 5845201=593*9857 5845202=2*11*47*5653 ……

5845300=2*2*5*5*58453

以上测试可知没有一个素数，验证了上题的第10个合数世纪的100个合数年号。

2-6 因数比的最大值

设整数a的小于其本身的因数之和为s，定义

p(a)=s/a 为整数a的因数比。

事实上，a为完全数时，p(a)=1。例如，p(6)=1。

有些资料还介绍了因数之和为数本身2倍的整数，例如p(120)=2。 试搜索指定区间[x,y]中因数比最大的整数。 （1） 设计要点

设置循环枚举区间[x,y]中的整数a。

为了求整数a的因数和s,显然1是因数,设置因数k(2——sqrt(a))的枚举循环，如果

k是a的因数，则a/k也是a的因数，实施求和s=s+k+a/k。

有一点值得注意：如果a=b*b，显然k=b,a/k=b是同一个因数，为避免重复求和，所以此时必须从和s中减去一个b。

设置max存储因数比最大值。枚举区间每一整数a，求得其因数和s。通过比值s/a与max比较，求取因数比最大值。

（2） 枚举描述

// 求[x,y]围整数的因数比最大值 #include #include void main()

{ double a,s,a1,s1,b,k,t,x,y,max=0; printf(\" 请输入整数x,y:\"); scanf(\"%lf,%lf\

for(a=x;a<=y;a++) // 枚举区间的所有整数a {s=1;b=sqrt(a);

for(k=2;k<=b;k++) // 试商寻求a的因数k if(fmod(a,k)==0)

s=s+k+a/k; // k与a/k是a的因数，求和 if(a==b*b)

s=s-b; // 如果a=b^2,去掉重复因数b

t=s/a; if(max{max=t;a1=a;s1=s;} }

printf(\" 整数%.0f的因数和为：%.0f ,\ printf(\"其因数比最大：%.5f \\n\}

数据测试：

请输入整数x,y:10000,100000

整数55440的因数和为：176688 ,其因数比最大：3.18701 算法中在区间枚举循环中含试商因数枚举的循环。设区间中整数个数为n,算法的时间复杂度为O(nn)。

思考：请探否存在因数比p(a)=s/a≥4的整数a？若存在，整数a至少为多大？

2-7 基于素数代数和的最值

定义和：

s(n)13355779(2n1)(2n1)

(和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项取“-”，即为-25*27。)

1) 求s(2013)。

2) 设1<=n<=2013，当n为多大时，s(n)最大。 3) 设1<=n<=2013，当n为多大时，s(n)最小。 （1） 设计要点

代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第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。 （2） 算法描述

// 基于素数的整数和 #include #include void main()

{ int t,j,n,k,k1,k2,a[3000]; long s,smax,smin; printf(\" 请输入整数n: \"); scanf(\"%d\

for(k=1;k<=n+1;k++) a[k]=0; for(k=2;k<=n+1;k++)

{for(t=0,j=3;j<=sqrt(2*k-1);j+=2) if((2*k-1)%j==0) {t=1;break;}

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+=(2*k-1)*(2*k+1); // 实施代数和

else

s-=(2*k-1)*(2*k+1);

if(s>smax){smax=s;k1=k;} // 比较求最大值smax if(s}

printf(\"s(%d)=%ld \\n\

printf(\"当k=%d时s有最大值: %ld\\n\printf(\"当k=%d时s有最小值: %ld\\n\}

数据测试：

请输入整数n: 2013 s(2013)=-889733139

当k=814时s有最大值: 46296494 当k=1999时s有最小值: -1018390543

2-8 完美四则运算式

把数字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 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=a*b+x;

if(c!=x*d || e>100) continue;

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++) {y=m[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; break;} // 检验数字0--9各只出现一次 if(t==0) // 输出一个解，用n统计个数 {n++;

printf(\"%2d: %2d*%1d+%3d/%1d-%2d=0 \\n\

} }

printf(\" n=%d.\\n\ }

数据测试：

1: 12*4+376/8-95=0 2: 17*3+258/6-94=0 3: 35*2+168/7-94=0 n=3.

2-9 区间的最续合数区间

搜索指定区间[c,d]的最续合数区间。 输入： 键盘输入区间围c,d。

输出： 区间最多连续合数的个数，连续合数的起始与终止数。 例如输入 c,d:10,100

最多连续合数的个数为：7 连续合数区间为：[90,96] （1） 应用试商设计

// 求指定区间最多有多少个连续合数 #include

#include void main()

{ long c,d,i,j,f,t,f1,i1,max;

printf(\" 请输入 c,d:\"); scanf(\"%ld,%ld\ f=c;max=0;

if(c%2==0) c++; i=c;

for(i=c;i<=d;i+=2) {t=0;

for(j=3;j<=sqrt(i);j+=2) // 试商判别素数 if(i%j==0) {t=1;break;}

if(t==0) // t为0表明i为素数 { if(i-f>max)

{max=i-f;f1=f+1;i1=i-1;}

f=i; // f为i的前一个素数 } }

printf(\" 最多连续合数的个数为：%ld\\n\ printf(\" 连续合数区间为：[%ld,%ld]\\n\ }

数据测试：

请输入 c,d:10000,1000000 最多连续合数的个数为：113

连续合数区间为：[492114,492226] （2） 筛法设计

求出区间[c,d]的所有相邻素数对f,m，求取m-f的最大值max。 注意到本题的搜索围较大,采用效率较高的筛法求素数是适宜的。

求素数的筛法是公元前三世纪的厄拉多塞(Eratosthenes)提出来的:•对于一个大整数x,只要知道不超过sqrt(x)的所有素数p，划去所有p的倍数2p,3p,...,剩下的整数就是不超过x的全部素数。

应用筛法求素数，为了方便实施\"划去\"操作，设置数组。

考虑到有时待测区间[c,d]比较大，为不使数组下标超维,或把[c,d]分割为若干子区间[cs,ds],确保在子区间中操作不超维。•

每一数组元素对应一个待判别的奇数，并赋初值0。如果该奇数为p的倍数则应划去,•对应元素加一个划去标记，通常给该元素赋值-1。最后,打印元素值不是-1(即没有划去)•的元素对应的奇数即所求素数。

在实际应用筛法的过程中，p通常不限于取不超过sqrt(x)的素数，而是适当放宽取不超过sqrt(x)的奇数(从3开始)。这样做尽管多了一些重复划去操作，但程序实现要简便些。

在指定区间[cs,ds](约定cs为奇数)上所有奇数表示为j=cs+2k,(k=0,1,...,e,这里

e=(ds-cs)/2)。于是k=(j-cs)/2是奇数j在数组中的序号(下标)。如果j为奇数的倍数时,•对应数组元素作划去标记,即a[(j-cs)/2]=-1。

根据cs与奇数i,确定 g=2*int(cs/(2*i))+1,使得gi接近区间下限cs,从而使划去的gi,(g+2)i,...在[cs,ds]中,减少无效操作,以提高对大区间的筛选效率。

最后,凡数组元素a[k]≠-1,•对应的奇数j=cs+2k则为素数。 • // 求指定区间最多有多少个连续合数 #include #include void main()

{ long c,d,cs,ds,ct,dt,f,g,i,j,k,m,max,a[11000]; int e,u,x,y;

printf(\" 请输入 c,d:\"); scanf(\"%ld,%ld\ if(d-c<=20000) {cs=c;ds=d;x=0;}

else {x=(d-c)/20000;cs=c;ds=d-20000*x;} f=cs;max=0;

for(y=1;y<=x+1;y++) // 把[c,d]中分x+1个子区间筛选素数

{ if(cs%2==0) cs++;

for(i=0;i<=10999;i++) a[i]=0; e=(ds-cs)/2;i=1; while (i<=sqrt(ds))

{i=i+2;g=2*(cs/(2*i))+1; if(g*i>ds) continue; if(g==1) g=3; j=i*g;

while (j<=ds)

{ if(j>=cs) a[(j-cs)/2]=-1; // 筛去标记-1 j=j+2*i; } }

for(u=1,k=0;k<=e;k++) { if(a[k]!=-1)

{ m=cs+2*k; // m即筛选所得素数

if(m-f>max) // 寻求两相邻素数间距的最大值

{ max=m-f;ct=f+1;dt=cs+2*k-1;}

f=m; } }

cs=ds+1;ds=ds+20000; // cs与ds增长后继续探求 }

printf(\" 最多连续合数的个数为：%ld\\n\ printf(\" 连续合数区间为：[%ld,%ld]\\n\ }

数据测试：

请输入 c,d:10,10000000 最多连续合数的个数为：153

连续合数区间为：[4652354,4652506]

2-10 三角形双分线

设一块木板为非等腰ABC，其三边长分别为BC=a,CA=b,AB=c，寻求三角形木板上的分割线，把该三角形木板分割为周长相等且面积相等的两块。

试确定双分线的具体位置。

依次输入正整数a,b,c(约定a,b,c<100)，输出各分割线的位置（四舍五入精确到小数点后第4位）。

（1） 设计要点

1） 设ABC的周长为p，AB边上的分割点为D，AC边上的分割点为E，BC边上的分割点为F（如图2-6所示）。显然，p=a+b+c。

若线段EF为双分线，则CEF的面积为ABC面积的一半，CE+CF=p/2（分割线段EF为两块公共）。

图2-6 ABC及其分割线示意图

2） 设CE=x, CF=p/2-x,则面积相等的条件为CE*CF=x(p/2-x)=ab/2 同样，设CF=x, CE=p/2-x,则面积相等的条件为CE*CF=x(p/2-x)=ab/2 整理为关于x的二次方程：

2

2x-(a+b+c)x+ab=0

可见若EF为双分线，则CE、CF须为以上二次方程的两个正根。

2

3） 若方程的判别式w=(a+b+c)-8*a*b≥0, 则方程的两个解为： x1=((a+b+c)-sqrt(w))/4 x2=((a+b+c)+sqrt(w))/4 显然，x1≤x2 4） 讨论方程的解

若x1>0 且x1<=a 且x2<=b，由取CF=x1, CE=x2为一条双分线。

若x1>0 且 x2<=a，则取CF=x2, CE=x1为另一条双分线。

2

5）若线段DF为双分线，判别式为w=(a+b+c)-8*a*c;

2

若线段DE为双分线，判别式为w=(a+b+c)-8*b*c; 其余求解与讨论类似。 （2） 算法描述 // 三角形双分线 #include \"math.h\" #include void main()

{double a,b,c,p,w,x1,x2;

printf(\" 输入三角形三边长a,b,c: \"); scanf(\"%lf,%lf,%lf\ if(a>=b+c ||b>=c+a ||c>=a+b)

{ printf(\" 输入的三边长不能构成三角形！\"); return; }

p=a+b+c;w=p*p-8*a*b; // 在CA，CB边上取分割点 if(w>=0)

{x1=p/4-sqrt(w)/4;x2=p/4+sqrt(w)/4; if(0printf(\" 双分线在CB上取CF=%.4f, 在CA上取CE=%.4f\\n\ if(0printf(\" 双分线在CB上取CF=%.4f, 在CA上取CE=%.4f\\n\ }

w=p*p-8*c*b; // 在AB，AC边上取分割点 if(w>=0)

{x1=p/4-sqrt(w)/4;x2=p/4+sqrt(w)/4; if(0printf(\" 双分线在AC上取AE=%.4f, 在AB上取AD=%.4f\\n\ if(0printf(\" 双分线在AC上取AE=%.4f, 在AB上取AD=%.4f\\n\ }

w=p*p-8*c*a; // 在BA，BC边上取分割点 if(w>=0)

{x1=p/4-sqrt(w)/4;x2=p/4+sqrt(w)/4; if(0printf(\" 双分线在BC上取BF=%.4f, 在BA上取BD=%.4f\\n\ if(0printf(\" 双分线在BC上取BF=%.4f, 在BA上取BD=%.4f\\n\ } }

数据测试：

输入三角形三边长a,b,c: 30,40,50

双分线在BC上取BF=17.7526, 在BA上取BD=42.2474 输入三角形三边长a,b,c: 57,78,92

双分线在BC上取BF=32.2845, 在BA上取BD=81.2155 3-1 递推b数列

定义b数列： b11,b22,bn3bn1bn2(n2) 递推求b数列的第20项与前20项之和。 (1) 递推描述

#include void main()

{ int k,n; long b[3000],s; printf(\" 请输入n: \"); scanf(\"%d\ b[1]=1;b[2]=2;s=3; for(k=3;k<=n;k++)

{ b[k]=3*b[k-1]-b[k-2];

s+=b[k]; }

printf(\" b(%d)=%ld \\n\ printf(\" s=%ld \\n\ }

(2) 数据测试 请输入n: 20 b(20)=63245986 s=102334155

3-2 递推数列中的素数

已知数列a(1)=2,a(k)=a(k-1)+k (k>1).试求该数列的前m项中的素数个数及最大素数。 输入m，输出前m项中的素数个数及最大素数。 (1) 算法描述

// 数列中的素数 #define N 30000 #include #include void main()

{int m,n,k,j,t,a[N]; long s;

printf(\" 请输入m: \"); scanf(\"%d\a[1]=2;s=1;

for(k=2;k<=m;k++) { a[k]=a[k-1]+k;

for(t=0,j=2;j<=sqrt(a[k]);j++) if(a[k]%j==0) {t=1;break;}

if(t==0) {s++;n=a[k];} // a[k]为素数,用s统计个数 }

printf(\" 前%d项中素数个数为：%ld \\n\ printf(\" 最大素数为：%d \\n\}

(2) 数据测试 请输入m: 2014

前2014项中素数个数为：329 最大素数为：2023067

3-3 双幂序列

设x,y为非负整数，试计算集合

M{2x,3y|x0,y0}

的元素由小到大排列的双幂序列第n项与前n项之和。 (1) 递推设计要点

集合由2的幂与3的幂组成，实际上是给出两个递推关系。 设置一维f数组，f[k]存储双幂序列的第k项。 显然，第1项也是最小项为f[1]=1（当x=y=0时）。

从第2项开始，为了实现从小到大排序，设置a,b两个变量，a为2的幂，b为3的幂，显然a≠b。

设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;在k循环过比较选择赋值：

当a当a>b时，由赋值f[k]=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。 （2） 递推描述

a=2;b=3; // 为递推变量a,b赋初值 for(k=2;k<=n;k++) { if(a{ f[k]=a;a=a*2;} // 用a给f[k]赋值

else

{ f[k]=b;b=b*3;} // 用b给f[k]赋值 }

3-4 多幂序列

设x,y,z为非负整数，试计算集合

M{2x,3y,5z|x0,y0,z0}

的元素由小到大排列的多幂序列第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当ca=2;b=3;c=5; // 为递推变量a,b,c赋初值 for(k=2;k<=n;k++) { if(a{ f[k]=a;a=a*2;} // 用a给f[k]赋值

else if(b{ f[k]=b;b=b*3;} // 用b给f[k]赋值 else

{ f[k]=c;c=c*5;} // 用c给f[k]赋值

}

3-5 双幂积序列的和

由集合M{23|x0,y0}元素组成的复合幂序列，求复合幂序列的指数和x+y≤n（正整数n≤50从键盘输入）的各项之和

xysxy023,x0,y0

xyn（1） 递推设计要点 当x+y=0时，s(1)=1；

当x+y=1时，s(1)=2+3；

222

当x+y=2时，s(2)=2+2×3+3=2*s(1)+ 3

32233

当x+y=3时，s(3)=2+2×3+2×3+3=2*s(2)+ 3

k

一般地，当x+y=k时，s(k)=2*s(k−1)+3 即有递推关系：

s(k)=2*s(k)+3

k

k

其中3可以通过变量迭代实现。这样可以省略数组，简化为一重循环实现复合幂序列求和。

（2） 递推描述

// 复合幂序列求和 #include void main()

{int k,n; long sum,t,s[100];

printf(\"请输入幂指数和至多为n:\"); scanf(\"%d\ t=1;s[0]=1; sum=1; for(k=1;k<=n;k++)

{t=t*3; // 迭代得t=3^k s[k]=2*s[k-1]+t; // 实施递推

sum=sum+s[k]; }

printf(\"幂指数和至多为%d的幂序列之和为:%ld\\n\}

（3） 数据测试

请输入幂指数和至多为n:50

幂指数和至多为50的幂序列之和为:717652233

3-6 粒子裂变

核反应堆中有α和β两种粒子，每秒钟一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t(t<20)秒时反应堆裂变产生的α粒子和β粒子数。 （1） 递推设计要点

设在t秒时α粒子数为f(t)，β粒子数为g(t)，依题可知：

g(t)=3f(t-1)+2g(t-1) （1） f(t)=g(t-1) （2） g(0)=0,f(0)=1

由（2）得f(t-1)=g(t-2) （3） 将式（3）代入（1）得

g(t)=2g(t-1)+3g(t-2) (t≥2) （4） g(0)=0,g(1)=3 （5） 以递推关系（4）与初始条件（5）完成递推。 （2） 递推描述 // 粒子裂变

#include void main()

{int t,k;long g[100]; printf(\" input t:\"); scanf(\"%d\

g[0]=0; g[1]=3; // 确定初始条件 for(k=2;k<=t;k++)

g[k]=2*g[k-1]+3*g[k-2]; // 完成递推 printf(\"%d 秒时反应堆中β粒子数为:%ld \\n\ printf(\"%d 秒时反应堆中α粒子数为:%ld \\n\}

数据测试： input t:18

18 秒时反应堆中β粒子数为:290565366 18 秒时反应堆中α粒子数为:96855123

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 void main()

{ int k; long t[1000];

t[10]=1; // 确定初始条件 for(k=9;k>=1;k--) // 逆推计算t(1) t[k]=2*(t[k+1]+1);

printf(\" 第 1 天摘桃%ld个。\\n\ for(k=1;k<=9;k++)

{ printf(\" 第 %d 天面临%4ld个桃，\

printf(\" 吃了%4ld+1=%4ld个，\ printf(\" 还剩%4ld个。\\n\ }

printf(\" 第10天早上还剩1个。\"); }

数据测试：

第 1 天摘桃1534个。

第 1 天面临1534个桃， 吃了 767+1= 768个， 还剩 766个。 第 2 天面临 766个桃， 吃了 383+1= 384个， 还剩 382个。 第 3 天面临 382个桃， 吃了 191+1= 192个， 还剩 190个。 第 4 天面临 190个桃， 吃了 95+1= 96个， 还剩 94个。 第 5 天面临 94个桃， 吃了 47+1= 48个， 还剩 46个。 第 6 天面临 46个桃， 吃了 23+1= 24个， 还剩 22个。 第 7 天面临 22个桃， 吃了 11+1= 12个， 还剩 10个。 第 8 天面临 10个桃， 吃了 5+1= 6个， 还剩 4个。 第 9 天面临 4个桃， 吃了 2+1= 3个， 还剩 1个。 第10天早上还剩1个。

3-8 猴子吃桃引申

有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了m个。第2天早上又将剩下的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上想再吃时，见只剩下d个桃子了。

求第1天共摘了多少个桃子(m,n,d由键盘输入)？ （1） 递推设计要点 建立递推关系：

t(k)=2*(t(k+1)+m) (k=1,2,…,n-1) 初始条件：t(n)=d

逆推求出t(1)，即为所求的第一天所摘桃子数。 （2） 递推描述

// 拓广猴子吃桃程序 #include

void main()

{ int d,k,m,n; long t[1000];

printf(\" 请确定正整数m,n,d: \"); scanf(\"%d,%d,%d\

t[n]=d; // 确定初始条件 for(k=n-1;k>=1;k--) // 逆推计算t(1) t[k]=2*(t[k+1]+m);

printf(\" 第 1 天摘桃%ld个。\\n\ for(k=1;k<=n-1;k++)

{ printf(\" 第 %d 天面临%4ld个桃，\

printf(\" 吃了%4ld+%d=%4ld个，\ printf(\" 还剩%4ld个。\\n\ }

printf(\" 第%d天早上还剩%d个。\}

数据测试：

请确定正整数m,n,d: 3,20,2

第 1 天摘桃4194298个。

第 1 天面临4194298个桃， 吃了2097149+3=2097150个， 还剩2097146个。 第 2 天面临2097146个桃， 吃了1048573+3=1048574个， 还剩1048570个。 第 3 天面临1048570个桃， 吃了524285+3=524286个， 还剩524282个。 第 4 天面临524282个桃， 吃了262141+3=262142个， 还剩262138个。 第 5 天面临262138个桃， 吃了131069+3=131070个， 还剩131066个。 第 6 天面临131066个桃， 吃了65533+3=65534个， 还剩65530个。 第 7 天面临65530个桃， 吃了32765+3=32766个， 还剩32762个。 第 8 天面临32762个桃， 吃了16381+3=16382个， 还剩16378个。 第 9 天面临16378个桃， 吃了8189+3=8190个， 还剩8186个。 第 10 天面临8186个桃， 吃了4093+3=4094个， 还剩4090个。 第 11 天面临4090个桃， 吃了2045+3=2046个， 还剩2042个。 第 12 天面临2042个桃， 吃了1021+3=1022个， 还剩1018个。 第 13 天面临1018个桃， 吃了 509+3= 510个， 还剩 506个。 第 14 天面临 506个桃， 吃了 253+3= 254个， 还剩 250个。 第 15 天面临 250个桃， 吃了 125+3= 126个， 还剩 122个。 第 16 天面临 122个桃， 吃了 61+3= 62个， 还剩 58个。 第 17 天面临 58个桃， 吃了 29+3= 30个， 还剩 26个。 第 18 天面临 26个桃， 吃了 13+3= 14个， 还剩 10个。 第 19 天面临 10个桃， 吃了 5+3= 6个， 还剩 2个。 第20天早上还剩2个。

3-9 水手分椰子

五个水手来到一个岛上，采了一堆椰子后，因为疲劳都睡着了。一段时间后，第一个水手醒来，悄悄地将椰子等分成五份，多出一个椰子，便给了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起，继续睡觉。不久，第二名水手醒来，同样将椰子等分成五份，恰好也多出一个，也给了猴子。然后自己也藏起一份，再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的一个给了猴子。第二天，五个水手醒来，发现椰子少了许多，心照不宣，便把剩下的椰子分成五份，恰好又多出一个，给了猴子。

计算问原来这堆椰子至少有多少个? 试应用迭代与递推两种算法求解。 （1） 迭代求解 1） 确定迭代式

首先根据相邻两人所藏椰子数确定迭代方程

4*y=5*y+1 (i=1,2,…,5) （1） 迭代方程即相邻两水手所藏椰子数的关系，式左的y是相邻的前一个水手藏椰子数，式右的y是相邻后一个水手藏椰子数。

根据以上迭代方程变形，得从前往后迭代的迭代式为

y=(4*y-1)/5 (i=1,2,…,5) （2） 如果经5次迭代保持y都是整数，即完成迭代。 2） 迭代描述

// 迭代求解5个水手分椰子 #include #include void main()

{int i; double k,x,y; i=1;k=1.0;y=k; while(i<=5)

{ i++;y=(4*y-1)/5; // 递推求后一个水手时的椰子y if(y!=floor(y)) { k=k+1.0;y=k;i=1;} // 若y不是整数,k增1从头重试 }

x=5*k+1; // 此处k为第1个水手所藏椰子数 printf(\"%d个水手分椰子，原有椰子至少有：%6.0f个.\\n\}

（2） 递推求解

1） 确定递推关系

设置y数组，第i个水手藏椰子数为y(i)(i=1,2,…,5)个，第二天5个水手醒来后各分得椰子为y(6)个，依题意原来这堆椰子数为

x=5*y(1)+1

为了求取y(1)，实施递推。相邻两人所藏椰子数y(i)与y(i+1)之间的关系为

4*y(i)=5*y(i+1)+1 (i=1,2,…,5) （3） 习惯按时间顺序递推，递推式变形为从y(i)推出y(i+1)的形式，即

y(i+1)=(4*y(i)-1)/5 (i=1,2,…,5) （4） 第二个问题，递推的初始（边界）值如何确定？

问题本身没有初始（边界）条件限制，只要求上面5个递推方程所涉及的6个量y(i)都是正整数。也就是说，若有6个整数y(i)满足5个方程4*y(i)=5*y(i+1)+1， (i=1,2,…,5)即为所求的一个解。

首先y(1)赋初值k(取值从1开始递增)后推出y(2)，由y(2)推出y(3)，…，依此经5次递推得y(6)。如果某一次推出的不是整数，则中止继续往后推，返回k增1后赋值给y(1)，从头开始。如果5次递推都是整数，则输出原有椰子数5*y(1)+1后结束。

2） 递推描述

// 递推求解5个水手分椰子 #include #include void main()

{int i; double k,x,y[7]; i=1;k=1.0;y[1]=k; while(i<=5)

{ i++;y[i]=(4*y[i-1]-1)/5; // 递推求后一个水手时的椰子y(i) if(y[i]!=floor(y[i]))

{ k=k+1.0;y[1]=k;i=1;} // 若y(i)不是整数,k增1重试 }

x=5*y[1]+1;

printf(\"%d个水手分椰子，原有椰子至少有：%6.0f个.\\n\}

数据测试：

5个水手分椰子，原有椰子至少有： 15621个. 3-10 n个水手分椰子

有n个水手来到一个岛上，采了一堆椰子后，因为疲劳都睡着了。一段时间后，第一个水手醒来，悄悄地将椰子等分成n份，多出m个椰子，便给了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起，继续睡觉。不久，第二名水手醒来，同样将椰子了等分

成n份，恰好也多出m个，也给了猴子。然而自己也藏起一份，再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的m个给了猴子。第二天，n个水手醒来，发现椰子少了许多，心照不宣，便把剩下的椰子分成n份，恰好又多出m个，给了猴子。

对于给定的整数n,m(约定0求解思路选择从后往前递推n次，递推式为

y(i)=(n*y(i+1)+m)/(n-1) （i=1,2,…,n）

为精简试验的次数,确保从y(n+1)递推出整数y(n),显然y(n+1)的试验取值k只能取k%(n-1)=n-m-1。因而在循环前k赋初值k=n-m-1,以后k按n-1增值。

（2） n个水手分椰子递推描述

// n个水手分椰子，每次给猴子m个椰子 #include #include void main() {int i,m,n;

double k,x,y[20];

printf(\"请输入人数n(1printf(\"请输入每次所剩椰子数m(0i=n+1;k=n-m-1;y[n+1]=k; while(i>1) {i--;

y[i]=(y[i+1]*n+m)/(n-1); // 递推求前一个水手时的椰子 if(y[i]!=floor(y[i]))

{k=k+n-1;y[n+1]=k;i=n+1;} // 若y(i)不是整数,k增n-1重试 }

x=n*y[1]+m;

printf(\"原有椰子至少为：%8.0f个.\\n\ for(i=1;i<=n;i++)

{printf(\"第%2d个水手面临椰子：\

printf(\"%8.0f=%d*%8.0f+%d个,\ printf(\"藏%8.0f个.\\n\ }

printf(\"最后一起分时有椰子：\");

printf(\"%8.0f=%d*%8.0f+%d个.\ printf(\"每人分得%8.0f个.\\n\

}

数据测试：

请输入人数n(1请输入每次所剩椰子数m(0第 1个水手面临椰子： 15621=5* 3124+1个,藏 3124个. 第 2个水手面临椰子： 12496=5* 2499+1个,藏 2499个. 第 3个水手面临椰子： 9996=5* 1999+1个,藏 1999个. 第 4个水手面临椰子： 7996=5* 1599+1个,藏 1599个. 第 5个水手面临椰子： 6396=5* 1279+1个,藏 1279个.

最后一起分时有椰子： 5116=5* 1023+1个.每人分得 1023个. 4-1 阶乘的倒数和

阶乘n!定义: n!=1(n=1)；n!=n*(n-1)! (n>1) 设计求n!的递归函数，调用该函数求

s1111 1!2!n!（1） 设计要点

定义n!的递归函数f(n),在求和的k(1——n)循环中实施求和

s+=(double)1/f(k); (2) 递归描述

#include long f(int n) { long g;

if(n==1) g=1; else g=n*f(n-1); return(g); }

void main() { int k,n; double s=1;

printf(\" 请输入n: \");scanf(\"%d\ for(k=1;k<=n;k++) s+=(double)1/f(k); printf(\" s=%f \\n\ }

数据测试： 请输入n: 15 s=2.718282

4-2 递归求解裴波那契数列 已知裴波那契数列定义：

f1f21,fnfn1fn2(n2)

建立f数列的递归函数，求f数列的第n项与前n项之和。 （1） 递归设计

解：定义f数列的递归函数f(n),在求和的k(1——n)循环中实施求和 s+=f(k)。 （2） 递归描述

#include

long f(int n) { long g;

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;

printf(\" 请输入n: \");scanf(\"%d\ for(k=1;k<=n;k++) s+=f(k);

printf(\" f(%d)=%ld \\n\ printf(\" s=%ld \\n\ }

数据测试： 请输入n: 40 f(40)=102334155 s=267914295

4-3 递归求解b数列 已知b数列定义：

b11,b22,bn3bn12bn2(n2)

建立b数列的递归函数，求b数列的第n(n≤30)项与前n项之和。 解：#include long b(int n) { long g;

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;

printf(\" 请输入n: \");scanf(\"%d\ for(k=1;k<=n;k++) s+=b(k);

printf(\" b(%d)=%ld \\n\ printf(\" s=%ld \\n\ }

数据测试： 请输入n: 30 b(30)=536870912 s=1073741823

4-4 递归求解双递推摆动数列 已知递推数列：

a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数） 试建立递归，求该数列的第n(n<100000)项与前n项的和。 // 摆动数列 #include int a(int n) { int g;

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;

printf(\" 请输入n: \");scanf(\"%d\ for(k=1;k<=n;k++) s+=a(k);

printf(\" a(%d)=%d \\n\ printf(\" s=%ld \\n\ }

数据测试： 请输入n: 2014

a(2014)=107 s=215629

4-5 辉三角的递归求解

应用递归设计输出n行辉三角。 // 辉三角递归设计 void c(int a[],int n) {int i; if(n==0) a[1]=1; else if(n==1)

{a[1]=1;a[2]=1;} else

{c(a,n-1); a[n+1]=1;

for(i=n;i>=2;i--) a[i]=a[i]+a[i-1]; a[1]=1; } }

#include void main()

{ int i,j,k,n,a[100];

printf(\" 请输入辉三角的行数：\"); scanf(\"%d\for(j=0;j<=n;j++) {c(a,j);

for(k=1;k<=30-2*j;k++) printf(\" \"); for(i=1;i<=j;i++)

printf(\"%4d\ printf(\"%4d\\n\

} }

数据测试：

请输入辉三角的行数：10 即得10行辉三角（略）。

4-6 顺转矩阵的递归设计

当数阵的行数与列数不相等时，数阵称为矩阵。显然，顺转方阵是顺转矩阵的特例。图

4-8为5行6列的顺转矩阵。

试应用递归设计构造并输出任意指定m行×n列的顺转矩阵。

图4-8 5行6列顺转矩阵

（1） 递归设计要点

构建m行n列的旋转矩阵，设置二维数组a(m,n)，a[h][v]存放矩阵中第h行第v列的整数。

1） 递归属性

把m行n列矩阵从外到分圈，外圈是一个m-2行n-2列阶顺转矩阵，具有与原问题相同的特性属性。

因此，设置旋转矩阵递归函数t(b,s,d)，其中b为每个矩阵的起始位置；s=min(m,n)是矩阵行与列的最小值；d是为a数组赋值的整数。

b赋初值1（取数组下标从1开始，矩阵的起始位置为(1,1)。以后每一圈后进入下一矩阵，起始位置b需增1。

d从1开始递增1取值，分别赋值给数组的各元素，至m*n为止。 s从矩阵的阶数min(m,n)开始，每一圈后进入矩阵，s需减2。 s>1时，在函数t(b,s,d)中还需调用t(b+1,s-2,d)。 s=0时返回，作为递归的出口；

s=1且m=n，即矩阵为一方阵且只有一个数，显然为a[b][b]=d，返回； s>1时，在函数t(b,s,d)中还需调用t(b+1,s-2,d)。 2） 一圈中各元素赋值

递归函数t(b,s,d)中对矩阵的一圈的各边的各个元素赋值： 1） 一圈的上行n+1-2*b个元素，从左至右递增 for(j=1;j<=n+1-2*b;j++)

{ a[h][v]=d;v++;d++;} // 行号h不变，列号v递增，数d递增 2） 一圈的右列m+1-2*b个元素，从上至下递增 for(j=1;j<=m+1-2*b;j++)

{ a[h][v]=d;h++;d++;} // 列号v不变，行号h递增，数d递增 3） 一圈的下行n+1-2*b个元素，从右至左递增 for(j=1;j<=n+1-2*b;j++)

{ a[h][v]=d;v--;d++; // 行号h不变，列号v递减，数d递增 if(d>m*n) break; }

4） 一圈的右列m+1-2*b个元素，从下至上递增

for(j=1;j<=m+1-2*b;j++)

{ a[h][v]=d;h--;d++; // 列号v不变，行号h递减，数d递增 if(d>m*n) break; }

经以上4步，完成一圈的赋值。 3） 完善递归出口

注意到当s=min(m,n)为奇数时，最后一圈(s=1)只有一半。为避免最后一圈的另一半再赋值可能因数据覆盖导致出错，当完成整数d=m*n赋值后，即返回，作为递归的出口。

主程序中，只要带实参调用递归函数t(1,min(m,n),1)即可。 按圈赋值完成，输出m行n列的顺转矩阵。

（2） 递归描述

// m×n顺转矩阵递归设计 #include int m,n,a[20][20]={0}; void main()

{ int h,v,b,s,d;

printf(\" 数阵为m行n列，请确定m,n：\");scanf(\"%d,%d\s=m>n?n:m; b=1;d=1;

void t(int b,int s,int d); // 递归函数说明 t(b,s,d); // 调用递归函数 printf(\" %d×%d顺转矩阵: \\n\ for(h=1;h<=m;h++) {for(v=1;v<=n;v++)

printf(\" %3d\ printf(\"\\n\"); }

return; }

void t(int b,int s,int d) // 定义递归函数 { int j,h=b,v=b;

if(s<=0) return; // 递归出口

if(s==1 && m==n) // n=m且n为奇数时的递归出口 { a[h][v]=d;return;}

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++;

if(d>m*n) break; // min(m,n)为奇数且n>m时停止循环 }

for(j=1;j<=m+1-2*b;j++) // 一圈的左行从下至上递增 { a[h][v]=d;h--;d++;

if(d>m*n) break; // min(m,n)为偶数或者nt(b+1,s-2,d); // 调用一圈递归函数 }

数据测试：

数阵为m行n列，请确定m,n：7,10 7×10顺转矩阵:

1 2 3 4 5 6 7 8 9 10 30 31 32 33 34 35 36 37 38 11 29 52 53 54 55 56 57 58 39 12 28 51 66 67 68 69 70 59 40 13 27 50 65 64 63 62 61 60 41 14 26 49 48 47 46 45 44 43 42 15 25 24 23 22 21 20 19 18 17 16

4-7 顺转矩阵的递推设计

试把m×n顺转矩阵的递归设计转变为递推设计，并进行比较。 （1） 递推设计

对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。 设置i(1——d)循环，从外圈至圈，分4边进行递推赋值。 （2） 递推描述

// m×n数字旋转矩阵 #include #include void main()

{int i,j,c,d,h,v,m,n,s,a[30][30];

printf(\" m行n列矩阵,请确定m,n: \"); scanf(\"%d,%d\ c=n;

if(mfor(i=1;i<=d;i++) // 从外至第d圈赋值 {h++;

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;break;}

} // 赋值完成即行退出 for(h=m+1-i;h>=i+1;h--)

{ s++;a[h][v]=s; // d圈的首列从下至上赋值 if(s==m*n) {i=d;break;}

}

}

printf(\" %d行%d列旋转矩阵为:\\n\ for(i=1;i<=m;i++)

{ for(j=1;j<=n;j++) // 按m行n列输出矩阵 printf(\"%4d\ printf(\"\\n\"); } }

数据测试：

m行n列矩阵,请确定m,n: 8,9 8行9列旋转矩阵为:

1 2 3 4 5 6 7 8 9 30 31 32 33 34 35 36 37 10 29 52 53 54 55 56 57 38 11 28 51 66 67 68 69 58 39 12 27 50 65 72 71 70 59 40 13 26 49 64 63 62 61 60 41 14 25 48 47 46 45 44 43 42 15 24 23 22 21 20 19 18 17 16

4-8 复杂排列的递归实现

应用递归设计实现n个相同元素与另m个相同元素的所有排列。 （1） 设计要点

设置递归函数p(k)，1≤k≤m+n，元素a[k]取值为0或1。

当k=m+n时，作变量h统计“0”的个数。若h=m则打印输出一排列，并用s统计排列个数。然后回溯返回，继续。

当k// n个1与另m个0的排列 #include

int m,n,r,a[30]; long s=0; void main() { int p(int k);

printf(\" input n,m: \"); scanf(\"%d,%d\ printf(\" %d个1与%d个0的排列:\\n\

p(1); // 从第1个数开始 printf(\"\\n s=%ld \\n\输出排列的个数 }

// 排列递归函数 #include int p(int k) { int h,i,j; if(k<=m+n)

{ for(i=0;i<=1;i++)

{ a[k]=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++;

if(h==m) // 若0的个数为m个,输出一排列 { s++; printf(\" \"); for(j=1;j<=n+m;j++) printf(\"%d\ if(s%10==0) printf(\"\\n\"); } } else p(k+1); // 若没到n+m个数,则调用p(k+1)探索下一个数 } }

return s; }

数据测试：

input n,m: 3,4

3个1与4个0的排列: 0000111 0001011 0001101 0001110 0010011 0010101 0010110 0011001 0011010 0011100 0100011 0100101 0100110 0101001 0101010 0101100 0110001 0110010 0110100 0111000 1000011 1000101 1000110 1001001 1001010 1001100 1010001 1010010 1010100 1011000 1100001 1100010 1100100 1101000 1110000 s=35

4-9 指定零数拆分的递归设计

我们探讨求解一般的整数拆分问题：把指定整数ss拆分为ms个指定互不相同的整数b1,b2,,bms之和，共有多少种不同的拆分法？展示出所有这些拆分式.

（1） 递归设计要点

我们考虑从键盘输入的ms个数中取m（m建立组合递归函数c(k)，得到从1—ms这ms个数中取m(wmin≤m≤wmax)个数的所有组合{a[1],…,a[m]}，当这m个数之和b[a[1]]+…+b[a[m]]＝ss时，输出ss的一个拆分式，并用n统计拆分式的个数。

（2） 递归设计描述

// 和数ss，零数取自指定数 #include

int k,m,n,ms,ss,a[100],b[100]; void main()

{ int i,h,wmin,wmax; int c(int k);

printf(\" 输入和为：\"); scanf(\"%d\

printf(\" 输入零数的个数：\");scanf(\"%d\ printf(\" 依次由小到大输入零数：\\n\"); for(i=1;i<=ms;i++)

{ printf(\" b[%d]=\ for(h=0,i=1;i<=ms;i++) { h=h+b[i];

if(h>ss) {wmax=i-1;break;} }

if(i>ms) // 输入的零数组太小，程序返回 { printf(\" 输入的零数组太小！\\n\"); return; }

for(h=0,i=ms;i>=1;i--) { h=h+b[i];

if(h>ss) {wmin=ms-i;break;} }

for(m=wmin;m<=wmax;m++) // 从ms个数中取m个数 c(1);

printf(\"n=%d\\n\输出拆分种数n }

// 组合递归函数c(k) int c(int k) { int i,j,t; if(k<=m) { a[0]=0;

for(i=a[k-1]+1;i<=ms+k-m;i++)

{ a[k]=i; // 探索第k个数赋值i

{ if(k==m) // 若已到m个数时，检测m个数之和 { for(t=0,j=m;j>0;j--) t=t+b[a[j]];

if(t==ss) // 若m个数之和为ss,输出一个拆分式

{ n++;printf(\"%d=\

for(j=1;j}

else c(k+1); // 若没到m个数,则调用 c(k+1) } } }

return n; }

数据测试： 输入和为：15

输入零数的个数：5

依次由小到大输入零数：1，3，4，7，8 15= 7+ 8 15= 3+ 4+ 8 15= 1+ 3+ 4+ 7 n=3

5-1 倒桥本分数式

把1,2,...,9•这9个数字填入下式的9个方格中，数字不得重复,要求1不得填在各分数的分母，且式中各分数的分子分母没有大于1的公因数，使下面的分数等式成立

□□ □□ □□ ── + ─── = ── □ □ □

这一填数分数等式共有多少个解•? 解: 在桥本分数式回溯设计中修改

// 把1,2,...,9填入□□/□+□□/□=□□/□ #include void main()

{int g,i,k,u,t,a[10]; long m1,m2,m3; i=1;a[1]=1; while (1) {g=1;

for(k=i-1;k>=1;k--)

if(a[i]==a[k]) {g=0;break;} // 两数相同,标记g=0 if(i==9 && g==1 && 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]) // 判断等式 {printf(\" %d/%ld+%d/%ld\

printf(\"=%d/%ld \\n\} }

if(i<9 && g==1)

{i++;a[i]=1;continue;} // 不到9个数,往后继续 while(a[i]==9 && i>1) i--; // 往前回溯 if(a[i]==9 && i==1) break;

else a[i]++; // 至第1个数为9结束 }

}

数据测试： 41/3+89/6=57/2 74/3+95/6=81/2

5-2 10数字分数式

把0,1,2,...,9•这10个数字填入下式的10个方格中,要求：

□ □ □ ── + ─── = ── □□ □□□ □□

（1） 各数字不得重复；

（2） 数字“0”不得填在各分数的分子或分母的首位；

（3） 式中各分数为最简真分数，即分子分母没有大于1的公因数。 这一分数等式填数趣题究竟共有多少个解答•? 试应用回溯求出所有解答。 回溯设计：

设置a数组表示式中的10个数字，即

a(1)a(4)a(8) a(2)a(3)a(5)a(6)a(7)a(9)a(10)同时，记式中的3个分母分别为 m1=a(2)a(3)=a(2)*10+a(3)

m2=a(5)a(6)a(7)=a(5)*100+a(6)*10+a(7) m3=a(9)a(10)=a(9)*10+a(10)

在上述回溯设计基础上修改若干参数：

数字从9个增加到10个，因而i<9改为i<10；i==9改为i==10； 数组元素取值修改为从“0”开始，即a(1)=0；a(i)=0；

数字“0”不得在各分数的分子与分母的首位，即“0”只能在a(3),a(6),a(7)与a(10)这4个数字中，因而在输出解的条件中增加a(3)*a(6)*a(7)*a(10)=0。

此外，需增加判断3个分数是否为真分数的测试循环。 10数字分数式回溯描述： // 10数字分数式 #include void main()

{int g,i,k,s,t,u,a[11]; long m1,m2,m3; i=1;a[1]=0;s=0; while (1) {g=1;

for(k=i-1;k>=1;k--)

if(a[i]==a[k]) {g=0;break;} // 两数相同,标记g=0 if(i==10 && g==1 && a[3]*a[6]*a[7]*a[10]==0) {m1=a[2]*10+a[3];

m2=a[5]*100+a[6]*10+a[7]; m3=a[9]*10+a[10];

if(a[1]*m2*m3+a[4]*m1*m3==a[8]*m1*m2) // 判断等式

{t=0;

for(u=2;u<=9;u++) // 测试3个分数是否为真分数 {if(a[1]%u==0 && m1%u==0) {t=1;break;} if(a[4]%u==0 && m2%u==0) {t=1;break;} if(a[8]%u==0 && m3%u==0) {t=1;break;} } if(t==0)

{printf(\" %d/%ld+%d/\

printf(\"%ld=%d/%ld\\n \

}

} }

if(i<10 && g==1)

{i++;a[i]=0;continue;} // 不到10个数,往后继续 while(a[i]==9 && i>1) i--; // 往前回溯 if(a[i]==9 && i==1) break;

else a[i]++; // 至第1个数为9结束 } }

数据测试：

4/19+5/608=7/32

5-3 回溯探索n数素数和环

把前n个正整数摆成一个环，如果环中所有相邻的两个数之和都是一个素数，该环称为一个n项素数和环。

对于指定的n，构造并输出所有不同的素数和环。 回溯设计：

设置a数组在前n个正整数中取值。为避免重复输出，约定第1个数a(1)=1。

设置b数组标记奇素数。对指定的正整数n，首先用试商判别法，把2n围的奇素数标记为“1”，例如，b(7)=1表明7为素数。

在永真循环中，i从2开始至n递增，a[i]从2开始至n递增取值。

（1） 元素a(i)的取值是否可行，赋值t=1；然后进行判断： 若a(j)==a(i)（j=1,2,…,i-1），即a(i)与前面的a(j)相同，a(i)取值不行，标注t=0； 若 b(a(i)+a(i-1))!=1，即所取a(i)与其前一项之和不是素数，标注t=0。 （2） 若判断后保持t=1；说明a(i)取值可行。

此时若i已取到n ，且 b(a(n)+1)=1（即首尾项之和也是素数），输出一个解。 若i最后回溯至i=1，完成所有探索，跳出循环结束。

考虑到当n较大时，n项素数和环非常多，约定只输出5个解后提前结束。 回溯实现n项素数环描述： // 回溯求解n项素数和环 #include #include void main()

{ int t,i,j,n,k,s,a[2000],b[1000];

printf(\" 前n个正整数组成素数和环，请输入整数n: \"); scanf(\"%d\

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)

{t=1;break;} if(t==0) b[k]=1; // 奇数k为素数的标记 }

printf(\" 前%d个正整数组成素数和环,其中5个为：\\n\ a[1]=1;s=0; i=2;a[i]=2; while(1) {t=1;

for(j=1;jif(a[j]==a[i] || b[a[i]+a[i-1]]!=1) // 出现相同元素或非素时返回

{t=0;break;}

if(t && i==n && b[a[n]+1]==1) { s++;

printf(\" %d： 1\

for(j=2;j<=n;j++) printf(\ printf(\"\\n\"); if(s==5) return;

}

if(t && i{i++;a[i]=2;continue;}

while(a[i]==n && i>1) i--; // 实施回溯 if(i>1) a[i]++; else break; } }

数据测试：

前n个正整数组成素数和环，请输入整数n: 10 前10个正整数组成素数和环,其中5个为： 1： 1,2,3,4,7,6,5,8,9,10 2： 1,2,3,4,7,10,9,8,5,6 3： 1,2,3,4,9,8,5,6,7,10 4： 1,2,3,8,5,6,7,4,9,10 5： 1,2,3,8,5,6,7,10,9,4

5-4 枚举求解8数素数和环

枚举求解8项素数和环，并与回溯结果进行比较。 设计要点：

为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。

环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数812345678——18765432中枚举。注意到所有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项素数环的各项，打印输出。 枚举实现8项素数和环描述： // 8项素数和环枚举求解 #include #include 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个奇素数标记 printf(\" 8项素数和环：\\n\");

for(a=12345678;a<=18765432;a+=9) // 步长为9枚举8位数 {t=0;y=a;

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[9-k]=x; // 用g数组记录a的第k位数字

y=y/10;

}

for(k=1;k<=8;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1;

if(t==1) continue; // 有相同数字或相邻和非素，返回 s++;

printf(\" %d: 1\输出8项素数和环 for(k=2;k<=8;k++) printf(\ printf(\"\\n\"); } }

数据测试： 8项素数和环：

1: 1,2,3,8,5,6,7,4 2: 1,2,5,8,3,4,7,6 3: 1,4,7,6,5,8,3,2 4: 1,6,7,4,3,8,5,2

5-5 递归求解20数素数和环 应用递归求解20项素数和环。 // 递归求解素数环问题 #include #include

int n,a[2000],b[1000];long s=0; void main() { int t,j,k; int p(int k);

printf(\" 前n个正整数组成素数环，请输入整数n: \"); scanf(\"%d\

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)

{t=1;break;} if(t==0) b[k]=1; // 奇数k为素数的标记 }

a[1]=1;k=2; p(k);

printf(\" 前%d个正整数组成素数环，以上是其中3个。\\n\}

// 素数环递归函数p(k) #include int p(int k) { int i,j,u; if(k<=n)

{ for(i=2;i<=n;i++)

{ a[k]=i; // 探索第k个数赋值i for(u=0,j=1;j<=k-1;j++) if(a[k]==a[j] || b[a[k]+a[k-1]]==0) // 若出现重复数字

u=1; // 若第k数不可置i,则u=1

if(u==0) // 若第k数可置i,则检测是否到n个数

{ if(k==n && b[a[n]+a[1]]==1 && s<3) // 若已到n个数时打印出一个解 { s++;

printf(\" %ld: 1\ for (j=2;j<=n;j++) printf(\ printf(\"\\n\");

} else p(k+1); // 若没到m个数,则探索下一个数 p(k+1) } } }

return s; }

数据测试：

前n个正整数组成素数环，请输入整数n: 20

1: 1,2,3,4,7,6,5,8,9,10,13,16,15,14,17,20,11,12,19,18 2: 1,2,3,4,7,6,5,8,9,10,13,16,15,14,17,20,11,18,19,12 3: 1,2,3,4,7,6,5,8,9,10,13,18,19,12,11,20,17,14,15,16 前20个正整数组成素数环，以上是其中3个。

5-6 奇数位全错位问题

在1—n的全排列中，统计并展示偶数在其自然位而奇数全错位的所有排列。 （1） 回溯设计

在以上5.6回溯设计的基础上修改一个条件：把a[i]!=i修改为i%2=0 and a[i]==i or i%2!=0 and a[i]!=i，即只有偶数在自然位或奇数错位时才接着进行元素相等的判断，否则返回进行下一轮探索。

事实上可进一步简化，固定偶数位，例如2只能处于第2位，8只能处于第8位等，只对奇数进行探索和回溯，这样算法效率会大大增加。 （2） 算法描述

// 偶数不错位奇数全错位的所有排列 #include void main()

{ int n,i,j,t,a[30];long s=0;

printf(\" input n (2for(i=2;i<=n;i+=2) a[i]=i; // 先确定偶数的自然位 i=1;a[i]=3; while(1) { t=1; if(a[i]!=i) {for(j=1;jelse t=0; //当前奇数在自然位时返回 if(t && (i>=n-1)) {s++; for(j=1;j<=n;j++) printf(\"%d\ printf(\" \"); if(s%5==0) printf(\"\\n\"); } if(t && i0 && a[i]>=n-1) i-=2; // 调整或回溯 if(i>0) a[i]+=2; else break; }

printf(\"\\n s=%ld\\n\}

（3）算法测试

input n (n<10):8

32147658 32547618 32741658 52147638 52741638 52743618 72143658 72541638 72543618 s=9

考察输出的解，所有偶数都在自然位，所有奇数都错位。 5-7 德布鲁金序列

由2个0或1组成的数环，形成2个由相连n个0,1数字组成的二进制数恰在环序列中出现一次。这个序列被称作n阶德布鲁金（Debrujin）序列（约定n阶德布鲁金序列由n个0开头）。

例如，n=3时，即3阶德布鲁金序列有00010111与00011101两个解：

解00010111中每相连3个数字组成的二进制数依次为000，001，010，101，011，111，110，100，这8个数恰各出现一次。

解00011101中每相连3个数字组成的二进制数依次为000，001，011，111，110，101，010，100，这8个数恰各出现一次。

以上两个解，事实上是互为顺时针方向与逆时针方向的关系，其中一个解为顺时针方向，则另一个解为逆时针方向。

输入正整数n，求解n阶德布鲁金序列。 1. 回溯设计要点

在n阶德布鲁金环序列中，共有m=2个二进制数字。设置一维a数组，约定前n个数字为0，即a(0)=a(1)=…=a(n-1)=0，a(n)=1，a(m-1)=1。

n

n

n

应用回溯法探求a(n+1)～a(m-2)，这些元素取0或1。问题的解空间是由数字0或1组成的m-n-2位整数组，其约束条件是0的个数为m/2-n个，且没有相同的由相连n个数字组成的二进制数。

当i≤m-2时，a(i)从0取值； 当i＞n+1且a(i)=1时回溯； 当i=n+1且a(i)=1时退出。

当a(n+1)～a(m-2)已取数字时，设置h统计其中0的个数，若h≠m/2-n，则返回； 若h=m/2-n，则进一步通过循环计算m1,m2，判断是否有相同的由n个数字组成的二进制数。

若存有相同的由n个数字组成的二进制数，标注t=1；若不存在有相同的由n个数字组成的二进制数，保持t=0，作打印输出。

按以上所描述的回溯的参量：n ,(计算m=2^n)

元素初值：a(n)=1，a(m-1)=1，其余数组元素初值取0。 取值点：a(i)=0，各数组元素从0开始取值。 回溯点：a(i)=1，各数组元素取值至1时回溯。

约束条件1：i=m-2 且 h=m/2-n (其中h为a(i)中0的个数) 约束条件2：m1≠m2，m1与m2分别为环序列中所有由相连的n个数字组成的前后的二进制数。

2. 回溯设计描述

// n阶德布鲁金环序列回溯设计 #include #include void main()

{ int d,i,h,k,j,m,m1,m2,n,s,t,x,a[200]; printf(\"请输入（2for(k=1;k<=n;k++) m=m*2; // 计算m=2^n

s=0;

for(k=0;k<=m+n;k++) a[k]=0; a[n]=1;a[m-1]=1; i=n+1; while(1)

{if(i==m-2)

{for(h=0,j=n+1;j<=m-2;j++) if(a[j]==0) h++;

if(h==m/2-n) // 判别是否有m/2-n个零 {for(t=0,k=0;k<=m-2;k++) for(j=k+1;j<=m-1;j++)

{d=1;m1=0;m2=0; // 检验是否有相同的由n位二进制数

for(x=n-1;x>=0;x--)

{m1=m1+a[k+x]*d; m2=m2+a[j+x]*d;d=d*2;} if(m1==m2) {t=1;break;} } if(t==0)

{ s++; // 统计解的个数并输出解 printf(\"NO(%4d): \ for(j=0;j<=m-1;j++) printf(\"%d\ printf(\"\\n\"); } } } if(i{i++;a[i]=0;continue;}

while(a[i]==1 && i>n+1) i--; // 向前回溯 if(a[i]==1 && i==n+1) break; else a[i]=1; } }

数据测试：

输入n=5，得5阶德布鲁金环序列的前3个解：

NO( 1): 1111 NO( 2): 1111 NO( 3): 0111 ……

NO(2048): 1001

当输入n=3或n=4时，可得相应的3阶或4阶环序列。

当n＞5时，算法运行的时间迅速增加。解决5阶以上的德布鲁金环序列问题，算法有待进行优化与改进。

如果约定n阶德布鲁金环序列由n个1开头，算法应如果变通？ 5-8 回溯实现复杂排列

应用回溯设计探索从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 && k=n-m && i==n, 当取值达n个，其中n-m个零，且棋盘全控时输出一个解。

（2）回溯设计描述 #include #define N 30 void main()

{int i,j,k,n,m,t,a[N]; long s=0;

printf(\" input n (n<10):\"); scanf(\"%d\ printf(\" input m(1for(j=1;jif(a[j] && a[j]==a[i]) {t=0;break;} // 非零元素相同，则返回 if(t && k==n-m && i==n) // 已取n 个值且0的个数为n-m时输出解 {s++;

for(j=1;j<=n;j++) printf(\"%d\ printf(\" \");

if(s%10==0) printf(\"\\n\"); }

if(t && (kif(kelse a[i]=1; // 若0的个数已达到n-m，则不再取0了 continue; }

while(a[i]==n) i--; // 调整或回溯或终止 if(i>0)

{if(a[i]==0) k--; // 改变取值为0的元素值前先把0的个数k减1 a[i]++;

}

else break; }

printf(\"\\n s=%ld\\n\}

数据测试：

input n (n<10):5 input m(100123 00124 00125 00132 00134 00135 00142 00143 00145 00152 00153 00154 00213 00214 00215 00231 00234 00235 00241 00243 ……

53400 54001 54002 54003 54010 54020 54030 54100 54200 54300 s=600

5-9 8对夫妇的特殊拍照

一对夫妇邀请了7对夫妇朋友来家餐聚，东道主夫妇编为0号，其他各对按先后分别编为1，2，…，7号。

餐聚后拍照，摄影师要求这8对夫妇男左女右站在一排，东道主夫妇相邻排位在横排的正中央，其他各对排位，1号夫妇中间安排1个人,2号夫妇中间安排2个人,依此类推。

共有多少种拍照排队方式？ （1） 回溯设计要点

在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)。

返回条件修改为（当ja(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#include #include void main()

{int i,j,g,n,m,s,a[20];

printf(\" input n (2i=1;a[i]=0;s=0; while(1) {g=1;

for(j=1;jif(a[j]==a[i] || a[j]%n==a[i]%n && (a[j]>a[i] || a[j]+1!=i-j)) {g=0;break;} // 出现相同元素或同余小在后时返回

if(g && i==m && a[1]%nfor(j=1;j<=m;j++)

printf(\"%d\输出一个排列 printf(\" \"); } }

if(g && i{i++;a[i]=0;continue;}

while(a[i]==m-1) i--; // 回溯到前一个元素 if(i>0) a[i]++; else break; }

printf(\"\\n 共有解s=%d个。\\n\}

数据测试：

input n (235743 27624 72642 62732

6-1 枚举求解0-1背包问题

应用枚举求解6件物品的0-1背包问题，并与例6.2.1的优化结果进行比较。 （1）枚举设计

当给定物品种数（而不是从键盘输入确定）时，例如给定6种物品，每一种物品的重量w(k)与效益p(k)(1≤k≤6)可任意从键盘输入，应用枚举设计，可设计6重循环：第一种物

品的循环变量为x(1)，其取值为0或1；第2种物品的循环变量为x(2)，其取值也为0或1；……。因而枚举可由循环结构

for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) ……

for(x[6]=0;x[6]<=1;x[6]++)

来实现。

对每一组x(k)(1≤k≤6)，计算重量之和sw与效益之和sp，当满足条件sw≤c时，通过sp与pmax比较求取效益的最大值pmax。 （2）枚举描述

// 0/1背包问题枚举求解 #include #define N 7 void main()

{int p[N],w[N],x[N],y[N]; int i,k,c,cw,sw,sp,pmax;

printf(\"input c:\"); scanf(\"%d\输入已知条件 for(k=1;k<=6;k++)

{printf(\"input w%d,p%d:\ scanf(\"%d,%d\ } pmax=0;

for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) for(x[3]=0;x[3]<=1;x[3]++) for(x[4]=0;x[4]<=1;x[4]++) for(x[5]=0;x[5]<=1;x[5]++) for(x[6]=0;x[6]<=1;x[6]++)

{for(sw=0,sp=0,k=1;k<=6;k++)

{sw=sw+x[k]*w[k]; // 求物品重量之和 sp=sp+x[k]*p[k]; // 求物品效益之和 }

if(sw<=c && sp>pmax)

{pmax=sp;cw=sw; // 通过比较求最大效益pmax for(i=1;i<=6;i++) y[i]=x[i]; } }

printf(\"c=%d\\n\

printf(\" i w(i) p(i) \\n\"); for(i=1;i<=6;i++) // 以表格形式输出结果 if(y[i]==1)

printf(\"%2d %3d %3d \\n\ printf(\"sw=%d, pmax=%d \\n\}

数据测试： input c:50

input w1,p1:15,32 input w2,p2:17,37 input w3,p3:20,46 input w4,p4:12,26 input w5,p5:9,21 input w6,p6:14,30 c=50

i w(i) p(i) 2 17 37 3 20 46 4 12 26 sw=49, pmax=109

6-2 枚举求解二维0-1背包问题

应用枚举求解8物品二维0-1背包问题，并与6.2.2动态规划的结论进行比较。 （1）枚举设计

当给定物品种数（而不是从键盘输入确定）时，例如给定8种物品，每一种物品的重量w(k)、容积v(k)与效益p(k)(1≤k≤8)可任意从键盘输入，应用枚举设计，可设计8重循环：第一种物品的循环变量为x(1)，其取值为0或1；第2种物品的循环变量为x(2)，其取值也为0或1；……。因而枚举可由循环结构

for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) ……

for(x[8]=0;x[8]<=1;x[8]++)

来实现。

对每一组x(k)(1≤k≤8)，计算重量之和sw，容积之和sv与效益之和sp，当满足条件sw≤c且sv≤d时，通过sp与pmax比较求取效益的最大值pmax。

n

以上枚举设计的时间复杂度为O(2)，空间复杂度为O(n)。 （2）给定物品种数时的枚举设计

// 二维约束0/1背包问题枚举求解

#include #define N 9 void main()

{int p[N],w[N],v[N],x[N],y[N]; int i,k,c,d,cw,cv,sw,sv,sp,pmax;

printf(\"input c:\"); scanf(\"%d\输入已知条件 printf(\"input d:\"); scanf(\"%d\ for(k=1;k<=8;k++)

{printf(\"input w%d,v%d,p%d:\ scanf(\"%d,%d,%d\ } pmax=0;

for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) for(x[3]=0;x[3]<=1;x[3]++) for(x[4]=0;x[4]<=1;x[4]++) for(x[5]=0;x[5]<=1;x[5]++) for(x[6]=0;x[6]<=1;x[6]++) for(x[7]=0;x[7]<=1;x[7]++) for(x[8]=0;x[8]<=1;x[8]++)

{for(sw=0,sv=0,sp=0,k=1;k<=8;k++)

{sw=sw+x[k]*w[k]; // 求物品重量之和 sv=sv+x[k]*v[k]; // 求物品容积之和 sp=sp+x[k]*p[k]; // 求物品效益之和

}

if(sw<=c && sv<=d && sp>pmax)

{pmax=sp;cw=sw;cv=sv; // 通过比较求最大效益pmax for(i=1;i<=8;i++) y[i]=x[i]; } }

printf(\"c=%d, d=%d \\n\

printf(\" i w(i) v[i] p(i) \\n\");

for(i=1;i<=8;i++) // 以表格形式输出结果 if(y[i]==1)

printf(\"%2d %3d %3d %3d \\n\ printf(\"sw=%d, sv=%d, pmax=%d \\n\}

数据测试：

input c:40 input d:70

input w1,v1,p1:8,14,20 input w2,v2,p2:6,10,14 input w3,v3,p3:11,19,28 input w4,v4,p4:13,22,31 input w5,v5,p5:7,13,19 input w6,v6,p6:15,27,40 input w7,v7,p7:12,21,30 input w8,v8,p8:9,16,23 c=40, d=70

i w(i) v[i] p(i) 1 8 14 20 5 7 13 19 6 15 27 40 8 9 16 23 sw=39, sv=70, pmax=102

6-3 装载问题

有n个集装箱要装上两艘载重量分别为c1,c2的轮船，其中集装箱i的重量为 wi，且wi≤c1c2,c1,c2,wiN（不考虑集装箱的体积）。

i1n试求解一个合理的装载方案，把所有n个集装箱装上这两艘船。

1．动态规划设计要点 （1）问题求解策略

试采用以下的装载策略：首先将第一艘船尽可能装满；将剩余的集装箱装上第二艘船。 设装载量为c1的船最多可装maxc1，如果满足不等式

wic2≤maxc1≤c1maxc1≤c1,wimaxc1≤c2

i1i1nn则装载问题有解。

装载问题不一定总有解。例如，当n=3,c1=c2=50,w={15,40,40}，显然无法把这三个集装箱装上这两艘轮船。当问题无解时，作无解说明。 （2）动态规划设计

为了求取maxc1，应用动态规划设计。

目标函数：maxxiwi

i1n

n约束条件：xiwi≤c1,(xi{0,1},c1,wiN,i1,2,L,n)

i1按装载每一个集装箱为一个阶段，共分为n个阶段。

设m(i,j)为船C1还可载重量为j，可取集装箱编号围为：i,i+1,…,n的最大装载重量值。则

当0≤j不装入集装箱i，这时最大重量值为m(i+1,j)；

装入集装箱i，这时已增加重量w(i)，剩余载重量为j−w(i)，可以选择集装箱i+1,…,n来装，最大载重量值为m(i+1, j−w(i))+w(i)。我们期望的最大载重量值是两者中的最大者。于是有递推关系

0≤j＜w(i)m(i1,j)m(i,j)max(m(i1,j),m(i1,jw(i))w(i))j≥w(i)

以上j、c1与w(i)均为正整数，i=1,2,…,n, 所求最优值为m(1,c1)。

构造最优解即给出所得最优值时的装载方案。

if(m[i][cw]>m[i+1][cw]) （其中cw为当前的装载量，i=1,2, n−1） 装载w[i]; else 不装载w[i];

if(所载集装箱重量≠m(1,c1)) 装载w[n]. 2．动态规划描述 // 装载问题 #include #define N 100 void main()

{int n,c1,c2,i,j,s,cw,sw,w[N],m[N][N];

printf(\" input c1,c2: \"); scanf(\"%d,%d\ printf(\" input n: \"); scanf(\"%d\ s=0;

for(i=1;i<=n;i++) // 输入n个集装箱重量整数 {scanf(\"%d\

if(s>c1+c2) return; // 确保n个集装箱重量之和不大于c1+c2 printf(\"集装箱重量：%d\ for(i=2;i<=n;i++)

printf(\

printf(\"\\n n=%d,s=%d \

printf(\"\\n c1=%d, c2=%d \\n\ for(j=0;jfor(j=w[n];j<=c1;j++) m[n][j]=w[n]; // 首先计算m(n,j) for(i=n-1;i>=1;i--) // 逆推计算m(i,j) for(j=0;j<=c1;j++)

if(j>=w[i] && m[i+1][j]m[i][j]=m[i+1][j];

printf(\"maxc1=%d \\n\得最优值m(1,c1) if(m[1][c1]>=s-c2) // 判断是否有解 {printf(\"C1:\"); cw=m[1][c1];

for(sw=0,i=1;i<=n-1;i++) // 构造最优解，输出船1的装载 if(m[i][cw]>m[i+1][cw]) {cw-=w[i];sw+=w[i]; printf(\" %3d\

w[i]=0; // w(i)装载后赋0,为装船2作准备 }

if(m[1][c1]-sw==w[n]) {printf(\" %3d\ sw+=w[n]; w[n]=0; }

printf(\" (%d)\\n\ printf(\"C2:\");

for(sw=0,i=1;i<=n;i++) // 输出船2的装载 if(w[i]>0) {sw+=w[i];

printf(\" %3d\ }

printf(\" (%d)\\n\ }

else printf(\"此装载问题无解！\"); // 输出无解信息 }

数据测试：

input c1,c2: 120,126 input n: 15

26 19 24 13 10 20 15 12 6 5 22 7 17 20 27

集装箱重量：26, 19, 24, 13, 10, 20, 15, 12, 6, 5, 22, 7, 17, 20, 27 n=15,s=243 c1=120, c2=126

maxc1=120

C1: 15 12 22 7 17 20 27 (120) C2: 26 19 24 13 10 20 6 5 (123)

6-4 最小子段和的动态规划（递推实现）设计

应用递推实现动态规划求解：给定n个整数（可能为负整数）组成的序列a1,a2,L,an，求该序列形如ak（1≤i≤j≤n）段和的最小值。

kij递推实现动态规划求解： 1） 动态规划算法设计

设q(j)为序列前j项之和的最小值，即 q(j)min{a(k)}1ijkij(1jn)

由q[j]的定义,得q[j]的递推关系:

q(j1)a(j)q(j1)0 q(j)a(j)q(j1)0(1jn)

初始条件：

Q[0]=0 (没有项时，其值自然为0)。 （2） 动态规划描述

// 动态规划求最小子段和 #include #include #include void main()

{ int i,j,k,t,n,s,smin,q[1000],a[1000];

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\" 序列中n个正负项,请确定n:\"); scanf(\"%d\

printf(\" 序列的%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,\ }

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]printf(\"\\n 最小子段和为：%ld\\n\

for(s=0,i=k;i>=1;i--) // 反推最小和子段的首标i { s+=a[i]; if(s==smin) break; }

printf(\" 最小子段从序列的第%d项到第%d项。\\n\}

数据测试：

序列中n个正负项,请确定n:20 序列的20个整数为：

-14,43,40,15,34,10,-23,-22,33,16,8,-16,7,-37,37,21,26,-5,41,10, 最小子段和为：-46

最小子段从序列的第12项到第14项。

6-5 最小子段和的动态规划（递归设计）设计

应用递归实现动态规划求解：给定n个整数（可能为负整数）组成的序列a1,a2,L,an，求该序列形如ak段和的最小值。

kij递归实现动态规划求解： 1） 动态规划算法设计

设q(j)为序列前j项之和的最小值，即 q(j)min{ak}1ijkij(1jn)

由q(j)的定义,得q(j)的递推关系:

q(j1)aj q(j)ajq(j1)0q(j1)0(1jn)

初始条件：

q(0)=0 (没有项时，其值自然为0)。 （2） 动态规划递归描述

// 动态规划(递归)求最小子段和 #include #include #include int j,a[1000];

void main()

{ int i,k,n,t,s,smin; int q(int j);

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\" 序列中n个正负项,请确定n:\"); scanf(\"%d\ printf(\" 序列的%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,\ }

smin=1000;

for(j=1;j<=n;j++)

if(q(j)printf(\"\\n 最小子段和为：%ld\\n\

for(s=0,i=k;i>=1;i--) // 反推最小和子段的首标i { s+=a[i];

if(s==smin) break; }

printf(\" 最小子段从序列的第%d项到第%d项。\\n\}

int q(int j) // 定义递归函数q(j) {int f;

if(j==0) f=0; else

{ if(q(j-1)>=0) f=a[j];

else f=q(j-1)+a[j]; }

return f; }

数据测试：

序列中n个正负项,请确定n:20 序列的20个整数为：

-22,10,21,-11,-42,-28,-34,44,12,-6,31,5,23,5,-37,-36,-16,-32,19,-34, 最小子段和为：-137

最小子段从序列的第4项到第20项。

6-6 矩阵连乘问题

设矩阵A为p行q列，矩阵B为q行r列，求矩阵乘积AB共需做pqr次乘法。 试求n（n>2）个矩阵Mi(i1,2,,n)的乘积M1M2Mn的最少乘法次数。其中n与Mi的行、列数ri,ri1均从键盘输入。

解：注意ri1是Mi的列数，也是Mi1的行数，这样才能确保Mi与Mi1能相乘。 多个矩阵相乘，满足乘运算结合律。

例如，求M1M2M3，先求前两个矩阵的乘积(M1M2)M3，还是先求后两个的乘积M1(M2M3)，都是可以的，但两者的乘法次数不一定相等，我们要求最少乘法次数。

设m(i,j)是求乘积MiMi12Mj的最少乘法次数，则有递推关系 m(i,i1)r(i)r(i1)r(i2) (i+1=j)

m(i,j)min(m(i,k)m(k1,j)r(i)r(k1)r(j1)) (i≤k≤j,i初始（边界）条件：m(i,j)=0 (i=j) 最优值为m(1,n). 程序设计：

为递推方便，设置d=i-j。显然，1≤d≤n-1。 // 矩阵连乘

#include void main()

{int d,n,i,j,k,t,r[100],m[100][100];

printf(\" 请输入矩阵的个数 n :\"); scanf(\"%d\

printf(\" 请输入第1个矩阵的行数 :\"); scanf(\"%d\ for(i=1;i<=n-1;i++)

{printf(\" 请输入第%d个矩阵的列数，也是第%d个矩阵的行数 :\ scanf(\"%d\}

printf(\" 请输入第%d个矩阵的列数 :\ 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++)

{j=i+d;

m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1]; for(k=i+1;k{t=m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1]; if(tprintf(\" %d个矩阵连乘的乘法次数的最小值为：%d \\n\}

数据测试：

请输入矩阵的个数 n :7 请输入第1个矩阵的行数 :5

请输入第1个矩阵的列数，也是第2个矩阵的行数 :6 请输入第2个矩阵的列数，也是第3个矩阵的行数 :4 请输入第3个矩阵的列数，也是第4个矩阵的行数 :8 请输入第4个矩阵的列数，也是第5个矩阵的行数 :7 请输入第5个矩阵的列数，也是第6个矩阵的行数 :6 请输入第6个矩阵的列数，也是第7个矩阵的行数 :9 请输入第7个矩阵的列数 :7

7个矩阵连乘的乘法次数的最小值为：1120

6-7 边数值三角形的最短路径

已知边数值三角形每两点间距离如图6-6所示，每一个点可向左或向右两个去向，求三角形顶点到底边的最短路径。

图6-6 三角形边数值数据

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 #include #include void main() { int n,i,j,t;

int a[50][50],l[50][50],r[50][50];char st[50][50];

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\"请输入数字三角形的行数n:\"); scanf(\"%d\

for(i=1;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\ r[i][j]=rand()/1000+1;printf(\"%4d\ printf(\"\\n\");}

for(j=1;j<=37-4*(n+1);j++) printf(\" \"); for(j=1;j<=n+1;j++) printf(\" . \"); printf(\"底边\\n\\n\");

for(j=1;j<=n+1;j++) a[n+1][j]=0;

for(i=n;i>=1;i--) // 逆推求取最短路径 {for(j=1;j<=i;j++)

if(a[i+1][j]+l[i][j]{a[i][j]=a[i+1][j+1]+r[i][j];st[i][j]='r';} }

printf(\"\\n 最短路程为：%d\printf(\"\\n 最短路径为：顶点A \"); for(j=1,i=1;i<=n;i++) if(st[i][j]=='l')

printf(\"L-%d-\ else

{printf(\"R-%d-\printf(\"底边。\"); }

数据测试：输入图6-6数据，得 最短路程为：72

最短路径为：顶点A R-28-L-14-R-9-L-9-L-6-L-6-底边。

6-8 整币兑零的最少零币个数

用m种零币t(1),t(2),…,t(m)（单位为分，约定t(1)1. 动态规划设计要点

设g(i,j)为用零币t(1),…,t(i)找钱数j的最少零币个数。 若j若j>t[i] 且 g(i,j-t(i))=0时，也不能兑t(i),最少零币个数为g(i-1,j)。 若j%t(i)=0 或其它情形时：此时兑t(i),最少零币个数为g(i,j-t(i))+1。 显然有递推关系：

g(i,j)= g(i-1,j) (jt(i) and g(i,j-t(i))=0) g(i,j)= g(i,j-t(i))+1 (其余情形)

(i=1,2,…,m；j=1,2,…,n)

边界条件：

g(1,j)=0 （j%t(1)≠0） g(1,j)=1 （j%t(1)=0） 2. 动态规划描述

// 整币兑零,最少零币个数动态规划求解 #include void main() { int i,j,m,n;

static int t[12],g[20][1001];

printf(\" 请输入整币值(单位数):\"); // 输入处理数据 scanf(\"%d\

printf(\" 请输入零币种数:\"); scanf(\"%d\

printf(\" (从小至大依次输入每种零币值)\\n\"); for(i=1;i<=m;i++)

{ printf(\" 第%d种零币值(单位数):\ scanf(\"%d\

}

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(jt[i] && g[i][j-t[i]]==0) g[i][j]=g[i-1][j]; else

g[i][j]=g[i][j-t[i]]+1;

}

printf(\" 最少零币个数为:%d\\n\输出最少零币个数 }

数据测试：

请输入整币值(单位数):365 请输入零币种数:5

(从小至大依次输入每种零币值) 第1种零币值(单位数):1 第2种零币值(单位数):7 第3种零币值(单位数):19 第4种零币值(单位数):28 第5种零币值(单位数):57 最少零币个数为:11

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≤jf(i,k)=min(f(j,k−1)+a(j+1,i)) （k≤j前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得边界值为：

f(j,0)=a(1,j) (1≤j≤i)

为简单计，在程序设计中省略a数组，用变量d替代。 2） 动态规划描述

// 在一个数字串中插入r个+号，使和最小 #include #include void main() { char sr[16];

int n,i,j,k,u,r,b[16],t[16],c[16][16];

double f[17][17],d;

printf(\"请输入整数：\"); scanf(\"%s\ n=strlen(sr);

printf(\"请输入插入的+号个数r：\"); scanf(\"%d\ if(n<=r)

{printf(\" 输入的整数位数不够或r太大！ \"); return;}

printf(\"在整数%s中插入%d个+号，使和最小：\\n\ 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{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\输出最优解 if(kprintf(\"+\"); }

printf(\"=%.0f\\n \输出最优值

}

数据测试：

请输入整数：2356

请输入插入的+号个数r：8

在整数2356中插入8个+号，使和最小： 36+54+37+8+59+4+12+35+6=251

6-10 枚举求解插入乘号的最大积

作为验证，应用于组合枚举求取插入乘号的乘积最大值及其乘积式。 1. 枚举设计要点

注意到n个数字之间共有n−1个插入乘号的位置，在这n−1个位置中组合选取r个位置t(1),t(2),…,t(r)供插入乘号。计算被这r个乘号分成的r+1个整数的积d。每计算一个d与存储最大乘积的变量max比较，若d>max，则作赋值max=d，同时乘号位置t数组赋值给s数组。

完成所有组合枚举后，得乘积最大值max，按s数组的值打印插入乘号的乘积式及其最大乘积max。

2. 基于组合枚举描述

// 基于组合枚举的插入乘号设计 #include #define N 30 void main() {char b[11];

int n,i,k,u,r,t[N],s[N]; long y,d,max;

printf(\" 请输入整数：\"); scanf(\"%s\ for(n=0,i=0;b[i]!='\\0';i++) n++;

printf(\" 请输入插入的乘号个数r：\"); scanf(\"%d\ printf(\" 在整数%s中插入%d个乘号，使乘积最大：\\n\ i=1;t[i]=1;t[0]=0;t[r+1]=n;max=0; while(1) {if(i==r)

{for(y=1,k=1;k<=r+1;k++)

{for(d=0,u=t[k-1]+1;u<=t[k];u++) d=d*10+b[u-1]-48;

y=y*d; // 求各段数之积,以便比较求最大

}

if(y>max) {max=y;

for(k=0;k<=r+1;k++) s[k]=t[k]; } }

else {i++; t[i]=t[i-1]+1; continue;}

while(t[i]==n-r+i-1) i--; // 调整或回溯或终止 if(i>0) t[i]++; else break; }

for(k=1;k<=r+1;k++)

{for(d=0,u=s[k-1]+1;u<=s[k];u++) d=d*10+b[u-1]-48;

if(k==r+1)

printf(\"%ld\// 输出插入*号后的乘积式 else

printf(\"%ld*\

}

printf(\"=%ld\}

数据测试：

输入整数：637829156

请输入插入的乘号个数r：4

在整数637829156中插入4个乘号，使乘积最大： 63*7*82*915*6=198529380

7-1 删除数字求最小值

给定一个高精度正整数b, 去掉其中k个数字后按原数字次序组成一个新的正整数。对给定的b,k，寻找一种删除数字方案，使得剩下的数字组成的新数最小。

解：应用贪心算法设计求解。 （1） 设计要点

操作对象为n位高精度数，存储在数组a中。

在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象，这就是所要选取的贪心策略。

当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部升序或相等，则删除右边的大数字。

当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。

若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。

3. 贪心算法描述

// 贪心删数字达最小 #include void main()

{ int i,j,k,m,n,x,a[200]; char b[200];

printf(\" 请输入整数：\");

scanf(\"%s\以字符串方式输入高精度整数 for(n=0,i=0;b[i]!='\\0';i++) {n++;a[i]=b[i]-48;}

printf(\" 删除数字个数: \");scanf(\"%d\

printf(\" 以上%d位整数中删除%d个数字分别为: \ i=0;m=0;x=0;

while(k>x && m==0) {i=i+1;

if(a[i-1]>a[i]) // 出现递减, 删除左边的数字 { printf(\"%d, \

for(j=i-1;j<=n-x-2;j++)// 删除一数字后，后面的数字前移 a[j]=a[j+1];

x=x+1; // x统计删除数字的个数 i=0; // 从头开始查递增区间 }

if(i==n-x-1) m=1; // 已无递减区间,m=1脱离循环 }

printf(\"\\n 删除后所得最小数: \");

for(i=1;i<=n-k;i++) // 打印剩下的左边n−k个数字 printf(\"%d\ printf(\"\\n\"); }

请输入整数：283

删除数字个数: 5

以上14位整数中删除5个数字分别为: 7, 6, 2, 9, 7, 删除后所得最小数: 136046283

7-2 3项埃及分数式

本章应用贪心算法构造了埃及分数式：3/11=1/5+1/15+1/165，试用枚举法求解分数m/d的所有3项埃及分数式，约定各项分母不超过200。

（1） 设计要点

设指定的分数m/d的三个埃及分数的分母为a,b,c (a重循环实施枚举。

确定a循环的起始值a1与终止值a2为:

1m2a1a1dzdz (即把b,c全放大为z) mz2d a23d1 (即把b,c全缩减为a)

m 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 void main()

{int a1,a2,a,b,c,d,m,n,z; double x,y; printf(\" 确定分数m/d,请输入m,d: \"); scanf(\"%d,%d\

printf(\" 请确定分母的上界：\"); scanf(\"%d\

printf( \" 把分数%d/%d分解为三个埃及分数之和: \\n\ printf( \" (分母不得为%d,最大分母不超过%d) \\n\ n=0;

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) // 输出分解式 { n=n+1;

printf(\" NO%d: %d/%d=1/%d\ printf(\"+1/%d+1/%d \\n\ break; } }

printf(\" 共上述%d个分解式.\\n\}

确定分数m/d,请输入m,d: 5,17

请确定分母的上界：1000

把分数5/17分解为三个埃及分数之和: (分母不得为17,最大分母不超过1000) NO1: 5/17=1/4+1/24+1/408 NO2: 5/17=1/4+1/28+1/119 NO3: 5/17=1/4+1/34+1/68 NO4: 5/17=1/6+1/8+1/408 共上述4个分解式.

7-3 最优装载

有n个集装箱要装上一载重量为c的轮船，其中集装箱i的重量为wi。要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

（1） 设计要点 约束条件：

xwii1nnic

目标函数：maxx,ii1xi{0,1}

其中xi=0表示不装船，xi=1表示装船。

贪心策略：对n个集装箱按重量升序排序，重量最轻者先装。

（2） 贪心设计描述

1） 调用递归的主程序设计 // 最优装载

#include int w[20001]; void main()

{ int i,n,k,c,s,cw;

void qk(int m1,int m2); // 函数声明 printf(\" input c:\"); scanf(\"%d\ printf(\" input n:\"); scanf(\"%d\ printf(\" 依次输入%d个集装箱重量：\\n\ for(i=1;i<=n;i++)

scanf(\"%d\输入每一集装箱重量 qk(1,n); // 调用rk函数排序

cw=c;s=0;k=0; // cw为轮船还可装的重量 printf(\" 以下集装箱装船：\"); // 输出装船结果 for(i=1;i<=n;i++)

{ if(w[i]>cw) break;

cw=cw-w[i]; s+=w[i]; k++;

printf(\" %d,\}

printf(\"\\n 最多装%d个集装箱，装船重量为：%d \\n\}

2) 分区交换排序递归函数设计

void qk(int m1,int m2) // 快速排序递归函数 { int i,j; if(m1{ i=m1;j=m2;w[0]=w[i]; // 定义第i个数作为分区基准 while(i!=j)

{ while(w[j]>=w[0] && j>i) // 从右至左逐个检查是否大于基准 j=j-1;

if(ii) // 从左至右逐个检查是否小于基准 i=i+1;

if(i(3) 数据测试 input c:100 input n:10

依次输入10个集装箱重量：18 21 14 9 25 32 16 12 26 20 以下集装箱装船： 9, 12, 14, 16, 18, 20, 最多装6个集装箱，装船重量为：89

7-4 币种统计

单位给每个职工发工资（约定精确到元），为了保证不至临时兑换零钱，且使每个职工取款的数最少，请在取工资前统计所有职工所需的各种票面（约定为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 void main()

{ int i,j,m,n,gz; 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}; printf(\" 请输入人数：\"); scanf(\"%d\

printf(\" 请依次输入各职工的工资(正整数)：\\n\"); for(i=1;i<=n;i++)

{ printf(\" 输入第%d个职工工资：\

scanf(\"%d\ su=su+gz;

for(j=1;j<=7;j++)

{ m=gz/b[j]; s[j]=s[j]+m; gz=gz-m*b[j]; } }

printf(\" 单位工资总额为: %ld \\n\ printf(\" 各面值币的统计结果: \\n\"); su1=0;

for(j=1;j<=7;j++)

{ printf(\" %3d---%3d \\n\ su1=su1+b[j]*s[j]; }

if(su==su1) printf(\" 经检验统计无误！\\n\"); }

请输入人数：3

请依次输入各职工的工资(正整数)： 输入第1个职工工资：4680 输入第2个职工工资：5742 输入第3个职工工资：7356 单位工资总额为: 17778 各面值币的统计结果: 100---176 50--- 2 20--- 3

10--- 1 5--- 1 2--- 1 1--- 1

经检验统计无误！

7-5 显示两端的取数游戏

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=2*n,2*n-1,…,k） 这样处理，为后续取数提供方便。

取数完毕，比较最后得分即可评定胜负。

2

算法操作为取数与移位，时间复杂度为O(n)。 （2） 算法描述

// 模拟A,B取数游戏 #include #include #include void main()

{ int j,k,n,sa,sb,t,c[1000],d[1000]; sa=sb=0;

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\" 序列中2n个整数, 请确定n:\"); scanf(\"%d\ for(j=1;j<=2*n;j++)

{c[j]=rand()%(2*n)+2; // 随机产生2n个整数 d[j]=c[j]; }

printf(\" 序列的%d个整数已产生，每次只显示两端整数。\\n \

printf(\" A先取，A，B轮流取，直到取完。\\n\"); for(k=1;k<=2*n;k++)

{if(k<2*n) printf(\"\\n 两端数为：%2d,%2d \ else printf(\"\\n 只剩下1个数：%2d \ if(k%2==1)

{t=d[k];

if(tfor(j=2*n;j>=k+1;j--) d[j]=d[j-1]; }

sa=sa+t; printf(\" A取数%2d; \

}

else

{ printf(\" B取数:\");scanf(\"%d\

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];}

} else

{ printf(\" A取数有误，重新开始！\"); return;} } }

printf(\" 原序列的%d个整数为：\ for(j=1;j<=2*n;j++) printf(\" %d\

printf(\"\\n 最后得分为 A=%d, B=%d,\ if(sa>sb) printf(\" 此游戏A胜！\\n\"); else if(sa序列中2n个整数, 请确定n:6

序列的12个整数已产生，每次只显示两端整数。 A先取，A，B轮流取，直到取完。 两端数为： 5, 3 A取数 5; 两端数为： 3, 3 B取数:3。 两端数为： 3, 3 A取数 3; 两端数为： 2, 3 B取数:3。 两端数为： 2,10 A取数10; 两端数为： 2,13 B取数:13。

两端数为： 2,13 A取数13; 两端数为： 2, 9 B取数:9。 两端数为： 2, 7 A取数 7; 两端数为： 2,10 B取数:10。 两端数为： 2, 4 A取数 4; 只剩下1个数： 2 B取数:2。

原序列的12个整数为： 5 3 2 4 10 7 9 13 13 10 3 3 最后得分为 A=42, B=40, 此游戏A胜！

7-6 全显取数游戏

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按贪心策略取数，即取两端数的较大者。

2

5） 算法操作为取数与移位，时间复杂度为O(n)。 （2） 算法描述

// 所有数显示，B先取不败取数游戏 #include #include #include void main()

{ int j,k,n,d1,d2,s1,s2,t,a[1000]; s1=s2=0;

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\" 序列中2n个整数, 请确定n:\"); scanf(\"%d\

printf(\" 序列的%d个整数依次为：\ for(j=1;j<=2*n;j++)

{a[j]=rand()%(2*n)+2; // 随机产生并显示2n个整数 printf(\" %d\ if(j%2==1) s1+=a[j]; else s2+=a[j]; }

printf(\"\\n B先取。\"); d1=1;d2=2*n; if(s1>s2)

{printf(\" B取数%d; \\n\ else

{printf(\" B取数%d; \\n\ printf(\" 请在剩余项：\");

for(j=d1;j<=d2;j++) printf(\" %d\ printf(\" 的两端取数。\\n\"); for(k=2;k<=n;k++) { if(a[d1]>a[d2])

{ printf(\" A取数: %d;\

printf(\" B取数: %d; \\n\ d1=d1+2; } else

{ printf(\" A取数: %d;\

printf(\" B取数: %d; \\n\ d2=d2-2; }

printf(\" 请在剩余项：\");

for(j=d1;j<=d2;j++) printf(\" %d\ printf(\" 的两端数取数。\\n\"); }

printf(\" A最后取数: %d;\\n\ if(s1>s2)

{ printf(\" 最后得分为:B=%d, A=%d \\n\ printf(\" 此游戏B胜！\\n\"); }

else if(s1{ printf(\" 最后得分为:B=%d, A=%d\\n\ printf(\" 此游戏B胜！\\n\");

} else

{ printf(\" 最后得分为:B=%d, A=%d\\n\ printf(\" 此游戏B与A平手！\\n\"); } }

序列中2n个整数, 请确定n:6

序列的12个整数依次为： 12 12 13 7 5 7 4 8 9 12 10 8 B先取。 B取数8;

请在剩余项： 12 12 13 7 5 7 4 8 9 12 10 的两端取数。 A取数: 12; B取数: 12;

请在剩余项： 13 7 5 7 4 8 9 12 10 的两端数取数。 A取数: 13; B取数: 7;

请在剩余项： 5 7 4 8 9 12 10 的两端数取数。 A取数: 10; B取数: 12;

请在剩余项： 5 7 4 8 9 的两端数取数。 A取数: 9; B取数: 8;

请在剩余项： 5 7 4 的两端数取数。 A取数: 5; B取数: 7;

请在剩余项： 4 的两端数取数。 A最后取数: 4;

最后得分为:B=54, A=53 此游戏B胜！

8-1 整除p的连写数

从1开始按正整数的顺序不间断连续写下去所成的整数称为连写数。要使连写数1112…m（连写到整数m）能被指定的整数p（<1000）整除，m至少为多大？

（1）模拟除法设计要点

要使连写数1234...m能被键盘指定的整数n整除，模拟整数的除法操作: 设被除数为a，除数为n，商为b，余数为c，则 b=a/n, c=a-b*n 或 c=a%n

当c≠0且m为1位数时,a=c*10+m 作为下一轮的被除数继续。

当c≠0一般地m为一个t位数时,则分解为t次(即循环t次)按上述操作完成。 直至c=0时，连写数能被n整除，作打印输出增连数1234...m除以n所得的商。 在整个模拟除法过程中,m按顺序增1。 （2） 模拟除法描述

// 模拟除法求连写数 #include #include void main()

{ int c,d,e,j,k,t,w,m,n; long a; printf(\" A给出整数n: \"); scanf(\"%d\

c=0;m=0; while(1) {m++;j=m;

{e=j/10;t=1;w=1;

while(e>0) // 对每一个j,计算t {e=e/10;t=t*10;w=w+1;} e=j;

for(k=1;k<=w;k++) // 对每一个j,分位试商 {d=e/t;e=e%t;t=t/10; a=c*10+d;c=a%n;} } if(c==0)

{printf(\" B寻求的整数m：%d. \\n\ printf(\" 连写数12...%d/%d=\ c=12;

for(j=3;j<=m;j++) {e=j/10;t=1;w=1;

while(e>0) // 对每一个j,计算t {e=e/10;t=t*10;w=w+1;} e=j;

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\ } printf(\"\\n\"); }

if(c==0) break; } }

A给出整数n: 23

B寻求的整数m：33. 连写数12...33/23=9271

8-2 03串积

程序设计爱好者A，B进行计算游戏：

B任给一个正整数b，A寻求另一个整数a, 使a 与b的积最小且全为0与3组成的数。 （1） 设计要点

按01串积设计，我们应用求余数判别。

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)*3，通过累加求和得k转化的整个二进制数除以b的余数s。

4） 判别余数s 是否被b整除：若s%b=0, 即找到所求最小的01串积。 5） a 从高位开始除以b的商存储在d数组，实施整数除法运算： x=e*10+a[j]; // e为上轮余数，x为被除数 d[j]=x/b; // d为a 从高位开始除以b的商 e=x%b; // e为试商余数

去掉d数组的高位“0”后，输出d即为所寻求的数。 6） 最后从高位开始打印a数组，即为01串积。 （2） 算法描述 // 03串积

#include void main()

{ int b,e,i,j,t,x,a[2000],d[2000],c[2000]; long k,s;

printf(\" B给出整数 b:\"); scanf(\"%d\ c[1]=1;

for(i=2;i<200;i++)

c[i]=10*c[i-1]%b; // c(i)为右边第i位1除以b的余数 k=1; while(1)

{ k++;j=k;i=0;s=0; while(j>0)

{i++;a[i]=j%2;

s+=a[i]*c[i]*3;j=j/2; s=s%b; // 除2取余法转化为二进制 }

if(s%b==0)

{for(e=0,j=i;j>=1;j--) { x=e*10+a[j]*3;

d[j]=x/b; e=x%b; // a 从高位开始除以b的商为d } j=i;

while(d[j]==0) j--; // 去掉d数组的高位“0” printf(\" A寻求整数a：\"); for(t=j;t>=1;t--)

printf(\"%d\

printf(\"\\n a*b的最小03串积为：\"); for(t=i;t>=1;t--)

printf(\"%d\ printf(\"\\n\");

break; }

} }

B给出整数 b:2013

A寻求整数a：1641

a*b的最小03串积为：3303333

8-3 阶乘与乘方的高精计算

通过选择,分别准确计算阶乘n!与乘方n^m的值。 （1） 竖式乘除设计要点

该题的综合高精度计算,主要操作是竖式乘计算。 乘模拟： x=a[j]*b+f;f=x/10;a[j]=x%10;

其中f是进位数。乘数b随所选计算种类而不同： 当选\"^\"计算幂m^n时,b固定为b=m。 当选\"!\"计算阶乘时,b=i,(i=1,2,...n)。 （2） 算法描述

// 高精度准确计算阶乘,乘方 #define MAX 6000 #include void main()

{ int d,i,j,x,b,f,n,t,m,a[MAX]; char z;

printf(\" !: 计算阶乘 n! \\n\"); printf(\" ^: 计算乘方 m^n \\n\"); printf(\"-------------------\\n\");

printf(\" 请选择(!,^):\");scanf(\"%c\选择运算类型 if(z!='!' && z!='^')

{ printf(\" 选择错误！\");return;} if(z=='!') printf(\"计算n!:\\n\"); if(z=='^') printf(\"计算m^n:\\n\");

for(i=0;iprintf(\" 请输入整数n:\"); scanf(\"%d\if(z!='!')

{ printf(\" 请输入整数m:\"); scanf(\"%d\if(n==0) n=1; t=1;

if(z=='!') printf(\"%d!=\if(z=='^') printf(\"%d^%d=\

for(d=0,i=t;i<=n;i++) // 实施竖式乘模拟 { if(z=='^')b=m;else b=i;

for(f=0,j=0;j<=d || f>0;j++)

{x=a[j]*b+f;f=x/10;a[j]=x%10;}

d=j-1; }

for(f=1,j=d;j>=0;j--) { printf(\"%d\

if(f++%60==0) printf(\"\\n\"); }

printf(\"\\n所得结果共%d位.\\n\}

（3）算法测试与说明

请选择(!,^):! 计算n!:

请输入整数n:40 40!=000

所得结果共48位.

以上乘模拟设计数组预定计算到6000位，必要时可进行增减。乘模拟的时间复杂度为O(nz)，其中z为乘积的位数。

8-4 排列组合数的高精计算

通过选择,分别准确计算排列数p(n,m)与组合数c(n,m)的值。 （1） 竖式乘除设计要点

该题的综合高精度计算,主要操作是竖式乘除计算。 乘模拟： x=a[j]*b+f;f=x/10;a[j]=x%10;

其中f是进位数。当选\"p\"计算排列数p(n,m)时,b=i,(i=n-m+1,...,n)。 在选 \"c\"计算组合数c(n,m)时才会有除模拟。 除模拟： x=f*10+a[j];a[j]=x/i;f=x%i;

其中f为余数，x是被除数，除数i是变化的，商为x/i。 （2） 算法描述

// 高精度准确计算排列,组合 #define MAX 6000 #include void main()

{ int d,i,j,x,b,f,n,t,m,a[MAX]; char z;

printf(\" p: 计算排列数 p(n,m) \\n\"); printf(\" c: 计算组合数 c(n,m) \\n\"); printf(\"-------------------\\n\");

printf(\" 请选择(p,c):\");scanf(\"%c\选择运算类型 if( z!='p' && z!='c')

{ printf(\" 选择错误！\");return;} if(z=='p') printf(\"计算p(n,m):\\n\"); if(z=='c') printf(\"计算c(n,m):\\n\"); for(i=0;iprintf(\" 请输入整数n:\"); scanf(\"%d\if(z!='!')

{printf(\" 请输入整数m:\"); scanf(\"%d\if(n==0) n=1; t=1;

if(z=='p') printf(\"p(%d,%d)=\if(z=='c') printf(\"c(%d,%d)==n-m+1;

for(d=0,i=t;i<=n;i++) // 实施竖式乘模拟 {if(z=='^')b=m;else b=i;

for(f=0,j=0;j<=d || f>0;j++)

{x=a[j]*b+f;f=x/10;a[j]=x%10;}

d=j-1; }

if(z=='c') // 当求组合数时实施竖式除模拟 {for(i=m;i>=2;i--)

{ for(f=0,j=d;j>=0;j--)

{x=f*10+a[j];a[j]=x/i;f=x%i;} while(a[d]==0)d--; }

}

for(f=1,j=d;j>=0;j--) { printf(\"%d\

if(f++%60==0) printf(\"\\n\");

}

printf(\"\\n所得结果共%d位.\\n\}

（3）算法测试与说明

请选择(p,c):c 计算c(n,m): 请输入整数n:100 请输入整数m:40 c(100,40)=0

所得结果共29位.

以上乘模拟设计数组预定计算到6000位，必要时可进行增减。

8-5 H形数积

定义形如ab…bc的数叫做H形数，其中a为高位，c为低位，数字为b的为中间段，其位数为H形数的位数减2（至少有1位）。

事实上所有3位数都是H形数，把3位数的中间数字多次重复可得4位以上的H形数。 给出一个整数x(约定x<=9999），寻求一个最小的乘数k(k>1),使得乘积k*x=n为H形数。

（1） 设计求解要点

作为H形数的特例，当a=b=c时，H形数即为全码相同数。 1) 定义余数统计函数

定义余数函数br(x,a,b,m,c)：首数字a后为m位数字b再接尾数字c的H形数除以x所得的余数。

设试商过程中余数为y,y赋初值a(首位数字);

进入m位b试商的循环: y=(y*10+b)%x,每一次试商求出除x的余数; 最后, y=(10*y+c)%x, 完成至末位数字c的试商. 所得y返回,即余数函数br(x,a,b,m,c)的值. 2） 从小到大枚举设计

事实上，面临两种枚举选择：

第一种是从2开始，从小到大枚举乘数k。

考虑到有时k非常大，第一种枚举时间复杂度比较高。同时，检测所得积是否为H形数也颇为繁复。

第二种枚举H形数：其位数le起点是x的位数h（≥3），步长为1递增。然后设置循环枚举三个数字a,b,c。

35

而第二种枚举的循环次数为：le*10,通常le<100，总循环次数<10，我们实施第二种枚举。

3）检测输出

检测：若br(x,a,b,m,c)＝0, 还要考察是否大于x。为避免输出x本身因（k>1）,而需加上条件：(a>t && le==h || le>h)，即所得余数为0的数若位数le与x的位数h相同，则

其首位a要大于x的首位t；或其位数le大于x的位数h。

满足以上条件，首先应用模拟除运算输出乘数k。然后根据参数a,b,le-2,c输出H形数积。

（2） 算法描述

// 枚举求解指定数x的最小H形数积 #include

long br(long x,int a,int b,int m,int c); void main()

{ long x; int a,b,c,d,e,h,j,t,le;

printf(\" 请输入个位数字不为5的奇数x: \"); scanf(\"%ld\ t=x;h=1;e=0; while(t>9)

{t=t/10;h++;} // 整数x的位数为h,最高位数字为t le=(h>3)?h:3; while(1)

{ for(a=1;a<=9;a++) for(b=0;b<=9;b++) for(c=0;c<=9;c++)

if(br(x,a,b,le-2,c)==0 && (a>t && le==h || le>h)) { printf(\" 寻求的最小乘数 k=\"); d=a;h=0; while(dprintf(\形数积 n=%d\输出最小H形数积 if(le<=8) for(j=1;j<=le-2;j++) printf(\"%d\ else

printf(\"%d(%d)\ printf(\"%d\\n\ } le++; } }

long br(long x,int a,int b,int m,int c) // 定义余数统计函数

{ long f,s,sb;int j; f=1;sb=0;s=0; for(j=1;j<=m;j++) { f=10*f;

if(f>x) f=f%x;

sb=(sb+f)%x; // 统计中段k位b除以x的余数sb }

s=(f*10*a)%x; // 统计首位a除以x的余数s s=(s+(sb*b)+c)%x; // 确定整个H形数除以x的余数s return(s); } （3） 算法测试与分析

请输入个位数字不为5的奇数x: 2013 寻求的最小乘数 k=3367, H形数积 n=6777771 请输入个位数字不为5的奇数x: 2099 寻求的最小乘数k=1082, H形数积 n=21(22)8

以上程序求取最小H形数积，事实上对于每个数x，存在一系列的H形数积。在输出解前加上一个记数器，对指定的整数x，可计算并输出x的前m个二部数积。

例如，计算并输出2013的前5个乘数k，所得积为H形数: 1: 寻求乘数 k=3367, H形数积 n=6777771 2: 寻求乘数 k=17111, H形数积 n=34444443 3: 寻求乘数 k=34222, H形数积 n=68888886 4: 寻求乘数 k=347739692, H形数积 n=69(10)6 5: 寻求乘数 k=3367003367, H形数积 n=67(11)1

8-6 自然对数底e的高精计算

自然对数的底数e是一个无限不循环小数, 是“自然律”的一种量的表达，在科学技术中用得非常多。学习了高数后我们知道，以e为底数的对数是最简的，用它是最“自然”的，所以叫“自然对数”。

试设计程序计算自然对数的底e，精确到小数点后指定的x位。 （1） 算法设计要点 （1）选择计算公式

计算自然对数的底e，我们选用以下公式：

e111111111(1(1)) （1） 1!2!n!23n（2）确定计算项数

其次，要依据输入的计算位数x确定所要加的项数n。显然，若n太小，不能保证计算所需的精度；若n太大，会导致作过多的无效计算。

可证明，式中分式第n项之后的所有余项之和Rnan。因此，只要选取n，满足a11nxn!10即可。即只要使

lg2lg3lgnx （2）

于是可设置对数累加实现计算到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。 （2） 自然对数的底e模拟描述 // 高精度计算自然对数的底e #include #include void main()

{ double s; int x,n,c,i,j,d,l,a[5000]; printf(\" 请输入精确位数:\"); scanf(\"%d\

for(s=0,n=2;n<=5000;n++) // 累加确定计算的项数n { s=s+log10(n);

if (s>x) break; }

for(i=0;i<=x+2;i++)

a[i]=0;

for(c=1,j=n;j>=2;j--) // 按公式分步计算 {d=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(\" e=%d.\// 遂位输出计算结果 for(l=10,i=1;i<=x;i++) { printf(\"%d\

l++;

if (l%10==0) printf(\" \"); if (l%50==0) printf(\"\\n\"); }

printf(\"\\n\"); }

数据测试： 请输入精确位数:100

e=2.7182818284 5904523536 0287471352 6624977572 4709369995 9574966967 6277240766 3035354759 4571382178 5251664274

8-7 进站时间模拟

根据统计资料，车站进站口行安检通过一个人的时间至少为2.4——3.8秒。现有n个人排队进站，大约需多少时间？ （1）随机模拟算法

一个人的进站时间至少为2.4——3.8秒，设时间精确到小数点后一位，则每一个人进站的时间在2.4,2.5,2.6,…,3.8等数据中随机选取。

应用C语言库函数srand(t)进行随机数发生器初始化，其中t为所取的时间秒数。这样可避免随机数从相同的整数取值。

为简化设计，把每一个人的进站时间乘以10转化为整数，即每一个人的进站时间为rand()%15+24，随机取值围为24,25,26,…,38，单位为1/10秒。则n个人的进站时间为

for(t=0,i=1;i<=n;i++) t=t+rand()%15+24;

求和完成后，转化为时间的分，秒输出。 （2）进站时间模拟描述

// 进站时间模拟 #include #include #include void main()

{int i,n,m,s; long t;

printf(\"请输入进站人数n：\");

scanf(\"%d\

t=time(0)%1000;srand(t); // 随机数发生器初始化 printf(\"%d人进站所需时间约为:\ for(t=0,i=1;i<=n;i++)

t=t+rand()%15+24; // 计算进站时间总和 m=t/600;

s=(t%600)/10; // 转化为m分s秒输出 printf(\"%d分%d秒.\\n\}

数据测试：

请输入进站人数n：245

245人进站所需时间约为:12分45秒.

8-8 模拟扑克升级发牌

模拟扑克升级发牌，把含有大小王的共54牌随机分发给4家，每家12，底牌保留6。 （1）模拟算法设计 1）模拟花色与点数

模拟发牌必须注意随机性。所发的一牌是草花还是红心，是随机的；是5点还是J点，也是随机的。

同时要注意不可重复性。如果在一局的发牌中出现两个黑桃K就是笑话了。•同时局与局之间必须作到互不相同，如果某两局牌雷同，也不符合发牌要求。

为此，对应4种花色，设置随机整数x，对应取值为1～4。对应每种花色的13点，设置随机整数y，对应取值为1～13。为避免重复，把x与y组合为三位数：z=x*100+y，并存放在数组m(54)中。发第i+1牌，产生一个x与y，得一个三位数z，数z与已有的i个数组元素m(0),m(1),…m(i−1)逐一进行比较，若不相同则打印与x,y对应的牌(相当于发一牌)后，然后赋值给m(i)，作为以后发牌的比较之用。若有相同的，则重新产生随机整数x与y得z，与m数组值进行比较。

2）模拟大小王

注意到在升级扑克中有大小王，它的出现给程序设计带来一定的难度。大小王的出现也是随机的，为此，把随机整数y的取值放宽到0～13，则z可能有•100，200，300，400。定义z=200时对应大王，z=100时对应小王，同上作打印与赋值处理•。若z=300或400，则返回重新产生x与y。

3） 打印输出

打印直接应用C语言中ASCII码1～6的字符显示大小王与各花色。设置字符数组d，打印点数时把y=1、13、12、11分别转化为A、K、Q、J。

为实现真正的随机，根据时间的不同，设置t=time()%10000;srand(t) 初始化随机数发生器，从而达到真正随机的目的。 （2） 发扑克牌描述

// 发扑克升级牌,有大小王,4个人每人12牌,底牌6. #include #include #include void main()

{int x,y,z,t,i,j,k,m[55]; char d[]=\" A234567891JQK\";

printf(\"\\n 东 南 西 北\\n\");

t=time(0)%1000;srand(t); // 随机数发生器初始化 m[0]=0;

for(i=1;i<=54;i++)

{if(i==49) printf(\" 底牌: \\n\"); for(j=1;j<=10000;j++)

{x=rand()%4+1; y=rand()%14; z=x*100+y;

if(z==300 || z==400) continue; t=0;

for(k=0;k<=i-1;k++)

if(z==m[k]) {t=1;break;} // 确保牌不重复 if(t==0)

{m[i]=z;break;} }

if(z==100 || z==200) printf(\" %c \ else if(y==10) printf(\" %c10 \ else printf(\" %c%c \ if(i%4==0) printf(\"\\n\"); }

printf(\"\\n\"); }

数据测试：

9-1 n皇后问题的递归设计

试应用递归设计求解n皇后问题。 (1) 递归设计要点

递归函数put(k)的设计针对n皇后问题数字解的n个整数中的第k个整数a(k)展开的。

设a(k)取值为i(1,2,…,n)，a(k)逐一与已取值的a(j)(j=1,2,,k-1)比较：

若满足a(k)=a(j) or |a(k)-a(j)|=k-j，即同行或同列或同对角线，显然不符合题意要求，记u=1, 即所取a(k)不妥，表示该行该列已放不下皇后，于是a(k)继续下一个i取值。

否则，符合题意要求，保持u=0, 即所取a(k)妥当。此时检测所完成的行数： 若k=n成立，完成了n行，按格式输出一个数字解，并用s统计解的个数； 若k=n不成立，未完成n行，继续调用put(k+1)，探讨下一行取值。 若a(k)取值到n仍不妥，则返回（回溯）到调用put(k)的put(k-1)环境下，继续a(k-1)的下一个取值。

最后若a(1)取值到n仍不妥，则返回到调用put(1)的主程序，输出解的个数s或“无解”,程序结束。

(2) 递归描述

// n皇后问题递归求解

#include int n,a[30],s=0; void main() { int put(int k);

printf(\" 求解n 皇后问题，请确定n: \"); scanf(\"%d\

put(1); // 从第1行开始放皇后 if(s>0)

printf(\"\\n %d皇后问题共有以上%d个解。\\n\ else

printf(\" %d皇后问题无解。\\n\

}

// n皇后问题递归函数 #include int put(int k) { int i,j,u; if(k<=n)

{ for(i=1;i<=n;i++) // 探索第k行从第1格开始放皇后 { a[k]=i;

for(u=0,j=1;j<=k-1;j++) if(a[k]==a[j] || abs(a[k]-a[j])==k-j )

u=1; // 若第k行第i格放不下,则置u=1

if(u==0) // 若第k行第i格可放,则检测是否满n行 { if(k==n) // 若已放满到n行时，则打印出一个解 { s++; printf(\" \"); for (j=1;j<=n;j++) printf(\"%d\ if(s%5==0) printf(\"\\n\"); }

else put(k+1); // 若没放满n行,则放下一行 put(k+1) } } }

return s; }

3. 算法测试

运行程序,输入n=8，可得八皇后问题的92个解。

求解n 皇后问题，请确定n: 6 246135 362514 415263 531642 6皇后问题共有以上4个解。

9-2 r个皇后全控n×m棋盘

在n×m的棋盘上，如何放置r个皇后，可以控制棋盘的每一个格子而皇后互相之间不能攻击呢（即任意两个皇后不允许处在同一横排,同一纵列,也不允许处在同一与棋盘边框成45度角的斜线上）？

求解r个皇后控制n×m广义棋盘问题，这类问题是r个皇后全控n×n棋盘的引申，是高斯八皇后问题与n后问题的进一步推广。 （1） 回溯设计要点

皇后控制棋盘问题比以上的n皇后问题求解难度更大些。 采用回溯法探求，设置a数组,数组元素a(i)表示第i行的皇后位于第a(i)列，当a(i)=0

时表该行没有皇后。

求r个皇后控制n×m棋盘的一个解，即寻求a数组的一组取值,该组取值中n-r个元素值为0，r个元素的值大于零且互不相同(即没有任两个皇后在同一列),第i个元素与第k个元素相差不为abs(i-k),(即任两个皇后不在同一45度角的斜线上)，且这r个元素可控制整个棋盘。

程序的回溯进程同n皇后问题设计，所不同的是所有元素从0 开始取值，且n个元素中要确保n-r个取0。

检验是否控制整个棋盘的检测函数g()设计基本同前。设置二维数组b(n,m)表示棋盘的每一格,数组的每一个元素置0。对一个皇后放置a(f)，其控制的围的每一个格置1。所有r个皇后控制完成后，检验b数组是否全为1：只要有一个不为1，即不是全控；若b数组所有元素都为1，棋盘全控，打印输出数字解，同时用变量s统计解的个数。

(2) r个皇后控制n×m棋盘回溯描述 // r个皇后控制n×m棋盘问题 #include #include int n,m,a[20]; void main()

{ int i,h,k,d,j,r,s,x; int g();

printf(\" 确定n行×m列棋盘，请输入n,m: \"); scanf(\"%d,%d\

printf(\" r个皇后控制，请输入r(r<＝n,m): \"); scanf(\"%d\ i=1;s=0;a[1]=0; while (1) {d=1;

for(k=i-1;k>=1;k--) {x=a[i]-a[k];

if(a[k]!=0 && x==0 || a[i]*a[k]>0 && abs(x)==i-k) d=0;

} // 非零元素不能相同，不同对角线 if(i==n && d==1) {h=0;

for(j=1;j<=n;j++) if(a[j]==0) h++;

if(h==n-r) // 判别是否有n-r个零

{if(g()==0) // 调用检测棋盘是否全控函数 {s++;

for(j=1;j<=n;j++) printf(\"%d\

printf(\" \"); if(s%5==0) printf(\"\\n\"); } } }

if(icontinue; }

while(a[i]==m && i>1) i--; // 向前回溯 if(a[i]==m && i==1) break; else a[i]=a[i]+1; }

if(s>0) // 输出解的个数

printf(\"\\n %d个皇后控制%d×%d棋盘,共有以上%d个解。\\n\ else

printf(\"\\n 该问题无解！\\n\"); }

// 检测棋盘是否全控函数 int g()

{int c,f,j,b[20][20],t=0; for(c=1;c<=n;c++) for(j=1;j<=m;j++) b[c][j]=0;

for(f=1;f<=n;f++) if(a[f]!=0)

{for(c=1;c<=n;c++) b[c][a[f]]=1; // 控制同行 for(j=1;j<=m;j++)

{b[f][j]=1; // 控制同列 if(f+abs(a[f]-j)<=n) // 控制两斜线 b[f+abs(a[f]-j)][j]=1; if(f-abs(a[f]-j)>=1) b[f-abs(a[f]-j)][j]=1; } }

for(c=1;c<=n;c++) for(j=1;j<=m;j++)

if(b[c][j]==0) t=1; // 棋盘中有一格不能控制，t=1

return t; }

（3） 算法测试与说明

确定n行×m列棋盘，请输入n,m: 10,9

r个皇后控制，请输入r(r<＝n,m): 5

0309050107 0701050903 3090501070 7010509030 5个皇后控制10×9棋盘,共有以上4个解。

当输入m=n时，即为控制n×n棋盘。

注意：当列数超过9时，为避免对“10”产生错误理解，输出解的各个整数间需用空格或“，”分开。

9-3 翻转硬币问题的递归设计

递归设计求解一般的m×n硬币矩阵，实施整行或整列翻转，如何实施翻转，使得矩阵正面朝上的硬币尽可能多。

算法描述：

#include #include #include

int a[100][100]; // 模拟硬币的矩阵 int b[100]; // 标记那些列翻 int r[100]; // 标记那些行翻

int mb[100],mr[100];// 记录最优行列翻转情况 int n,m,cln; void init()

{ FILE *fp;char fname[30]; int i,j;

printf(\" 请输入数据文件名: \");

gets(fname); // 输入数据文件 if((fp=fopen(fname,\"r\"))==NULL)

{ printf( \"The file was not opened！\" ); return; } printf(\" 请输入矩阵行、列数: \"); scanf(\"%d,%d\ for(i=1;i<=m;i++) for(j=1;j<=n;j++)

{ fscanf(fp,\"%d\从文件读数据到二维a数组 cln+=a[i][j]; }

printf(\" 游戏开始时硬币矩阵为(1表示正面，0表示反面)：\\n\"); for(i=1;i<=m;i++) // 输出矩阵的原始数据

{ for(j=1;j<=n;j++)

printf(\"%3d\ printf(\"\\n\"); }

printf(\" 共有%4d个正面。\\n\}

void colm(int y) // 某一列的翻转操作 { int i;

for( i=1;i<=m;i++) a[i][y]=1-a[i][y]; }

void line(int x) // 某一行的翻转操作 {int i;

for( i=1;i<=n;i++) a[x][i]=1-a[x][i]; }

int sums(int x){// 统计第x行的和 int i,sum=0;

for( i=1;i<=n;i++) sum+=a[x][i]; return sum; }

void dfs(int t)

{ int i,j,sum=0,x1,x2;

if(t==n+1)// 递归终止条件 {

for( i=1;ifor( i=1;i<=m;i++){// 贪心求出每一行的最值 x1 = sums(i); // 第i行不翻转时的和 line(i); // 把第i行翻转 x2 = sums(i); // 第i行翻转时的和 line(i); // 第i行翻转还原

if(x1>x2){ r[i]=0; sum+=x1;}// 记录第i行的最优选择 else {r[i]=1; sum+=x2;} }

for( i=1;iif(sum>cln)// 更新最优值并记录行列翻转情况 {for(i=1;i<=m;i++) mr[i]=r[i]; for(j=1;j<=n;j++) mb[j]=b[j]; cln=sum; }

return; }

b[t]=0;// 第t列不翻 dfs(t+1);

b[t]=1;// 第t列翻 dfs(t+1); }

void main() {

int i,j; init(); dfs(1);

printf(\"翻转下列行：\");

for(i=1;i<=m;i++) if(mr[i]){ printf(\"%d \ printf(\"\\n翻转下列列：\");

for(j=1;j<=n;j++) if(mb[j]) { printf(\"%d \ printf(\"\\n最优硬币矩阵为： \\n\"); for(i=1;i<=m;i++) {for(j=1;j<=n;j++)

printf(\"%3d\ printf(\"\\n\"); }

printf(\" 此时硬币正面最多为：%d\\n\}

输入数据文件自定。

9-4 矩阵中的最小对称路径

给一个n行n列网格，每一个格子里有一个正整数。

你需要从网格的左上角走到右下角，确定数字之和最小的最优对称路径。路径中每一步能往右、往下，也能往左、往上走到相邻格子，不能斜着走，也不能走出网格。为了美观，你经过的路径必须关于“左下-右上”对角线对称。图9-6是一个6×6网格上的对称路径。

图9-6 对称路径示意

对于给定的n×n网格，在所有合法路径中求路径各格子数字之和最小的最优对称路径。 输入n(2≤n≤50)及相应的n阶方阵,输出方阵中最优对称路径的数字和，并输出其中一条最优对称路径。 （1） 设计要点

设（i,j）为网格中第i行第j列所在的格，注意到“左下-右上”对角线为i+j=n+1,因而网格(i,j)与网格(n+1-j,n+1-i)关于“左下右上”对角线对称。

设置二维数组a(i,j)存储(i,j)格中的数字；

二维数组b(i,j)为从(i,j)格至(n+1-j,n+1-i)格这一对称路径段的最小数字和；

二维数组c(i,j)存储(i,j)格下一步的位置数：该位置数为4位数，其中高2位整数为下一格的行号，低2位整数为下一格的列号；

一维数组f(k)为最优路径中网格右下部第k步的位置：该位置数为4位数，其中高2位整数为行号，低2位整数为列号。

显然，最优对称路径的数字和为b(1,1)。 应用动态规划求路径的最优值。 初始条件：

for(i=1;i<=n;i++) // 对角线上b数组赋初值 b[i][n+1-i]=a[i][n+1-i];

b数组初始化：按斜行初步逆推得b[i][j], c[i][j] 每一格与上下左右四格比较，优化b数组： 产生最优路径：

i=1;j=1;m=0;

while(i+je=c[i][j];i=e/100;j=e%100;f[m]=(n+1-j)*100+(n+1-i); }

for(k=m;k>=1;k--) // 对称输出路径的右下部分 { e=f[k];i=e/100;j=e%100;printf(\" %d\printf(\" %d\\n\}

（2） 算法描述

// 可上下左右的最小对称路径t5 #include void main()

{ int d,e,m,n,i,j,k,t,a[100][100],b[100][100],c[100][100],f[100]; printf(\" 请输入数字网格的行数n:\"); scanf(\"%d\ for(i=1;i<=n;i++) for(j=1;j<=n;j++)

scanf(\"%d\键盘输入产生n阶方阵 for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++)

printf(\"%4d\打印n阶方阵 printf(\"\\n\"); }

for(i=1;i<=n;i++) // 对角线上b数组赋初值 b[i][n+1-i]=a[i][n+1-i];

for(i=n-1;i>=1;i--) // 按斜行初步逆推得b[i][j] for(j=n-i;j>=1;j--)

{ if(b[i+1][j]{ b[i][j]=a[i][j]+a[n+1-j][n+1-i]+b[i+1][j];

c[i][j]=(i+1)*100+j; }

else

{ b[i][j]=a[i][j]+a[n+1-j][n+1-i]+b[i][j+1]; t=1;

while(t>0) // 与上下左右格比较，没有任何调整时保持t=0,结束循环 { t=0;

for(i=n-1;i>=1;i--) for(j=n-i;j>=1;j--) { d=b[i][j];

if(j>1 && b[i][j-1]+a[i][j]+a[n+1-j][n+1-i]if(jif(i>1 && b[i-1][j]+a[i][j]+a[n+1-j][n+1-i]if(iprintf(\" 最小路径数和为:%d\\n\输出最小路径数和 printf(\" 一条最小路径为: \\n \"); // 输出一条最小的路径 i=1;j=1;m=0;

while(i+je=c[i][j];i=e/100;j=e%100;f[m]=(n+1-j)*100+(n+1-i); c[i][j]=i*100+j+1; }

}

}

for(k=m;k>=1;k--) // 对称输出路径的右下部分 { e=f[k];i=e/100;j=e%100;printf(\" %d\printf(\" %d\\n\}

（3） 数据测试

1 18 18 1 1 1 1 18 18 18 18 1 1 18 1 18 18 1 18 18 18 18 18 1 18 2 2 18 1 18 18 18 18 18 1 18 18 1 18 1 18 18 18 18 18 1 18 1 2 18 18 1 1 1 1 18 1 1 2 18 18 18 18 18 18 1 18 18 18 18 18 18 2 1 2 18 1 18 18 18 18 18 2 1 18 2 1 1 18 18 18 18 18 1 18 18 18 18 18 18 18 18 18 18 1 1 1 1 1 18 18 18 18 18 18 18 18 18 18 1 1 最小路径数和为:70 一条最小路径为:

1 1 1 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1 1 18 1 1 1 1 1 1 1 1 2 2 1 2 1 2 1 1 1 1 1 1 1 1

9-5 指定入出口马步遍历的递归设计

应用递归探索在n×m棋盘中，指定入口即起点(x,y)与指定出口即终点(x1,y1)的所有马步遍历路径。

(1) 递归设计

递归过程中，栈保留了递归过程中的各个状态的参数，因而可省略以上回溯设计中的t,x,y数组。

控制马步规则的a、b数组同前，对当前位置（x,y），马步可跳的位置有8个（x+a(k),y+b(k)）,其中

a(k)={ 2, 1,-1,-2,-2,-1, 1, 2}

b(k)={ 1, 2, 2, 1,-1,-2,-2,-1}（k=1,2,…,8）

二维数组d(i,j)表示棋盘第i行第j列格(i,j)(1≤i≤n,1≤j≤m)的信息，若d(i,j)=0，表示(i,j)位置为空，可供走位。

建立递归函数t(g,x,y)，对候选位置(u,v)，若满足可走条件 1≤u≤n,1≤v≤m，且d(u,v)=0 则走第g步：d(u,v)=g。

在控制k循环中若对所有k=1,2,…,8，候选位置(u,v)均不满足以上可走条件(或位置出界，或位置非空)，则通过实施回溯，继续前一步的检测。

若第g步全部8个位置已走完，或者第g步满足可走条件且g=m*n时，即已实现遍历，则回溯到g-1步。对于g-1步，k=k+1后继续检测，直到k>8时回溯到前一步。若第g步已经成功且g到回溯到第1步结束。

在探索第g步的下一个位置时，应该取消当前成功所走马步：d(u,v)=0，为后面的探索留出空位。探索中每实现一次遍历，则以二维表形式输出一个遍历解，并且取消最后的成功马步后，即d(u,v)=0，回溯到前一步。

若回溯完成仍没有实现马步遍历，即解的个数仍为z=0，则输出未找到遍历解信息，否则输出解的总数。

若回溯完成仍没有实现遍历，即仍为q=0，输出未找到遍历解信息。 （2）递归回溯剖析

以下以3行4列，起点为（1,1）为例说明递归回溯过程： g= 2, k=1, d(3,2)= 2

g= 3, k=3, d(2,4)= 3 （k=1,2时无法走位） g= 4, k=6, d(1,2)= 4 （k=1——5时无法走位） g= 5, k=1, d(3,3)= 5

g= 6, k=4, d(1,4)= 6 （k=1——3时无法走位） g= 7, k=7, d(2,2)= 7 （k=1——6时无法走位） g= 8, k=2, d(3,4)= 8 （k=1时无法走位）

g= 9, k=5, d(1,3)= 9 （k=1——4时无法走位） g=10, k=7, d(2,1)=10 （k=1——6时无法走位）

以上进展顺利，只有11与12两个数未放，程序调用tr(11,u,v)时，对于k=1——8，条件均不满足走位，即g=11无格可放。因而回到g=10, 取消d(2,1)=10, 使d(2,1)=0。

接着g=10，k从原有的7增1,即k=8，也无法走位，即无法放置10； 回溯，取消d(1,3)=9, 使d(1,3)=0。 接着g=9，k从原有的5增1,即k=6,…… 直到12个整数全部旋转完成，输出遍历解。

(3) 递归描述

// 递归探求马步遍历 #include

int k,n,m,x1,y1,z,d[20][20]={0}; void main() { int g,x,y;

void tr(int g,int x,int y);

printf(\" 棋盘为n行m列，请输入n,m: \"); scanf(\"%d,%d\ printf(\" 指定入口位置(x,y)，请输入x,y: \"); scanf(\"%d,%d\ printf(\" 指定出口位置(x1,y1)，请输入x1,y1: \"); scanf(\"%d,%d\

g=2;z=0;

d[x][y]=1; // 起始位置赋初值 tr(g,x,y); // 调用tr(g,x,y) if(z>0)

printf(\" 共有以上%d个指定马步路径. \\n\ else printf(\" 未找到指定路径! \\n\"); }

// 指定马步路径递归函数 void tr(int g,int x,int y) {int i,j,u,v,k=0;

static int a[9]={0,2,1,-1,-2,-2,-1,1,2}; // 按可能8位给a,b赋初值 static int b[9]={0,1,2,2,1,-1,-2,-2,-1}; while(k<8)

{ k=k+1;u=x+a[k];v=y+b[k]; // 探索第k个可能位置 if(u>0 && u<=n && v>0 && v<=m && d[u][v]==0)

{ d[u][v]=g; // 所选位走第g步 if(g==m*n)

{if(u==x1 && v==y1) { z++;

printf(\" 第%d个指定马步路径为: \\n\

for(i=1;i<=n;i++) // 以二维形式输出一个解 {for(j=1;j<=m;j++)

printf(\"%4d\ printf(\"\\n\"); } }

d[u][v]=0; break; }

else tr(g+1,u,v); // 递归进行下一步探索 d[u][v]=0; // 实施回溯 }

} }

（4） 数据测试

棋盘为n行m列，请输入n,m: 5,5 指定入口位置(x,y)，请输入x,y: 1,1 指定出口位置(x1,y1)，请输入x1,y1: 5,5 第1个指定马步遍历为:

1 12 17 6 23 16 7 22 11 18 21 2 13 24 5 8 15 4 19 10 3 20 9 14 25 ……

第56个指定马步遍历为:

1 18 13 8 3 12 7 2 21 14 17 22 19 4 9 6 11 24 15 20 23 16 5 10 25

共有以上56个指定马步路径.

9-6 设置障碍的马步遍历

在一个n行m列棋盘中，任指定一处障碍。请设计递归程序，寻求一条起点为（1,1）的越过障碍的遍历路径。

// 递归探求n×m棋盘设置障碍的马步遍历 #include

int k,n,m,x1,y1,d[20][20]={0}; long z; void main() { int g,q,x,y;

int tr(int g,int x,int y);

printf(\" 棋盘为n行m列，请输入n,m: \"); scanf(\"%d,%d\

printf(\" 指定障碍位置(x1,y1)，请输入x1,y1: \"); scanf(\"%d,%d\

g=2;z=0;x=1;y=1; // 起点约定为(1,1) d[x][y]=1;

q=tr(g,x,y); // 调用tr(g,x,y) if(z>0)

printf(\" 共有以上%d个指定马步遍历. \\n\ else printf(\" 未找到指定马步遍历! \\n\"); }

// 马步路径递归函数 int tr(int g,int x,int y) {int i,j,u,v,k=0,q=0;

int a[9]={0,2,1,-1,-2,-2,-1,1,2}; // 按可能8位给a,b赋初值 int b[9]={0,1,2,2,1,-1,-2,-2,-1}; while(q==0 && k<8)

{ k=k+1;u=x+a[k];v=y+b[k]; // 探索第k个可能位置

if(u>0 && u<=n && v>0 && v<=m && d[u][v]==0 && !(u==x1 && v==y1)) { d[u][v]=g; // 所选位走第g步 if(g==m*n-1) {z++;

printf(\" 第%ld个指定障碍的马步遍历为: \\n\

for(i=1;i<=n;i++) // 以二维形式输出一个解 {for(j=1;j<=m;j++) if(i==x1 && j==y1) printf(\" ×\"); else printf(\"%4d\ printf(\"\\n\"); } g=g-1; }

else q=tr(g+1,u,v);

if(q==0) d[u][v]=0; // 实施回溯 if(g==2 && k==8)

q=1; // 回溯完,则返回 } }

return q; }

棋盘为n行m列，请输入n,m: 7,7

指定障碍位置(x1,y1)，请输入x1,y1:1,1 ……

第39554个指定障碍的马步遍历为: 1 32 17 8 27 34 19 16 29 26 33 18 7 48 25 2 31 28 9 20 35 30 15 42 × 36 47 6 41 24 3 44 21 10 37 14 43 22 39 12 5 46 23 40 13 4 45 38 11

9-7 哈密顿圈的回溯设计

应用回溯设计求解一般马步哈密顿圈。 // 马步哈密顿圈回溯设计 #include void main()

{ int i,j,k,q,u,v;

int n,m,d[20][20]={0},x[400]={0},y[400]={0},t[400]={0};

int a[9]={0,2,1,-1,-2,-2,-1,1,2}; // 按可能8位给a,b赋初值 int b[9]={0,1,2,2,1,-1,-2,-2,-1};

printf(\" 棋盘为n行m列，请输入n,m: \");

scanf(\"%d,%d\ i=1; u=1;v=1;

x[i]=u;y[i]=v;d[u][v]=1; // 起始位置赋初值 while(i>0)

{q=0; // 尚未找到第i+1步方向 for(k=t[i]+1;k<=8;k++)

{ u=x[i]+a[k];v=y[i]+b[k]; // 探索第k个可能位置

if(u>0 && u<=n && v>0 && v<=m && d[u][v]==0) // 所选位为空可走 { x[i+1]=u;y[i+1]=v;d[u][v]=i+1; // 则走第i+1步 t[i]=k; // 记录第i+1步方向 q=1;break; } }

if(q==1 && i==m*n-1)

{ if(u==2 && v==3 || u==3 && v==2)

{ printf(\" 此哈密顿圈的一个解为: \\n\");

for(j=1;j<=n;j++) // 以二维形式输出遍历解 {for(k=1;k<=m;k++)

printf(\"%4d\ printf(\"\\n\"); } return; }

t[i]=d[x[i]][y[i]]=d[x[i+1]][y[i+1]]=0; i--; // 实施回溯,寻求新的解 }

else if(q==1) i++; // 继续探索 else

{t[i]=d[x[i]][y[i]]=0; i--; } // 实施回溯 } }

棋盘为n行m列，请输入n,m: 6,5

此哈密顿圈的一个解为: 1 8 11 20 29 10 21 30 3 12 7 2 9 28 19 22 17 24 13 4 25 6 15 18 27 16 23 26 5 14

9-8 纵向双拼组建哈密顿圈

设计用起点为（1,1），终点为（2,2）或（1,3）的遍历，实现纵向双拼哈密顿圈。 （1） 纵向双拼设计要点

设一个起点为(1,1)的n行m列马步遍历路径的终点为(2,2)或(1,3)，则可拼接成纵向双拼为一个2n行m列的组合哈密顿圈。

同时要实现左上角置“1”的习惯，注意到A的每一项在B基础上增加m*n，左上角实为元素d(n,1),因而可设c=d(n,1)-1，组合圈的每一项均减去c，这样左上角置“1”，非正项每项加2mn。 （2） 算法描述

// 纵向双拼组合哈密顿圈 #include

int k,m,n,z,d[20][20]={0}; void main()

{ int c,i,j,g,q,x,y;

int t(int g,int x,int y);

printf(\" 组合元素为n行m列，请确定n,m: \"); scanf(\"%d,%d\ g=2;z=0;x=1;y=1;

d[x][y]=1; // 起始位置赋初值 q=t(g,x,y); // 调用t(g,x,y) if(z>0)

{printf(\" 一个%d行%d列组合型哈密顿圈：\\n\ c=d[n][1]-1;

for(i=n;i>=1;i--)

{for(j=1;j<=m;j++) // 输出倒行遍历 if(d[i][j]-c>0) printf(\"%4d\ else

printf(\"%4d\ printf(\"\\n\"); }

for(i=1;i<=n;i++)

{for(j=1;j<=m;j++) // 输出原遍历 printf(\"%4d\ printf(\"\\n\"); } }

else printf(\" 未找到指定路径! \\n\"); }

// 指定马步路径递归函数 int t(int g,int x,int y) {int u,v,k=0,q=0;

int a[9]={0,2,1,-1,-2,-2,-1,1,2}; // 按可能8位给a,b赋初值 int b[9]={0,1,2,2,1,-1,-2,-2,-1}; while(q==0 && k<8)

{ k=k+1;u=x+a[k];v=y+b[k]; // 探索第k个可能位置

if(u>0 && u<=n && v>0 && v<=m && d[u][v]==0) // 所选位为空可走 { d[u][v]=g; // 则走第g步 if(g==m*n)

{if(u==2 && v==2 || u==1 && v==3) // 原遍历终点为(2,2)或(1,3) {z++;q=1;return q; } g=g-1; }

else q=t(g+1,u,v);

if(q==0) d[u][v]=0; // 实施回溯 if(g==2 && k==8)

q=1; // 回溯完,则返回 } }

return q; }

组合元素为n行m列，请确定n,m: 5,5

一个10行5列组合型哈密顿圈： 1 16 21 12 3 22 11 2 7 20 17 50 15 4 13 10 23 6 19 8 49 18 9 14 5 24 43 34 39 30 35 48 31 44 33 42 25 40 29 38 47 36 27 32 45 26 41 46 37 28

9-9 构建哈密顿圈的一元旋转组合模型

设一元旋转组合模型的组合元素为n行m列的遍历A，按图9-7的旋转模式实施组合：

O

遍历A作为基础横放在棋盘下部，而右边与左边的竖立模块为组合元素A分别逆时针旋转90

00

与270后列倒置而成，横放棋盘上部的为A遍历旋转180而成。

为使旋转过程中的相邻遍历首尾衔接，我们选择A遍历的始点即入口为(1,1)，终点即出口为(2,m-1)，使得遍历的终点(2,m-1) 能与下一个旋转后的遍历始点(1,1)构成“日”形关系，从而可组合为哈密顿圈。

按图9－7的组合模式，组合的棋盘为(2n+m)×m的矩形棋盘，正中空洞为m×(m-2n)的

矩形空洞。注意到m≤2n时组合时无空洞，而当n<3时无遍历，显然要求m>2n≥6。

图9-7 一元旋转组合模式

(1) 探索遍历回溯算法设计

应用回溯探索在n×m广义棋盘中指定始点为(1,1)、终点为(2,m-1)的特殊马步遍历。 设置数组x(i),y(i)记录遍历中第i步的行列位置，二维数组d(u,v)记录棋盘中位置(u,v)即第u行第v列所在格的步数值。

例如第9步走在(3,2）格，则x(9)=3,y(9)=2；d(3,2)=9。若d(i,j)=0，表示棋盘中的(i,j)格为空，可以走位。

注意到马走“日”形，马最多可走8个方向。图2所示当马处在(x,y)时可选的8个方向。 设置控制马步规则的数组a(k)、b(k)，若马当前位置为（x,y），马步可跳的8个位置分别为（x+a(k),y+b(k)），（k=1,2,…,8），其中

a(k)={ 2, 1,-1,-2,-2,-1, 1, 2 }

b(k)={ 1, 2, 2, 1,-1,-2,-2,-1 } 在回溯过程中，需知第i步到第i+1步原已选取到哪一个方向，设置t(i)记录第i步到第i+1步已选取的方向数，回溯时只要从t(i)+1——8选取方向即可。

回溯从i=1开始进入条件循环，条件循环的条件为i>0。当i>0时还未完成回溯，可试探走马。

设置k（t(i)+1——8）循环依次选取方向，并求出此方向的走马位置：u=x(i)+a(k), v=y(i)+b(k)。

判断：若1≤u≤n, 1≤v≤m, d(u,v)=0，即所选位置在棋盘中且该位为空，可走马步d(u,v)=i+1；同时记录下此时的方向t(i)=k，q=1标志此步走马成功，退出选方向循环。

第i步走马成功后，检测若i=m*n-1，且满足终点条件（u=2,v=m-1），标志已搜索到满足组合要求的遍历A，即进入组建并输出含空洞的哈密顿圈后结束。

第i步走马成功后，检测若i当回溯到i=0时，所有结点搜索完成，结束。 (2) 左上角置“1”规化输出

哈密顿圈是一个封闭圈，无所谓起点与终点。为方便查阅，习惯把棋盘的左上角置“1”进行规化输出。

注意到组合后的棋盘左上角元素实为A遍历的d(n,m)。因而可设e=d(n,m)-1，组合圈的每一项均减去e，这样使棋盘左上角置“1”。同时，为衔接必需，左边遍历的所有元素需加

上mn，下部A遍历的所有元素需加上2mn，右边遍历的所有元素需加上3mn，而上部遍历中出现的所有非正项均需加上4mn。

(3) 一元旋转模型构建含空洞的哈密顿圈算法描述

// 一元旋转模型构建 #include void main()

{ int e,i,j,k,m,n,q,u,v;

int d[20][20]={0},x[400]={0},y[400]={0},t[400]={0};

int a[9]={0,2,1,-1,-2,-2,-1,1,2}; // 8个马位方向数据 int b[9]={0,1,2,2,1,-1,-2,-2,-1};

printf(\" 遍历为n行m列(m>2n)，请输入n,m: \");scanf(\"%d,%d\ i=1;u=1;v=1;x[i]=u;y[i]=v;d[u][v]=1; // 遍历始点为(1,1) while(i>0)

{q=0; for(k=t[i]+1;k<=8;k++)

{ u=x[i]+a[k];v=y[i]+b[k]; // 探索第k个可能方向 if(u>0 && u<=n && v>0 && v<=m && d[u][v]==0)

{ x[i+1]=u;y[i+1]=v;d[u][v]=i+1; // 则走第i+1步

t[i]=k;q=1;break; // 记录第i+1步方向 } }

if(i==m*n-1 && u==2 && v==m-1 && q==1) // 遍历终点为(2,m-1) { printf(\" 一个%d行%d列棋盘，\

printf(\"中央含%d行%d列空洞的哈密顿圈：\\n\

e=d[n][m]-1; // 棋盘左上角元素原为d(n,m) for(i=n;i>=1;i--)

{ for(j=m;j>=1;j--) // 输出上部A的行列倒置遍历 if(d[i][j]-e>0) printf(\"%4d\ else printf(\"%4d\ printf(\"\\n\"); }

for(j=1;j<=m;j++)

{for(i=1;i<=n;i++) // 输出左边旋转遍历 printf(\"%4d\

for(i=1;i<=m-2*n;i++) // 输出中间空洞

printf(\" \");

for(i=n;i>=1;i--) // 输出右边旋转遍历 printf(\"%4d\

printf(\"\\n\"); }

for(i=1;i<=n;i++)

{ for(j=1;j<=m;j++) // 输出下部原始遍历A printf(\"%4d\ printf(\"\\n\"); }

printf(\" 该含空洞的哈密顿圈共有%d个马步！\\n\ return; }

else if(q==1) i++; // 继续下一步探索 else {t[i]=d[x[i]][y[i]]=0; i--;} // 实施回溯

}

if(q==0) printf(\" 未能组合哈密顿圈! \\n\"); }

(4) 测试示例

遍历为n行m列(m>2n)，请输入n,m: 3,8

一个14行8列棋盘，中央含8行2列空洞的哈密顿圈： 1 94 91 10 13 6 89 8 92 15 96 3 90 9 12 5 95 2 93 14 11 4 7 88 16 29 32 73 68 71 31 36 17 70 87 74 28 33 30 67 72 69 35 18 37 82 75 86 38 27 34 85 66 83 21 24 19 78 81 76 26 39 22 65 84 79 23 20 25 80 77 64 40 55 52 59 62 45 50 47 53 60 57 42 51 48 63 44 56 41 54 61 58 43 46 49

该含空洞的哈密顿圈共有96个马步！