На калькуляторе есть всего две клавиши с нестандартными операциями: 2а+1 и (а-1)/3. При этом вторая операция доступна, если а-1 делится на 3. Как с помощью этого калькулятора из 1 получить 8, выполнив наименьшее число операций?
update
Наименьшее количество операций предложил Andrew Antonets.Ответ
Из 1 можно получить 8 за 15 операций:
1-3-7-15-31-63-127-42-85-171-343-114-229-76-25-8.
1-3-7-15-31-63-127-42-85-171-343-114-229-76-25-8.
Какая пара не является решением?
Доказать, что этот путь - кратчайший, видимо, невозможно (только перебором вручную всего дерева), но вариант в 20 операций такой:
ОтветитьУдалить1-3-7-15-31-63-127-42-85-28-9-19-6-13-27-55-18-37-12-25-8
Операции очевидны, поэтому не стал указывать.
Но построение дерева с 20 уровнями узлов - дело трудоемкое. Теоретически на нижнем уровне будет миллион узлов, но вторая операция не всегда возможна, да и будут образовываться "кольца"... Так, на 9-м уровне будет 7 узлов. Но к 20-му до тысячи наберется, так что доказательство оставлю или более усидчивым головоломщикам, или избыточно любознательным программистам.
я сходу нашел в 15 операций (комментарий ниже), но с доказательством пока туго.
УдалитьПытался рассуждать от обратного, в духе "8 четное, четные числа можно получить только второй операцией..." до пока дело не пошло
1-3-7-15-31-63-127-42-85-171-343--114-229-76-25-8
ОтветитьУдалитьвопросы с доказательством пока не решены :)
Доказательства у меня тоже нет. Есть только ответ и 15 - минимальное количество операций.
Удалить