Цикл while

В языке C++ существует три вида циклов: цикл while c предусловием, цикл while с постусловием, цикл for.

Цикл `while` ("пока") с предусловием

Цикл while с предусловием позволяет выполнить одну и ту же последовательность действий пока проверяемое условие истинно. При этом условие записывается до тела цикла и проверяется до выполнения тела цикла.

При выполнении цикла while сначала проверяется условие. Если оно ложно, то цикл не выполняется и управление передается на следующую инструкцию после тела цикла while. Если условие истинно, то выполняется инструкция, после чего условие проверяется снова и снова выполняется инструкция. Так продолжается до тех пор, пока условие будет истинно. Как только условие станет ложно, работа цикла завершится и управление передастся следующей инструкции после цикла.

Синтаксис цикла while ("пока") c предусловием такой:

while (условие)
{
     блок инструкций
}

Например, следующий фрагмент программы напечатает на экран квадраты всех целых чисел от 1 до 10:

int i=1;
while (i <= 10)
{
    cout << i * i << endl;
    ++i;
}

В этом примере переменная i внутри цикла изменяется от 1 до 10. Такая переменная, значение которой меняется с каждым новым проходом цикла, называется счетчиком. Заметим, что после выполнения этого фрагмента значение переменной i будет равно 11, поскольку именно при i==11 условие i<=10 впервые перестанет выполняться.

В следующем примере цикл используется для того, чтобы найти количество знаков в десятичной записи целочисленной переменной i.

int Ndigits (int n)
{
    int result = 0;
    while (n != 0)
    {
        result = result + 1;
        n = n / 10;
    }
    return result;
}

Внутри цикла значение переменной n уменьшается в 10 раз до тех пор, пока она не станет равна 0. Уменьшение целочисленной переменной в 10 раз (с использованием целочисленного деления) эквивалентно отбрасыванию последней цифры этой переменной.

Цикл `while` ("пока") с постусловием

Цикл "пока" с постусловием отличается от цикла с предусловием тем, что сначала выполняется блок цикла, а потом проверяется условие. Если условие истинно, то цикл будет выполнен еще раз, и так до тех пор, пока условие будет истинно. Синтаксис цикла с постусловием такой (обратите внимание на обязательную точку с запятой после условия):

do
{
    Блок инструкций
}
while (условие);

Поскольку условие проверяется после выполнения тела цикла, то блок цикла с постусловием всегда будет выполнен хотя бы один раз, независимо от истинности условия. Это может привести к ошибкам, поэтому использовать цикл while с постусловием следует только тогда, когда это действительно упрощает алгоритм.

Упражнения

A: Список квадратов

По данному числу N распечатайте все квадраты натуральных чисел, не превосходящие N, в порядке возрастания.

Ввод	Вывод
50	1 4 9 16 25 36 49

B: Список степеней двойки

По данному числу N распечатайте все целые степени двойки, не превосходящие N, в порядке возрастания.

Функцией pow пользоваться нельзя!

Ввод	Вывод
50	1 2 4 8 16 32

C: Точная степень двойки

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.

Решение оформите в виде функции bool IsPowerOf2 (int n).

Ввод	Вывод
8	YES
3	NO

D: Двоичный логарифм

По данному натуральному числу \(N\) выведите такое наименьшее целое число \(k\), что \(2^k\ge N\).

Решение оформите в виде функции int Log2 (int n).

Ввод	Вывод
7	3

E: Утренняя пробежка

В первый день спортсмен пробежал \(x\) километров, а затем он каждый день увеличивал пробег на 10% от предыдущего значения. По данному числу \(y\) определите номер дня, на который пробег спортсмена составит не менее \(y\) километров.

Программа получает на вход действительные числа \(x\) и \(y\) и должна вывести одно натуральное число.

Ввод	Вывод
10 20	9

F: Банковские проценты

Вклад в банке составляет \(x\) рублей. Ежегодно он увеличивается на \(p\) процентов и округляется до целого числа копеек по правилам арифметики. Определите, через сколько лет вклад составит не менее \(y\) рублей.

Программа получает на вход три натуральных числа: \(x\), \(p\), \(y\) и должна вывести одно целое число.

Ввод	Вывод
100 10 200	8

G: Сумма цифр

Дано натуральное число N, вычислите сумму его цифр. Решение оформите в виде функции int SumOfDigits (int n).

Ввод	Вывод
179	17

H: Количество нулей

Дано натуральное число N, вычислите количество нулей в его десятичной записи. Решение оформите в виде функции int NumberOfZeroes (int n).

Ввод	Вывод
10709	2

I: Минимальная и максимальная цифры

Дано натуральное число N. Определите минимальную и максимальную цифру в его десятичной записи. Решение оформите в виде функций int MinDigit (int n) и int MaxDigit (int n)

Ввод	Вывод
179	1 9

J: Обращение числа

Дано натуральное число N, не заканчивающееся нулем. Получите число, составленное из тех же цифр, но записанных в обратном порядке. Решение оформите в виде функции int Reverse (int n).

Ввод	Вывод
179	971

K: Количество палиндромов

Натуральное число называется палиндромом, если его десятичная запись читается одинаково как слева направо, так и справа налево. Напишите функцию bool IsPalindrome (int n), определяющую, является ли данное число палиндромом. Используя эту функцию определите по заданному числу N количество палиндромов, не превосходящих N.

Ввод	Вывод
100	18

L: Сумма последовательности - 1

Программа получает на вход последовательность целых чисел и должна определить сумму этих чисел. Последовательность завершается числом 0, при считывании которого программа должна завершить работу и вывести результат. Числа, следующие за числом 0, считывать не нужно.

Ввод	Вывод
1 7 9 0 5	17

M: Сумма последовательности - 2

Решите задачу, аналогичную предыдущей, при условии, что признаком окончания входной последовательности являются два числа 0, записанные подряд.

Ввод	Вывод
1 7 0 9 0 0 5	17

N: Числа Фибоначчи

По данному числу \(n\) определите \(n\)-е число Фибоначчи \(\varphi_n\). Решение оформите в виде функции int phi (int n). Рекурсией пользоваться нельзя, решение должно иметь сложность \(O(n)\).

Ввод	Вывод
5	8

O: Номер числа Фибоначчи

Дано натуральное число \(A\). Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число \(n\), что \(\varphi_n=A\). Если \(А\) не является числом Фибоначчи, выведите число -1.

Ввод	Вывод
8	5
10	-1

P: Исполнитель “Раздвоитель”

Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка.

Дано два натуральных числа A и B (A>B). Напишите алгоритм для Развоителя, который преобразует число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по одной в строке, первая команда обозначается, как -1, вторая команда как :2.

Ввод	Вывод
179 20	-1 :2 -1 :2 :2 -1 -1

Q: Гипотеза Гольдбаха

Гипотеза Гольдбаха (недоказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел. Дано натуральное четное число, большее 2, выведите два простых числа, дающих в сумме данное.

Ввод	Вывод
4	2 2

R: Алгоритм Евклида

Даны два натуральных числа. Вычислите их наибольший общий делитель при помощи алгоритма Евклида, реализованного без использования рекурсии. Решение оформите в виде функции int gcd (int a, int b).

Ввод	Вывод
12 33	3

S: Бинарный алгоритм Евклида

В бинарном алгоритме Евклида не используются операции деления и остатка, а используется только проверка на чётность и деление на 2. Идея бинарного алгоритма Евклида следующая:
\(НОД(a,b)=2НОД(a/2,b/2)\), если \(a\) и \(b\) четные,
\(НОД(a,b)=НОД(a/2,b)\), если \(a\) четное, \(b\) нечетное,
\(НОД(a,b)=НОД(a,b/2)\), если \(a\) нечетное, \(b\) четное,
\(НОД(a,b)=НОД(a-b,b)\), если \(a\) и \(b\) нечетные, \(a\ge b\).

Реализуйте бинарный алгоритм Евклида для вычисления НОД двух чисел.

Ввод	Вывод
12 33	3

T: Сумма двух дробей

Даны две дроби \(\frac ab\) и \(\frac cd\) (числа \(a\) и \(c\) — целые, \(b\) и \(d\) — натуральные). Вычислите их сумму и запишите ее в виде смешанной дроби \(x\frac yz\) (число \(x\) целое, числа \(y\) и \(z\) натуральные, дробь \(\frac yz\) — правильная несократимая).

Программа получает на вход четыре числа \(a\), \(b\), \(c\), \(d\) и должна вывести ответ в виде смешанной дроби. Если целая часть смешанной дроби равна 0, ее выводить не надо. Если дробная часть смешанной дроби равна 0, ее выводить не надо. Если число отрицательное, то перед ним выводится знак “-”. Следуйте формату вывода, приведенному в примерах.

Ввод	Вывод
1 2 1 3	5/6
1 2 2 3	1 1/6
3 2 2 4	2
2 1 -4 2	0
-1 2 -1 3	-5/6
-1 2 -2 3	-1 1/6
3 10 -1 10	1/5

U: Сумма двух квадратов

Дано натуральное число \(N\). Определите, можно ли его представить в виде суммы двух точных натуральных квадратов.

Если число \(N\) представимо в виде суммы двух натуральных квадратов, выведите два натуральных числа \(a\) и \(b\) таких, что \(a^2+b^2=N\), иначе выведите строку Impossible.

Ввод	Вывод
20	2 4
21	Impossible

V: Теорема Лагранжа

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы не более, чем четырех точных квадратов. По данному числy N выведите от 1 до 4 натуральных чисел, квадраты которых в сумме дают значение N.

Ввод	Вывод
7	2 1 1 1

W: Выдача сдачи

Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими способами можно выдать сдачу в \(N\) рублей. Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1.

Программа получает на вход число N, не превышающее 100.

Ввод	Вывод
2	2
5	4

W+: Выдача сдачи - 2

Решите предыдущую задачу в ограничениях N≤10⁷, время на тест — 1 секунда. Учтите, что для хранения ответа необходимо использовать тип long long.

Тесты к этой задаче закрытые.

X: Разложение на множители

Дано натуральное число \(N>1\). Выведите все его простые натуральные делители с учетом кратности. Алгоритм должен иметь сложность \(O(\sqrt{n})\).

Ввод	Вывод
132	2 2 3 11
2	2

Y: Количество целочисленных точек в круге

Дано натуральное число \(R\le 10^6\). Определите количество целочисленных точек, находящихся внутри и на границе круга радиуса \(R\) с центром в начале координат. Ограничение по времени на решение — 1 секунда.

Учтите, что для хранения ответа необходимо использовать тип long long.

Тесты к этой задаче закрытые.

Ввод	Вывод
2	13

Z: Исполнитель “Водолей”

У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

Наполнить сосуд A (обозначается >A).
Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>).
Вылить воду из сосуда B (обозначается B>).
Перелить воду из сосуда A в сосуд B (обозначается как A>B).
Перелить воду из сосуда B в сосуд A (обозначается как B>A).

Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полность наполняется.

Программа получает на вход три натуральных числа A, B, N, не превосходящих 10⁴ Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.

Количество операций в алгоритме не должно превышать 10⁵. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10⁵ операций.

Тесты к этой задаче закрытые.

Ввод	Вывод
3 5 1	>A A>B >A A>B
3 5 100	Impossible

Цикл while

Цикл while ("пока") с предусловием

Цикл while ("пока") с постусловием

Упражнения

A: Список квадратов

B: Список степеней двойки

C: Точная степень двойки

D: Двоичный логарифм

E: Утренняя пробежка

F: Банковские проценты

G: Сумма цифр

H: Количество нулей

I: Минимальная и максимальная цифры

J: Обращение числа

K: Количество палиндромов

L: Сумма последовательности - 1

M: Сумма последовательности - 2

N: Числа Фибоначчи

O: Номер числа Фибоначчи

P: Исполнитель “Раздвоитель”

Q: Гипотеза Гольдбаха

R: Алгоритм Евклида

S: Бинарный алгоритм Евклида

T: Сумма двух дробей

U: Сумма двух квадратов

V: Теорема Лагранжа

W: Выдача сдачи

W+: Выдача сдачи - 2

X: Разложение на множители

Y: Количество целочисленных точек в круге

Z: Исполнитель “Водолей”

Цикл `while` ("пока") с предусловием

Цикл `while` ("пока") с постусловием