Условие
Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на [latex]2[/latex], если нечетное, прибавим [latex]1[/latex]. После нескольких таких изменений мы всегда получаем число [latex]1[/latex]. Например, из числа [latex]11[/latex] получается число [latex]12[/latex], затем [latex]6[/latex], [latex]3[/latex], [latex]4[/latex], [latex]2[/latex] и, наконец, [latex]1[/latex]. Таким образом, для получения [latex]1[/latex] из [latex]11[/latex] нужно проделать [latex]6[/latex] изменений.
Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения [latex]1[/latex].
Тестирование
| № | Входные данные | Выходные данные |
| 1 | 1 | 0 |
| 2 | 11 | 6 |
| 3 | 65 | 13 |
| 4 | 1024 | 10 |
Код
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main() { int n, i; // n для числа, i для счета преобразований cin >> n; for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); // Преобразовываем n, пока не получим 1 cout << i; // Выводим значение счетчика return 0; } |
Решение
Так как в качестве ответа на задачу нам нужно вывести значение переменной-счетчика, которая отвечает за количество проделанных изменений, то объявлять ее нужно будет не в начальных условиях цикла for, а в пределах главной функции:
|
1 2 3 4 5 |
#include <iostream> using namespace std; int main() { int n, i; // n для числа, i для счета преобразований |
Теперь опишем, каким образом будет работать цикл:
- Цикл начинается со значением счетчика 0, так как возможны случаи, когда операций над [latex]n[/latex] вообще не нужно будет производить (конкретно — при [latex]n=1[/latex]).
- Поскольку нам гарантируют, что входное число [latex]n[/latex] — натуральное, то цикл будет работать до тех пор, пока [latex]n>1[/latex].
- После каждой итерации значение счетчика будет увеличено на [latex]1[/latex].
- Тело цикла состоит из единственного оператора присваивания переменной с числом [latex]n[/latex] нового значения. [latex]n[/latex] может быть преобразовано двумя способами, и для определения нужного используется проверка на его четность:
- если [latex]n[/latex] — нечетное, то значение [latex]n[/latex] увеличивается на [latex]1[/latex];
- в противном случае [latex]n[/latex] делится на [latex]2[/latex].
Реализуем описанный алгоритм, после которого отправляем на печать значение счетчика i:
|
1 2 |
for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); cout << i; |
Ссылки
Условие задачи на E-Olymp;
Код программы на Ideone.com;
Подтверждение решения на E-Olymp.