i=1;a[i]=0; k=1; while(1) {t=1;
for(j=1;j if(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(\ printf(\ if(s==0) printf(\ } if(t && (k if(k else 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(\} 5-10 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)。 返回条件修改为（当j a(j)=a(i) or a(j)%n=a(i)%n and (a(j)>a(i) or a(j)+1!=i-j) 其中a(j)=a(i)，为使a数组的2n个元素不重复取值； a(j)%n=a(i)%n and a(j)>a(i)，避免同一对取余相同的数左边大于右边，导致重复； a(j)%n=a(i)%n and a(j)+1!=i-j，避免同一对数位置相差不满足题意相间要求。 例如，a(j)=0时，此时a(i)=n，为0号情侣，位置应相差1（即中间没有人），即i-j=1。 a(j)=1时，此时a(i)=n+1，为1号情侣，位置应相差2（即中间有1人），即i-j=2。 这些都应满足条件a(j)+1=i-j。如果a(j)+1!=i-j，不满足要求，返回。 设m=2n，若满足条件(g>0 and i=m and a(1)%n 2. 程序实现 // 8对夫妇拍照 #include {int i,j,g,n,m,s,a[20]; printf(\scanf(\ m=2*n; i=1;a[i]=0;s=0; while(1) {g=1; for(j=1;j if(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]%n for(j=1;j<=m;j++) printf(\输出一个排列 printf(\ } } if(g && i {i++;a[i]=0;continue;} while(a[i]==m-1) i--; // 回溯到前一个元素 if(i>0) a[i]++; else break; } printf(\共有解s=%d个。\\n\} 习题6 6-1 n个矩阵连乘问题 设矩阵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 {int d,n,i,j,k,t,r[100],m[100][100]; printf(\请输入矩阵的个数 n :\ printf(\请输入第1个矩阵的行数 :\ for(i=1;i<=n-1;i++) {printf(\请输入第%d个矩阵的列数，也是第%d个矩阵的行数 :\ scanf(\ } 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(t printf(\个矩阵连乘的乘法次数的最小值为：%d \\n\} 6-2 应用顺推实现动态规划求解点数值三角形的最优路径 在一个n行的点数值三角形中，寻找从顶点开始每一步可沿左斜（L）或右斜（R）向下至底的一条路径，使该路径所经过的点的数值和最小。 应用顺推实现动态规划求解从项到底的最小路程。 （1）建立递推关系 设点数值三角形的数值存储在二维数组a(n,n),数组b(i,j)为从顶点（1,1）到点(i,j)的最小数值和。b(i,j)与stm(i,j)(i=2,3,…,n)的值由b数组的第i-1行的第j-1个元素与第j个元素值的大小比较决定，即有递推关系： b(i,j)=a(i,j)+b(i-1,j); （b(i-1,j) 其中i=2,3,…,n 比较b(n,1),b(n,2),…,b(n,n)所得最小值min即为所求的最小路径。 边界条件： b(1,1)=a(1,1); b(i,1)=a(i,1)+b(i-1,1); b(i,i)=a(i,i)+b(i-1,i-1); i=2,…,n。 （2）顺推计算最优值 b[1][1]=a[1][1]; for(i=2;i<=n;i++) { b[i][1]=a[i][1]+b[i-1][1]; b[i][i]=a[i][i]+b[i-1][i-1]; } for(i=3;i<=n;i++) // 顺推得b[n][j] for(j=2;j<=i-1;j++) if (b[i-1][j] b[i][j]=a[i][j]+b[i-1][j-1]; min=10000; for(j=1;j<=n,j++) // 比较得最短路程 if(b[n][j] { min=b[n][j];m=j;} printf(\ 6-3 应用顺推实现动态规划求解n行m列边数值矩阵最大的路程 已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。 动态规划算法设计： 设矩阵的行数n，列数m，每点为(i, j)，i=1,2,…,n；j=1,2,…,m。显然，该边数值矩阵每行有m?1条横向数值边，每列有n?1条纵向数值边。 从点(i,j)水平向右的边长记为r(i,j)(j 设a(i,j)为左上角顶点(1,1)到点（i,j）的最大路程。 a(i,j)的值由a(i-1,j)+d(i,j)与a(i,j-1)+r(i,j)比较，取其较大者得到，即有递推关系： a(i,j)=max(a(i-1,j)+d(i-1,j),a(i,j-1)+r(i,j-1)) 其中i=2,…,n；j=2,…,m。 注意到左边纵列与上边横行只有惟一出口，因而有边界条件： a(1,1)=0; a(i,1)=a(i-1,1)+d(i-1,1); i=2,…,n a(1,j)=a(1,j-1)+r(1,j-1); j=2,…,m （2）逆推计算最优值 a[1][1]=0; for(i=2;i<=n;i++) a[i][1]=a[i-1][1]+d[i-1][1]; // 左边纵列初始化 for(j=2;j<=m;j++) a[1][j]=a[1][j-1]+r[1][j-1]; // 上边横行初始化 for(i=2;i<=n;i++) // 顺推求解a(i,j) for(j=2;j<=m;j++) if(a[i-1][j]+d[i-1][j]>a[i][j-1]+r[i][j-1]) a[i][j]=a[i-1][j]+d[i-1][j]; else