Вопрос вероятности: оценка количества попыток, необходимых для исчерпывающей попытки найти все возможные места размещения при поиске по слову.

Question

Было бы разумно систематически пробовать все возможные места размещения в поиске слов ?

Сетки обычно имеют размеры 15 * 15 (15 ячеек в ширину, 15 ячеек в высоту) и содержат около 15 слов для размещения, каждое из которых можно разместить в 8 возможных направлениях. В общем, кажется, что вы можете рассчитать все возможные места размещения следующим образом: ширина * высота * 8_directions_to_place_word * количество слов

Так что для такой сетки кажется, что нам нужно всего лишь попробовать 15 * 15 * 8 * 15 = 27 000, что вовсе не так уж плохо. Я ожидаю какого-то огромного числа, поэтому либо размер сетки и количество слов действительно мало, либо в моей математике есть что-то подозрительное.

Answer 1

Формально говоря, предполагая, что x - это количество строк, а y - это число столбцов, вы должны суммировать все вероятности каждого возможного направления для каждого возможного слова.

Входные данные: x, y, l (средняя длина слова), n (всего слов)

так что у вас есть

• по горизонтали слово может начинаться от 0 до x-l и идти вправо или от l до x влево для каждой строки: 2x(x-l)
• тот же подход используется для вертикальных слов: они могут идти от 0 до y-l вниз или от l до y вверх. Так что это 2y(y-l)
• для диагональных слов вы должны учитывать все возможные начальные позиции x*y и вычитать l^2, поскольку прямоугольник поля не может быть использован. Как и прежде, вы умножаете на 4, поскольку у вас есть 4 возможных направления: 4*(x*y - l^2).

Затем вы умножаете весь результат на количество включенных слов:

total = n*(2*x*(x-l)+2*y*(y-l)+4*(x*y-l^2)