wata napisał(a)
a co daje to sortowanie liczb dokladnie ?
Jak skreślasz liczby to maszyna drukuje ci je na kuponie w kolejności od najmniejszej.
Sortowanie w zasadzie nie jest potrzebne, ale ulepsza wynik.
Swoją drogą ładny temacik się zrobił, ciekawe kto wygra ;]
mam taka mala prosbe czy ktos kto ma takie uprawnienia moglby zmienic nazwe tematu np. na "[konkurs] program bez tablic" ??
imho aktualny temat lepiej opisuje to co faktycznie się tu znajduje, niż ten proponowany przez Ciebie... a ja się póki co zastanawiam czy aby mój algorytm nie ma błędu + ewentualna optymalizacja. Także możliwe, że wrzucę jakiś update...
EDIT: jest tak jak sądziłem - w programie jest błąd i trzeba dodawać nowe warunki (morze warunków), żeby wyszło to co trzeba. Mimo to nie poddam się i próbuję to naprawić/zmienić ;]
@Yorkouza: zamknij kod programu w repeat ... until (x1=x2) or (x1=x3) or (x2=x3) or (x4=x1) or (x4=x2) or (x4=x3) or (x5=x1) or (x5=x2) or (x5=x3) or (x5=x4) or (x6=x1) or (x6=x2) or (x6=x3) or (x6=x4) or (x6=x5); i sprawdź jak często zwraca zdublowane.
funkcja newx jest skopana: załóż sytuację, kiedy wylosowane x=N, dowolna z poprzednich wylosowanych to N a wszystkie po niej < N - funkcja zwróci N (np. 31,19,9,31,... albo 13,11,13,...).
poza tym sam pomysł zwiększania x jest trochę naciągany - w ten sposób zwiększasz dwukrotnie prawdopodobieństwo, że dwie liczby będą leżeć obok siebie.
ale nie poddawaj się i próbuj dalej, miałeś ciekawy i oryginalny pomysł, pewnie wpadniesz na kolejny taki.
@Opi: masz gdzieś błąd, ale nie mam siły analizować. przypisz a6 = a5; zamiast losować wartość a6 (czyli hipotetyczna sytuacja, że a6 wylosuje się tak samo jak a5), zapuść program kilkadziesiąt razy i wyjdzie duplikat (pomijając fakt, że liczby nie są wtedy posortowane), np. 26,39,47,27,47.
ale chociaż nie mam siły wniknąć głębiej w sens algorytmu, to wygląda całkiem interesujaco.
PANOWIE i PANIE: upewnijcie się, że kod działa poprawnie zanim go wkleicie. przydaje się zapuścić kod w pętli kończącej się, jeśli wystąpił duplikat.
na razie nadal trzy poprawnie działające rozwiązania i dwa nowe działające "prawie" ;-) do tego uścisk dłoni prezesa dla Opiego za fajne sortowanie.
@ŁF: tak, zauważyłem że program działa niepoprawnie czasami liczba zostanie zwiększona przy kolejnym porównaniu w funkcji NewX i jednocześnie zrównuje się, lub nawet jest większa od poprzedniej, która podczas porównywania była mniejsza. Chciałem uniknąć pętli i uprościć algorytm, a zamiast tego zagmatwałem się po odnalezieniu błędu. Wyszedłem z założenia, że działanie tak jak maszyna lotto będzie logiczne, a jednak w języku programowania nie jest to takie oczywiste :) Pokombinuję jeszcze nad rozwiązaniem, ale już widać, że zmiany będą zwiększać złożoność algorytmu ;/
A co do pomysłu zwiększania x to moim zdaniem nie jest naciągany i nie wydaje się zwiększać prawdopodobieństwa na wystąpienie liczb obok siebie. Wyszedłem z założenia, że po wylosowaniu liczby wszystkie większe przesuwają się w lewo (zmniejszają o 1). Wydawało się to logiczne.
ŁF napisał(a)
@Opi: masz gdzieś błąd, ale nie mam siły analizować. przypisz a6 = a5; zamiast losować wartość a6 (czyli hipotetyczna sytuacja, że a6 wylosuje się tak samo jak a5), zapuść program kilkadziesiąt razy i wyjdzie duplikat (pomijając fakt, że liczby nie są wtedy posortowane), np. 26,39,47,27,47.
ale chociaż nie mam siły wniknąć głębiej w sens algorytmu, to wygląda całkiem interesujaco.
Błąd zdaje się był przy sprawdzaniu warunku if j > 6 then begin s:= ''; j := 0; end;
Teraz jest dobrze, po podstawieniu a6 = a5, tak jak ŁF sugerujesz, wyniki nie pojawiają się, więc warunek until j = 6 jest "poprawnie" nie spełniony (pętla nieskończona).
var
j: byte = 0;
i, a1, a2, a3, a4, a5, a6: byte;
s: string;
begin
Randomize;
repeat
s := '';
j := 0;
a1 := Random(49)+1;
a2 := Random(49)+1;
a3 := Random(49)+1;
a4 := Random(49)+1;
a5 := Random(49)+1;
a6 := Random(49)+1;
for i := 1 to 49 do
if i = a1 then
begin
Inc(j);
s := s + IntToStr(a1) + ' ';
end
else
if i = a2 then
begin
Inc(j);
s := s + IntToStr(a2) + ' ';
end
else
if i = a3 then
begin
Inc(j);
s := s + IntToStr(a3) + ' ';
end
else
if i = a4 then
begin
Inc(j);
s := s + IntToStr(a4) + ' ';
end
else
if i = a5 then
begin
Inc(j);
s := s + IntToStr(a5) + ' ';
end
else
if i = a6 then
begin
Inc(j);
s := s + IntToStr(a6) + ' ';
end;
until j = 6;
writeln(s);
readln;
end.
ŁF napisał(a)
do tego uścisk dłoni prezesa dla Opiego za fajne sortowanie.
Dziękuję, nie sądziłem, że mój przykład z sortowaniem okaże się tak trafny. Myślałem, że zaraz ktoś coś lepszego poda ;]
Pozdrawiam ŁF
ok, teraz powinno działać. fajny algorytm, jednak jest to tylko kompletnie inaczej zrealizowane sprawdzanie tego dłuuugiego warunku gwarantującego, że nie będzie dubli. ilość losowań jest nawet większa niż w Twoim pierwszym kodzie, wiesz dlaczego?
co do sortowania - chyba nie da się napisać prostszego algorytmu sortowania bez użycia tablic.
stringi to jednak tablice!
zbiory mozna udawac kuglujac bitami, a I latwo sprawdzic czy juz byl numerek I w naturalny sposob wynik bedzie posortowany.
pascalowy zbior to tyz tablica, niby bitow ale zawsze.
ma nie byc tablic?
nie potrzeba tablic, wystarczy kilk prostych zmiennych jedno while I jeden if [diabel],
aha jedno losowanie wystarczy [browar]
(rysik mojego palma jest bez alta)
@Opi: ten ostatni algorytm jest zupełnie niewydajny... powtarzanie wszystkich losowań, zamiast pojedynczego zwiększy złożoność i to znacznie :)
@Xitami_: zaprezentuj kod, bo tak to ciężko się domyślić co dokładnie miałeś na myśli i czy jest to faktycznie algorytm, który może walczyć o miano zwycięskiego :P
@manfredek: ten algorytm to jest taki sam jak mój (prawie), tylko moim zdaniem nieco gorszy. Co prawda mniejsza szansa na dubla (np. gdyby losowane było kolejno: 33, 32, 32), ale dodatkowo wyniki mogą przekroczyć 49 ;] Dodatkowo nieładnie wygląda niewysłanie zmiennych do funkcji, zamiast tego odnoszenie się do globalnych. W linijce wypisywania zmiennych widać, że zmieniałeś mój kod dla oszczędności czasu xD
Teraz kombinuję na bitach, więc zaraz pogadamy ;P
Edit: Ha, mam:
//[CIACH!] Reason: deprecated. Kod poprawny jest niżej.
Na tablicach bez używania tablic. Amen.
manfredek napisał(a)
Teraz kombinuję na bitach, więc zaraz pogadamy
Wrzuć w pętle losowanie
begin
Randomize;
for k := 0 to 100 do
begin
Write(Randek, ' ', Randek, ' ', Randek, ' ', Randek, ' ', Randek, ' ', Randek);
ReadLn;
end;
end.
a zauważysz, że po 8/9 losowaniu, następuje wewnątrz funkcji Randek nieskończone niespełnienie warunku.
Na pewno jest to spowodowane tym, że:
[Pascal Warning] Project1.dpr(33): W1036 Zmienna 'j' nie została zainicjowana
[Pascal Warning] Project1.dpr(41): W1035 Wynik wartości funkcji 'Randek' nie został zdefiniowany
Ale cały algorytm całkiem dobrze się prezentuje i do kilku pierwszych losowań spełnia swoją rolę.
Co ważniejsze, jest to inny od dotychczas zaprezentowanych algorytmów.
Jeszcze sortowanie by się przydało ;)
ŁF napisał(a)
ilość losowań jest nawet większa niż w Twoim pierwszym kodzie, wiesz dlaczego?
Nie bardzo, ale po każdym zdublowaniu liczby następuje kolejne losowanie, a tym samym wykona się ponownie pętla for.
// właśnie o to chodzi - powtarzasz wszystkie losowania - Ł
Yorkouza napisał(a)
@Opi: ten ostatni algorytm jest zupełnie niewydajny... powtarzanie wszystkich losowań, zamiast pojedynczego zwiększy złożoność i to znacznie :)
W tym tkwi problem, pokombinuję jeszcze ;]
Yorkouza napisał(a)
A co do pomysłu zwiększania x to moim zdaniem nie jest naciągany i nie wydaje się zwiększać prawdopodobieństwa na wystąpienie liczb obok siebie. Wyszedłem z założenia, że po wylosowaniu liczby wszystkie większe przesuwają się w lewo (zmniejszają o 1). Wydawało się to logiczne.
jest. dla uproszczenia przykład na dwóch liczbach: standardowo masz p=2/48, że następna liczba wypadnie obok poprzedniej (z góry lub dołu mod 49); u Ciebie jest to 1/49 (losowo wypadnie wyżej) + 1/49 (losowo wypadnie niżej) + 1/49 (wypadnie to samo, co poprzednio i zostanie zwiększone o 1).
1/24 < 3/49
dodatkowy problem polega na tym, że losowanie odbywa się na zbiorze 49 liczb, więc mianownik jest inny - ale u mnie jest analogiczny problem (tylko później).
manfredek, popraw błąd i będziemy mieć czwarte działające rozwiązanie.
PROSZĘ PORZĄDNIE PRZETESTUJCIE SWOJE ROZWIĄZANIA PRZED UMIESZCZENIEM ICH NA FORUM (manfredek, to się odnosi też i do Ciebie)
[Pascal Warning] Project1.dpr(33): W1036 Zmienna 'j' nie została zainicjowana
A tam. Ona nie ma być czym inicjalizowana, ale też się poprawi. [EDIT: A jednak nie. Po co. Jej wartość niezbyt mnie obchodzi. Wcześniej przez copy'ego-paste'a miałem w elsie te 'j', ale teraz jest już 'i' i działa dobrze.
Hehehe, wiedziałem że coś jest źle, dzięki za wychwycenie błędu. Zaraz to poprawię.
Gotowe.
program lotto;
uses Crt;
var
a1_32: longword;
a33_64: longword;
i : Integer;
function Losuj(init : byte):byte;
function Randek: byte;
var
i, j : Byte;
begin
while true do
begin
i := Random(49) + 1;
if(i > 32) then
begin
j := i - 32;
if(((a33_64 and (1 shl j)) shr j) = 1) then
begin
a33_64 := a33_64 and (not(1 shl j));
Randek := i;
Break;
end;
end
else begin
if(((a1_32 and (1 shl i)) shr i) = 1) then
begin
a1_32 := a1_32 and (not(1 shl i));
Randek := i;
Break;
end;
end;
end;
end;
begin
if init <> 0 then begin
a1_32 := $FFFFFFFF;
a33_64 := $FFFFFFFF;
end;
Losuj := Randek;
end;
begin
Randomize;
for i:=0 to 100 do
begin
WriteLn(Losuj(1), ' ', Losuj(0), ' ', Losuj(0), ' ', Losuj(0), ' ', Losuj(0), ' ', Losuj(0)); {jak widać, aby losować wszystkie 6 ponownie, należy pierwsze losowanie wywołać z 1 jako parametr, a następne z 0.}
end;
ReadLn;
end.
Ja proponuję inne podejście. Wszystkie możliwe wyniki losowania (sześcioelementowe podzbiory zbioru
1,..,49) ustawiamy (wirtualnie) w ciąg o C(49,6) = 13983816 elementach uporządkowany leksykograficznie:
a=(a1,..,a6) jest przed b=(b1,..,b6) <==>
a1 < b1 lub (a1 = b1 oraz a2 < b2) lub ...
Losujemy jedną liczbę z przedziału [1,13983816] i odtwarzamy ciąg, który w opisanym wyżej
uporządkowaniu jest na wylosowanym miejscu.
Kod jest w Javie, przeróbka na C++ jest trywialna
Random r=new Random();
int l=1+r.nextInt((int)C(49,6));
System.out.println("Wylosowano "+l);
int zIlu=49;
long s=0;
int n=zIlu-1;
int k=5;
long poprzednia=0;
for(int i=0;i<6;i++)
{
//while(s<l) tak było, ma być jak niżej
while(s<l && n>=k)
{
poprzednia=s;
s+=C(n,k);
n--;
}
int liczba=zIlu-n-1;
System.out.print(liczba+" ");
l-=poprzednia;
n=zIlu-liczba-1;
s=0;
poprzednia=0;
k--;
}
Wynik jest od razu posortowany. C(n,k) to współczynnik Newtona
private static long C(int n,int k)
{
long wynik=1;
int i=k;
while(i>0)
{
wynik*=n;
n--;
i--;
}
return wynik/silnia(k);
}
//------------------------
private static int silnia(int n)
{
int s=1;
while(n>0)
{
s*=n;
n--;
}
return s;
}
pozdrawiam
//Dopisałem deklarację zmiennej zIlu (=49). Mój program testowy był bardziej uniwersalny, ilość liczb spośród których losujemy i ilość losowanych liczb były parametrami przekazywanymi do programu. W tym co zamieściłem na forum opuściłem odczyt parametrów, ale w dwóch miejscach zostało odwołanie do zmiennej zIlu.
//(15.6) Nagrody jeszcze nie otrzymałem, pozwalam sobie więc poprawić nagrodzony (choć trochę błędny) algorytm. Funkcję C(n,k) zostawiam w dotychczasowej, kiepskiej, postaci.
ha ha ha, każdy rzeźbi, włącznie ze mną, a rozwiązanie faktycznie jest takie banalne (jeśli chodzi o ilość losowań i szybkość).
bogdans, brawo!
prościej juz się chyba nie da... czy tez moze ktos jeszcze chce spróbować?
Nie wiem czy dobrze zrozumiałem (nie znam Javy i jestem zmęczony... piwem), ale ten algorytm losuje jedną z możliwych do wylosowania kombinacji 6 liczb bez powtórzeń, a następnie ustala jakie to są liczby? A w zbiorze tym (zbiorze 6-cio elementowych, różnych rozwiązań) możliwe ułożenia liczb są już posortowane (z założenia) tj. słowa w encyklopedii?
To już są, jak dla mnie, wyższe techniki matematyczne :) Mam pewnie do czynienia z absolwentami/studentami wyższych roczników studiów informatycznych uniwersyteckich? :P
Tak czy inaczej, ja również gratuluję ciekawego pomysłu, chociaż przyznam szczerze, że mam pewne wątpliwości do jego szybkośći... no, ale ja się nie znam.
Yorkouza napisał(a)
Nie wiem czy dobrze zrozumiałem ...
Dobrze
Yorkouza napisał(a)
To już są, jak dla mnie, wyższe techniki matematyczne :) Mam pewnie do czynienia z absolwentami/studentami wyższych roczników studiów informatycznych uniwersyteckich?...
Czy ja wiem? Ja mam tylko maturę, ale lubię takie zabawki, w sumie w symbolu Newtona nie ma nic, czego nie można policzyć na palcach :-)
A jak to się liczy, gdyby kogoś to interesowało to ja, czy Bogdans, możemy o tym opowiedzieć.</quote>
bogdans napisał(a)
Ja proponję inne podejście...
Ciekawym, czy mój post był jakąś inspiracją? :-)
Właśnie to samo miałem na myśli, napisałem że jedno WHILE jedno IF i jedno losowanie...
I prawie się udało.
Założyłem, że nie będę potrzebował liczyć bo „sprytnie” skorzystam z tego, że
i to oczywiście zadziałało.
Oraz, że (1) (tu nie do końca wyjszło)
oraz, że (2) ,
(kiedy liczymy na całkowitych liczbach, kolejność mnożeń i dzieleń ma znaczenie).
Udało się prawie, bo musiałem dodać jedo IF, tam gdie liczę (1).
Poprawnie napisana funkcja BINOMIAL (Newton czy C() u Bogdansa) powinna uwzględniać takie przypadki jak np.
Mój algorytm (PARI/GP):
n=48; k=5;
b=4847/246/345/444/5; // czyli: binomial(49-1, 6-1);
c=1; // “skreślony” numerek
z=random(13983816)+1; // numer kombinacji + 1 (b49/6)
while(k+1>0,
if(z<b,
print1(c" "); c++;
if(n>0, // ponadplanowy IF
b=bk/n; // (1) czyli b=binomial(n-1, k-1)
,
b=1;
);
n--; k--;
,
c++;
z=z-b;
b=b*(n-k)/n; // (2) czyli: b=binomial(n-1,k);
n--;
);
);
PARI/GP ale chyba zrozumiałe.
Razem: bez tablic, jedno WHILE, dwa razy IF, góra 49 kroków prowadzi do posortowanego rozwiązania.
@Bogdans: nie „domyślałeś” sztuczek z liczeniem symbolu Newtona, a sposób w jaki go liczysz nie podoba mnie mi się szczerze mówiąc. Dowcipniej jest chyba jednak tak: (48,5)= 48*47/2*46/3*45/4*44/5.
Czyli ja mam krótszego? :-(
Może ktoś pozbyłby się tego „zbędnego” IF?
Jeżeli <tex>{n\choose{k}}<\frac{MAX_{}INT}{k}</tex> to może lepszy sposób niż <tex>k</tex> losowych podmian w tablicy o długości <tex>n</tex>?
24 bity wystarczą, żeby zapamiętać 6 skreśleń w zakładzie Wielkiego Lotka.
3 4 5 w tej grupie jest C(2,2)=1 element (bo wybieramy dwie liczby z dwóch większych od 3)
Losujemy liczbę z zakresu [1,10], załóżmy że wylosowaliśmy 8. 8>C(4,2) więc ósmy ciąg nie należy do pierwszej grupy, 8<=C(4,2)+C(3,2) więc ósmy ciąg jest w drugiej grupie. W drugiej grupie wszystkie ciągi
zaczynają się od 2, zatem pierwszy wyraz ciągu wynosi 2. Dalej ograniczamy się do drugiej grupy (początkowe 2 pomijam, bo jest w każdym ciągu z tej grupy)
3 4 w tej podgrupie są C(2,1)=2 elementy (bo wybieramy jedną liczbę z dwóch większych od 3)
3 5
....
4 5 w tej podgrupie jest C(1,1)=1 element (bo wybieramy jedną liczbę z jednej większej od 4)
W podgrupach poprzedzających było 6 elementów, zatem badany ciąg jest w tej grupie na 8-6=2 miejscu. Ponieważ C(2,1)=2<=2, to badany ciąg jest w pierwszej podgrupie. W tej podgrupie wszystkie ciągi zaczynają się od 3. Zatem druga liczba w ciągu to 3.
Ja też mm z matematyki tylko maturę, lubię czasami pokombinować/pogłówkować, ale oczytywanie się z zakresu "zabawek" matematycznych niekoniecznie mnie bawi.
Zastanawia mnie jednak czemu za poprawną liczbę rozwiązań przyjmujecie 13 miliardów (z hakiem). Tyle jest z powtórzeniami... bez powtórzeń moim zdaniem możliwych rozwiązań jest 10068347520...
Gdzieś ty się tych miliardów dopatrzył ? 13 983 816 to jest 13 milionów z hakiem.
C(n,k) = (n*(n-1)(n-2)...(n+1-k))/123...k to ilość k-elementowych podzbiorów zbioru n-elementowego. W szczególności C(49,6)=(494847464544)/12345*6 to ilość 6-elementowych podzbiorów zbioru 49=elementowego.
hmm... jak widać zdążyłem już zapomnieć nauki o prawdopodobieństwie z liceum ;/ kończę już z głupimi pytaniami ;P
Sprawdziłem szybkość swojego algorytmu (z niepoprawioną funkcją C(...)). (RAM 2 050 280k).
100 000 losowań zajmuje około 200 ms.
Witam,
No jest bardzo duży błąd w rozumowaniu tutaj z tym "bez tablic" ponieważ, po wylosowaniu jakieś liczby musimy ją zapamiętać w celu porównania a tym samym wyeliminowania duplikatów, a każdy zbiór zmiennych będzie tak naprawdę tablicą która nie jest uporządkowana.
a więc czy zrobimy tak:
var
a,b,c,d,e,f : byte;
(jak by nie patrzeć jest to "tablica")
czy tak:
var
A: array[1..6] of integer;
to kompletnie nie ma znaczenia...
tylko musicie się więcej napisać
Pozdrawiam.
edit: Trzeba tak losować i porównywać żeby nie zapamiętywać :)
Mocne, bardzo mnie to poruszyło :D
Ale jak tak traktujesz pojęcie "bez tablic" to jak się ustosunkujesz do faktu, że program w zasadzie jest tablicą poleceń (w końcu jest zapisany jako uszeregowany zbiór wywołań procesora). Idąc Twym tokiem rozumowania w ogóle nie możemy pisać programów, boć to "tablice".
To w takim razie ja mam rozwiązanie. Kup kostkę 49 ścienną i rzucaj nią sobie dopóki nie będziesz miał sześciu różnych liczb.
EOT
Satyricon: naciągane. Rozumiem, że możesz kilka zmiennych tego samego typu, położonych jeszcze obok siebie w pamięci utożsamiać z tablicą i w kilku językach nawet tak możesz się do nich odwoływać (C). Ale z punktu widzenia specyfikacji samego języka programowania tablica, nawet jednoelementowa, to co innego niż zwykły int, char czy struct i kompilator nie ma problemów z odróżnieniem jednego od drugiego. Taki punkt widzenia przyjęto w tym watku i doskonale sobie z tego powinieneś zdawać sprawę, o ile przeczytałeś chociaż kilka postów, więc daruj sobie swoje i tak naciągane wnioski.
imho wygrywa bogdans (może niekoniecznie najszybsze rozwiązanie, ale najlepiej spełniające założenia zadania).
uśmiech Adama przyślemy pocztą gołębią. chyba, że ktoś się nie zgadza z moją opinią odnośnie jego rozwiązania.
f(c,z,b,n,k)={
if(z<b,
print1(c" ");
if(n,f(c+1, z , b*k \n, n-1, k-1 ));
,
if(n,f(c+1, z-b, b*(n-k)\n, n-1, k ));
);
}
f(1, 0, 48*47\2*46\3*45\4*44\5, 48, 5) \\ pierwsza
f(1, random(49*48\2*47\3*46\4*45\5*44\6)+1, 48*47\2*46\3*45\4*44\5, 48, 5) \\ losowa
f(1, 49*48\2*47\3*46\4*45\5*44\6-1, 48*47\2*46\3*45\4*44\5, 48, 5) \\ ostatnia
mgr.Dobrowolski napisał
f(c,z,b,n,k)={
if(z<b,
print1(c" ");
if(n,f(c+1, z , bk \n, n-1, k-1 ));
,
if(n,f(c+1, z-b, b(n-k)\n, n-1, k ));
);
}
Ale co to właściwie jest ?
bogdans napisał(a)
Ale co to właściwie jest ?
f(c,z,b,n,k)
funkcja pokazujaca K-elementowa kombinacje ze zbioru N elementowego, kombinacja ta jest Z-ta z kolei, N-elementowy zbior to kolejne liczby naturalne, poczynajac od C. Pomocnicze B sluzy do oobliczania symbolu Newtona. [diabel]
Czyli w sumie, kolejne rozwiazanie konkursu
mgr.Dobrowolski napisał(a)
Czyli w sumie, kolejne rozwiazanie konkursu
Rozwiązanie będzie jak to przepiszesz do Delphi, a na razie jest to tylko schemat.
Opi napisał(a)
mgr.Dobrowolski napisał(a)
Czyli w sumie, kolejne rozwiazanie konkursu
Rozwiązanie będzie jak to przepiszesz do Delphi, a na razie jest to tylko schemat.
Jest to sprawdzony kod, kod PARI/GP.
Ale dobra, przepisałem na pascal (Free Pascal), zmierzyłem czas znalezienia wszystkich C(49,6) kombinacji (oczywiście bez wyświetlania).
uses sysutils;
function C(n,k:integer):integer;
var i:integer;
begin
//if 2*k>n then k:=n-k;
result:=1;
for i:=1 to k do begin
result:=result*n div i;
n:=n-1;
end
end;
procedure BogdanS(l,n,k:integer); // kosmetyczne poprawki
var zilu, liczba, poprzednia, s:integer;
begin
dec(n); dec(k);
zilu:=n;
while k>=0 do begin
s:=0; poprzednia:=0;
while s<l do begin
poprzednia:=s;
s:=s + C(n,k);
dec(n);
end;
liczba:=zilu-n;
//write(liczba,#32);
l:=l-poprzednia;
n:=zilu-liczba;
dec(k)
end;
end;
procedure BogdansX(l,b,n,k:integer); // pozbyłem się wołania funkcji C(n,k)
var zilu, liczba, poprzednia, s:integer;
begin
dec(n); dec(k);
zilu:=n;
while k>=0 do begin
s:=0; poprzednia:=0;
while s<l do begin
poprzednia:=s;
s:=s + b;
if n>0 then b:=b*(n-k) div n
else b:=1;
dec(n);
end;
liczba:=zilu-n;
//write(liczba,#32);
l:=l-poprzednia;
n:=zilu-liczba;
if n-k+1>0 then b:=b*k div (n-k+1)
else b:=1;
dec(k)
end;
end;
procedure xitami(z,b,n,k: integer);
var c:integer;
begin
dec(n); dec(k);
c:=1;
while k>=0 do
if z<b then begin
//write(c,#32);
inc(c);
if n>0 then
b:=b*k div n;
dec(n); dec(k);
end else begin
inc(c);
z:=z-b;
b:=b*(n-k) div n;
dec(n)
end
end;
procedure f(c,z,b,n,k:integer); // wersja rekurencyjna
begin
if z<b then begin
//write(c,#32);
if n>0 then
f(c+1, z, b*k div n, n-1, k-1)
end else
if n>0 then
f(c+1, z-b, b*(n-k) div n, n-1, k )
end;
var n,k,z,b,nk:integer; czas:double;
begin
n:=49; k:=6;
b:=C(n-1, k-1);
nk:=C(n,k);
writeln(n,' ',k,' ',nk);
writeln('--------------- sekund');
czas:=time;
for z:=0 to nk-1 do
f(1,z,b, n-1, k-1);
writeln(' rekurencja ',(time-czas)*24*60*60:8:2);
czas:=time;
for z:=1 to nk do
bogdansx(z, b, n, k);
writeln(' BogdansX ',(time-czas)*24*60*60:8:2);
czas:=time;
for z:=1 to nk do
bogdans(z, n, k);
writeln(' Bogdans ',(time-czas)*24*60*60:8:2);
czas:=time;
for z:=0 to nk-1 do
xitami(z, b, n, k);
writeln(' Xitami ',(time-czas)*24*60*60:8:2);
writeln;
end.
Wyniki to:
Running "c:\download\lotto1.exe "
49 6 13983816
--------------- sekund
rekurencja 43.96
BogdansX 38.81
Bogdans 88.57
Xitami 31.04</b></b>