30. Шахматная доска и максимум суммы цифр
Внешний цикл выбирает объект, внутренний обрабатывает его части. У доски это строка и клетки. У последовательности чисел — очередное число и его цифры. После урока 23 применим эту идею к двум задачам из Lesson-7.
Как получить чередование клеток
Нумеруем строки и столбцы с нуля. Чёрную клетку обозначим 0, белую — 1. В левом верхнем углу поставим 0.
При переходе к соседней клетке вправо или вниз сумма row + col увеличивается на единицу. Её чётность меняется. Поэтому цвет удобно вычислять как (row + col) % 2.
Строка row |
Столбец col |
Сумма | Цвет |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
2 |
0 |
Сначала маленькая доска из двух строк и четырёх столбцов. Полная программа:
#include <stdio.h>
int main(void)
{
for (int row = 0; row < 2; row++) {
for (int col = 0; col < 4; col++) {
printf("%d", (row + col) % 2);
}
printf("\n");
}
return 0;
}
Вывод:
0101
1010
Перевод строки находится после внутреннего цикла, но внутри внешнего. Поэтому одна готовая строка заканчивается одним переводом строки. col начинается с нуля при каждом новом входе во внутренний цикл.
Если вычислять только col % 2, все строки будут одинаковыми. Если переносить строку внутри внутреннего тела, каждая клетка окажется на отдельной строке.
Практика: шахматная доска 10 × 10
Напечатайте десять строк по десять цифр без пробелов. Соседи по горизонтали и вертикали должны различаться; первая клетка — 0. Сколько раз выполнится печать клетки, а сколько — перевод строки?
Два счётчика и формула цвета
#include <stdio.h>
int main(void)
{
for (int row = 0; row < 10; row++) {
for (int col = 0; col < 10; col++) {
printf("%d", (row + col) % 2);
}
printf("\n");
}
return 0;
}
Вывод:
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
Клетка печатается 10 × 10 = 100 раз. Перевод строки — 10 раз. Последние допустимые индексы: row = 9, col = 9. Индекс 10 уже не проходит условие.
Максимальное число и максимальная сумма цифр — разные задачи
Сравним 900 и 89. Само число 900 больше, но сумма его цифр равна 9, а у 89 — 17. Если задача спрашивает число с наибольшей суммой цифр, победитель — 89.
Нужно хранить две связанные величины:
best_number— само выбранное число, которое потом выведем;best_sum— сумму его цифр, по которой сравниваем кандидатов.
Сначала научимся находить сумму одного числа. В этой задаче работаем с входом от -9999 до 9999, как в предыдущем уроке. Знак в сумму не входит. Полная программа:
#include <stdio.h>
int digit_sum(int n)
{
int sum = 0;
while (n != 0) {
int digit = n % 10;
if (digit < 0) {
digit = -digit;
}
sum += digit;
n /= 10;
}
return sum;
}
int main(void)
{
printf("%d\n", digit_sum(900));
printf("%d\n", digit_sum(89));
printf("%d\n", digit_sum(-305));
printf("%d\n", digit_sum(0));
return 0;
}
Вывод:
9
17
8
0
У отрицательного числа остаток может быть отрицательным. Меняем знак только отдельной цифры: она лежит от -9 до 9, поэтому это безопасно. Исходный параметр постепенно делим на десять. Для нуля тело не выполняется, и начальная сумма 0 уже является правильным ответом.
Практика: найти число среди десяти
Прочитайте ровно десять целых чисел от -9999 до 9999. Выведите само число, сумма цифр которого максимальна. При равенстве сумм сохраните первое встретившееся число. Ноль здесь — обычный элемент, а не команда завершения.
Пример ввода:
900 89 98 -99 123 0 909 7 -18 10
Правильный вывод — -99. У него и у 909 сумма цифр равна 18, но -99 встретилось раньше.
Храним победителя и его сумму
#include <stdio.h>
int digit_sum(int n)
{
int sum = 0;
while (n != 0) {
int digit = n % 10;
if (digit < 0) {
digit = -digit;
}
sum += digit;
n /= 10;
}
return sum;
}
int main(void)
{
int best_number = 0;
int best_sum = -1;
for (int count = 0; count < 10; count++) {
int x;
if (scanf("%d", &x) != 1) {
printf("Input error\n");
return 1;
}
if (x < -9999 || x > 9999) {
printf("Out of range\n");
return 1;
}
int sum = digit_sum(x);
if (sum > best_sum) {
best_sum = sum;
best_number = x;
}
}
printf("%d\n", best_number);
return 0;
}
Сумма цифр неотрицательна, поэтому начальное best_sum = -1 гарантирует выбор первого успешно прочитанного числа. Даже если все десять чисел равны нулю, результат будет правильным.
best_number = 0 пока лишь начальное значение переменной. До итоговой печати обязательно пройдёт десять успешных чтений; при ошибке программа завершится раньше.
Обновляем обе переменные вместе. Условие sum > best_sum оставляет первого при равенстве. Если заменить его на sum >= best_sum, будет выбран последний кандидат с максимальной суммой.
Проследим начало примера:
| Очередное число | Сумма цифр | Выбранное число после сравнения | Лучшая сумма |
|---|---|---|---|
900 |
9 |
900 |
9 |
89 |
17 |
89 |
17 |
98 |
17 |
89 |
17 |
-99 |
18 |
-99 |
18 |
Остальные числа не улучшают результат. Внешний for делает десять проходов. На каждом вызов digit_sum запускает свой while. Циклы вложены по выполнению, хотя текст внутреннего цикла вынесен в функцию.
Проверьте решение на десяти нулях, одинаковых суммах, отрицательных числах, победителе в начале и в конце. Отдельно проверьте ранний конец ввода: вместо найденного ответа должна быть ошибка.
