Остановится ли? (Задача)

сегодня в 13:27

В древней рукописи найден такой код (на каком-то древнем и давно забытом языке программирования):

while n > 1

if n mod 2 = 0 then

n:=n/2

else

n:=3*n+3

Рядом с кодом написан вопрос: «Остановится ли это когда-нибудь?» ()



Решение:

Запишем в более наглядном виде, как меняется n на каждом шаге:

Чтобы цикл остановился, n должно стать равным 1. Подумаем, в каких случаях это возможно.

Во втором случае (n нечетное) оно возрастает и становится равным 3(n+1), то есть, к делителям числа добавляется 3. Рано или поздно n опять станет нечетным и кратным 3 (не равным 1), и цикл никогда не остановится.

Если у числа n нет простых делителей, отличных от 2 (другими словами, n является степенью двойки), цикл остановится.

Осталось реализовать эту проверку: существует множество способов, самый эффективный – используя битовые операции: если все биты кроме старшего нулевые, то n является степенью двойки, иначе – нет.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html