Задача на e-olymp 388
Ссылка на засчитанное решение.
Условие
Возьмем какое-нибудь натуральное число [latex]n[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.
Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения 1.
Число [latex]n(1\leq n \leq10^{9}).[/latex]
Тесты
| Входные данные(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 19 20 |
import java.util.*; import java.lang.*; import java.io.*; class Main{ public static void main (String[] args) throws java.lang.Exception{ Scanner x = new Scanner(System.in); int counter = 0; int n = x.nextInt(); while (n != 1) { counter++; if(n % 2 == 0){ n = n / 2; } else { n++; } } System.out.print(counter); } } |
Решение
Пусть [latex]n[/latex] – это число, которое мы будем изменять, а [latex]counter[/latex] – количество превращений. Цикл должен выполняться до того момента, пока [latex]n[/latex] Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число – чётное, то делим его на 2, в противном случае – добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.