讨论 / 我的怎么错了?谁有更好的DFS写法?
小小小学生 2009-04-22 02:15:00
点我顶贴 收藏 删除
program li;

type arr=array[1..10] of boolean;

var n,p,q,i:longint; s:string;

a:array[0..10000] of longint;

b:arr;

function judge(j:longint):boolean;

var i:longint;

begin

judge:=false;

for i:=p+1 to q-1 do

if j mod i=0 then begin judge:=true; break; end;

end;

procedure dfs(x:longint;ss:string;b:arr);

var i,j:longint;

begin

ss:=ss+s[x]; b[x]:=false;

for i:=1 to length(s) do

if b[i] then dfs(i,ss,b);

if length(ss)=length(s) then

begin

val(ss,j);

if judge(j) then

begin inc(a[0]); a[a[0]]:=j; end;

end;

end;

procedure print;

var i,j,t:longint;

begin

for i:=1 to a[0]-1 do

for j:=1 to a[0]-i do

if a[j]>a[j+1] then

begin t:=a[j]; a[j]:=a[j z+1]; a[j+1]:=t; end;

for i:=1 to a[0] do writeln(a[i]);

end;

begin

readln(n); str(n,s); a[0]:=0;

readln(p,q);

if p>q then

begin i:=p; p:=q; q:=i; end;

for i:=1 to length(s) do

begin

fillchar(b,sizeof(b),true);

dfs(i,’’,b);

end;

if a[0]=0 then writeln(’No answer’) else print;

end.

#1 小小小学生@2009-04-11 19:49:00
回复 删除
顶起顶起``
#2 小小小学生@2009-04-14 02:31:00
回复 删除
顶起顶起~
#3 小小小学生@2009-04-15 21:51:00
回复 删除
顶起顶起````
#4 小小小学生@2009-04-18 22:28:00
回复 删除
顶起顶起
#5 小小小学生@2009-04-18 22:28:00
回复 删除
顶起顶起
#6 zrp@2009-04-21 18:37:00
回复 删除
应该是先求1-N的全排列,然后再查看当前排列是否合法吧.....

另外,你只悬赏三分还指望有大牛帮你看啊.......

^_^

#7 zrp@2009-04-21 18:45:00
回复 删除
哦,发现问题了:

for i:=p+1 to q-1 do

if j mod i=0 then begin judge:=true; break; end;

你不觉得这个循环很耗时吗?

最好在读入P,Q后立刻算出P-Q的最小公倍数u,然后再看每个

j mod u =0 or <>0 就可以了

#8 小小小学生@2009-04-22 02:15:00
回复 删除
全排列。。。。

我就是全排列的DFS写不好。。。。。。

查看更多回复
提交回复