[algorytmy] Analiza zestawów liczb

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» Grza 02:20 » Holyboy 01:28 » cVas 01:24 » elliot_pl 01:17 » emigrus 01:06 » bagi_glog 01:06 » Pinokio.p 01:04 » Pawelec 00:54 » Chrisu 00:46 » pol150257 00:44 » dida 00:39 » Zbyszek.J 00:33 » rooter666 00:28 » toledo 00:19 » Dexter 00:02 » dawidy 23:49 » akslow 23:40 » Mariosti 23:33 » Raist 23:30 » Lukas12p 23:25 Dzisiaj przeczytano 41115 postów, wczoraj 25974 Szybkie ładowanie jest: włączone.

ccc

A R C H I W A L N A W I A D O M O Ś Ć

[algorytmy] Analiza zestawów liczb - how to? , kubazzz 8/05/10 16:15
Nie potrafię wymyślić jaki jest patent na tworzenie algorytmów do wynajdywania (nie)występujących kombinacji w danym zbiorze liczb.
Najprostsze zastosowanie tego jest w różnych rodzajach gier liczbowych.

Opisowo:
mamy grę liczbową w której jest 80 liczb, 20 losowanych codziennie.
Interesujące są kombinacje 3 liczb.
3 z 80 to 82 160 kombinacji
W każdym losowaniu jest 1 140 kombinacji 3 z 20.

Nie jest wielkim problemem wypisanie tych wszystkich 1140 kombinacji z jednego losowania.
Ale jeśli weźmiemy powiedzmy 30 kolejnych losowań i chcemy znaleźć wszystkie kombinacje które wystąpiły, a jeśli się powtarzają to ile razy, to już zaczyna się gmatwanina, jak to zliczać albo sortować.

A jakby było odwrotnie - znaleźć kombinacje, które w ogóle nie wystąpiły w tych 30 losowaniach, to nie wiem jak to robić.

Jedyne co mi przychodzi do głowy, to zrobić zestaw wszystkich możliwych kombinacji i potem wywalać te które wystąpiły.
Ale jak operować na danych tutaj? Tablice?

SM-S908

ja też myślę, ale nie mam czasu , Chrisu 8/05/10 16:23
nad najczęściej trafianymi kombinacjami 3 i 4 liczb z 49. A dalo mi do myślenia jak sprawdzałem swoje liczby i na lotto.pl wyświetliłem sobie "swoje liczby" i wyniki z ostatnich chyba 3000 losowań... No i okazało się, że w jednej "szóstce" czwórki i trójki padają "bardzo" często, a w drugiej tylko trójki i to czasami tylko...
/// GG# 1 110 10 10 11 100 10 \\\
1. tu nie chodzi , kubazzz 8/05/10 18:11
  o oszukiwanie loterii, chociaż czasem rzeczywiście można się zirytować przy pewnych spostrzeżeniach.
  Chodzi bardziej o to jak faktycznie zrobić taki algorytm.
  SM-S908
ewentualnie... , kubazzz 8/05/10 18:12
może ktoś poleci jakieś lepsze miejsce do tego typu rozkmin?
SM-S908
to zależy od założenia, czy masz więcej pamięci czy mocy obliczeniowej , bwana 8/05/10 19:32
jeśli pamięci, to robisz tablicę rekordów z unikalnym indeksem w funkcji wzajemnie jednoznacznej do losowanej trójki liczb albo hash. Składujesz w pamięci licznik dla każdej możliwej kombinacji i zwiększasz go o 1 po każdym losowaniu. Wtedy łatwo sprawdzić co się powtórzyło ile razy, w szczególności co wypadło 0 razy.

Jeśli masz więcej mocy obliczeniowej, to składujesz tylko wylosowane kombinacje w liście. Po 20 losowaniach zliczasz wystąpienia poszczególnych kombinacji. Można to uzyskać np. sortując listę według rosnącej wartości wyprowadzonej z trójki liczb i zliczać powtórzenia badając przedziały monotoniczności wartości w tablicy.

Dopełnienie zbioru kombinacji (czyli to, co w losowaniach nie padło) obliczysz generując kolejne kombinacje i sprawdzając czy wygenerowana trójka liczb wystąpiła w tablicy (tej już posortowanej).

Ogólnie oba rozwiązania są młotkowe i pewnie są znane jakieś bardziej optymalne sposoby opracowania takiego zagadnienia. Ale na dobry początek może być.

Jeśli robisz to na jakieś laborki, to większą wartość może mieć np. to co napisałem (że zależy od tego czy jest ograniczona pamięć czy wydajność i inne dywagacje) niż seksowność kodu.
"you don't need your smile when I cut
your throat"
1. hmm , recydywista 9/05/10 13:11
  przy takich liczbach jak podał kuba to się w ogóle nie ma co zastanawiać, problem by był jakby trzeba zapamiętać np. 10 miliardów kombinacji
  Computers are useless. They can only
  give you
  answers.
  1. zapewne tak , bwana 10/05/10 13:44
    ale fajnie jest przed napisaniem programu zrobić studium przypadku, omówić, dlaczego tak a nie inaczej projektujesz dany program, jakie założenia brzegowe uwzględniasz itepe. Od wczesnych studiów (informatyka) miałem zwyczaj robić laborki (i własne wprawki) w taki sposób. To dobry nawyk.
    "you don't need your smile when I cut
    your throat"
hmm , recydywista 9/05/10 13:09
tablice tylko że z haszowaniem. Patrz Thomas Cormen "Wprowadzenie do algorytmów", rozdział 12. :)
Computers are useless. They can only
give you
answers.
1. obczaję , kubazzz 10/05/10 17:02
  mam nadzieję, że zrozumiem:)
  SM-S908