Задачка

← →
Oleg_Gashev (2002-09-07 19:24) [0]

Делать ничего не хотелось, вот и написал. Hапечатать все перестановки чисел 1..N.

#include <stdio.h> #define SIZE 3 int PermutationsNumber; void InsertNumber(int Number,int a[SIZE]); void main(void) { int a[SIZE]; PermutationsNumber=0; InsertNumber(1,a); printf("%d\n",PermutationsNumber); } void InsertNumber(int Number,int a[SIZE]) { int i,t,k; int b[SIZE]; if (Number-1==SIZE) { PermutationsNumber++; for (i=0;i<SIZE;i++) printf("%d ",a[i]); printf("\n"); return; } a[Number-1]=Number; for (k=0;k<SIZE;k++) b[k]=a[k]; InsertNumber(Number+1,b); for (i=Number-2;i>=0;i--) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; for (k=0;k<SIZE;k++) b[k]=a[k]; InsertNumber(Number+1,b); } }

А вот Вам задачка: сгенерировать все подмножества данного n-элементного множества {0,.., n-1}

Олег.

← →
Николай Быков (2002-09-07 19:27) [1]

А правда stdio.h лучше чем iostream.h?
Мне так говорили, а во всех книгах стоит iostream.h ..
А чем он лучше?

← →
Suntechnic (2002-09-07 19:32) [2]

>Николай Быков © (07.09.02 19:27)
А правда stdio.h лучше чем iostream.h?
Мне так говорили, а во всех книгах стоит iostream.h ..
А чем он лучше?

Их сравнивать нечего. stdio.h это библиотека С, а iostream.h это библиотека С++. Т.е. теоретически если ты пишешь программу на С++ надо бы использовать iostream.h, ну а на С просто выбора нет.

← →
MrBeer (2002-09-07 19:44) [3]

> 2 Николай Быков

"Просьба писать по существу. Жалко что я не модератор и не могу удалить отсюда сообщения ..." ;))

← →
Николай Быков (2002-09-07 19:59) [4]

2 МрБир
А Си приплюс вообще не к месту на сайте про Делфи

← →
Suntechnic (2002-09-07 20:00) [5]

>MrBeer © (07.09.02 19:44)
"Просьба писать по существу. Жалко что я не модератор и не могу удалить отсюда сообщения ..." ;))

Не забывайтесь. Это раздел потрепаться!

← →
Mister X (2002-09-07 20:01) [6]

Особенно ламеры не к месту на сайте Делфи. И не только здесь, а ВЕЗДЕ.

← →
MrBeer (2002-09-07 20:09) [7]

> 2 ALL:

1) etot source na C ne C++.
2) rech" idyot o algoritme, a ne realizacii - pishite hot" v psevdo-kode.

← →
Oleg_Gashev (2002-09-07 20:39) [8]

Нда, тяжко у людей с логикой. Алгоритм ищите сами, надоело решения выдавать. А задача на уровне школы.

← →
evgeg (2002-09-07 20:44) [9]

> MrBeer

Ну уж вы то здесь точно ничего по существу не написали.

> Oleg_Gashev

Наверное, всем неохота такие задачки решать. Да и ваше решение в первом сообщении как то не впечатляет.

← →
MrBeer (2002-09-07 20:48) [10]

> 2 evgeg ©

Ya vsego-lish otvetil Nikolaju ego zhe slovami kotorie on adresoval mne v drugoi vetke.

← →
Oleg_Gashev (2002-09-07 20:54) [11]

> Да и ваше решение в первом сообщении как то не впечатляет.

Может быть. Решение построено на алгоритме, взятом из Кнута. Том 1. Глава 1.2.5. Метод 1.

Для каждой перестановки a(1) a(2) a(3) .... a(n-1) из {1,2,..,n-1} объектов построим еще n перестановок, помещая число n на все возможные места.

Если Вы упростите мой код, прошу его привести. Вижу упрощение только в задании переменной b. Так как она задается дважды как
for (k=0;k<SIZE;k++) b[k]=a[k];

← →
MBo (2002-09-08 09:26) [12]

Порт на Delphi. Массив B не нужен.

procedure TForm1.Button1Click(Sender: TObject);
const
Size = 3;
type
ta = array[0..Size - 1] of integer;
var
PermNum: Integer;
a: ta;

procedure InsertNumber(Number: Integer; a: ta);
var
i, t: Integer;
s: string;
begin
s := "";
if (Number - 1 = Size) then begin
Inc(PermNum);
for i:=0 to Size - 1 do
s := s + Format("%d ", [a[i]]);
Memo1.Lines.Add(s);
Exit;
end else begin
a[Number-1] := Number;
InsertNumber (Number + 1, a);
for i:=Number - 2 downto 0 do begin
t:= a[i];
a[i]:= a[i+1];
a[i+1]:= t;
InsertNumber(Number + 1, a);
end;
end;
end;

begin
Memo1.Clear;
PermNum:=0;
InsertNumber(1,a);
Memo1.Lines.Add(Format("%d permutations",[PermNum]));
end;

← →
Oleg_Gashev (2002-09-08 09:49) [13]

>MBo

В твоем коде массив b действительно не нужен. В С я не могу передать а, так как а является указателем. Мне необходимо было передать его значение. Вот и пришлось вводить новую переменную.

← →
MBo (2002-09-08 11:00) [14]

В предыдущем моем постинге
else begin и соотв. end лишние- и так уже есть exit

>Oleg_Gashev © (08.09.02 09:49)
Понимаю.
Нашел у себя в старом такую задачу.
Алгоритм тот же, отличие только:
вместо
for i:=Number - 2 downto 0 do begin
было
for i:=Number+1 to MaxNum
c соотв. коррекцией обменного куска.

>задачка: сгенерировать все подмножества данного n-элементного множества

procedure TForm1.Button3Click(Sender: TObject);
var
Start:string;

procedure Chooser(N:Integer; S:String);
begin
if N>Length(Start) then begin
Memo1.Lines.Add(S);
Exit;
end;

Chooser(N+1,S);
S:=S+Start[N];
Chooser(N+1,S);

// сначала написал ;)))
// for b:=False to True do begin
// if b then S:=S+Start[N];
// Chooser(N+1,S);
// end;

end;

begin
Memo1.Clear;
Start:="1234";
Chooser(1,"");
end;

← →
MBo (2002-09-08 11:03) [15]

модификация для множеств (S:set of Char)

Chooser(N+1,S);
Include(S,Start[N]);
Chooser(N+1,S);

← →
Oleg_Gashev (2002-09-08 11:28) [16]

В прведенном мной алгоритме порядок вывода перестановок не будет лексикографическим. Если делать его лексикографическим, вижу пока только решение в построении дерева с последующим обходом для вывода результатов.

Дерево будет строится так. От вершины дерева строю SIZE узлов 1,2,...,SIZE. От этих узлов строю ветки 1,2,...,SIZE, пропуская значение узла. И так далее. То есть кол-во веток будет уменьшаться в зависимости от уровня дерева.

В конце остается только оббежать все дерево.

← →
Oleg_Gashev (2002-09-08 11:35) [17]

-1---------2---------3---
! ! !
+---+ +---+ +---+
! ! ! ! ! !
2 3 1 3 1 2
! ! ! ! ! !
3 2 3 1 2 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

← →
Oleg_Gashev (2002-09-08 11:37) [18]

Нда, sorry за рисунок.

← →
MBo (2002-09-08 12:58) [19]

Еще вариант, тоже не упорядоченный лексикографически и не
"алгоритмический" - используются готовые списки, но симпатичный, потому что "прозрачный"
procedure TForm1.Button4Click(Sender: TObject);
var
Start:String;
List: TStringList;

procedure Mix(N:Integer);
var i:integer;
begin
if n=0 then begin
Memo1.Lines.Add(List.Commatext);
Exit;
end;
for i:= 0 to List.Count do begin
List.Insert(i,Start[n]);
Mix(n-1);
List.Delete(i);
end;
end;

begin
Start:="ABCD";
List:=TStringList.Create;
Mix(Length(Start));
Memo1.Lines.Add(IntToStr(Memo1.Lines.Count)+" permutations");
List.Free;
end;

← →
MBo (2002-09-08 13:01) [20]

аналогично можно и без списка, Insert и Delete делая с простой строкой

← →
Oleg_Gashev (2002-09-08 21:56) [21]

> MBo

А перебора не будет?

← →
MBo (2002-09-09 06:24) [22]

>А перебора не будет?
О чем это?

Задачка Найти похожие ветки