《计算机常用算法与程序设计案例教程》习题解答

计算机常用算法与程序设计案例教程 习题解答提要 习题 1 1分数分解算法描述 把真分数 a/1”的埃及分数之和： （ 1） 寻找并输出小于 a/； （ 2） 若 c900000000，则退出； （ 3） 若 c 900000000，把差 a/c 整理为分数 a/b，若 a/b 为埃及分数，则输出后结束。 （ 4） 若 a/继续（ 1）、（ 2）、（ 3）。 试描述以上算法。 解： 设 )(这里 x)表示取正数 ，注意到 1 )1( )1(11 db c=d+1，则 a,b) ) c=b/a)+1; if(c900000000) +); a=a*b=b*c; / a,选择下一个 分母作准备 if(a=1) ); 1求出以下程序段所代表算法的时间复杂度 （ 1） m=0; k=1;k=1;m=m+j; 解：因 s=1+2+ +n=n(n+1)/2 时间复杂度为 O( （ 2） m=0; k=1;k=a*10099;b=2) x=0,k=1; +则 p(n)= =( ) i,j,n,a3030; 请确定方阵阶数 n: ); %d,&n); i=1;aij=j; / 方阵左部元素赋值 if(i+jn+1 & ij) aij=n+1 / 方阵下部元素赋值 if(i+jn+1 & i a,c,p,n; p=2011; c=1111;n=4; / 变量 c与 c!=0) / 循环模拟整数 竖式 除法 a=c*10+1; c=a%p; n=n+1; / 每试商一位 由 %d 个 1组成的整数能被 %d 整除。 n,n,p); 习题 2 2解不等式 设 不等式 2011/12/11 13/12/11 12/11 112010 n 解：上下限一般为键盘输入的 a,b。 / 解不等式 : a # a,b,c,d,i; ts,s; 请输入 a,b: ); %d,%d,&a,&b); i=0;s=0; s x; x=65; ) x=x+66; if(x%5=1 & x%7=4) 至少有兵 : %。 ,x); 2分解质因数 对给定区间 m,n的正整数分解 质因数 , 每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。 例如 , 2012=2*2*503, 2011=(素数 !)。 解：对区间中的每一个整数 i(b=i)，用 k(2 i)试商： 若不能整除，说明该数 后继续试商。 若能整除，说明该数 k 是 b 的因数，打印输出 k*； b 除以 k 的商赋给 b(b=b/k) 后继 续用 注意，可能有多个 ，直至不能整除， 后继续试商。 按上述从小至大试商确定的因数显然为质因数。 如果有大于 n)的因数 (至多一个 !) ,在试商循环结束后要注意补上，不要遗失。 如果整个试商后 b 的值没有任何缩减，仍为原待分解数 n，说明 n 是素数，作素数说明标记。 若 k是 格式输出，然后 b=b/k。 若 后继续。 若上述试商完成后 1 b,i,k,m,n,w=0; m,n中整数分解质因数（乘积形式） .n); 请输入 m,n:); %&m,&n); i=m; %,k); / 返回再试 if(b=1) %ldn,k); k+; if(b1 & b=1，即 (2 (2k+1)中至少有一个素数，实施“ +”； 否则，若 ak+ak+1=0，即 (2 (2k+1)中没有素数，实施“ -”。 同时，设置最大值变量 小值变量 在循环中，每计算一个和值 s，与 较确定最大值，同时记录此时的项数 时记录此时的项数 / 基 于素数的整数和 # t,j,n,k,k1,k2,a3000; s, 请输入整数 n: ); %d,&n); k=1;k=1) s+=(2*(2*k+1); / 实施代数和 2*(2*k+1); if(ss;k1=k; / 比 较求最大值 if(s1(k=0 9)，说明 回。 在不存在重复数字的情形下，检测若 f0+f1+f4=0，说明 7 位平方数 d 中没有数字“ 0” ,“ 1” ,“ 4” ,印输出。 / 组成没有重复数字的 7位平方数 # k,m,n,t,f10; a,b,c,d,w; n=0; b=356789);c=876532); a=b; m=w%10;fm+;w=w/10; t=0,k=1;t=1; / 测试三个平方数是否有重复数字 if(t=0 & f0+f1+f4=0) / 测试平方数中没有数字 0,1,4 n+; %2d: ,n); % n,d,a); 共可组成 %位平方数 .n,n); 2写出例 2运行程序。 对称方阵程序： # i,j,n,a3030; 请确定方阵阶数 n: ); %d,&n); i=1;aij=(n+1)/2; / 方阵左部元素赋值 if(i+j=n+1 & i=j) aij=; / 方阵下部元素赋值 if(i+jn+1 & i x,y,t,k,a,b,c,d,e,n=0; m6,f11; a=12;m1=a;m2=c;m3=e;m4=b;m5=d; x=0;x=y%10;fx=fx+1; y=(10; / 分离数字 t=0,x=1;x # a,b,k; s,x; a=1; 1) a+;s=0; / 检验 b=a*100区间 f+1,f+n中的 应用试商法求指定区间 c,d(约定起始数 c=3， d=c+10000)上的所有素数。求出该区间内的一个素数 m，设前一个素数为 f, 判别： 若 n，则输出结果 f+1,f+n后结束； 否则，作赋值 f=m，为求下一个素数作准备。 如果在区间 c,d中没有满足条件的解，则作赋值： c=d+2， d=c+10000，继续试商下去，直到找出 所要求的解。 （ 2） 程序实现 / 求最小的连续 # c,d,f,m,j; t,n; 求最小的 n); 请输入 n:); %d,&n); c=3;d=c+10000; f=3; ) m=c; / 满足条件即行输出 最小的 %,n); % n,f+1,f+n); ; if(t=0) f=m; / 每求出一个素数 f if(md) c=d+2;d=c+10000; / 每一轮试商后改变 c, 2和积 9数字三角形 求解和为给定的正整数 s（ s 45）的 9个互不相等的正整数填入 9数字三角形，使三角 形三边上的 4个数字之和相等（ 三边上的 4个数字之积也相等（ 图 2 数字三角形 （ 1）求解要点。 把和为 个正整数存 储于 b(1)， b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即 b(1) # k,j,t,s,s1,s2,n,b10; 请输入正整数 s： ); %d,&s); n=0; b1=1;b1 k,n; b3000,s; 请输入 n: ); %d,&n); b1=1;b2=2;s=3; k=3;k3*m( m(i)=3*m(1; 特别注意：两队列若出现相等时，给 排头都要增 1。 *m(=3*m( m(i)=2*m(1; ; ; / 为避免重复项， （ 2） 程序设计 / 双关系递推 # n,p2,p3,i;s,m3000; m1=1;s=1; ; / 排头 p2, 请输入 n: ); %d,&n); i=2;i k,m,t,p2,p3, a,b,c,s,f100; 求数列的第 请输入 m: ); %d,&m); f1=1; a=2;b=3;c=5;s=1; k=2;k k,n; t,s100; 请输入幂指数和至多为 n:); %d,&n); t=1;s0=1; ; k=1;k t,k;g100; t:); %d,&t); g0=0; g1=3; / 确定初始条件 k=2;k i,j,c,d,h,v,m,n,s,a3030; m行 请确定 m,n: ); %d,%d,&m,&n); c=n; if(mi; / 一圈的右列从下至上递增 s+; ahv=s; if(s=m*n) h=i; v=n+1-i;vi; / 一圈的上行从右至左递增 s+; ahv=s; if(s=m*n) v=i; %n,m,n); i=1;i k; t1000; t10=1; / 确定初始条件 k=9;k=1; / 逆推计算 t(1) tk=2*(tk+1+1); 第 1 天摘桃 %n,t1); k=1;k d,k,m,n; t1000; 请确定正整数 m,n,d: ); %d,%d,%d,&m,&n,&d); tn=d; / 确定初始条件 k=k=1; / 逆推计算 t(1) tk=2*(tk+1+m); 第 1 天摘桃 %n,t1); k=1;k k; s,f50; f1=1;f2=1; s=f1+f2; / 数组元素与和变量赋初值 k=3;k k; a,b,s; a=1;b=1;s=a+b; / 迭代变量 a,b, k=2; 设计求 n!的递归函数，调用该函数求 !1!21!111 解： 定义 n!的递归函数 f(n),在求和的 k(1 n)循环中实施求和 s+=(k); 程序设计： #f(n) g; if(n=1) g=1; g=n*f( g); k,n; s=1; 请输入 n: );%d,&n); k=1;k f(n) g; if(n=1 | n=2) g=1; g=f(f( g); k,n; s=0; 请输入 n: );%d,&n); k=1;k b(n) g; if(n=1) g=1; if(n=2) g=2; g=3*b(2*b( g); k,n; s=0; 请输入 n: );%d,&n); k=1;k a(n) g; if(n=1) g=1; if(n%2=0) g=a(n/2)+1; g=a(2)+a(n+1)/2); g); k,n; s=0; 请输入 n: );%d,&n); k=1;k=2;ai=ai+a a1=1; # i,j,k,n,a100; 请输入杨辉三角的行数： ); %d,&n); j=0;j # i,j,c,d,h,v,m,n,s,a3030; m行 请确定 m,n: ); %d,%d,&m,&n); c=n; if(m=i+1; s+;ahv=s; / if(s=m*n) i=d; / 赋值完成即行退出 h=m+1-i;h=i+1; s+;ahv=s; / if(s=m*n) i=d; %n,m,n); i=1;i m,n,a2020=0; h,v,b,s,d; 数阵为 m行 确定 m,n： ); %d,%d,&m,&n); s=m; if(mn) s=n; b=1;d=1; t(b,s,d); / 递归函数说明 t(b,s,d); / 调用递归函数 %d % n,m,n); h=1;hm*n) j=1;jm*n) / 另一递归出口 t(b+1,d); / 调用内一圈递归函数 4应用递归设计 实现 有 排列 。 解： 设置递归函数 p(k)， 1 k m+n，元素 ak取值为 0或 1。 当 k=m+变量 0”的个数。若 h=用 后回溯返回，继续。 当 k m,n,r,a30; s=0; p(k); n,m: ); %d,%d,&n,&m); %与 %的排列 :n,n,m); p(1); / 从第 1个数开始 n s=%n,s); / 输出排列的个数 / 排列递归函数 #p(k) h,i,j; if(k g,i,k,u,t,a10; m1,m2,i=1;a1=1; 1) g=1; k=k=1;if(ai=ak) g=0; / 两数相同 ,标记 g=0 if(i=9 & g=1 & a11 & a71) m1=a2*10+a3; m2=a5*10+a6; m3=a8*10+a9; t=0,u=2; / 往前回溯 if(ai=9 & i=1) ai+; / 至第 1个数为 9结束 5两组均分 参加拔禾比赛的 12个同学的体重如下： 48， 43， 57， 64， 50， 52， 18， 34， 39， 56， 16， 61 为使比赛公平，要求参赛的两组每组 6个人，且每组同学的体重之和相等。 请设计算法解决这 “两组均分”问题。 （ 1） 求解要点 一般地，对已知的 2n(个整数，确定这些数能否分成 2个组，每组 每组数据的和相等。 我们可采用回溯法逐步实施调整。 对于已有的存储在 求出总和 这 2显然无法分组 )。把这 2每组 方便调整 , 设置数组 a(i):1 2n。 考察 b(1)所在的组 ,只 要另从 b(2) b(2n)中选取 数。即定下 a(1)=1, 其余的a(i)(i=2, ,n)在 2 2组合与顺序无关 ,不妨设 2 a(2) # n,m,aN,b2*N,i,j,t; s1,s=0; 把 2每组 n); t=)%1000;t); / 随机数发生器初始化 n :); %d,&n); s=0,i=1;ai+; if(m0) 共有以上 %,m); 无法实现二堆均分 . ); 5指定低逐位整除数探求 试求出所有 最高位为 3的 24位低逐位整除数（除个位数字为“ 0”外 ,其余各位 数字 均不得为“ 0”）。 / 最高位为 3的 整除 # i,j,n,r,t,a100; s=0; 逐位整除 确定 n： ); %d,&n); 所求 %的右逐位整除数： n,n); j=1;j=1; / 检测 i r=r*10+aj; r=r%i; if(r!=0) ai=ai+1;t=1; / 余数 r!=0时 ai增 1,t=1 ai9 & i1) ai=1; / 回溯 ai=ai+1; t=0; / 余数 r=0时 ,t=0 if(t=0 & i=n) if(an=3) s+; %,s); j=n;j=1;%d,aj); n); ai=ai+1; if(s0) 最高位为 3的 %,n,s); 未找到 ,n); 5枚举求解 8项素数和环，与回溯结果进行比较。 (1) 设计要点 为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“ 1”。 环中的每一项为一个数字，相连的 8项构成一个 8位数。因而设置 1”开头的 8位数 812345678 18765432中 枚举 。注意到所有 1 8没有重复数字的 8位数的数字和为 9 的倍数，该数也为 9的倍数，为此， 枚举 循环步长可取 9，以精简 枚举 次数。 为操作与判断方便，设置 3个数组： 位数 f3=2，即 个数字“ 3”。 位数 g4=6，即 位数为数字“ 6”。 b13=1，标识“ 1”表示 13为素数，标识“ 0”为非素数。 枚举 实施： 1） 注意到 8项中每相邻两项之和不超过 15,对 15以内的 5个素数用 1” ,其余均为“ 0”。 2） 在 8位数的 a 循环中，对 次求余分离出各个数字 x，应用 fx+统计数字用 g9数字。 3） 设置 k(1 8)判断循环： 若 fk!=1 ，表明数字 回。 若 bgk+gk+1!=1，表明相邻的第 k+1项之和不是素数，返回。顺便说明，为判断方便，首项“ 1”先行赋值给 g9，以与 g8相邻，在 4） 通过以上判断筛选的 a，其各个数字即为所求的 8项素数环的各项，打印输出。 (2) 枚举 实现 8项素数和环 / 8项素数和环 枚举 求解 # t,k,s,x,g10,f10,b18;a,y; k=1;k #n,a2000,b1000;s=0; t,j,k; p(k); 前 输入整数 n: ); %d,&n); k=1;k p(k) i,j,u; if(k d,i,j,s,t,u,v,a20,b300; s=31;s=28; s=%2d： n,s); v=0; / a0=0;a1=1;a6=s; a2=a1+1;a20) 5 枚举 探索 4阶 德布鲁金 环， 并 与 德布鲁金 环的回溯程序运行结果进行比较。 求解由 16个 0或 1组成的环序列，形成的由每相连 4个数字组成的 16个二进制数恰好在环中都出现一次。 (1) 枚举 设计要点 约定序列由 0000开头，第 5个数字与第 16个数字显然都为 1(否则会出现 00000)。余下10个数字应用 枚举 探求。 设置一维 约定 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（否则出现 0001或 0000重复），即循环的初值可定为 7。同时，高位不会超过 4个 1（否则出现 11111超界），即循环的终值可定为 9+28+27+26。 对区间 n1,的每一个整数 n(为不影响循环，赋值给 b)，通过除以 2取余转化为 10个二进制数码。用变量 的个数，若 i 6返回，确保 16 个数 字中有 8个 1时转入下面的检验：计算 m1,验 a(0) a(18)中每 4个相连数字组成的二进制数若有相同，显然不能满足题意要求，标记 t=1退出。若所有由 4个相连数字组成的 16个二进制数没有相同的，满足 德布鲁金 环序列条件，作打印输出。 （ 2） 4阶 德布鲁金 环序列 枚举 实现 # b,m,m1,m2,n,n1,n2,i,j,k,t,a20; m=0; 28; 12+256+128+64; / 确定 枚举 范围 n=n1;n=5; / 正整数 n(即 b)转化为二进制数 ak=b%2; b=b/2; i+=ak; if(i!=6) / 确保 8个 1转入以下 检验 t=0,k=0;k i,j,n,m,a100; s=0; n (ai+; n 总数为 :%n,s); / 输出 C(n,m)的值 5 回溯实现复杂排列 应用回溯法探索 从 同元素中 取 m（约定 1 m n） 个 元素与另外 （ 1）算法设计要点 引入变量 的个数， 当 k ai=0，元素需从 0开始取 值；否则， 0的个数已达 ai=1，即从 1开始取值。这样处理， 使 0的个数不超过 少一些无效操作，提高了回溯效率 。 按以上所描述的回溯的参量： n,m(m n) 元素初值： a1=0，数组元素取初值 0。 取值点：当 k ai=0，需从 0开始取值；否则， ai=1，即从 1开始取值。 回溯点： ai=n，各元素取值至 约束条件 1： ak!=0 & ai=ak | ai*ak 0 & ai-ak)=(其中 i k)，排除同 一列或同对角线上出现 2个皇后。 约束条件 2： i=n & h=& b111, 当取值达 n 个，其中 零，且棋盘全控时输出一个解。 （ 2）复杂 排列 回溯优化设计 # 30 i,j,h,k,n,m,t,aN; s=0; n (if(ai=0) / 改变取值为 0的元素值前先把 0的个数 ai+; n s=%ldn,s); 58对夫妇特殊的拍照 一对夫妇邀请了 7对夫妇朋友来家餐聚，东道主夫妇编为 0号，其他各对按先后分别编为 1， 2， 7号。 餐聚后拍照，摄影师要求这 8对夫妇男左女右站在一排，东道主夫妇相邻排位 在 横排的正中央，其他各对排位， 1号夫妇中间安排 1个人 ,2号夫妇中间安排 2个人 ,依此类推。 共有多少种拍照排队方式？ 1. 设计要点 在 个相同元素（相当于 ， 取到 2 数为 0的为 0号 （即东道主） ，余数为 1的为 1号，余数为 例如， n=4，数组元素为 0与 4，对 4同余，为一对“ 0”； 1与 5对 4同余，为一对“ 1”； 一般地， +同余，为一对 i,(i=0,1,2,3)。 返回条件修改为（当 ja(i) or a(j)+1!=其中 a(j)=a(i)，为使 a(j)%n=a(i)%n a(j)a(i)，避免同一对取余相同的数左边大于右边，导致重复； a(j)%n=a(i)%n a(j)+1!=免同一对数位置相差不满足题意相间要求。 例如， a(j)=0时，此时 a(i)=n，为 0号情侣，位置应相差 1（即中间 没有 人），即 。 a(j)=1时，此时 a(i)=n+1，为 1号情 侣，位置应相差 2（即中间有 1人），即 。 这些都应满足条件 a(j)+1=果 a(j)+1!=满足要求，返回。 设 m=2n， 若满足条件 (g0 i=m a(1)%n # i,j,g,n,m,s,a20; n (2ai | aj+1!= g=0; / 出现相同元素或同余小在后时返回 if(g & i=m & a1%ai+; n 共有解 s=%n,s); 习题 6 6 设矩阵 A为 p行 阵 B为 q行 矩阵乘积 试求 n（ n2） 个矩阵 ),2,1( 的乘积21的最少乘法次数。其中 数1, ii 解： 注意1是1样才能确保 多个矩阵相乘，满足乘运算结合律。 例如，求321 求前两个矩阵的乘积321 )( 是先求后两个的乘积 )(321 是可以的，但两者的乘法次数不一定相等，我们要求最少乘法次数。 设 m(i,j)是求乘积12的最少乘法次数，则有递推关系 )2()1()()1,( (i+1=j) )1()1()(),1(),(m ),( (i k j,i d,n,i,j,k,t,r100,m100100; 请输入矩阵的个数 n :); %d,&n); 请输入第 1个矩阵的行数 :); %d,&r1); i=1;iairi aij=aj+dj; aij=airi %d,anm); 所求左上角顶点到右下角顶点的最大路程即最优值为 a(n,m)。 6求解 边数值 三角形 的最短路径 已知边数值三角形每两点间距离如图 7一个点可向左或向右两个去向，求三角形顶点到底边的最短路径。 图 7角形 边数值数据 1) 算法设计 设边数值三角形为 不包含作为边终止点的三角形底边 )，每点为 (i， j)， i=1,2,，n； j=1,2,， i,j)向左的边长记为 l(i,j)，点 (i,j)向右的边长记为 r(i,j)。记a(i,j)为点（ i,j） 到底边的最短路程。显然 a(i,j)=a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j) st(i,j)= l , r 应用逆推求解，所求的顶点 a(1,1). 2) 边数值三角形最短路径搜索 # n,i,j,t,s; a5050,l5050,r5050;050; t=%1000;t); / 随机数发生器初始化 请输入数字三角形的行数 n:); %d,&n); i=1;i=1; / 逆推求取最短路径 j=1;说明前面为 b(i,j)赋值不对 ,作修改 : b(i,j)=yb+ b(i+1,j),则 i,j)=D,否则 i,j)=R 这样反推所得 b(1,1)即为所求的最小路径数字和。 为了打印最小路径 ,利用 先打印 a(1,1),i=1,j=1. 若 i,j)=R 则 ,即 j=j+1,然后打印 右边整数 a(i,j); 若 i,j)=D 则 ,即 i=i+1,然后打印 下面整数 a(i,j); 若 i,j)=O 则 i,j 均增 1,即 i=i+1,j=j+1,然后打印 斜向右下整数a(i,j); 依此类推 ,直至打印到终点 a(n,m)。 6西瓜分堆 已知的 把这堆西瓜分成两堆，每堆的个数不一定相等，使两堆西瓜重量之差为最小。 (1） 设计要点 两组数据之和不一定相等，不妨把较少的一堆称为第 1堆。设 b(i)之和为 s，则第 1堆数据之和 s/2，这里 x为 问题要求在满足 s/2前提下求 大值 样两堆数据和之差的最小值为 为了求 用动态规划设计，按分每一个瓜为一个阶段，共分为 一个阶段都面临两个决策：选与不选该瓜到第 1组。 1） 建 立递推关系 设 m(i,j)为 第 1堆距离 s/2还差重量 为 j， 可取 瓜编号 范围为 ： i,i+1, ,。则 当 0 j=1; / 逆推计算 m(i,j) j=0;j=b(i) & m(i+1,j)m(i+1, （其中 i=1,2, n1） 第 1堆分 b(i); 不分 b(i); if(m(1,sb=b(n) 则第 1堆分 b(n)。 （ 2）求解 两组数据和之差的最小值 程序设计 / 求解 两组数据和之差的最小值 # 40 n,c1,i,j,s,t,cb,sb,bN,mN10*N; n: ); %d,&n); s=0; i=1;i=1; / 逆推计算 m(i,j) j=0;j=bi & mi+1jmi+1 bi;bi; %3d,bi); bi=0; / b(i)分后赋 0,为输出第 2堆作准备 if(m1bn) %3d,bn); bn; bn=0; (%d)n, 第 2堆 : ); ,i=1;bi; %3d,bi); (%d)n, 6 应用递推实现动态规划求解 序列的 最小子段和 应用递推实现动态规划求解：给定 能为负整数）组成的序列12, , , na a a，求该序列形如 段和的最小值。 递推实现动态规划求解： 1） 动态规划算法设计 设 qj为序列前 )1(m 1 j 由 qj的定义 ,得 qj的递推关系 : )1(01 011 初始条件： Q0=0 (没有项时，其值自然为 0)。 （ 2） 动态规划程序实现 / 动态规划求最小子段和 # i,j,k,t,n,s,q1000,a1000; t=)%1000;t); / 随机数发生器初始化 序列中 请确定 n:); %d,&n); 序列的 %n ,n); i=1;i=0) qj=aj