Задача e-olimp.com №388
Ссылка на засчитанное решение.
Условие
Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.
Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения 1.
Число N (1 ≤ N ≤ 109).
Тесты
Входные данные(N) | Выходные данные |
11 | 6 |
43 | 9 |
1 | 0 |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int main() { int N, counter=0; cin >> N; while(N!=1){ counter++; if(N%2==0){ N = N/2; } else{ N++; } } cout << counter << endl; return 0; } |
Для запроса на выполнение нажать здесь.
Решение
Пусть [latex]N[/latex] — это число, которое мы будем изменять, а [latex]counter[/latex] — количество превращений. Цикл должен выполняться до того момента, пока [latex]N \neq 1[/latex]. Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число — чётное, то делим его на 2, в противном случае — добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.
— Все формулы должны оформляться в latex и выглядеть так — [latex]N[/latex] , а не так — N.
— Добавьте ссылку на код в ideone, чтобы можно было его запустить для проверки.
— Вы делаете ++counter в обоих ветках условного оператора. Лучше написать это один раз до или после него.
P.S. оказалось, что я тоже решал эту задачу, но рекурсией без цикла. Приведу решение для любопытных читателей.
P.P.S. Есть похожая интересная задача про сиракузскую последовательность. Почитайте из любопытства.
Спасибо. Исправила.