Была задачка такая в школе у нас на одной важной работе. Про пещеры и клад. К ней нужно было применить алфавитный подход... <<Известно, что ровно в двух пещерах из пяти есть клады. Сколько битов нужно, чтобы закодировать информацию о расположении кладов?>> Если задачу решать традиционно, как на первый взгляд кажется - изящно, то ответ получится примерно таков: 1 2 3 4 5 0 1 0 0 1 Итого: 5 битов.
Мы же говорим о рациональном подходе. Всего 5 пещер. В двух клады. Сколько вариантов расположения кладов существует? 1 2 3 4 5 1-2,1-3,1-4,1-5,2-3,2-4,2-5,3-4,3-5,4-5 Итого: 10 вариантов - вот тебе и алфавит. Можешь пронумеровать варианты(0, 1,2,3...) и информацию хранить будешь в скольки битах? 10=2^i 2^3=8(10 сюда не входит) 2^4=16(10 входит. Пусть будет немного лишней информации, зато она не потеряется.) Получаем 4 бита.
Запишем этот алгоритм, и на место команды1 поставим команду сместиться на (a, b). (здесь a, b -это нужные нам координаты смещения в команде1)
Повтори 2 раз Сместиться на (a, b) Сместиться на (3, 2) Сместиться на (2, 1) Конец Сместиться на (−6, −4)
Выполнение этого алгоритма приведёт к следующим смещениям по оси икс: a + 3 + 2 + a + 3 + 2 - 6 Так как нам известно, что в результате этих смещений чертёжник вернулся в исходную точку, то это значит что сумма всех смещений равна нулю. Можем записать уравнение и найти a: a + 3 + 2 + a + 3 + 2 - 6 = 0 2a + 4 = 0 2a = -4 a = -4 / 2 = -2 (нашли смещение по x в команде1)
Далее, делаем то же самое для смещения по y: Выполнение этого алгоритма приведёт к следующим смещениям по оси игрек: b + 2 + 1 + b + 2 + 1 - 4 Составляем уравнение: b + 2 + 1 + b + 2 + 1 - 4 = 0 2b + 2 = 0 2b = -2 b = -2 / 2 = -1 (нашли смещение по y в команде1)
Значит, вместо команды1 нужно поставить команду, указанную в варианте ответа 1) Сместиться на (-2, -1)
