#define NMax 10 # include“ stdio.h” aino int 1, j, n, k, p, g, m int a [NMAX][NMAX] scanf(“%d”,&n) for(k=1;(1 k++) lif (k<n)g=k else(2) for(p=1: p<=g: p++) lif (3) i=g-p+1: j=p: I f(4) i=i+n-g: j=j+n-g: alil[j]= for (i=l: i<=n: i++) I for (j=l: j<=n: j++) printf(“%d”,a[i][j); printf(“Ⅶn”) 【上海大学2002六、1(10分】 39.约瑟夫环问题:设有n个人围坐一圈,并按顺时针方向1-n编号。从第s个人开始进 行报数,报数到第m个人,此人出圈,再从他的下一个人重新开始从1到m的报数进行下去, 直到所有的人都出圈为止 PROCEdURE Josef (A: ARRAY [1.. n OF integer: s, m: integer) BEGIN FOR i: =1 TO n Do A[i]: =i FoR i: =n doWnto 2 DO BEGIN SI:=(1) //计算出圈人s IF SI=0 THEN(2) W:=A[s1] //A[s1]出圈 FOR j: =(3 D0A[j]:=A[j+1] A[]: =w END write(出圈序列为:’):;/输出出圈序列 FOR i: =n DOWNTo 1 DO write(ali]:writeln END;【华南师范大学2000五、2(9分)】 40.设有一个背包可以放入的物品重量为S,现有n件物品,重量分别为W,W2, 问能否从这n件物品中选择若干件放入背包,使得放入的重量之和正好是S。设布尔函数 Knap(S,n)表示背包问题的解,W(i=1,2,,n)均为正整数,并已顺序存储地在数组W中 请在下列算法的下划线处填空,使其正确求解背包问题。 Knap(s, n) 右#define NMAX 10 #include “stdio.h” main() { int i,j,n,k,p,q,m; int a [NMAX][NMAX]; scanf(“%d”,&n); m=1; for(k=1；(1) ；k++) {if（k<n） q=k； else(2) __; for(p=1;p<=q;p++) {if(3) {i=q-p+1；j=p；} else{i=p；j=q-p+1；} if(4) {i=i+n-q；j=j+n-q；} a[i][j]=m；(5) _; } for（i=1；i<=n;i++） { for（j=1；j<=n；j++） printf（“%4d”,a[i][j]）;printf(“\n”); } } } 【上海大学 2002 六、1 （10 分）】 39. 约瑟夫环问题：设有 n 个人围坐一圈，并按顺时针方向 1—n 编号。从第 s 个人开始进 行报数，报数到第 m 个人，此人出圈，再从他的下一个人重新开始从 1 到 m 的报数进行下去 ， 直到所有的人都出圈为止。 PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer); BEGIN FOR i:= 1 TO n DO A[i]:=i; sl:=s; FOR i:=n DOWNTO 2 DO BEGIN sl:= (1) __；//计算出圈人 s1 IF sl=0 THEN (2) _； w:=A[sl]; //A[s1]出圈 FOR j:= (3) __ DO A[j]:=A[j+1]; A[i]:=w; END; write('出圈序列为：’)；//输出出圈序列 FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END; 【华南师范大学 2000 五、2 (9 分)】 40. 设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 W1，W2，...，Wn。 问能否从这 n 件物品中选择若干件放入背包，使得放入的重量之和正好是 S。设布尔函数 Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组 W 中。 请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若 S=0