2

Вот условие: Имеется двумерное игровое поле размером N x N (N - натуральное число, вводится с клавиатуры), представленное в виде вложенного списка:

P = [[0] * N for i in range(N)]

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

Вот код:

import random


random.seed(1)

N = int(input())
P = [[0] * N for i in range(N)]
M = 10

while M > 0:
    row = random.randint(0, N - 1)
    pos = random.randint(0, N - 1)
    if P[row-1][pos] + P[row - len(P) + 1][pos] + P[row][pos] + P[row][pos - len(P) + 1] + P[row][pos - 1] + P[row - len(P) + 1][pos - len(P) + 1] + P[row - len(P) + 1][pos - 1] + P[row - 1][pos - len(P) + 1] + P[row - 1][pos-1] == 0:
        P[row][pos] = 1
        M -= 1
    else:
        continue

В матрице 10х10 у меня все ок. Проблема в том что в матрице 7х7 тоже должно поместиться 10 единиц, но у меня влезает только 9 единиц, и дальше начинается бесконечный цикл, который ищет место для 10 единицы. У меня есть мысль что условие строгое, но я не уверен.

5
  • 1
    и какой вопрос-то? еслип предыдущие 9 единиц стоят так, что больше нет подходящего места для десятой, то хоть обыщись, места не найдешь. 7 июл 2022 в 8:27
  • Да, я понимаю, но по условию в матрице 7х7 может поместиться 10 единиц
    – Kazak
    7 июл 2022 в 9:11
  • в 7х7 даже 16 поместиться может. Но вероятность получить такое расположение случайной расстановкой исчезающе мала. 7 июл 2022 в 9:17
  • 1
    Насколько "случайной" должна быть расстановка? Выберите из диапазона от "вероятности любых возможных расстановок должны быть равны" через "вероятности могут быть различны, но не могут быть нулевые" до "какие попало вероятности". 7 июл 2022 в 10:38
  • Думаю, что для начала лучше исправить три проблемы, что я выделил в ответе. 7 июл 2022 в 11:00

1 ответ 1

1
  1. При случайной расстановке вариант с 10 единицами не гарантирован. Например, имея квадрат с вертикальной нумерацией от A до F и горизонтальной от 1 до 7, мы можем получить ситуацию, при которой сначала будут заняты ячейки B2, B5, E2, E5, что полностью выведет из доступности квадрат 6x6 (A1-F6). Дальнейшая случайная расстановка может позволить ещё пять - B7, E7, G2, G5, G7. Итого гарантировано только 9. В таком случае нужна проверка на зацикливание и потом перезапуск. Или вообще по-другому делать - см.комментарий Романа ниже.

  2. Ваши псевдослучайные генераторы при всех прогонах выдают одинаковые последовательности. Надо убрать random.seed (1).

  3. Вы для каждого найденного элемента рассчитываете все девять "запретных" полей, хотя у граничных элементов их будет меньше. Да еще и неправильно рассчитываете. Даже если компонент (например) P[0][3] и будет разрешенным, то P[row-1][pos] начнет проверять граничность с компонентом P[-1][3], что эквивалентно P[6][3], а этот элемент не имеет никакого отношения к P[0][3]. Вы какой-то тор реализовали, а не квадрат. Надо правильную проверку сделать, убрав элементы с минусом (добавить что-то вроде row_c = row - 1 if row > 0 else 0, а все индексы row - 1 заменив на row_c и аналогично с pos)

  4. else лучше убрать. Смысла он не несет, цикл и без continue продолжится.

2
  • 1
    Такая итерприрация "случайной расстановки" неконструктивна и для даной задачи, уверен, неправильна. Очевидно, что 10 единиц можно расставить в квадрате 7х7. Очевидно, что не одним способом. В задаче под "случайная расстановка" имеется ввиду "случайная из доступных/разрешенных", а не "со случайным размещением единиц по одной". 7 июл 2022 в 10:24
  • Я написал этот ответ, отталкиваясь от конкретного кода, так как вопрос по нему, как я понимаю, а не "выполните мне домашку". 7 июл 2022 в 10:30

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.