Bartex321 Temat założony przez niniejszego użytkownika |
szybkie algorytmy łamania szyfrów » 2019-11-12 18:22:16 Witam, bardzo proszę administrację o przeczytanie przed usunięciem :) Rozwiązuję zadania informatyczne w internecie i natknąłem się na zadanie, które sprowadza się do znalezienia ilości poprawnych kluczy do zamka szyfrowego. Do programu mam podaną ilość "pokręteł", liczb na jednym pokrętle, oraz numery pokręteł, które muszą mieć inną wartość, aby zamek się otworzył np.: 3 - ile pokręteł 3 - ile liczb na jednym pokrętle
1 2 2 3 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył 1 3
oznacza to następujący zamek: 1 1 1 2 2 2 3 3 3 Poprawne szyfry to: 123, 132, 213, 231, 312, 321, a odpowiedź to 6 Rozwiązuje to na razie metodą brut force, sprawdzając czy każdy szyfr pasuje, jednak jest to zbyt wolne, ma ktoś pomysł na szybszy algorytm / algorytm szukający liczby pasujących kodów zamiast wszystkich rozwiązań? |
|
darko202 |
» 2019-11-13 08:28:51 |
|
Bartex321 Temat założony przez niniejszego użytkownika |
» 2019-11-13 15:17:36 Wzór na ilość wszystkich kombinacji jest dość prosty i nie potrzeba mi wikipedii, problem jest w tym, że muszę odjąć kody, które się powtarzają Np przy wejściu 4 4 1 2 - 1 i 2 liczba muszą być inne 1 3 - 1 i 3 liczba muszą być inne 2 3 - 2 i 3 liczba muszą być inne Będzie 256 wszystkich kombinacji odjąć: 1. 64 zaczynających się na 11/22/33/44 2. 16 postaci1x1/2x2/3x3/4x4 3. 16 postaci x11/x22/x33/x44 Kod 1111 jest odejmowany w każdym punkcie, a powinien być liczony tylko raz |
|
darko202 |
» 2019-11-14 07:43:07 mylnie używasz nazwy "kombinacja", gdyż w matematyce kombinacja to podzbiór liczb - czyli coś nieuporządkowanego Ty chcesz mieć ciągi uporządkowane, a w tym wypadku mowa jest o "wariancjach" i mamy dwa przypadki bez powtórzeń i z powtórzeniami
na oba są wzory i jestem przekonany, że uwzględniają opisywane przez Ciebie przypadki.
Twoim problemem jest chyba to, że musisz wykorzystać równocześnie oba. ale to proste, gdyż w tym przypadku dzielisz pokrętła na dwie grupy (z powtórzeniami, bez powtórzeń) i dla każdej z tych grup korzystasz z odpowiedniego wzoru
wynikiem jest iloczyn wyników
Pozdrawiam
|
|
Bartex321 Temat założony przez niniejszego użytkownika |
» 2019-11-14 15:30:09 Przeanalizowałem obie wariacje i nie widzę ich zastosowania, ja losuje po jednej cyfrze z n podzbiorów, w kazdym jest m liczb. Wzory obu wariacji dla losowania 1 z m liczb skracają się do m = m, co jest dobrym, ale bezużytecznym wynikiem.
Zauważcie, że gdy mamy przykładowy zamek, używając oznaczeń z początku wiadomości n = 3; m = 3; 1 i 2 muszą mieć inne wartości Wzór na wszystkie kombinacje to: 3 * 3 * 3, drugie pokretlo musi miec inna wartosc niz 1 wiec wybieramy tam w zasadzie jedna z 2, a nie 3 liczb - wzor wyglada nastepujaco: 3 * (3 - 1) * 3 Niestety przy zamku: n = 3; m = 3; 1 i 3, 2 i 3 maja inne wartosci (3 - 1) * (3 - 1) * 3 jest poprawny (1 pokretlo ma inna wartosc niz 3; 2 pokretlo ma inna wartosc niz 3) 3 * 3 * (3 - 1 - 1) jest zly (3 pokretlo musi miec inna wartosc niz 1 i 2 wiec wybieramy z 1, a nie 3 liczb, niestety nie uwzglednia kombinacji 11x, 22x, 33x) Moje pytanie jak to zaprogramować, aby komputer odejmował od poprawnych pokręteł? |
|
darko202 |
» 2019-11-15 08:58:42 Przeczytałem Twoje słowa i przykro mi, bo podałem Ci prawidłową ścieżkę do znalezienia rozwiązania.
Badane ilości układów pokręteł podpada pod definicję "wariancji" (matematyka - kombinatoryka).
musisz to tylko zobaczyć i zastosować.
Pozdrawiam |
|
Bartex321 Temat założony przez niniejszego użytkownika |
» 2019-11-16 17:12:45 Myślę nad tym od dwóch dni i nic...
Odchodząc już od tego zamka mam 3-cyfrową liczbę z cyfr 1, 2, 3, pierwsza cyfra musi być inna od pozostałych. Wynik to 12 między 1 i 2, oraz 1 i 3 cyfrą są wariacje bez powtórzeń - 6 wariacji między 2 i 3 cyfrą jest wariacja z powtórzeniami - 9 wariacji wariacja bez powtórzeń całej liczby - 6 wariacji wariacja z powtórzeniami całej liczby - 27 wariacji
Jedyne co mi przychodzi do głowy to 6 + 6, czyli zależności między 1 i 2, oraz 1 i 3 cyfrą, ale to jest przypadkowa zbieżność...
|
|
darko202 |
» 2019-11-18 13:22:54 podchodzisz do tego w zły sposób gdyż aby to rozwiązać musisz tylko zrozumieć czym jest * "wariancja bez powtórzeń" - ciąg liczb bez możliwych powtórzeń (a1,...,aN) * "wariancja z powtórzeniami" - ciąg liczb z możliwymi powtórzeniami (b1,...,bN)
z treści zadania wynika, że możemy mieć do czynienia z sytuacją mieszaną tzn. szukamy ciągu, w którym na pewnych miejscach nie mogą wystąpić powtórzenia ale na pozostałych mogą czyli np. ciągu (a1,b1,b2,a2,b3,a3,b4), gdzie : A = (a1,a2, a3) "wariancja bez powtórzeń" B = (b1,b2,b3,b4) "wariancja z powtórzeniami" o ilości możliwych ciągów decydują wzory na odpowiednią wariancję ostatecznym wynikiem jest iloczyn ilość(A)*ilość(B)
to które wyrazu ciągu należą do A, a które B musisz rozstrzygnąć na podstawie warunków początkowych
np. z twojego przykładu "2 3 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył"
co można zaprezentować na przykładzie mamy 5 - ile pokręteł 7 - ile liczb na jednym pokrętle
1 3 3 4 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył 1 4
szukamy ciągu 5 cyfrowego (a1,b1,a2,a3,b2) (a1,a2,a3) = 7*6*5 "wariancja bez powtórzeń" (b1,b2) = 7*7 "wariancja z powtórzeniami"
może być jeszcze bardziej skomplikowany przypadek, gdzie nie ma wszystkich warunków poczatkowych na "wariancja bez powtórzeń"
np. mielibyśmy tylko 2 warunki 1 3 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył 1 4
co powodowałoby że szukalibyśmy rozwiązania dla 5 cyfrowego (a1,b1,c1,c2,b2) gdzie (a1) = 7 "wariancja bez powtórzeń" (b1,b2) = 7*7 "wariancja z powtórzeniami" (c1,c2) = 6*6 "wariancja z powtórzeniami" (ale warunki początkowe ograniczają ilość liczb do wyboru)
no i przykład można dalej komplikować gdzie mielibyśmy np. po kilka "wariancja bez powtórzeń" i kilka "wariancji z powtórzeniami"
ale jak zaprezentowałem Ci rozwiązanie opiera się o znaną z matematyki teorię o "wariancjach"
Powodzenia
|
|
« 1 » 2 |