logowanie

matematyka » forum » forum zadaniowe - zadania różne » zadanie

Inne, zadanie nr 14

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

mlodyx
postów: 3
2011-04-14 21:46:01

Lotto

Wiemy z symbolu newtona ze gdy n=49 a k=6
dla ${n \choose k}$ = 13983816 roznych elementow bez powtorzen..

np:
1,2,3,4,5,6
1,2,3,4,5,7
itd

Napisz funkcje która zwroci numer elementu np:
F(1,2,3,4,5,7) == 2

I na odwrot ktora zwroci elementy np:
F(2) == 1,2,3,4,5,7

Jak to ugryzc ?


Mariusz Śliwiński
postów: 489
2011-04-14 22:39:20

O ile dobrze rozumiem to chcesz napisać funkcję, która pewnej kombinacji przypisze jej liczbę porządkową w zbiorze posortowanych rosnąco tychże kombinacji.

To jest problem programistyczny.
Należy napisać funkcję, która przypisze wszystkie kombinacje do tablicy i problem rozwiązany. Można wywoływać funkcję w jedną jak i w drugą stronę.


mlodyx
postów: 3
2011-04-15 12:01:48

Umiem napisac taka funkcje ktora to zwroci, w te i w druga strone.. Ale to jest nieoplacalne poniewaz robie to za pomoca petli inkrementujac licznik. Szukam i wiem ze musi byc jakas funkcja matematyczna ktora zwroci x element ze zbioru.

To zadanie z kombinatoryki.. szukalem w necie wiele razy ale nie znalezlem

Czy ktos ma jakis pomysl?


Mariusz Śliwiński
postów: 489
2011-04-15 13:22:36

Musisz odwołać się do zbioru z elementami, którymi są posortowane kombinacje. Nie uzyskasz wyniku funkcji bez tego zbioru.

Zbiór ten możesz generować automatycznie za pomocą pętli, ale rozumiem kłopot czasu generowania tablicy.
Na szybko napisałem funkcję dla kombinacji 49 z 3 i chodzi to błyskawicznie, ale to jest wielokrotnie mniejszy zbiór. Sprawdzę
późnym wieczorem dla 49 z 6 jaki czas potrzebny jest na generowanie tego zbioru.

Właściwe jest raczej wygenerowanie tego zbioru i zapisanie go do bazy, a następnie odwoływanie się do tej bazy.




mlodyx
postów: 3
2011-04-15 13:50:56

Nie sprawdzaj bo to jest czasochlonne, juz sprawdzalem nawet jesli podzielisz zbior na kilkaset czesci i zaczniesz petle ustawiajac od ktorej ma zaczac nic mi to nie da bo 6 z 49 jest przykladem, ja musze operowa na ogromnych zbiorach

Aczkolwiek znalazlem cos takiego w necie na pewnym forum:


Cytuje:
Jesli ktos widzial juz te wiadomosc to przepraszam. Niestety, onet niusy nie pokazuja niektorych postow wyslanych przeze mnie. Biorac pod uwage fakt, ze Pytajacy korzystal z Onetu, ponawiam odpowiedz.

Problem - Wzór

Jest (sobie) posortowana lista kombinacji N z M liczb. Wewnątrz kombinacji liczby też są posortowane.

Należy znaleźć wzór ogólny na numer kombinacji na liście mając:
N, M, Mmin, Mmax, Ni -liczby w kombinacji-(gdzie [i] należy do zbioru <1,N)

Udało mi się kilka lat temu znależć wzór dla N=4.

Może ktoś potrafi dla dowolnych N i M.

Zdaje się, że to będzie

n = sum_{i=1}^{N}(
sum_{k=N_(i-1) +1}^{N_i - 1}( NEWTON((M - k) nad (N - i)) )
) + 1

przy dodatkowo zdefiniowanym N_0 = 0, a NEWTON(n nad k) to symbol Newtona.

Sprawdzilem Derivem tylko dla tego przykładu:
1 | 2 | 3 | 14 | 15 | 49 | 8074
i zgadza się. Pozostałe sprawdź sam.

koniec cytatu

i wlasnie o takie cos mi chodzilo ale szczerze powiem nie rozumiem tego wzoru...


Mariusz Śliwiński
postów: 489
2011-04-16 10:09:04


$\sum_{i=1}^{N} \left( \sum_{k=N_{i-1} +1}^{N_i - 1} {{M - k}\choose {N - i}} \right) + 1$

Dla tak zdefiniowanej funkcji wartość dla podanego przykładu wynosi: http://www.math.edu.pl/kalkulator.php?id=0 $ 0 $ 0 $ 9*C(45,2) $ 0 $ 34*C(35,0) $ 1

Dla pozostałych przykładów także wartości są odpowiednio większe.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj