Счётчики, Накопители и Обработка цифр - Язык программирования C++ для спортивного программирования
Неделя 3Циклы, Счётчики и Накопители, Обработка цифр
Счётчики, Накопители и Обработка цифр
Чтение n чисел по одному: подсчёт, сумма и произведение по мере поступления, наименьшее и наибольшее, ввод до нуля, предыдущее число. Затем одно число, разобранное через % 10 и / 10: сумма и количество цифр, переворот, палиндромы, делители, простые числа, НОД, степени двойки и числа Фибоначчи.
Теория
Урок 3 из 6
33 мин чтения
Вопросов: 10
Большинство задач на циклы читают список чисел и хотят о нём один ответ: сумму,
сколько в нём чётных, самое большое число. Во второй половине урока те же циклы
берутся за одно число и разбирают его по цифрам. Хранить сами числа не нужно —
массивы будут на следующей неделе. Цикл читает их по одному, а несколько
переменных помнят то, что важно об уже прочитанных числах.
Чтение n чисел
Часто ввод начинается с того, сколько чисел будет дальше:
Каждая итерация читает одно число в x, использует его и отпускает: на
следующей итерации в x уже следующее число. cin всё равно, стоят ли числа в
одной строке или в нескольких.
Счётчики и накопители
Счётчик считает, сколько раз что-то случилось: он начинается с 0 и каждый
раз увеличивается на единицу. Накопитель собирает сумму: он начинается с 0,
и к нему прибавляется каждое число.
Прочитайте n оценок. Выведите их сумму и сколько из них не меньше 90, а на
следующей строке — среднее с двумя знаками после точки.
Ввод
Вывод
Где стоит каждая строка — главное в любом счётчике и накопителе:
Обратите внимание на три вещи:
Оба начинаются с 0 — до цикла. Объявленные внутри цикла, они бы на каждой
итерации начинались с 0 заново.
Сумма — long long. Сто тысяч чисел до 10⁹ дают в сумме до 10¹⁴ — гораздо
больше, чем помещается в int (неделя 1).
Для среднего нужен double: sum / n само по себе — целочисленное
деление, а (double)sum / n — нет.
По той же схеме считается и складывается что угодно: положительные числа,
числа, равные x, кратные 3 в диапазоне. Меняется только if.
Произведение устроено так же, но начинается с 1 — начавшись с 0, оно
навсегда осталось бы нулём. n! — это 1 · 2 · … · n:
20! — примерно 2,4 · 10¹⁸ и ещё помещается в long long; 21! уже нет.
Так же и со степенью на ходу: p начинается с 1 и становится a, a², a³, …
— одно умножение на итерацию, без pow и без округлений:
дальше
Практика: Счётчики и Накопители
Суммы, количества, минимумы и максимумы по списку чисел, прочитанных по одному.
Это сумма 1 + a + a² + … + aⁿ. Умножение идёт первым, поэтому цикл никогда не
вычисляет aⁿ⁺¹ — степень, о которой никто не просил и которая могла бы
переполниться. Чтобы знаки чередовались, 1 − a + a² − …,
заведите sign, который начинается с 1 и после каждого слагаемого становится
-sign.
Наименьшее и наибольшее
Чтобы найти максимум, храните в mx наибольшее из уже увиденных чисел, и пусть
каждое новое число бросает ему вызов: mx = max(mx, x). Весь вопрос в том, с
чего mx начинается.
Прочитайте n температур, которые могут быть ниже нуля. Выведите самую
низкую и самую высокую.
Ввод
Вывод
Первое показание читается до цикла и становится и mn, и mx: из
прочитанных пока показаний оно и самое холодное, и самое тёплое. Затем цикл
читает остальные n - 1. Пройдите по шагам:
Самое холодное и самое тёплое — всегда в актуальном состоянии
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 int n, x;
9 cin >> n >> x;
10 int mn = x, mx = x;
11 for (int i = 1; i < n; i++) {
12 cin >> x;
13 mn = min(mn, x);
14 mx = max(mx, x);
15 }
16 cout << mn << " " << mx << "\n";
17 return 0;
18}
Читаем n
строка 9
Будет 4 показания.
ввод
4
-3
-8
2
-1
n4x—mn—mx—i—
нажми пуск
1 / 21
Начинать с mx = 0 — классическая ошибка: для недели, когда ни разу не было
выше нуля, программа напечатает 0 — температуру, которой не было. Начинать с
первого числа всегда безопасно. (Другое безопасное начало — значение меньше
любого возможного ввода, например -2000000000, если числа не меньше −10⁹.)
Чтобы запомнить, где стояло лучшее число, храните и его позицию и
обновляйте её в том же if, что и значение:
С > запоминается первый из нескольких равных максимумов, с >= — последний.
Чтобы посчитать, сколько раз встречается максимум, рядом с ним заводят
счётчик: новый, бо́льший максимум начинает счёт заново с 1, а равный ему
прибавляет единицу.
До нуля
Иногда ввод не говорит, сколько будет чисел. Вместо этого конец отмечает особое
значение — часто 0, который в число списка не входит:
Числа даны до 0. Выведите, сколько из них чётных, и их сумму.
Ввод
Вывод
while (cin >> x && x != 0) читает число и сразу его проверяет: цикл
останавливается на 0 и никогда его не считает. (cin >> x ложно, когда ввод
закончился, поэтому цикл безопасен даже без 0.)
Помним предыдущее
Некоторые ответы зависят от двух соседей: больше ли это число предыдущего?
Храните предыдущее число в переменной и обновляйте её в конце каждой
итерации:
Числа даны до 0. Выведите, сколько из них больше числа прямо перед ними.
Ввод
Вывод
В 3 5 5 2 8 9 1 больше своего предыдущего числа 5, 8 и 9: всего 3.
prev = x стоит последним: пока выполняется if, в prev должно оставаться
старое число.
Теперь цикл — это вы. Обновляйте переменные по мере того, как приходят числа:
Будьте накопителемпопробуй!
Отщипываем цифры
На неделе 1 % 10 давал последнюю цифру числа, а / 10 её отбрасывал. С циклом
эти две операции разбирают число по цифрам, сколько бы цифр в нём ни было. Такой
же цикл находит делители, проверяет, простое ли число, и идёт по
последовательностям вроде чисел Фибоначчи.
Каждая итерация смотрит на последнюю цифру и убирает её. Цифры выходят справа
налево, а цикл заканчивается, когда ничего не осталось: он выполняется по разу
на каждую цифру. Посмотрите, как он складывает цифры числа 3905:
Отщипываем цифры с помощью % 10 и / 10
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 int n;
9 cin >> n;
10 int sum = 0;
11 while (n > 0) {
12 sum += n % 10;
13 n /= 10;
14 }
15 cout << sum << "\n";
16 return 0;
17}
Читаем n
строка 9
n равно 3905.
ввод
3905
n3905sum—
нажми пуск
1 / 16
Цикл уничтожает n — в конце оно равно 0. Если число понадобится и после,
отщипывайте цифры от копии.
Считаем цифры
Прочитайте n (0 ≤ n ≤ 10¹⁸). Выведите сумму его цифр и сколько в нём цифр.
Ввод
Вывод
Правильность решают две детали:
do-while, а не while. У числа 0 одна цифра — 0. Цикл while (n > 0) для
него даже не начнётся и насчитает ноль цифр; do-while сначала выполнится один
раз.
long long n. 10¹⁸ не помещается в int.
Нули внутри числа — такие же цифры: в 90060 пять цифр, и цикл считает каждый из
трёх нулей.
У отрицательного числа те же цифры, что у его модуля, но % сохраняет знак:
-25 % 10 равно -5. Сначала возьмите n = abs(n).
Переворачиваем число
Каждую цифру, снятую с конца n, можно приписать в конец нового числа rev:
умножить rev на 10, чтобы освободить место, и прибавить цифру.
m
цифра
rev
1234
4
0 · 10 + 4 = 4
123
3
4 · 10 + 3 = 43
12
2
43 · 10 + 2 = 432
1
1
432 · 10 + 1 = 4321
Число — палиндром, если читается одинаково в обе стороны, как 12321, — то
есть если оно равно своему перевёрнутому:
Прочитайте n. Выведите его перевёрнутое число, а затем YES, если n —
палиндром, и NO, если нет.
Ввод
Вывод
Цикл работает с копией m, потому что сравнению в конце всё ещё нужно n. Нули
в конце при переворачивании исчезают: 120 перевёрнутое — это 21, — значит, 120
не палиндром, и это правильно.
Когда в числе фиксированное число цифр, цикл не нужен: трёхзначное n —
палиндром, если n / 100 == n % 10.
Теперь отщипайте цифры сами:
Отщипните цифрыпопробуй!
Делители
d делит n, если n % d == 0. Чтобы найти все делители, переберите каждое d
от 1 до n:
Со счётчиком и накопителем внутри if тот же цикл считает делители и
складывает их:
Число совершенное, если оно равно сумме своих делителей, меньших его самого:
6 = 1 + 2 + 3. Прочитайте n и выведите эту сумму, а затем YES, если n —
совершенное, и NO, если нет.
Ввод
Вывод
У 28 делители меньше него — 1, 2, 4, 7 и 14, и в сумме они дают 28.
Простое число имеет ровно два делителя: 1 и само себя; 1 — не простое. Значит,
n простое, если его не делит ни одно d от 2 до n - 1, — и поиск можно
остановить на первом, которое делит:
Почему можно остановиться на d * d <= n? Если n = a · b, то меньшее из a и
b не больше √n, поэтому делитель, если он есть, обнаружится к этому моменту.
Для n до 10⁵ хватает и цикла до n; для 10¹² — только цикла до √n: миллион
шагов вместо триллиона.
Наибольший общий делитель
НОД двух чисел — наибольшее число, которое делит оба. Евклид заметил, что он
не меняется, если большее число заменить остатком: gcd(a, b) = gcd(b, a % b).
Повторяйте, пока остаток не станет 0:
Прочитайте a и b и выведите их наибольший общий делитель.
Ввод
Вывод
Для 84 и 36: 84 % 36 = 12, затем 36 % 12 = 0, поэтому НОД равен 12. Числа
уменьшаются быстро — меньше сотни шагов даже около 10¹⁸.
Два числа взаимно просты, если их НОД равен 1. Их наименьшее общее
кратное — это a / gcd · b: сначала делим, чтобы произведение не переполнилось.
Идём по последовательности
Многие циклы вместо счётчика несут вперёд одно-два значения.
Удвоение. Степени двойки меньше X: начните с 1 и удваивайте, пока число ещё
меньше X:
Для X до 10⁹ он выполняется всего около 30 раз — удвоение растёт быстро.
Обратный вопрос, является ли x степенью двойки?, решается делением пополам:
делите на 2, пока x чётное; x было степенью двойки ровно тогда, когда
осталась 1.
По два сразу. Каждое число Фибоначчи — сумма двух предыдущих:
0, 1, 1, 2, 3, 5, 8, 13, … Храните последние два, a и b, и сдвигайте оба на
одно место вперёд:
Порядок важен: c хранит новое число, пока a и b сдвигаются. Если написать
a = b; b = a + b;, к b прибавится уже новое a, и все числа после первых
нескольких окажутся неверными.
Проверьте себя
5
78 92 85 100 64
419 2
83.80
А вы знали?
Говорят, юному Карлу Фридриху Гауссу учитель велел сложить числа от 1 до 100, а
он почти сразу назвал ответ: 50 пар — 1 + 100, 2 + 99, … — каждая по 101, значит,
5050. Цикл складывает их по одному — сто сложений; формуле Гаусса,
n · (n + 1) / 2, хватает одного. Для n ≤ 10⁵ в задачах этой недели и то, и
другое работает мгновенно.
А вы знали?
Евклид описал свой способ находить наибольший общий делитель в «Началах» около
300 года до нашей эры. Его часто называют старейшим алгоритмом, который до сих
пор используется каждый день: тот же цикл работает в каждом компьютере, который
шифрует сообщения, — с числами из сотен цифр.
int n;cin >> n;for(int i = 0; i < n; i++){ int x; cin >> x; // следующее число // ... используем x ...}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; long long sum = 0; // накопитель начинается с 0 int top = 0; // счётчик тоже начинается с 0 for(int i = 0; i < n; i++){ int x; cin >> x; // по одной оценке: хранить все не нужно sum += x; if(x >= 90){ top++;}} cout << sum << " "<< top << "\n"; cout << fixed << setprecision(2)<<(double)sum / n << "\n"; return 0;}
long long f = 1;for(int i = 1; i <= n; i++){ f *= i;}
проверь себя1 балл
Ввод — 4 7 0 3 0. Что напечатает этот код?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Числа даны до 0: 5 3 4 1 1 2 0. Сколько из них меньше числа прямо перед ними?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Сколько раз выполнится тело цикла while (n > 0) { n /= 10; }, если n равно 70500?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Цикл while (n > 0), который считает цифры n, для n = 0 насчитает одну цифру.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Цикл rev = rev * 10 + m % 10; m /= 10; выполняется, пока m > 0, начиная с m = 4070 и rev = 0. Чему равно rev в конце?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Какие значения d перебирает for (int d = 2; d * d <= n; d++), когда n равно 50?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Начиная с a = 0, b = 1, пять раз выполняется a = b; b = a + b;. Чему равно b в конце?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Цикл умножает p на каждое из n чисел. С какого значения должно начинаться p?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Ввод — 4 5 6. Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Программа начинает с mx = 0 и для каждого числа делает mx = max(mx, x). Числа — -5 -2 -9. Что она напечатает как максимум?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
6
-3 -8 2 -1 5 -4
-8 5
7 4 -6 3 10 0
3 8
3 5 5 2 8 9 1 0
3
90060
15 5
12321
12321
YES
28
28
YES
84 36
12
long long p = 1, sum = 1; // a^0 = 1 уже в суммеfor(int k = 1; k <= n; k++){ p *= a; // теперь p — это a^k sum += p;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int x; cin >> x; int mn = x, mx = x; // первое показание — пока и самое холодное, и самое тёплое for(int i = 1; i < n; i++){ // остальные n - 1 показаний cin >> x; mn = min(mn, x); mx = max(mx, x);} cout << mn << " "<< mx << "\n"; return 0;}
if(x > mx){ mx = x; pos = i; // i считается с 1}
if(x > mx){ mx = x; cnt = 1; // новый максимум: пока встретился один раз} else if(x == mx){ cnt++; // тот же максимум ещё раз}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int x, count = 0; long long sum = 0; while(cin >> x && x != 0){ // останавливаемся на 0: он не входит в список if(x % 2 == 0){ count++; sum += x;}} cout << count << " "<< sum << "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int prev, x, rises = 0; cin >> prev; // перед первым числом ничего нет while(cin >> x && x != 0){ if(x > prev){ rises++;} prev = x; // x становится «предыдущим» для следующего числа} cout << rises << "\n"; return 0;}
while(n > 0){ int d = n % 10; // последняя цифра // ... используем d ... n /= 10; // отбрасываем её}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long n; cin >> n; int sum = 0, count = 0; do{ sum += n % 10; // последняя цифра count++; n /= 10; // отбрасываем её} while(n > 0); // do-while: у 0 тоже одна цифра cout << sum << " "<< count << "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long n; cin >> n; long long m = n, rev = 0; // работаем с копией: n понадобится в конце while(m > 0){ rev = rev * 10 + m % 10; // последняя цифра m приписывается в конец rev m /= 10;} cout << rev << "\n"; cout <<(rev == n ? "YES" : "NO")<< "\n"; return 0;}
for(int d = 1; d <= n; d++){ if(n % d == 0){ cout << d << "\n";}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; long long sum = 0; for(int d = 1; d < n; d++){ // каждый кандидат меньше n if(n % d == 0){ sum += d;}} cout << sum << "\n"; cout <<(sum == n ? "YES" : "NO")<< "\n"; return 0;}
bool prime =(n >= 2);for(int d = 2; d * d <= n; d++){ if(n % d == 0){ prime = false; break;}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long a, b; cin >> a >> b; while(b != 0){ long long r = a % b; // gcd(a, b) = gcd(b, a % b) a = b; b = r;} cout << a << "\n"; return 0;}
long long p = 1;while(p < X){ cout << p << " "; p *= 2;}
long long a = 0, b = 1; // F(0) и F(1)for(int i = 0; i < n; i++){ long long c = a + b; a = b; b = c;}// теперь a — это F(n)
int x, count = 0;while(cin >> x && x != 0){ count++;}cout << count;
for(int i = 0; i < 3; i++){ int sum = 0; int x; cin >> x; sum += x; cout << sum << " ";}
