Counters, Accumulators and Digit Processing - Забони барномасозии C++ барои барномасозии рақобатӣ
Week 3Loops, Counters and Accumulators, Digit Processing
Counters, Accumulators and Digit Processing
Reading n numbers one at a time: counting, adding and multiplying as they arrive, the smallest and the largest, input that ends with a zero, the number before. Then one number taken apart with % 10 and / 10: digit sums and counts, reversing, palindromes, divisors, primes, the gcd, powers of two and Fibonacci numbers.
Назария
Дарси 3 аз 6
Хониш: 35 дақиқа
Саволҳо: 10
Most loop problems read a list of numbers and want one answer about it: the
total, how many of them are even, the biggest one. The second half of this
lesson turns the same loops on a single number and takes it apart digit by
digit. The numbers don't have to be
kept — arrays come next week. A loop reads them one at a time, and a few
variables remember what matters about the numbers seen so far.
Reading n numbers
The input often starts with how many numbers follow:
Each iteration reads one number into x, uses it, and lets it go: on the next
iteration x holds the next number. cin doesn't care whether the numbers stand
on one line or on several.
Counters and accumulators
A counter counts how many times something happened: it starts at 0 and goes
up by one each time. An accumulator collects a total: it starts at 0 and
each number is added to it.
Read n marks. Print their sum and how many of them are 90 or more, and on
the next line their average with two digits after the point.
Input
Output
Where each line goes is the heart of every counter and accumulator:
Three things to notice:
Both start at 0, before the loop. Declared inside the loop, they would
start again from 0 on every iteration.
The sum is a long long. A hundred thousand numbers of up to 10⁹ add up
to 10¹⁴ — far more than an int holds (Week 1).
The average needs a double: sum / n alone is integer division, and
(double)sum / n is not.
The same pattern counts and adds anything: the positive numbers, the numbers
equal to x, the multiples of 3 in a range. Only the if changes.
A product works the same way, but starts at 1 — starting at 0, it would
stay 0 forever. n! is 1 · 2 · … · n:
20! is about 2.4 · 10¹⁸ and still fits in a long long; 21! doesn't.
The same goes for a running power: p starts at 1 and becomes a, a², a³, …
one multiplication per iteration — no pow, and no rounding:
навбатӣ
Practice: Counters and Accumulators
Sums, counts, minimums and maximums over a list of numbers read one at a time.
That sums 1 + a + a² + … + aⁿ. The multiplication comes first, so the loop
never computes aⁿ⁺¹, a power nobody asked for that could overflow. To alternate the signs, 1 − a + a² − …, keep a
sign that starts at 1 and becomes -sign after each term.
The smallest and the largest
To find the maximum, keep the largest number seen so far in mx, and let every
new number challenge it: mx = max(mx, x). The whole question is what mx
starts as.
Read n temperatures, which can be below zero. Print the coldest and the
warmest.
Input
Output
The first reading is read before the loop and becomes both mn and mx: it
is the coldest and the warmest of the readings seen so far. The loop then reads
the other n - 1. Step through it:
The coldest and the warmest, kept up to date
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}
Read n
сатр 9
4 readings are coming.
вуруд
4
-3
-8
2
-1
n4x—mn—mx—i—
пахш кун
1 / 21
Starting mx = 0 is the classic mistake: for a week that never got above zero
it prints 0, a temperature that never happened. Starting from the first number
is always safe. (The other safe start is a value below every possible input,
such as -2000000000 when the numbers are at least −10⁹.)
To remember where the best number was, keep its position too, and update it
in the same if as the value:
With >, the first of several equal maxima is kept; with >=, the last.
To count how many times the maximum occurs, a counter goes with it: a new,
bigger maximum starts the count again from 1, and an equal one adds to it.
Until a zero
Sometimes the input doesn't say how many numbers there are. Instead, a special
value marks the end — often a 0 that isn't one of the numbers:
Numbers are given until a 0. Print how many of them are even, and their sum.
Input
Output
while (cin >> x && x != 0) reads a number and checks it in one go: the loop
stops at the 0 and never counts it. (cin >> x is false when the input runs
out, so the loop is safe even without the 0.)
Remembering the one before
Some answers depend on two neighbours: is this number bigger than the previous
one? Keep the previous number in a variable, and update it at the end of
each iteration:
Numbers are given until a 0. Print how many of them are bigger than the
number just before them.
Input
Output
For 3 5 5 2 8 9 1, the numbers bigger than the one before are 5, 8 and 9: 3.
prev = x comes last: while the if runs, prev must still be the old number.
Now you are the loop. Keep the variables up to date as the numbers arrive:
Be the accumulatorсанҷида бин!
Peeling off the digits
In Week 1, % 10 gave the last digit of a number and / 10 dropped it. With a
loop, those two operations take a number apart digit by digit, however many
digits it has. The same kind of loop finds divisors, tests whether a number is
prime and walks along sequences such as the Fibonacci numbers.
Each iteration looks at the last digit and then removes it. The digits come out
from right to left, and the loop ends when nothing is left: it runs once per
digit. Watch it add up the digits of 3905:
Peeling the digits off with % 10 and / 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}
Read n
сатр 9
n is 3905.
вуруд
3905
n3905sum—
пахш кун
1 / 16
The loop destroys n — at the end it is 0. If the number is still needed
afterwards, peel the digits off a copy.
Counting the digits
Read n (0 ≤ n ≤ 10¹⁸). Print the sum of its digits and how many digits it
has.
Input
Output
Two details decide whether this is right:
do-while, not while. The number 0 has one digit, 0. A while (n > 0)
loop would never start for it and report no digits; a do-while runs once
first.
long long n. 10¹⁸ doesn't fit in an int.
Zeros inside the number are digits like any other: 90060 has five digits, and
the loop counts each of its three zeros.
A negative number has the same digits as its absolute value, but % keeps
the sign: -25 % 10 is -5. Take n = abs(n) first.
Reversing a number
Every digit that comes off the end of n can be stuck onto the end of a new
number rev: multiply rev by 10 to make room, then add the digit.
m
digit
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
A number is a palindrome when it reads the same both ways, like 12321 —
that is, when it equals its reverse:
Read n. Print its reverse, and YES if n is a palindrome, NO if not.
Input
Output
The loop works on the copy m, because the comparison at the end still needs
n. Trailing zeros vanish in the reverse: 120 reversed is 21 — so 120 is not a
palindrome, which is right.
When a number has a fixed number of digits, the loop isn't needed: a three-digit
n is a palindrome when n / 100 == n % 10.
Now peel some digits yourself:
Peel the digitsсанҷида бин!
Divisors
d divides n when n % d == 0. To find all the divisors, try every d from 1
to n:
With a counter and an accumulator in the if, the same loop counts the
divisors and adds them up:
A number is perfect when it equals the sum of its divisors smaller than
itself: 6 = 1 + 2 + 3. Read n and print that sum, then YES if n is
perfect and NO if not.
Input
Output
For 28 the divisors below it are 1, 2, 4, 7 and 14, which add up to 28.
A prime number has exactly two divisors, 1 and itself; 1 is not prime. So
n is prime when no d from 2 to n - 1 divides it — and the search can stop at
the first one that does:
Why stop at d * d <= n? If n = a · b, the smaller of a and b is at most
√n, so a divisor, if there is one, shows up by then. For n up to 10⁵ a loop to
n is fast enough too; for 10¹² only the √n loop is — a million steps instead
of a trillion.
The greatest common divisor
The gcd of two numbers is the largest number that divides both. Euclid
noticed that it doesn't change when the larger number is replaced by its
remainder: gcd(a, b) = gcd(b, a % b). Repeat until the remainder is 0:
Read a and b and print their greatest common divisor.
Input
Output
For 84 and 36: 84 % 36 = 12, then 36 % 12 = 0, so the gcd is 12. The numbers
shrink fast — fewer than a hundred steps even near 10¹⁸.
Two numbers are coprime when their gcd is 1. Their least common multiple
is a / gcd · b — divide first, so the product doesn't overflow.
Walking along a sequence
Many loops carry one or two values forward instead of a counter.
Doubling. Powers of 2 below X: start at 1 and double while the number is
still below X:
It runs only about 30 times for X up to 10⁹ — doubling gets big fast. The
reverse question, is x a power of 2?, halves instead: divide by 2 while x
is even; x was a power of 2 exactly when 1 is left.
Two at a time. Each Fibonacci number is the sum of the two before it:
0, 1, 1, 2, 3, 5, 8, 13, … Keep the last two, a and b, and move both one
place forward:
The order matters: c keeps the new number while a and b move up. Writing
a = b; b = a + b; would add the new a to b, and every number after the
first few would be wrong.
Check your understanding
5
78 92 85 100 64
419 2
83.80
Did you know?
As the story goes, the young Carl Friedrich Gauss was told by his teacher to add
up the numbers from 1 to 100, and had the answer almost at once: 50 pairs —
1 + 100, 2 + 99, … — each making 101, so 5050. A loop adds them one by one, a
hundred additions; Gauss's formula, n · (n + 1) / 2, needs one. For the
n ≤ 10⁵ of this week's problems, both are instant.
Did you know?
Euclid wrote his method for the greatest common divisor in the Elements,
around 300 BC. It is often called the oldest algorithm still in everyday use:
the same loop runs inside every computer that encrypts a message today, with
numbers hundreds of digits long.
int n;cin >> n;for(int i = 0; i < n; i++){ int x; cin >> x; // the next number // ... use x here ...}
#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; // an accumulator starts at 0 int top = 0; // a counter starts at 0 too for(int i = 0; i < n; i++){ int x; cin >> x; // one mark at a time: no need to keep them all 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 хол
The input is 4 7 0 3 0. What does this print?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
Numbers are given until a 0: 5 3 4 1 1 2 0. How many of them are smaller than the number just before them?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
How many times does the body of while (n > 0) { n /= 10; } run when n is 70500?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
A while (n > 0) loop that counts the digits of n reports one digit for n = 0.
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
The loop rev = rev * 10 + m % 10; m /= 10; runs while m > 0, starting from m = 4070 and rev = 0. What is rev at the end?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
Which values of d does for (int d = 2; d * d <= n; d++) try when n is 50?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
Starting from a = 0, b = 1, this runs five times: a = b; b = a + b;. What is b at the end?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
A loop multiplies p by each of n numbers. What should p start as?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
The input is 4 5 6. What does this print?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
A program starts with mx = 0 and does mx = max(mx, x) for each number. The numbers are -5 -2 -9. What does it print as the maximum?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
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 is already in the sumfor(int k = 1; k <= n; k++){ p *= a; // now p is 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; // the first reading is the coldest and warmest so far for(int i = 1; i < n; i++){ // the other n - 1 readings cin >> x; mn = min(mn, x); mx = max(mx, x);} cout << mn << " "<< mx << "\n"; return 0;}
if(x > mx){ mx = x; pos = i; // i counts from 1}
if(x > mx){ mx = x; cnt = 1; // a new maximum: seen once so far} else if(x == mx){ cnt++; // the same maximum again}
#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){ // stop at the 0: it is not a number of the list 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; // the first number has nothing before it while(cin >> x && x != 0){ if(x > prev){ rises++;} prev = x; // x becomes "the one before" for the next number} cout << rises << "\n"; return 0;}
while(n > 0){ int d = n % 10; // the last digit // ... use d ... n /= 10; // drop it}
#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; // the last digit count++; n /= 10; // drop it} while(n > 0); // do-while: 0 still has one digit 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; // work on a copy: n is needed at the end while(m > 0){ rev = rev * 10 + m % 10; // the last digit of m goes to the end of 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++){ // every candidate below 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) and F(1)for(int i = 0; i < n; i++){ long long c = a + b; a = b; b = c;}// now a is 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 << " ";}
