bulgakov

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

Сначала маленькая доска из двух строк и четырёх столбцов. Полная программа:

C
#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. Сколько раз выполнится печать клетки, а сколько — перевод строки?

Два счётчика и формула цвета
C
#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, как в предыдущем уроке. Знак в сумму не входит. Полная программа:

C
#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 встретилось раньше.

Храним победителя и его сумму
C
#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. Циклы вложены по выполнению, хотя текст внутреннего цикла вынесен в функцию.

Проверьте решение на десяти нулях, одинаковых суммах, отрицательных числах, победителе в начале и в конце. Отдельно проверьте ранний конец ввода: вместо найденного ответа должна быть ошибка.

ПрактикаЗагружаем тест…