02/10/2018, 13:57
BCPERMU PTIT spoj – Liệt kê hoán vị (Cơ bản)
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCPERMU/ 1. Đề bài Liệt kê hoán vị Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n. Input Dòng duy nhất chứa số n (1<=n<=8) Output Các hoán vị sắp xếp theo thứ tự từ điển tăng dần. Example Input: ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCPERMU/
1. Đề bài Liệt kê hoán vị
Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n.
Input
Dòng duy nhất chứa số n (1<=n<=8)
Output
Các hoán vị sắp xếp theo thứ tự từ điển tăng dần.
Example
Input:
3
Output:
123
132
213
231
312
321
2. Code Liệt kê hoán vị pascal c++
a. code pascal BCPERMU
const
nmax=8;
type
data = byte;
var
n:data;
dd:array[1..nmax] of boolean;
res:array[1..nmax]of data;
procedure xuat;
var i:data;
begin
for i:=1 to n do
write(res[i]);
writeln;
end;
procedure try(i:data);
var j:data;
begin
if i>n then
xuat
else
for j:=1 to n do
if not dd[j] then
begin
dd[j]:=true;
res[i]:=j;
try(i+1);
dd[j]:=false;
end;
end;
begin
readln(n);
fillchar(dd,sizeof(dd),false);
try(1);
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | const nmax=8; type data = byte; var n:data; dd:array[1..nmax] of boolean; res:array[1..nmax]of data; procedure xuat; var i:data; begin for i:=1 to n do write(res[i]); writeln; end; procedure try(i:data); var j:data; begin if i>n then xuat else for j:=1 to n do if not dd[j] then begin dd[j]:=true; res[i]:=j; try(i+1); dd[j]:=false; end; end; begin readln(n); fillchar(dd,sizeof(dd),false); try(1); end. |
b. code c++ BCPERMU
#include <stdio.h>
using namespace std;
#define nmax=8;
int n;
bool dd[10];
int res[10];
void xuat()
{
int i;
for (i=1; i<=n; i++)
printf("%d",res[i]);
printf("
");
}
void dequy(int i)
{
int j;
if (i>n)
{
xuat();
}
else
{
for (j=1; j<=n; j++)
{
if (dd[j]==false)
{
dd[j]=true;
res[i]=j;
dequy(i+1);
dd[j]=false;
}
}
}
}
int main()
{
scanf("%d",&n);
int i;
for (i=1; i<=3; i++) dd[i]=false;
dequy(1);
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include <stdio.h> using namespace std; #define nmax=8; int n; bool dd[10]; int res[10]; void xuat() { int i; for (i=1; i<=n; i++) printf("%d",res[i]); printf("
"); } void dequy(int i) { int j; if (i>n) { xuat(); } else { for (j=1; j<=n; j++) { if (dd[j]==false) { dd[j]=true; res[i]=j; dequy(i+1); dd[j]=false; } } } } int main() { scanf("%d",&n); int i; for (i=1; i<=3; i++) dd[i]=false; dequy(1); return 0; } |
