DjangoBB LoFi version

Полная версия: P3: непонятное поведение массивов

Начало » Python для новичков » P3: непонятное поведение массивов

Thackeray

Дек. 7, 2017 09:35:48

Есть код, который моделирует случайное блуждание.

Проблема в том. что при использовании трех разных способов генерации массивов, выдается разный результат.
Блок 1 - для генерации используется книжный модуль (можно не рассматривать) - работает ок
Блок 2 - для генерации используется первый способ - работает ок
Блок 3 - второй способ - вроде бы тот же, записанный по-другому - результат deadEnds3 всегда равен 0
При этом если сравнить три массива, сгенерированные этими способами как a == и == с - результат выражения True. То есть массивы создаются одинаковые. Но ведут себя по-разному. Почему?

Других отличий в трех способах нет, поэтому собака зарыта где-то там.

Сама задача
Предположим, вы потеряли свою собаку в большом городе, улицы которого образуют знакомый узор
таблицы. Предполагается, что с севера на юг и с востока на запад есть n улиц,
и все они распределены равномерно и пересекаются под прямым углом, образуя
узор в виде решетки. Пытаясь удрать из города, собака выбирает направление
случайно, но на каждом перекрестке проверяет по запаху, не была ли она уже
здесь раньше. Но собака вполне может застрять в тупике, когда у нее нет ни
какого выбора, кроме как попасть на собственные следы. Каков шанс, что это
случится?

Книжная реализация https://introcs.cs.princeton.edu/python/14array/selfavoid.py.html

 import random
import stdarray
n = int(input())
trials = int(input())
deadEnds = 0
deadEnds2 = 0
deadEnds3 = 0
#block 1
for t in range(trials):
    a = stdarray.create2D(n, n, False)
    x = n // 2
    y = n // 2
    while (x > 0) and (x < n - 1) and (y > 0) and (y < n - 1):
        a[x][y] = True
        if a[x-1][y] and a[x+1][y] and a[x][y-1] and a[x][y+1]:
            deadEnds += 1
            break
        r = random.randrange(1, 5)
        if r == 1 and (not a[x+1][y]): x += 1
        elif r == 2 and (not a[x-1][y]): x -= 1
        elif r == 3 and (not a[x][y+1]): y += 1
        elif r == 4 and (not a[x][y-1]): y -= 1
#block 2
for q in range(trials):
    b = [None] * n
    for row in range(n):
        b[row] = [False]*n
    x = n // 2
    y = n // 2
    while (x > 0) and (x < n - 1) and (y > 0) and (y < n - 1):
        b[x][y] = True
        if b[x-1][y] and b[x+1][y] and b[x][y-1] and b[x][y+1]:
            deadEnds2 += 1
            break
        r = random.randrange(1, 5)
        if r == 1 and (not b[x+1][y]): x += 1
        elif r == 2 and (not b[x-1][y]): x -= 1
        elif r == 3 and (not b[x][y+1]): y += 1
        elif r == 4 and (not b[x][y-1]): y -= 1
#block 3
for w in range(trials):
    c = [[False] * n ]* n
    x = n // 2
    y = n // 2
    while (x > 0) and (x < n - 1) and (y > 0) and (y < n - 1):
        c[x][y] = True
        if c[x-1][y] and c[x+1][y] and c[x][y-1] and c[x][y+1]:
            deadEnds3 += 1
            break
        r = random.randrange(1, 5)
        if r == 1 and (not c[x+1][y]): x += 1
        elif r == 2 and (not c[x-1][y]): x -= 1
        elif r == 3 and (not c[x][y+1]): y += 1
        elif r == 4 and (not c[x][y-1]): y -= 1
print(str(100 * deadEnds // trials) + '% dead ends')
print(str(100 * deadEnds2 // trials) + '% dead ends')
print(str(100 * deadEnds3 // trials) + '% dead ends')

Входные и выходные:
20
100
39% dead ends
22% dead ends
0% dead ends

20
100
35% dead ends
26% dead ends
0% dead ends

20
100
31% dead ends
33% dead ends
0% dead ends

scidam

Дек. 7, 2017 10:19:49

Причина с последним вариантом должна быть ясна из следующего примера:

 >>> x= [[False]*2]*2
>>> x
[[False, False], [False, False]]
>>> x[0][0]=True
>>> x
[[True, False], [True, False]]
>>>

А почему так, можно прочесть здесь.

Чтобы результат был одинаков, добавьте перед каждым основным блоком random.seed(10), чтобы последовательность случайных чисел для каждого расчетного блока повторялась.

PEHDOM

Дек. 7, 2017 10:52:08

потому что операции с списками ссылочные , а не атомарные и умножив список на n вы получите n ссылок на один и тот же список, вместо n разных списков.

 >>> n = 2
>>> c = [[False] * n ]* n
>>> c[0] is c[1]
True
>>>

Thackeray

Дек. 7, 2017 11:41:19

Спасибо! Вот же, если бы не случайность, не обнаружилось бы, ведь *n до этого вполне работало как n отдельных оъектов, а [*n]*n, выходит, нет..