Help meeeeeeeeeeee!

Tiêu đề: Help meeeeeeeeeeee! Sun 14 Mar 2010, 21:27

Bạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái.
Ví dụ: Cho từ “abc”, chương trình của bạn phải đưa ra được các từ "abc", "acb", "bac", "bca", "cab" và "cba" (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho).
Input
Dữ liệu vào được cho trong tệp input.txt chứa một số từ. Dòng đầu tiên là một số tự nhiên cho biết số từ được cho ở dưới. Mỗi dòng tiếp theo chứa một từ. Trong đó, một từ có thể chứa cả chữ cái thường hoặc hoa từ A đến Z. Các chữ thường và hoa được coi như là khác nhau. Một chữ cái nào đó có thể xuất hiện nhiều hơn một lần.
Output
Với mỗi từ đã cho trong file Input.txt, kết quả nhận được ra file Output.txt phải chứa tất cả các từ khác nhau được sinh từ các chữ cái của từ đó. Các từ được sinh ra từ một từ đã cho phải được đưa ra theo thứ tự tăng dần của bảng chữ cái.
Sample Input
2
abc
acba
Sample Output
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

Tiêu đề: Re: Help meeeeeeeeeeee! Sun 14 Mar 2010, 21:47

Bài này thì cũng......khá đấy.

Đối với bài này, ta ko làm đệ quy như theo cách tạo hoán vị bình thường được. Bạn để ý là có hoán vị giống nhau nếu như dùng đệ quy như bình thường.

Đối với bài này, ta nên dùng đệ quy có kết hợp thêm điều kiện. Đầu tiên, ta xếp các kí tự của chuỗi đã nhập theo thứ tự từ điển. Ví dụ 'abac' thì xếp lại thành 'aabc' . Gán ss='' sau đó cho đệ quy như bình thường, khi đọc kết quả ra thfi gán st= thứ đã tạo ra, nếu st<>ss thì in ra, ko thì ko in. Như thế là ổn.

Tiêu đề: Re: Help meeeeeeeeeeee! Sun 14 Mar 2010, 21:49

Đệ quy theo thứ tự từ điển thì mình làm rồi đây. Nhưng thấy ko ổn lắm. Ko bt còn cách nào gọn hơn ko?

Code:: const fi='hvchuoi.inp';
fo='hvchuoi.out';
var f:text;
n:byte;
s:string;
x:array[1..20] of char;
dd:array[1..20] of boolean;
procedure inp;
begin
assign(f,fi);
reset(f);
readln(f,s);
n:=length(s);
close(f);
end;
procedure test;
var i:byte;
begin
for i:=1 to n do
write(f,x[i]);
writeln(f);
end;
procedure try(i:byte);
var j:byte;
begin
for j:=1 to n do
if not dd[j] then
begin
x[i]:=s[j];
dd[j]:=true;
if i=n then test
else try(i+1);
dd[j]:=false;
end;
end;
procedure pri;
begin
assign(f,fo);
rewrite(f);
try(1);
close(f);
end;
begin
inp;
fillchar(dd,sizeof(f),false);
pri;
end.

Tiêu đề: Re: Help meeeeeeeeeeee! Mon 15 Mar 2010, 23:31

Mình thấy có điều hơi lạ. Nhìn vào phong cách lập trình rất chuẩn mực của các bạn hoàn toàn không giống học sinh THCS. Sao tiêu đề lại là lớp 9. Thật khó hiểu Rolling Eyes

Tiêu đề: Re: Help meeeeeeeeeeee! Tue 16 Mar 2010, 20:56

Cái này là lớp 9 100% đó.

Tiêu đề: Re: Help meeeeeeeeeeee! Wed 17 Mar 2010, 15:09

^^ đúng đó. Mấy mình là lớp 9 thôi.

Tiêu đề: Re: Help meeeeeeeeeeee! Wed 17 Mar 2010, 15:16

Cho hỏi thêm câu nhé. Trường của các bạn thuộc thành phố hay là tỉnh nào vậy?

Tiêu đề: Re: Help meeeeeeeeeeee! Wed 17 Mar 2010, 15:29

administrators đã viết:: Cho hỏi thêm câu nhé. Trường của các bạn thuộc thành phố hay là tỉnh nào vậy?

Là trường THCS Nguyễn Văn Linh thuộc quận Cẩm Lệ, Thành phố Đà Nẵng. Đó là trường mình, còn bạn hoangtin thì ko phải ở Đà Nẵng, bạn ấy ở Bình Định. Mình và bạn quen nhau qua mạng.

Tiêu đề: Re: Help meeeeeeeeeeee! Wed 17 Mar 2010, 21:06

Mình học trường THCS xã Hoài Thanh Tây ( trường làng) tỉnh Bình Định. Ko ở thành phố đâu.

Tiêu đề: Re: Help meeeeeeeeeeee! Mon 26 Jul 2010, 20:39

Bài này là hoán vị đó mà:
Các bạn có thể tham khảo code của mình:

Code:: Var A:Array['A'..'Z'] of longint;
B:Array[1..500000] of String[9];
Max:longint;
S,S1:String[9];

Procedure Input;
Begin
Readln(S);
Max:=0;
End;

Procedure Try(i:longint);
Var j:char;
Begin
If i>length(S) then
Begin
Inc(Max);
B[Max]:=S1;
Exit;
End;
For j:='A' to 'Z' do
If A[j]>0 then
Begin
Dec(A[j]);
S1:=S1+j;
Try(i+1);
Delete(S1,i,1);
Inc(A[j]);
End;
End;

Procedure Output;
Var i:longint;
Begin
S1:='';
For i:=1 to length(S) do Inc(A[S[i]]);
Try(1);
Writeln(Max);
For i:=1 to Max do Writeln(B[i]);
End;

BEGIN
Input;
Output;
END.