Для не-британцев в аудитории есть сегмент дневного игрового шоу, где у участников есть набор из 6 чисел и случайно сгенерированное целевое число. Они должны достичь целевого числа, используя любое (но не обязательно все) из 6 чисел, используя только арифметические операторы. Все вычисления должны привести к положительным целым числам.
Пример: Youtube: Обратный отсчет - самая необычная игра чисел?
Подробное описание дано в Википедии: Обратный отсчет (Game Show)
Например:
- Контентант выбирает 6 чисел - два больших (варианты включают 25, 50, 75, 100) и четыре маленьких (числа 1 ... 10, каждое из которых включено в пул дважды).
- Числа определены являются 75, 50, 2, 3, 8, 7приведены с целевым числом 812.
- Одна попытка: (75 + 50 - 8) * 7 - (3 * 2) = 813 (это 7 баллов за решение в пределах 5 от цели)
- Точный ответ был бы (50 + 8) * 7 * 2 = 812 (Это набрало бы 10 очков, точно соответствующих цели).
Очевидно, что эта проблема существовала до появления телевидения, но статья в Википедии не дает ей названия. Я также видел эту игру в начальной школе, которую я посещал, где игра называлась «Крипто» как соревнование между классами - но поиск ее теперь ничего не показывает.
Я принимал в этом участие несколько раз, и мой папа написал электронную таблицу Excel, в которой пытался решить проблему, я не помню, как она работала (только то, что она не работала, что с пределом строк в 65535 в Excel), но конечно, должно быть алгоритмическое решение проблемы. Возможно, есть решение, которое работает так, как работает человеческое познание (например, параллельно, чтобы найти числа «достаточно близко», затем выбрать кандидатов и выполнить «меньшие» операции).
Ответы:
Отказ от ответственности: Этот ответ не отвечает на вопрос, который полностью. Но это слишком долго для комментария.
NP-трудной? Я считаю, что эта проблема может быть NP-трудной .
Рассмотрим частный случай задачи о ранце :
Это звучит несколько похоже на нашу проблему с обратным отсчетом, и это кажется намного проще. Тем не менее, рюкзак (и этот особый случай рюкзака) является NP-сложным (и NP-полным, конечно).
Мне не удалось использовать это для доказательства того, что обратный отсчет является NP-сложным. Я не мог избавиться от деления. Предположим, у нас есть тысяча 2, и b = 7. Это никогда не будет решаемо с помощью рюкзака, но всегда (?) С обратным отсчетом, по крайней мере, всеми способами, которые я пытался перенести.
Теперь, если бы обратный отсчет действительно был NP-сложным, мы могли бы заключить, что там с очень высокой вероятностью не существует алгоритма, который был бы значительно более эффективным, чем перебор, использующий все возможности. (И если мы найдем такой алгоритм, мы станем очень известными.)
Нет, я не думаю, что должен быть эффективный алгоритм.
Эвристика. У видео на YouTube, на которое есть ссылки в вопросе, есть хороший пример: участник нашел точный ответ Кстати в первый раз: выведите очень большое число, затем разделите его и дайте результат.
С другой стороны, мы, люди, чувствуем, что нам не нужно пытаться (произвольный пример) 50 * 75 * 100/2/3/7, чтобы достичь трехзначного числа. Но компьютеры ничего не чувствуют , они просто подсчитывают.
В конце концов, если мы внедрили некоторую эвристику, и эта эвристика не находит точного решения, нам все равно придется попробовать все другие решения, чтобы убедиться, что их действительно нет.
Я думаю, что участник видео на Youtube очень быстро проверяет большое количество возможностей и быстро отбрасывает те, которые не (или, скорее всего, не) дадут решение.
Вывод. При реализации алгоритма можно позаботиться о том, чтобы лишить равных вычислений, таких как a / b / c = a / (b * c), но я думаю, что это довольно сложно сделать, и я не знаю, значительно ли это улучшает время выполнения.
Компьютеры, конечно, быстрее, чем люди, проверяют большое количество возможностей. И в наши дни даже смартфоны настолько быстры, что могут решить эту проблему, я думаю, за секунду, просто испробовав все возможности. (Я не проверял это.) Всего шесть цифр, было бы иначе, если бы их было, например, 60.
источник
Алгоритм на самом деле не очень сложный.
Учитывая два числа a и b, мы можем получить результаты a + b, abs (a - b) (я не знаю, допустимы ли отрицательные числа, и в этом случае мы можем получить a - b и a + b), a * b, и, возможно, a / b или b / a, если результатом является целое число. Таким образом, возможные результаты представляют собой набор из пяти чисел. Назовите этот набор S (a, b).
Возьмите шесть чисел a, b, c, d, e и f.
Для каждого подмножества двух чисел найдите числа, которые они могут произвести.
Затем для каждого подмножества из трех чисел найдите числа, которые они могут произвести: S (a, b, c) = S (S (a, b), c) объединение S (S (a, c), b) объединение S ( S (б, в), а).
Затем то же самое для каждого подмножества из 4 или 5 чисел, затем для всех 6 чисел.
источник