Рубрики

Головоломка | Символы

Есть две ворота. Один попадает в ад, а другой попадает в рай. Привратник задает Сахилу загадку, чтобы решить, какие ворота ему открыть. Очевидно, что если Сахиль ответит на загадку правильно, врата в рай будут открыты, иначе — врата в ад. В соответствии с задачей Sahil задается n последовательных целых чисел от 1 до n, которые записываются в ряд. Он должен поставить знаки «+» и «-» перед ними, чтобы полученное выражение было равно 0 или, если задание невозможно выполнить, Сахиль должен сказать привратнику: «Для данной задачи не существует решения» . Привратник ожидает, что Сахил найдет свой ответ за минимальное время, используя эффективный подход, а не изучая все возможные способы размещения знаков. Сахиль приходит к вам, считая вас своим другом. Не могли бы вы помочь ему найти решение?

Решение :
Головоломка имеет решение тогда и только тогда, когда n или n + 1 делится на 4.

Пояснение:
Задача эквивалентна разбиению n целых чисел от 1 до n на два непересекающихся подмножества с одинаковой суммой. Непересекающиеся подмножества являются подмножествами без общего элемента. Два непересекающихся подмножества будут:
1) подмножество чисел со знаком плюс перед ними, и
2) подмножество чисел со знаком минус перед ними.

Поскольку сумма первых n последовательных целых чисел равна S = 1 + 2 + 3 + —————— + n = (n) (n + 1) / 2, сумма чисел в каждом из подмножеств должна быть равна ровно на половину S, т. е. S / 2. Это означает, что значение S, т. Е. (N) (n + 1) / 2, должно быть четным, чтобы головоломка имела решение.

Подходить :

1) Ясно, что n (n + 1) / 2 четно тогда и только тогда, когда n кратно 4 или n + 1 кратно 4.

2) Действительно, если n (n + 1) / 2 = 2t, это означает, что n (n + 1) = 4t, и поскольку либо n, либо n + 1 нечетно, то другой должен делиться на 4. И наоборот, если либо n, либо n + 1 кратно 4, и, следовательно, n (n + 1) / 2, очевидно, четно.

3) Теперь рассмотрим случай, когда n делится на 4. В этом случае мы можем, например, разбить последовательность целых чисел от 1 до n на n / 4 группы из четырех последовательных целых чисел, а затем поставить знак «+» перед первое и четвертое число и знак «-» перед вторым и третьим числом в каждой из этих n / 4 групп. Это можно понимать как:

(1 — 2 — 3 + 4) + (5 — 6 — 7 + 8) + ———— + ((n — 3) — (n — 2) — (n — 1) + n) = 0. — — (1)

4) Теперь рассмотрим случай, когда n + 1 делится на 4, тогда n = 4t — 1, что подразумевает n = 3 + 4 (t — 1), и мы можем использовать ту же идею, сначала позаботившись о первых трех номера следующим образом:

(1 + 2 — 3) + (4 — 5 — 6 + 7) + ———— + ((n — 3) — (n — 2) — (n — 1) + n) = 0. ——— — (2)

Итак, подведем итог, проблема будет иметь следующие решения:
Вычислить n mod 4, т. Е. Остаток от деления n на 4.
Решение 1. Если остаток равен 0, вставьте знаки «+» и «-», как указано в формуле (1).
Решение 2: Если остаток равен 3, вставьте знаки «+» и «-», как указано в формуле (2).
В противном случае верните сообщение «Для данной проблемы не существует решения».

Ссылка: Алгоритмические головоломки — Ананы Левитин, Мария Левитин

Рекомендуемые посты:

Головоломка | Символы

0.00 (0%) 0 votes