Untitled
unknown
plain_text
4 months ago
3.4 kB
4
Indexable
from random import randint def randomize(): r = [] while len(r) != 6: rd = randint(0, 2137)%49 +1 if rd not in r: r.append(rd) return r randomized = randomize() args = [3,6,34, 13, 43, 22] print(f'r:\t{randomized}') print(f'args:\t{args}') def check(args: list=args): matched = 0 args.sort() randomized.sort() print(f's r:\t{randomized}') print(f's args:\t{args}') n = len(args) i,j = 0,0 while i < n and j < n: if args[i] == randomized[j]: matched+=1 i+=1 j+=1 elif args[i] < randomized[j]: i+=1 else: j+=1 print(f'i {i}, j {j}, m {matched}') return matched print(check()) """ przykładowe wywołanie kodu r: [29, 10, 43, 1, 4, 23] args: [3, 6, 34, 13, 43, 22] s r: [1, 4, 10, 23, 29, 43] s args: [3, 6, 13, 22, 34, 43] i 0, j 1, m 0 i 1, j 1, m 0 i 1, j 2, m 0 i 2, j 2, m 0 i 2, j 3, m 0 i 3, j 3, m 0 i 4, j 3, m 0 i 4, j 4, m 0 i 4, j 5, m 0 i 5, j 5, m 0 i 6, j 6, m 1 1 """ """ mój pseudokod z komentarzem randomized - zakładamy, że to zdefiniowana lista wylosowana przez komputer args - liczby podane przez użyszkodnika fun check(args) matched = 0 sort(args) sort(randomized) # sotrujemy aby móc kroczyć po elementach dwóch list jednocześnie - tutaj sensowne będzie zastosowanie algorytmu quicksort (złożoność O(n*log(n)) ) ponieważ możliwy zakres danych w liście [1,49] jest większy niż ilość danych (6) i,j = 0,0 n=|args| while i < n and j < n # w najgorszym wypadku będziemy mieli złożoność O(2n) ponieważ musimy porównać elementy z dwóch list które potencjalnie mogą być równe if args[i] == randomized[j] # dodajemy do zliczania, wykonujemy krok na obydwóch listach matched += 1 i += 1 j += 1 else if args[i] < randomized[j] # wykonujemy krok tylko na liście argumentów, gdy argument był mniejszy od danych na konkretnym indeksie i += 1 else # wykonujemy krok tylko na liście danych z komputera j += 1 # dlaczego nie iterujemy po jednej liście i po drugiej? # while i < n # while j < n # if args[i] == randomized[j] # matched += 1 # niby kod jest zdecydowanie prostszy ale pesymistyczna złożoność obliczeniowa (ilość porównań) w tym wypadku wynosi O(n^2), w tym przypadku różnica jest niewielka (12 : 36) ale weźmy n = 1000 -> wtedy mamy 2000 : 1 000 000 co robi sporą różnicę """ """ Chat mówi o takim pseudokodzie FUNCTION randomize(): Initialize r as an empty list WHILE length of r != 6: Generate random number rd between 1 and 49 IF rd NOT IN r: Append rd to r RETURN r randomized = CALL randomize() args = [3, 6, 34, 13, 43, 22] FUNCTION check(args): Initialize matched to 0 SORT args SORT randomized n = length of args Initialize i = 0, j = 0 WHILE i < n AND j < n: IF args[i] == randomized[j]: matched += 1 i += 1 j += 1 ELSE IF args[i] < randomized[j]: i += 1 ELSE: j += 1 RETURN matched result = CALL check(args) """
Editor is loading...
Leave a Comment