сегодня в 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
Комментариев нет:
Отправить комментарий