Уведомления

Группа в Telegram: @pythonsu

#1 Май 26, 2019 14:01:32

Vladimirv
Зарегистрирован: 2013-03-22
Сообщения: 108
Репутация: +  7  -
Профиль   Отправить e-mail  

Легкая задача

PEHDOM
Соотвевенно если у нас n-многоугольник, то чтобы фишка обошла все вершины нужно чтобы “орел” выпал на n-1 раз больше или меньше чем “решка”(не обязательно подряд, просто больше или меньше). Тогда и только тогда фишка обойдет все вершины.

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

PEHDOM
А она, допустим в трехугольнике, может сделать один ход влево и два вправо, или два хода влево, или два вправо и все вершины будуд обойдены. а разница между количеством орлов и решек равна 1 или 2, тоесть такой подход не подходит

А вот тут самое то!
Переделал код, чтобы выводились строки там, где число ходов влево и вправо равно.
Если посмотрите, что выводит код ниже, то видно, что когда число выпадений равно (diff = x0-x1 == 0), отклонение фишки (колонка shift) составляет приличное значение. И это всего при 100 шагов!!! 

 #
from random import randint
  
def choices(attempt, steps=100):
    lst = []
    max_left = 0
    max_right = 0
    center = 0
    for _ in range(steps):
        x = randint(0, 1)
        lst.append(x)
        if x == 1:
            center += 1
        else:
            center -= 1
        if center > max_right:
            max_right = center
        if center < max_left:
            max_left = center
    x1 = sum(lst)
    x0 = len(lst)-x1
    diff = x0-x1
    # max_shift - показывает max отклонение фишки от своего угла.
    max_shift = abs(max_left) if abs(max_left) > max_right else max_right
    return attempt, x0, x1, diff, max_left, max_right, max_shift
  
attempts = 100
fmt = '{:<5} | {:>5} | {:>5} | {:>5} | {:>5} | {:>5} | {:>5}'
print(fmt.format(*'# x0 x1 x0-x1 left right shift'.split()))
i, n = 0, 0
while n < attempts:
    i += 1
    t = choices(i)
    diff = t[3]
    if diff == 0:
        n += 1
        print(fmt.format(*t))

Отредактировано Vladimirv (Май 26, 2019 14:11:38)

Офлайн

#2 Май 26, 2019 14:28:10

Vladimirv
Зарегистрирован: 2013-03-22
Сообщения: 108
Репутация: +  7  -
Профиль   Отправить e-mail  

Легкая задача

Вдруг, кому-то лень будет запускать.
Вывод скрипта:

 #
#     |    x0 |    x1 | x0-x1 |  left | right | shift
16    |    50 |    50 |     0 |    -5 |     5 |     5
18    |    50 |    50 |     0 |   -13 |     3 |    13
24    |    50 |    50 |     0 |    -7 |     5 |     7
46    |    50 |    50 |     0 |    -6 |     7 |     7
49    |    50 |    50 |     0 |    -8 |     2 |     8
102   |    50 |    50 |     0 |    -7 |     4 |     7
105   |    50 |    50 |     0 |    -6 |     5 |     6
106   |    50 |    50 |     0 |    -6 |     3 |     6
138   |    50 |    50 |     0 |   -13 |     0 |    13
143   |    50 |    50 |     0 |    -2 |     7 |     7
186   |    50 |    50 |     0 |    -9 |     5 |     9
204   |    50 |    50 |     0 |    -1 |     8 |     8
237   |    50 |    50 |     0 |    -2 |     7 |     7
238   |    50 |    50 |     0 |    -8 |     4 |     8
242   |    50 |    50 |     0 |    -7 |     4 |     7
250   |    50 |    50 |     0 |    -4 |     5 |     5
255   |    50 |    50 |     0 |    -4 |     9 |     9
269   |    50 |    50 |     0 |    -7 |     7 |     7
280   |    50 |    50 |     0 |    -5 |     7 |     7
293   |    50 |    50 |     0 |   -13 |     1 |    13
300   |    50 |    50 |     0 |    -2 |     5 |     5
309   |    50 |    50 |     0 |   -10 |     0 |    10
316   |    50 |    50 |     0 |   -10 |     1 |    10
327   |    50 |    50 |     0 |    -9 |     6 |     9
337   |    50 |    50 |     0 |   -12 |     4 |    12
346   |    50 |    50 |     0 |     0 |    12 |    12
356   |    50 |    50 |     0 |    -2 |    11 |    11
382   |    50 |    50 |     0 |    -7 |     1 |     7
383   |    50 |    50 |     0 |     0 |    13 |    13
396   |    50 |    50 |     0 |    -6 |     6 |     6
401   |    50 |    50 |     0 |    -5 |     9 |     9
408   |    50 |    50 |     0 |    -3 |     5 |     5
420   |    50 |    50 |     0 |   -11 |     5 |    11
422   |    50 |    50 |     0 |    -6 |     7 |     7
430   |    50 |    50 |     0 |   -10 |     3 |    10
440   |    50 |    50 |     0 |   -15 |     2 |    15
459   |    50 |    50 |     0 |    -5 |     4 |     5
467   |    50 |    50 |     0 |    -4 |    10 |    10
542   |    50 |    50 |     0 |    -6 |     3 |     6
558   |    50 |    50 |     0 |   -11 |     5 |    11
571   |    50 |    50 |     0 |    -6 |     3 |     6
584   |    50 |    50 |     0 |    -7 |     6 |     7
592   |    50 |    50 |     0 |    -1 |     9 |     9
604   |    50 |    50 |     0 |    -7 |     4 |     7
614   |    50 |    50 |     0 |     0 |    13 |    13
615   |    50 |    50 |     0 |    -6 |     4 |     6
637   |    50 |    50 |     0 |    -2 |     9 |     9
672   |    50 |    50 |     0 |    -4 |     8 |     8
674   |    50 |    50 |     0 |    -9 |     4 |     9
678   |    50 |    50 |     0 |    -7 |     4 |     7
688   |    50 |    50 |     0 |    -3 |     7 |     7
713   |    50 |    50 |     0 |    -5 |     5 |     5
714   |    50 |    50 |     0 |    -4 |     3 |     4
718   |    50 |    50 |     0 |     0 |     7 |     7
723   |    50 |    50 |     0 |    -5 |     7 |     7
739   |    50 |    50 |     0 |    -2 |    11 |    11
753   |    50 |    50 |     0 |    -8 |     2 |     8
765   |    50 |    50 |     0 |    -7 |     5 |     7
768   |    50 |    50 |     0 |    -7 |     3 |     7
788   |    50 |    50 |     0 |    -1 |    10 |    10
790   |    50 |    50 |     0 |    -7 |     3 |     7
807   |    50 |    50 |     0 |    -9 |     5 |     9
868   |    50 |    50 |     0 |    -6 |     1 |     6
876   |    50 |    50 |     0 |    -4 |     7 |     7
879   |    50 |    50 |     0 |    -4 |     4 |     4
892   |    50 |    50 |     0 |    -3 |     9 |     9
908   |    50 |    50 |     0 |    -4 |     8 |     8
914   |    50 |    50 |     0 |     0 |    10 |    10
926   |    50 |    50 |     0 |    -3 |     6 |     6
927   |    50 |    50 |     0 |    -3 |     6 |     6
928   |    50 |    50 |     0 |    -3 |    11 |    11
933   |    50 |    50 |     0 |    -7 |     3 |     7
944   |    50 |    50 |     0 |    -5 |     5 |     5
950   |    50 |    50 |     0 |    -9 |     2 |     9
954   |    50 |    50 |     0 |    -3 |     5 |     5
970   |    50 |    50 |     0 |    -8 |     5 |     8
978   |    50 |    50 |     0 |    -6 |     5 |     6
987   |    50 |    50 |     0 |    -9 |     6 |     9
988   |    50 |    50 |     0 |    -4 |     4 |     4
997   |    50 |    50 |     0 |    -7 |     5 |     7
999   |    50 |    50 |     0 |    -5 |     7 |     7
1027  |    50 |    50 |     0 |   -11 |     5 |    11
1030  |    50 |    50 |     0 |    -5 |     5 |     5
1039  |    50 |    50 |     0 |    -5 |     4 |     5
1042  |    50 |    50 |     0 |    -9 |     2 |     9
1043  |    50 |    50 |     0 |    -2 |     8 |     8
1050  |    50 |    50 |     0 |    -4 |     9 |     9
1060  |    50 |    50 |     0 |    -2 |    18 |    18
1063  |    50 |    50 |     0 |   -12 |     1 |    12
1075  |    50 |    50 |     0 |    -5 |     3 |     5
1078  |    50 |    50 |     0 |    -4 |     3 |     4
1081  |    50 |    50 |     0 |    -2 |    12 |    12
1085  |    50 |    50 |     0 |   -11 |     4 |    11
1089  |    50 |    50 |     0 |   -13 |     1 |    13
1097  |    50 |    50 |     0 |    -6 |     7 |     7
1118  |    50 |    50 |     0 |    -4 |     6 |     6
1120  |    50 |    50 |     0 |     0 |    14 |    14
1133  |    50 |    50 |     0 |    -4 |     7 |     7
1140  |    50 |    50 |     0 |    -6 |     2 |     6
1143  |    50 |    50 |     0 |    -7 |     8 |     8
left, right - соответственно максимальное отклонение фишки влево и право
shift - максимальное абсолютное значение из left, right

Отредактировано Vladimirv (Май 26, 2019 14:33:59)

Офлайн

#3 Май 26, 2019 15:03:39

Vladimirv
Зарегистрирован: 2013-03-22
Сообщения: 108
Репутация: +  7  -
Профиль   Отправить e-mail  

Легкая задача

Чуть не забыл)

py.user.next
В каждой точке вероятность шага влево и вправо одинаковая. Это всё равно что монетку подбрасывать и ждать, когда выпадут орлы больше раз, чем решки.

PEHDOM
Если абстрагироваться от фишки передвигающейсмя по вершинам то py.user.next абсолютно прав
PEHDOM, тут вы погорячились, еще и применив слово „абсолютно“. Ну просто жесть)))

py.user.next не сказал ничего нового, это задано в условии задачи.
maybelll
На каждом шаге фишку перемещают в одну из соседних вершин с одина- ковыми вероятностями.
Главное же, действия повторяются многократно и ожидание того, что шаги вправо и влево будут выпадать равномерно не обосновано, даже при том, что их число в итоге одинаково.

Офлайн

#4 Май 26, 2019 15:40:44

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10031
Репутация: +  857  -
Профиль   Отправить e-mail  

Легкая задача

Vladimirv
Уже писал, для того чтобы, фишка не отклонялась должен быть постоянный баланс ходов, а вероятность этого минимальная.
Да баланс может меняться. Оно может сбалансироваться, разбалансироваться и снова сбалансироваться, и снова разбалансироваться. Где тут математическое описание и обоснование того, как именно оно будет в теории себя вести?

PEHDOM
она не может не обойти, поскольку у нас колличество ходов фишки стремиться к беконечности, то вероятность что рано или поздно таки обойдет стремиться к единице.
Ну притянуто за уши. Звучит как “если я бесконечно буду каждый день ходить в один и тот же хлебный магазин, то рано или поздно я найду там телевизор”. Ну да, возможно. Какая вероятность встретить динозавра на улице? 0.5 - либо встретишь, либо не встретишь.

Там doza_and выше писал
doza_and
Надо проверять сходимость такого ряда.

Может быть, и нужен какой-то ряд для начала, а может и закон есть какой-то (теорема), я там насчитал штуки четыре примитивных теоремы, как-то выведенных.



Офлайн

#5 Май 26, 2019 19:54:41

Vladimirv
Зарегистрирован: 2013-03-22
Сообщения: 108
Репутация: +  7  -
Профиль   Отправить e-mail  

Легкая задача

py.user.next
Да баланс может меняться.
Все пробил!!! py.user.next съехал со своей позиции)))
А ведь рассказывал то:
py.user.next
Она может бесконечно топтаться на месте и никогда не обойти его.
Если баланс меняется, а как только что мы услышали, он таки может быть нарушен. Значит фишка обходит вершины.

В завершении, для тех кому лень было следить за ходом дискуссии, вникать в код, смотреть столбцы чисел и т.д. и т.п.
Графики.
Графики строятся только для тех случаев, когда число шагов влево и право равно.
Выбрал пару самых интересных, остальные в zip-е прилагаются.
Интересные они тем, что в них встречается максимальное число торжественных моментов для теории вероятности.
Торжественные моменты это когда график пересекает ось Х, а соответственно Y = отклонение == 0. Это означает, что в этих точках наблюдается равновероятностное выпадение ходов. Но это не мешает фишки дрейфовать и соответственно обойти вершины.

Отредактировано Vladimirv (Май 26, 2019 20:01:40)

Прикреплённый файлы:
attachment image_png.zip (173,5 KБ)

Офлайн

#6 Май 26, 2019 19:58:03

Vladimirv
Зарегистрирован: 2013-03-22
Сообщения: 108
Репутация: +  7  -
Профиль   Отправить e-mail  

Легкая задача

И код для тех, кто хочет повторить:

 #
from random import randint
import matplotlib.pyplot as plt
  
def choices(attempt, steps=100):
    lst, y = [], [0]
    center = 0
    for _ in range(steps):
        x = randint(0, 1)
        lst.append(x)
        if x == 1:
            center += 1
        else:
            center -= 1
        y.append(center)
    return sum(lst), y
  
attempts = 10
i, n = 0, 0
while n < attempts:
    i += 1
    x1, y = choices(i)
    if x1 == 50:
        n += 1
        filename = 'graf_{:0=2d}.png'.format(n)
        plt.figure()
        plt.xlabel('Шаги')
        plt.ylabel('Отклонение фишки')
        plt.title('График "Отклонение фишки от начального положения"')
        plt.plot(y, linestyle='steps')
        plt.savefig(filename)

Офлайн

#7 Май 26, 2019 22:50:19

PEHDOM
Зарегистрирован: 2016-11-28
Сообщения: 2196
Репутация: +  294  -
Профиль   Отправить e-mail  

Легкая задача

py.user.next
. Звучит как “если я бесконечно буду каждый день ходить в один и тот же хлебный магазин, то рано или поздно я найду там телевизор”.
Ну вобщем да, а уже среднее колличество походов в хлебный зависит от вероятности нахождения телевизора. Теорвер эта такая штука которую нельзя вот так просто взять и перенести ИРЛ. Нужно понимать что ты можешь найти телевизор на следующий день , а твой сосед через мильен лет, но в среднем вы дожны ходить полмиллиона лет в хлебный чтобы найти телевизор. Вот както так оно работает XD



==============================
Помещайте код в теги:
[code python][/code]
Бериегите свое и чужое время.

Отредактировано PEHDOM (Май 26, 2019 22:50:48)

Офлайн

#8 Май 27, 2019 01:25:35

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10031
Репутация: +  857  -
Профиль   Отправить e-mail  

Легкая задача

Vladimirv
Все пробил!!! py.user.next съехал со своей позиции)))
Да нигде не доказано, что она не может бесконечно топтаться.

Графики, конечно, красивые и ты молодец, что потрудился там и так далее, но это не доказательство. Во-первых, в питоне (да и вообще в языках) random - это не random, это псевдо-random. Так что полагаться на него нельзя, надо математически доказывать. Во-вторых, баланс может меняться в любой момент времени как в положительную сторону, так и в отрицательную сторону. А где ты доказал, что он будет сохраняться пока фишка не достигнет начальной позиции, обойдя многоугольник вокруг? Я не вижу доказательства, графики, числа - это всё картинки. Можно и неправильную картинку построить и она так же красиво будет выглядеть.

PEHDOM
Ну вобщем да, а уже среднее колличество походов в хлебный зависит от вероятности нахождения телевизора.
Вероятность появления телевизора (как товара) равна нулю. А ты говоришь “а он будет бесконечно туда ходить и телевизор там появится”. Вот это иллюстрация твоего обоснования про обход всего многоугольника. Ты просто говоришь “а я вот хочу, чтобы фишка его обошла, хочу, чтобы в бесконечности она его обошла”.



Отредактировано py.user.next (Май 27, 2019 01:26:30)

Офлайн

#9 Май 27, 2019 11:27:27

PEHDOM
Зарегистрирован: 2016-11-28
Сообщения: 2196
Репутация: +  294  -
Профиль   Отправить e-mail  

Легкая задача

py.user.next
Вероятность появления телевизора (как товара) равна нулю. А ты говоришь “а он будет бесконечно туда ходить и телевизор там появится”. Вот это иллюстрация твоего обоснования про обход всего многоугольника. Ты просто говоришь “а я вот хочу, чтобы фишка его обошла, хочу, чтобы в бесконечности она его обошла”.
на самом деле нет, вероятность появления телевизора в хлебном не равна нулю, но мы уходим в офтоп. Это классическая ошибка человека который только начинает знакомится с теорвером. По типу если вероятность выпадения орла и решки равна 50/50 то подбрасывая монетку она будет поочередно выпадать то орлом то решкой и только изредка может два раза подряд выпасть одним номиналом. На самом же деле теорвер это скорее статистика чем математика, и когда говорят что вероятность выпадения орла и решки равна 50/50 то это значит что если ты будешь подбрасывать монетку достаточно долго ( в идеале бесконечно) то количество выпадений орла и решки будет одинаково (ну или очень близко к тому..) . И на самом деле вероятность того что подбрасывая монетку 10 раз у тебя будут поочередно выпадать то орел то решка ровно такая же как и та что выпадет 10 орлов подряд. ВОт такой вот казус.

Теперь давай возьмем n-угоугольник , вероятность того что в первый же ход фишка передвинется на “свободную” вершину равна 1(куда бы она не пошла все вершины кроме той где она стояла свободные). Вероятность того что на второй ход она передвинется на свободную вершину равна 1/2. Вероятность того что на третий ход она передвинется на еще одну “свободную” вершину равна 1/2 при условии что до этого она уже переместилась на свободную вершину тоесь 1/2*1/2=1/2**2 и так далее Тоесть вероятность что на n-й ход фишка займет последню вершину равна 1/2**(n-1). Тоесть мы видим что даже вероятность того что фишка с первого раза пройдет все вершины отлична от нуля.У нас же количество ходов ноограничено что должно сводить вероятность того что фишка когданить обойдет все вершины к единице . Точную формулу я к сожаления не првиеду, так как повторюсь, учил я все это довольно давно,и многое подзабыл, но то что фишка рано или поздно обойдет все вершини это не мое “я вот хочу”, это математически обоснованая вероятность.



==============================
Помещайте код в теги:
[code python][/code]
Бериегите свое и чужое время.

Отредактировано PEHDOM (Май 27, 2019 15:35:13)

Офлайн

#10 Май 27, 2019 16:06:33

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10031
Репутация: +  857  -
Профиль   Отправить e-mail  

Легкая задача

PEHDOM
У нас же количество ходов ноограничено что должно сводить вероятность того что фишка когданить обойдет все вершины к единице .
Рассмотрим треугольник. Может ли фишка не обойти треугольник при бесконечном множестве ходов? Ну… может. А почему нет-то?

То, что она может обойти с первого раза, это понятно. Но может ли она его не обойти? Тут пока что аргументы 1) “а я хочу, чтобы баланс нарушался” и 2) “а нарушение баланса вероятно, и поэтому он нарушится”.



Отредактировано py.user.next (Май 27, 2019 16:07:40)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version