Сколько времени понадобится циклу для генерации нужного числа?

Question

Делаю задачу, вот условие:

Напишите цикл,который проверяет,насколько сложно выиграть в смоделированной вами лотерее. Создайте список или кортеж с именем my_ticket. Напишите цикл,который продолжает генерировать комбинации до тех пор,пока не выпадет выигрышная комбинация. Выведите сообщение с информацией о том,сколько выполнений цикла понадобилось для получения выигрышной комбинации.

Я написал код, он запускает цикл, но я не пойму, сколько времени он будет подбирать нужную комбинацию? И подберёт ли её вообще? Код ниже:

from random import choice
tickets = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'a', 'b', 'g', 'd', 'h']

my_ticket = '8g29' # нужная комбинация
kolvo = 0 # количество попыток

while my_ticket:
    one = choice(tickets) # рандом подбор элементов
    two = choice(tickets)
    three = choice(tickets)
    four = choice(tickets)
    win = one + two + three + four # соединение этих элементов в одну строку
    print(f"Сгенерированый номер: {win}")
    if win != my_ticket:
        kolvo += 1
        print("Это не выигрышный номер.")
        
    if win == my_ticket:
        print("Это выигрышный номер!")
        print(f"Кол-во попыток: {kolvo}")
        break

Answer 1

import random

tickets = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'a', 'b', 'g', 'd', 'h']

my_ticket = '8g29'
kolvo = 0 
generated_combinations = set()

while True:
    one = random.choice(tickets)
    two = random.choice(tickets)
    three = random.choice(tickets)
    four = random.choice(tickets)
    win = one + two + three + four 
    

    if win in generated_combinations:
        continue 
    
    generated_combinations.add(win)
    kolvo += 1
    print(f"Сгенерированная комбинация: {win}")
    
    if win == my_ticket:
        print("Это выигрышная комбинация!")
        print(f"Количество попыток: {kolvo}")
        break
    else:
        print("Это не выигрышная комбинация.")

такой код считает количество попыток, и делает подбор не случайным

Answer 2

В среднем программа угадает комбинацию за 50625 попыток. Почему так, читайте дальше.

Если вы действительно хотите смоделировать случайный подбор комбинации и хотите сделать это как можно быстрее, можно так:

import random

items = '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'a', 'b', 'g', 'd', 'h'
n = len(items)
target = tuple(map(items.index, ('8', 'g', '2', '9')))

tries = 0
while True:
    tries += 1
    for i in target:
        if random.randrange(n) != i:
            break
    else:
        print(f'Количество попыток {tries}')
        break

$ python run.py
Количество попыток 80238

$ python run.py
Количество попыток 5078

$ python run.py
Количество попыток 8546

$ python run.py
Количество попыток 26911

$ python run.py
Количество попыток 36731

В коде выше символы в строках заменены на их индексы. Очередная попытка состоит в последовательном подборе индексов, который прерывается как только нашлось не совпадение. С точки зрения статистики этот тот же процесс, что и подбор кусочков строк из списка. Но не тратится время на составление строк, и попытка прерывается как можно раньше.

Число попыток до угадывания - случайная величина. Можно вычислить приближение к среднему и стандартному отклонению для неё.

import random

items = '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'a', 'b', 'g', 'd', 'h'
n_items = len(items)
target = tuple(map(items.index, ('8', 'g', '2', '9')))


def run():
    tries = 0
    while True:
        tries += 1
        for i in target:
            if random.randrange(n_items) != i:
                break
        else:
            return tries


def main():
    n = 0
    s = 0
    s2 = 0
    while True:
        t = run()
        n += 1
        s += t
        s2 += t * t
        e = s / n
        d = s2 / n - e * e
        if n % 100 == 0:
            print(n, f'{e:.1f} {d ** 0.5:.1f}')

main()

Первое число в строке - число поставленных экспериментов, второе - среднее количество попыток, третье - стандартное отклонение:

$ python stats.py
100 56089.4 57876.8
200 53791.5 52270.7
300 53862.6 50109.1
...
100000 50735.6 50624.6
100100 50738.3 50630.1
100200 50740.5 50633.0
...

Если ждать достаточно долго, среднее сойдётся к пределу 50625, стандартное отклонение к 50624.5. Потому что количество попыток подчиняется распределению Паскаля. В нашем случае в алфавите пятнадцать букв. Вероятность угадать одну букву - ¹/₁₅, вероятность угадать четыре буквы - (¹/₁₅)⁴ = ¹/₅₀₆₂₅. Последнюю величину обозначим p. Тогда среднее число неудачных попыток будет E = ^(1-p)/_p, дисперсия D = ^(1-p)/_p². Подставляем p, получаем E = 50624, D = 50624·50625. Стандартное отклонение √D ≅ 50624.5.

Заметьте что в распределение Паскаля описывает число неудач до первой удачи, а наша программа считает число на единицу большее - добавляется последняя успешная попытка. Поэтому среднее в нашем эксперименте на единицу больше. Дисперсия и стандартное отклонение те же и там и там.

БЛОГ НА HUSL

Сколько времени понадобится циклу для генерации нужного числа?

Ответы (2 шт):