将2^n个0和2^n 个1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为n+1的单位进行数二进制数。
要求给出一种排法,用上面的方法产生出来的2^(n+1)个二进制数都不相同。
例如,当n=2时, 即2^2个0 和2……2个1 排成如下一圈:
比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101,011,111,110,100共8个二进制数且都不相同。
程序说明
以n=4为例,即有16个0,16个1,
数组a用以记录32个0,1的排法,
数组b统计二进制数是否已出现过。
程序清单
PROGRAM NOI00;
VAR
A : ARRAY[1..36] OF 0..1;
B :ARRAY[0..31] OF INTEGER;
I, J, K, S, P : INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27;
WHILE A[J]=1 DO J:=J-1;
a[j]:=1;
FOR I:=J+1 TO 27 DO a[i]:=0;
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
s:=0;
FOR K:=I TO I+4 DO S:=S*2+A[K];
b[s]:=1;
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF s=32 THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.