TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
#27 Kit
Dík za upozornění.
Příspěvky odeslané z IP adresy 83.240.123.–
Program VycetKombinaci_k_n;
var
n,k,i: integer;
P: array[1..32767] of integer;
konec: string;
function F(x: integer): integer;
begin
P[k-x]:=P[k-x]+1;
F:=P[k-x];
end;
function G(x: integer): integer;
var i: integer;
begin
for i:=k-x+1 to k do P[i]:=P[i-1]+1;
G:=P[i];
end;
procedure R;
var i: integer;
begin
for i:=1 to k-1 do write(P[i],' ');
writeln(P[k]);
end;
procedure S(x: integer);
begin
if x=0 then
begin
repeat
F(x);
R;
until P[k]=n;
end;
if x>0 then
begin
repeat
S(x-1);
F(x);
G(x);
R;
until P[k]=n;
end;
end;
begin
repeat
writeln('Zvol n v rozmezí od 0 do 32 767 a stiskni Enter.');
readln(n);
writeln('Zvol k v rozmezí od 0 do n a stiskni Enter.');
readln(k);
if k=0 then writeln('{}');
if (k>0) and (n=k) then
begin
for i:=1 to k do P[i]:=i;
R;
end;
if (k>0) and (n>k) then
begin
for i:=1 to k do P[i]:=i;
R;
S(k-1);
end;
writeln('Chceš-li pokračovat, stiskni Enter, v opačném případě
napiš "konec" a stiskni Enter.');
readln(konec)
until konec='konec'
end.
Tak tady to je. V kódu byly dvě banální chyby. Jedna šla odstranit i bez znalosti algoritmu konstrukce všech k-prvkových kombinací z n prvků, na němž je program založen. Tento algoritmus, totiž algoritmus konstrukce všech k-prvkových kombinací z n prvků x1, ... , xn, spočívá pro n > k v postupném převedení variace (x1, ... , xk) na variaci (x(n - k + 1), ... , xn). V tomto převedení lze rozlišit n nad k kroků; v každém z nich vznikne jedna k-prvková variace z daných n prvků taková, že její členy jsou uspořádány podle velikosti zleva doprava od nejmenšího po největší. Protože mezi množinou všech takovýchto variací a množinou všech k-prvkových kombinací sestrojitelných z daných n prvků existuje bijekce, která každé variaci V přiřazuje množinu M(V) všech jejích prvků, |M| = k, a obráceně každé k-prvkové podmnožině M množiny {1, ... , n} variaci V(M) tvořenou jejími prvky, lze sestrojení všech variací z daných n prvků považovat za sestrojení všech kombinací z nich. Mohu přiložit i zápisy algoritmu pro konkrétní dvojice (n, k), ale uvítal bych, kdybys sem nejdřív dal svůj kód po opravě.
#22 Mircosoft
Tak už to mám - tentokrát již doopravdy - odladěné. Jak budu mít čas, dotáhnu zdrojový kód tak, aby program vypisoval kombinace pro libovolnou "rozumně" zvolenou dvojici (n, k), kde k, n jsou celá nezáporná čísla splňující nerovnost k <nebo= n, a zdrojový kód zde vystavím. Podotýkám, že jsem při konečném odlaďování užil tvůj poslední příspěvek jako zdroj námětů. Co přesně bylo potřeba udělat, nevím, jisté však je, že to už funguje. Budu-li mít čas, doplním ke kódu i vysvětlení, jak že to ten program vlastně ty kombinace vytváří a vypisuje.
Jinak jsem studentem práv, nikoli informatiky nebo něčeho podobného, takže známka z toho nebude.
Program VycetKombinaci_k_n;
var
n,k,i: integer;
P: array[1..32766] of integer;
function F(x: integer): integer;
begin
P[k-x]:=P[k-x]+1;
F:=P[k-x]
end;
function G(x: integer): integer;
begin
for i:=k-x+1 to k do P[i]:=P[i-1]+1;
G:=P[i]
end;
procedure R;
begin
for i:=1 to k-1 do write(P[i],' ');
writeln(P[k])
end;
procedure S(x:integer);
begin
if x=2 then
begin
repeat
repeat
F(0);
R;
until P[k]=n;
F(1);
G(1);
R;
until P[k]=n;
end;
if x>2 then
begin
repeat
S(x-1);
F(k-1);
G(k-1);
R;
until P[k]=n
end
end;
begin
writeln('Zvol n v rozmeí od 3 do 32 767 a stiskni Enter.');
readln(n);
writeln('Zvol k v rozmezí od 2 do n-1 a stiskni Enter.');
readln(k);
for i:=1 to k do P[i]:=i;
for i:=1 to k-1 do write(P[i],' ');
writeln(P[k]);
i:=k;
S(i);
writeln('Pro ukončení stiskni Enter.');
readln
end.
Hotovo. Přikládám kód programu po odladění.
Vzkaz pro uživatele Kit a RomanZ: Díky, měli jste pravdu, stačilo použít standardní rekurzi.
Vzkaz pro uživatele Microsoft: Myšlenku máš v zásadě dobrou, ale Tvůj program k-prvkové podmnožiny n prvkové množiny nesype. Chyba Tvého řešení je podle mě již na úrovni algoritmu. A jedna malá poznámka: 0-prvkové kombinace mají smysl. Každá množina obsahuje právě jednu: { }.
Program VycetKombinaci_k_n;
var
n,k,i: integer;
P: array[1..32766] of integer;
function F(x: integer): integer;
begin
P[k-x]:=P[k-x]+1;
F:=P[k-x]
end;
function G(x: integer): integer;
begin
for i:=k-x+1 to k do P[i]:=P[i-1]+1;
G:=P[i]
end;
procedure R;
begin
for i:=1 to k-1 do write(P[i],' ');
writeln(P[k])
end;
procedure S(x,n: integer);
begin
if x=2 then
begin
repeat
repeat
F(0);
R;
until P[x]=n;
F(1);
G(1);
R;
until P[x]=n;
end;
if x>2 then
begin
repeat
S(x-1,n);
F(x-1);
G(x-1);
R;
until P[x]=n
end
end;
begin
writeln('Zvol n v rozmezí od 3 do 32 767 a stiskni Enter.');
readln(n);
writeln('Zvol k v rozmezí od 2 do n-1 a stiskni Enter.');
readln(k);
begin
for i:=1 to k do P[i]:=i;
for i:=1 to k-1 do write(P[i],' ');
writeln(P[k]);
S(k,n);
writeln('Pro ukončení stiskni Enter.');
readln
end
end.
Tak jsem si dal tu práci a pokusil se přece jen program obsahující rekurentně deklarovanou proceduru provádějící k do sebe zanořených cyklů napsat. I když mi to pořád nejede, myslím, že jsem se již podstatně přiblížil k řešení. Část procedury pro první IF je funkční, část pro druhé zatím nikoli. Program se zanoří až do nejnižšího cyklu a provádí jej tak dlouho, dokud nenaplní kapacitu proměnné P[k]; omezující podmínku "until P[k]=n" ignoruje. Pokud někdo bude vědět, kde je chyba, uvítám, když to sem napíše.
#7 Kit
Poslední dva body už neumím napsat. Teoreticky dovedu napsat program pro libovolné k z množiny {1, 2, ...}, odpovídající na vstup n, dovedu vlastně i napsat program, který by odpovídal na vstup k, n, nic z obojího však pro mě není prakticky proveditelné, mají-li moje programy fungovat i pro vysoké hodnoty k.
Program VycetKombinaci3_n;
var n,i,j,k : integer;
begin
write('Zvol n v rozmezí od 3 do 32 767 a stiskni enter:');
readln(n);
if n=3 then
begin
writeln(1,' ',2,' ',3);
write('Pro ukončení stiskni Enter.');
readln;
end;
if n>3 then
begin
i:=1;
j:=2;
k:=3;
writeln(i,' ',j,' ',k);
repeat
repeat
repeat
k:=k+1;
writeln(i,' ',j,' ',k);
until k=n;
j:=j+1;
k:=j+1;
writeln(i,' ',j,' ',k);
until k=n;
i:=i+1;
j:=i+1;
k:=j+1;
writeln(i,' ',j,' ',k);
until k=n;
write('Pro ukončení stiskni Enter.');
readln;
end;
end.
#7 Kit
Program VycetKombinaci2_n;
var n,i,j : integer;
begin
write('Zvol n v rozmezí od 2 do 32 767 a stiskni enter:');
readln(n);
if n=2 then
begin
writeln(1,' ',2);
write('Pro ukončení stiskni Enter.');
readln;
end;
if n>2 then
begin
i:=1;
j:=2;
writeln(i,' ',j);
repeat
repeat
j:=j+1;
writeln(i,' ',j);
until j=n;
i:=i+1;
j:=i+1;
writeln(i,' ',j);
until j=n;
write('Pro ukončení stiskni Enter.');
readln;
end;
end.
#7 Kit
Program VycetKombinaci1_n;
var n,i : integer;
begin
write('Zvol n v rozmezí od 1 do 32 767 a stiskni enter:');
readln(n);
if n=1 then
begin
writeln(1);
write('Pro ukončení stiskni Enter.');
readln;
end;
if n>1 then
begin
i:=1;
writeln(i);
repeat
i:=i+1;
writeln(i);
until i=n;
write('Pro ukončení stiskni Enter.');
readln;
end;
end.
#7 Kit
#7 Kit
OK, popíši tedy svoji konstrukci systému všech k-prvkových podmnožin n-prvkové množiny pro k=1, 2, 3. Pak sem pro jednotlivá k dám kódy mých prográmků, které umí prvky systému vypsat. Dál se pokusím vyložit svoji obecnou konstrukci systému všech k-prvkových podmnožin n-prvkové množiny. A nakonec uvedu kód příslušného prográmku, který ale jaksi nejede.
Mám následující problém: Chci napsat program, který pro uživatelem "rozumně" zvolená čísla k, n vypíše všechny k-prvkové kombinace z n prvků. Bylo by to velmi jednoduché, kdybych měl k dispozici jazyk, ve kterém by šlo napsat program, jenž by si pro zvolené k vždy sám "doprogramoval" k do sebe vnořených cyklů (1. do 2., 2. do 3., ..., k-1. do k-tého.); stačilo by dát programu rekurentní návod, jak to v závislosti na uživatelem zvolených číslech k, n udělat. Že něco takového jde, už vím. Uvítám nicméně praktickou radu, kudy se při řešení problému vydat.
Poznámka: Zatím umím programovat jen v Pascalu. V něm jsem již napsal programy, které pro uživatelem zvolené n vypíší všechny 1-, 2- a 3-prvkové kombinace z n prvků.
