[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
	» KHot 12:16 » zbiggy 12:08 » RoBakk 12:07 » Rafael_3D 12:04 » Fl@sh 11:59 » Armitage 11:57 » Promilus 11:56 » metacom 11:50 » myszon 11:48 » rurecznik 11:46 » Kool@ 11:45 » Star Ride 11:44 » JE Jacaw 11:40 » rzymo 11:40 » Dexter 11:37 » Liu CAs 11:36 » Ramol 11:33 » Lucyferiu 11:28 » Hitman 11:25 » DJopek 11:25 Dzisiaj przeczytano 41109 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