有N个硬币（6<=N<=30）正面朝上排成一排，每次将5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找出步数最少的翻法并把翻币过程及次数打印出来（用o表示正面，x表示反面，‘o’和‘x’均为小写字母）。
Input
一行，整数N
Output
如果有解，从步骤0开始输出各步骤，step后面的步骤数为长度为两位的整数，如果无解，输出“have not solution”。
Sample Input
11
Sample Output
step 0:ooooooooooo step 1:*****oooooo step 2:oo******ooo step 3:***********
用PASCAL语言编写一个程序
这道题，我使用队列写的，比知道你能否用上，
var
qm : array[1..1000] of string[60];
num : array[1..1000] of byte;
pnt : array[1..1000] of word;
closed,open,n,i : word;
Procedure print;
Var buf : array[1..50] of word;
i,j,k : word;
begin
i := open; j := 0;
while i <> 0 do begin
j := j+1;
buf[j] := i;
i := pnt[i];
end;
for k := j downto 1 do writeln('Step ',j-k:2,' : ',qm[buf[k]]);
readln;
halt;
end;
procedure comp(x : byte);
var
i,k1,k2 : integer;
begin
for i := 1 to open do
if num[i] = num[closed]+5-x-x then exit;
open := open+1;
qm[open] := qm[closed];
k1 := 0; k2 := 0;
for i := 1 to n do begin
if (qm[open,i] = 'o') and (k1 < x)
then begin
inc(k1);
qm[open,i] := '*'
end
else if (qm[open,i] = '*') and (k2 < 5-x) then begin
inc(k2);
qm[open,i] := 'o'
end;
if (k1 = x) and (k2 = 5-x) then break
end;
pnt[open] := closed;
num[open] := num[closed]+5-x-x;
if num[open] = 0 then print;
end;
begin
assign(input,'work1.IN');reset(input);
assign(output,'work1.OUT');rewrite(output);
repeat
readln(n);
until n in [6..60];
qm[1] := '';
for i := 1 to n do qm[1] := qm[1]+'o';
num[1] := n; pnt[1] := 0;
closed := 0; open := 1;
while open < 1000-5 do begin
inc(closed);
for i := 0 to 5 do
if (num[closed] >= i) and (n-num[closed] >= 5-i) then comp(i)
end;
close(input);close(output);
end.
这道题老师给我们讲过，我感觉挺难的，
不过好像分治也能写出的
经典的广度优先搜索题 type ss=array[1..5000] of 0..9; var n,m,open,closed,k:integer; a,b:ss;p:array[1..5000] of integer;
function check(xx:integer):boolean; var i:integer; begin check:=true; for i:=1 to open do if xx=a[i] then check:=false; end;
procedure print; var i,j,o,o1,c,d:integer; a1,b1:ss; begin i:=0; d:=open; repeat inc(i); a1[i]:=a[d]; b1[i]:=b[d]; c:=p[d]; d:=c; until c=0; o1:=0; if k>0 then begin for o:=1 to n do write('o'); writeln; repeat dec(k); inc(o1); for o:=1 to k*5+b1[i] do write('o'); for o:=1 to o1*5+a1[i] do write('*'); writeln; until k=0; end; for j:=i downto 1 do begin for o:=1 to b1[j] do write('o'); for o:=1 to o1*5+a1[j] do write('*'); writeln; end; halt; end;
procedure inp; begin write('n='); readln(n); m:=(n mod 5)+5;k:=(n div 5)-1; a[1]:=0; b[1]:=m; p[1]:=0; end;
procedure try; var i,x,y,x1,y1:integer; begin closed:=0;open:=1; repeat inc(closed); x:=a[closed]; y:=b[closed]; for i:=1 to 5 do if (i<=y) and (x>=5-i) then begin y1:=y-i+5-i; x1:=x+i-5+i; if check(x1) then begin inc(open); a[open]:=x1; b[open]:=y1; p[open]:=closed; if y1=0 then print; end; end; until closed=open; end;
begin inp; try; if closed=open then writeln('no solution'); readln; end.