Урок №6 Поиск min/max и делителей

Теория:

IПоиск min/max

Рассмотрим самую популярную задачу на обработку чисел: поиск минимума или максимума среди них.

Алгоритм поиска

Чтобы найти наибольшее число среди введённых, необходимо создать специальную переменную, которая будет хранить в себе максимальное число. Данная переменная изначально должна быть заведомо меньше всех исследуемых чисел.

Затем необходимо перебрать все исследуемые числа и сравнить с созданной переменной. Если очередное число меньше того, которое записано на текущий момент, как максимальное, идём дальше. Если же очередное число окажется больше, то записываем его в переменную, хранящую максимальное число, то есть обновляем эту переменную.

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

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

Начальное значение специальной переменной

Начальное значение специальной переменной крайне важно. От него зависит, будет ли программа работать корректно.

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

Если мы знаем область поиска, то ситуация будет проще. Например, если необходимо найти минимальное число от 1 до 100 включительно, которое удовлетворяет специальным условиям, можно просто положить в качестве начального значения специальной переменной, отвечающей за максимальное число, 101. В таком случае, специальная переменная также гарантированно обновится, а значит и эта программа будет работать корректно.

Но иногда не ясно, в каком интервале будут исследуемые числа, поэтому невозможно выбрать число, которое заведомо больше или меньше всех исследуемых. В таком случае в качестве первоначального значения обоих специальных переменных кладут первое исследуемое число. Тогда либо специальная переменная обновится и в конце будет содержать необходимое значение, либо не обновится. Второй случай будет означать, что необходимым числом было самое первое число.

Код

Давайте же наконец рассмотрим код, определяющий максимальное число среди пяти введённых с клавиатуры:

int max = 0; // создаём специальную переменную
int x = 0; // создаём скользящую переменную
for (int i = 0; i < 5; i++){ // создаём цикл for
    if (scanf("%d", &x) != 1){ // безопасное считывание
        printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
        return -1; // возвращаем -1, если не установлен другой код ошибки чтения
    }
    if (x > max){ // если очередное число больше специальной переменной
        max = x; // обновляем значение специальной переменной
    } 
}

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

Однако если все введённые числа будут строго отрицательными, специальная переменная так и останется нулём, вместо того, чтобы принять значение наибольшего из введённых чисел. Как уже было сказано, необходимо положить в специальную переменную значение самого первого введённого числа. Но как определить это в программе?

Заметим, что все введённые числа индексируются циклом for, поэтому каждому очередному введённому числу будет соответствовать уникальное значение индекса цикла for. Самому первому числу соответствует нулевое значение индекса, поэтому в цикл for необходимо добавить соответствующее условие (8-10 строки):

int max = 0; // создаём специальную переменную
int x = 0; // создаём скользящую переменную
for (int i = 0; i < 5; i++){ // создаём цикл for
    if (scanf("%d", &x) != 1){ // безопасное считывание
        printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
        return -1; // возвращаем -1, если не установлен другой код ошибки чтения
    }
    if (i == 0){ // если значение индекса 0 - это самое первое введённое число 
        max = x; // обновляем значение специальной переменной
    }
    if (x > max){ // если очередное число больше специальной переменной
        max = x; // обновляем значение специальной переменной
    } 
}
Оптимизация

Можно заметить, что обновление специальной переменной происходит или когда индекс равен нулю или когда найдено очередное число, которое больше, чем сама специальная переменная. В целях оптимизации и экономии кода можно объединить эти два условия в один цикл if (8-10 строки):

int max = 0; // создаём специальную переменную
int x = 0; // создаём скользящую переменную
for (int i = 0; i < 5; i++){ // создаём цикл for
    if (scanf("%d", &x) != 1){ // безопасное считывание
        printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
        return -1; // возвращаем -1, если не установлен другой код ошибки чтения
    }
    if (x > max || i == 0){ // если очередное число больше специальной переменной или значение индекса равно нулю
        max = x; // обновляем значение специальной переменной
    } 
}

IIПоиск представителя

Иногда необходимо найти не максимальное или минимальное число, а представителя этого минимального или максимального числа.

Постановка задачи

Допустим, необходимо найти на каком натуральном числе от 0 до 10 включительно принимает наименьшее значение функция:

3x^3-x^2+2x-4

В данной задаче очевидно будет неверным предоставить в качестве ответа само наименьшее значение. Для того, чтобы выписать то число, на котором принимается наименьшее значение, конечно, можно составить обратную функцию и по значению вычислить аргумент, но бывают ситуации, когда сделать это не только затруднительно, но и невозможно. Так как же быть в таких случаях?

Ответ прост: давайте будем хранить представителя максимального или минимального значения в отдельной отведённой исключительно для этого самого представителя переменной.

Код

Напишем код, ищущий наименьшее значение функции из примера выше среди натуральных чисел от 0 до 10 включительно:

int min = 0; // создаём специальную переменную
int y = 0; // создаём переменную для хранения значений функции
for (int x = 0; x <= 10; x++){ // создаём цикл for
    y = 3 * x * x * x - x * x + 2 * x - 4; // вычисляем значение функции
    if (y < min || x == 0){ // если очередное число больше специальной переменной или значение индекса равно нулю
        min = y; // обновляем значение специальной переменной
    } 
}

Добавим в код хранение переменной представителя: числа, для которого значение функции на нём будет минимальным (3 и 8 строки):

int min = 0; // создаём специальную переменную
int y = 0; // создаём переменную для хранения значений функции
int x_min = 0; // создаём переменную для хранения представителя
for (int x = 0; x <= 10; x++){ // создаём цикл for
    y = 3 * x * x * x - x * x + 2 * x - 4; // вычисляем значение функции
    if (y < min || x == 0){ // если очередное число больше специальной переменной или значение индекса равно нулю
        min = y; // обновляем значение специальной переменной
        x_min = x; // обновляем значение переменной представителя
    }
}

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

IIIПоиск делителей

Рассмотрим очень популярную среди математиков задачу: поиск делителей числа.

Делителем числа называется число, которое делит исходное число без остатка.

Для этого сначала разберёмся, как найти все делители некоторого числа. Самая логичная мысль: пробежаться по всем числам от 1 до этого числа включительно и проверить, делят ли они это число. И это один из самых распространённых способов. Реализуем его:

int y = 80; // создаём переменную для хранения числа, делители которого нужно выписать на экран
for (int d = 1; d <= y; d++){ // создаём цикл for
    if (y % d == 0){ // если очередной кандидат на делитель делит исследуемое число без остатка
        printf("%d ", d); // выписываем значение очередного кандидата на экран и ставим после пробел
    }
}

После запуска данного кода в командной строке будут выписаны все делители числа 80 через пробел:

1 2 4 5 8 10 16 20 40 80
Process returned 0 (0x0)   execution time : 0.008 s
Press any key to continue.

IVПодсчёт количества делителей

Довольно часто требуется посчитать количество делителей.

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

Реализуем это в коде:

int y = 80; // создаём переменную для хранения числа, количество делителей которого нужно посчитать
int count = 0; // создаём переменную-счётчик для хранения количества делителей
for (int d = 1; d <= y; d++){ // создаём цикл for
    if (y % d == 0){ // если очередной кандидат на делитель делит исследуемое число без остатка
        count++; // увеличиваем значение переменной-счётчика на единицу
    }
}
printf("%d\n", count); // выписываем значение переменной-счётчика на экран

После запуска данного кода в командной строке будет выписано количество всех делителей числа 80:

10

Process returned 0 (0x0)   execution time : 0.008 s
Press any key to continue.

Практика

1Задача №1.

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

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int max = 0; // создаём специальную переменную
    int x = 0; // создаём скользящую переменную
    printf("Print 5 numbers: "); // приглашаем пользователя на ввод
    for (int i = 0; i < 5; i++){ // создаём цикл for
        if (scanf("%d", &x) != 1){ // безопасное считывание
            printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
            return -1; // возвращаем -1, если не установлен другой код ошибки чтения
        }
        if (x > max || i == 0){ // если очередное число больше специальной переменной или значение индекса равно нулю
            max = x; // обновляем значение специальной переменной
        }
    }
    printf("%d\n", max);// выводим ответ на экран
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 5 numbers: 12 17 28 -10 20
28

Process returned 0 (0x0)   execution time : 9.299 s
Press any key to continue.

2Задача №2.

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

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int x = 0; // создаём скользящую переменную
    printf("Print 3 numbers: "); // приглашаем пользователя на ввод
    for (int i = 0; i < 3; i++){ // создаём цикл for
        if (scanf("%d", &x) != 1){ // безопасное считывание
            printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
            return -1; // возвращаем -1, если не установлен другой код ошибки чтения
        }
        for (int d = 1; d <= x; d++){ // создаём цикл for
            if (x % d == 0){ // если очередной кандидат на делитель делит исследуемое число без остатка
                printf("%d ", d); // выписываем значение очередного кандидата на экран и ставим после пробел
            }
        }
        printf("\n"); // сносим курсор на строку вниз для красивого вывода
    }
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 3 numbers: 10 24 30
1 2 5 10
1 2 3 4 6 8 12 24
1 2 3 5 6 10 15 30

Process returned 0 (0x0)   execution time : 3.695 s
Press any key to continue.

Домашнее задание:

1Задача №1.

Среди семи введённых пользователем целых чисел найти минимальное чётное число.

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int min = 0; // создаём специальную переменную
    int x = 0; // создаём скользящую переменную
    printf("Print 7 numbers: "); // приглашаем пользователя на ввод
    for (int i = 0; i < 7; i++){ // создаём цикл for
        if (scanf("%d", &x) != 1){ // безопасное считывание
            printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
            return -1; // возвращаем -1, если не установлен другой код ошибки чтения
        }
        if ((x < min && x % 2 == 0) || i == 0){ // если очередное число меньше специальной переменной и чётное или значение индекса равно нулю
            min = x; // обновляем значение специальной переменной
        }
    }
    printf("min: %d\n", min);// выводим ответ на экран
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 7 numbers: 12 10 -23 11 90 87 56
min: 10

Process returned 0 (0x0)   execution time : 10.131 s
Press any key to continue.
Обратите внимание, что скобки внутри условия главного цикла if необязательно, но всегда лучше перестраховаться, потому что в дальнейшем нас ждут огромные программы длинной до 1000 строк, искать оплошности с условиями в циклах if среди которых будет очень затруднительно.

2Задача №2.

Среди восьми введённых пользователем целых чисел найти число, имеющее максимальную последнюю цифру.

Не забудьте, что для вычисления последней цифры числа достаточно просто взять остаток от модуля этого числа при делении на 10.
Необходимо брать остаток при делении на 10 именно от модуля, потому что, например, остаток от числа -22 будет равен -2, а не просто 2.
Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h
#include <math.h> // подключаем библиотеку math.h

int main() { //создаём главную функцию
    int x = 0; // создаём скользящую переменную
    int max = 0; // создаём специальную переменную
    int x_max = 0; // создаём переменную для хранения представителя
    printf("Print 8 numbers: "); // приглашаем пользователя на ввод
    for (int i = 0; i < 8; i++){ // создаём цикл for
        if (scanf("%d", &x) != 1){ // безопасное считывание
            printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
            return -1; // возвращаем -1, если не установлен другой код ошибки чтения
        }
        if (abs(x % 10) > max){ // если последняя цифра очередного числа больше специальной переменной
            max = x % 10; // обновляем значение специальной переменной
            x_max = x; // сохраняем представителя
        }
    }
    printf("The max last digit has %d\n", x_max);// выводим ответ на экран
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 8 numbers: 12 21 -13 89 36 77 24 55
The max last digit has 89

Process returned 0 (0x0)   execution time : 15.177 s
Press any key to continue.
Обратите внимание, что скобки внутри условия главного цикла if необязательно, но всегда лучше перестраховаться, потому что в дальнейшем нас ждут огромные программы длинной до 1000 строк, искать оплошности с условиями в циклах if среди которых будет очень затруднительно.

3Задача №3.

Среди десяти введённых пользователем целых чисел найти число, имеющее максимальную сумму двух последних цифр, и саму максимальную сумму. В случае если число состоит менее чем из двух цифр, считать недостающие цифры нулями.

Не забудьте, что для получения доступа к второй с конца цифре необходимо разделить модуль числа на 10, а потом уже взять от результата остаток при делении на 10.
Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h
#include <math.h> // подключаем библиотеку math.h

int main() { //создаём главную функцию
    int x = 0; // создаём скользящую переменную
    int max = 0; // создаём специальную переменную
    int x_max = 0; // создаём переменную для хранения представителя
    int sum = 0; // создаём переменную для хранения суммы двух последних цифр
    printf("Print 10 numbers: "); // приглашаем пользователя на ввод
    for (int i = 0; i < 10; i++){ // создаём цикл for
        if (scanf("%d", &x) != 1){ // безопасное считывание
            printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
            return -1; // возвращаем -1, если не установлен другой код ошибки чтения
        }
        sum = (abs(x) / 10) % 10 + abs(x) % 10; // вычисляем сумму двух последних цифр
        if (sum > max){ // если сумма последних двух цифр очередного числа больше специальной переменной
            max = sum; // обновляем значение специальной переменной
            x_max = x; // сохраняем представителя
        }
    }
    printf("The max sum of 2 last digits (%d) has %d\n", max, x_max);// выводим ответ на экран
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 10 numbers: 123 239 1299 1289 -1329 23 0 8 1 23
The max sum of 2 last digits (18) has 1299

Process returned 0 (0x0)   execution time : 19.372 s
Press any key to continue.
Обратите внимание, что скобки внутри условия главного цикла if необязательно, но всегда лучше перестраховаться, потому что в дальнейшем нас ждут огромные программы длинной до 1000 строк, искать оплошности с условиями в циклах if среди которых будет очень затруднительно.

4Задача №4.

Выписать на экран отчёт о том, какие делители есть у чисел от 1 до 30 включительно.

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    for (int x = 1; x <= 30; x++){ // создаём цикл for
        printf("%d: ", x); // выписываем число, делители которого будут выписаны после
        for (int d = 1; d <= x; d++){ // создаём цикл for по кандидатам в делители
            if (x % d == 0){ // проверяем, является ли кандидат дилителем
                printf("%d ", d); // выписываем, если является
            }
        }
        printf("\n"); // сносим курсор на строку вниз для красивого вывода
    }
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
1: 1
2: 1 2
3: 1 3
4: 1 2 4
5: 1 5
6: 1 2 3 6
7: 1 7
8: 1 2 4 8
9: 1 3 9
10: 1 2 5 10
11: 1 11
12: 1 2 3 4 6 12
13: 1 13
14: 1 2 7 14
15: 1 3 5 15
16: 1 2 4 8 16
17: 1 17
18: 1 2 3 6 9 18
19: 1 19
20: 1 2 4 5 10 20
21: 1 3 7 21
22: 1 2 11 22
23: 1 23
24: 1 2 3 4 6 8 12 24
25: 1 5 25
26: 1 2 13 26
27: 1 3 9 27
28: 1 2 4 7 14 28
29: 1 29
30: 1 2 3 5 6 10 15 30

Process returned 0 (0x0)   execution time : 0.015 s
Press any key to continue.

5Задача №5.

Найти, какое число от 1 до 100 имеет больше всего различных натуральных делителей, кроме единицы и самого себя. Выписать на экран это число, всех его делителей и их количество.

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int count = 0; // создаём переменную-счётчик для подсчёта делителей
    int max_count = 0; // создаём специальную переменную
    int x_max = 0; // создаём переменную для хранения представителя
    for (int x = 1; x <= 100; x++){ // создаём цикл for
        count = 0; // обнуляем счётчик делителей, чтобы считать каждый раз снова с нуля
        for (int d = 2; d < x; d++){ // создаём цикл for по кандидатам в делители
            if (x % d == 0){ // проверяем, является ли кандидат делителем
                count++; // увеличиваем переменную-счётчик
            }
        }
        if (count > max_count){ // если количество делителей для очередного числа больше, чем значение специальной переменной
            max_count = count; // обновляем специальную переменную
            x_max = x; // запоминаем представителя
        }
    }
    printf("The number has the most divisors (%d) is %d: ", max_count, x_max); // выписываем ответ
    for (int d = 2; d < x_max; d++){ // создаём цикл for, так как необходимо также выписать делителей
        if (x_max % d == 0){ // проверяем, является ли кандидат делителем
            printf("%d ", d);
        }
    }
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
The number has the most divisors (10) is 60: 2 3 4 5 6 10 12 15 20 30
Process returned 0 (0x0)   execution time : 0.005 s
Press any key to continue.

6Задача №6.

Найти максимальный натуральный делитель введённого пользователем числа, кроме самого числа. Выписать этот делитель на экран.

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int x = 0; // создаём пользовательскую переменную
    int d_max = 0; // создаём переменную для хранения максимального делителя
    printf("Print 1 number: "); // приглашаем пользователя на ввод
    if (scanf("%d", &x) != 1){ // безопасное считывание
        printf("Reading error.\n"); // уведомляем пользователя об ошибке чтения в случае некорректного считывания
        return -1; // возвращаем -1, если не установлен другой код ошибки чтения
    }
    for (int d = 1; d < x; d++){ // создаём цикл for
        if (x % d == 0){ // проверяем, является ли кандидат делителем
            d_max = d; // сохраняем делитель
        }
    }
    printf("The most divisor which %d has is %d\т", x, d_max); // выписываем ответ
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
Print 1 number: 1245
The most divisor which 1245 has is 415

Process returned 0 (0x0)   execution time : 1.392 s
Press any key to continue.

7Задача №7.

Найти, какое число среди чисел от 1 до 999 имеет самый большой максимальный натуральный делитель, отличный от самого числа, и оканчивающийся той же цифрой, что и само число. Выписать это число и его делитель, удовлетворяющий условию задачи.

Решение:
#include <stdio.h> // подключаем библиотеку stdio.h
#include <stdlib.h> // подключаем библиотеку stdlib.h

int main() { //создаём главную функцию
    int d_max = 0; // создаём переменную для хранения максимального делителя
    int max_d_max = 0;  // создаём специальную переменную
    int x_max = 0; // создаём переменную для хранения представителя
    for (int x = 1; x < 1000; x++){ // создаём цикл for
        d_max = 0; // обнуляем переменную для хранения максимального делителя
        for (int d = 1; d < x; d++){ // создаём цикл for
            if (x % d == 0 && x % 10 == d % 10){ // проверяем, является ли кандидат делителем и имеет ли он ту же последнюю цифру
                d_max = d; // сохраняем делитель
            }
        }
        if (d_max > max_d_max){ // если максимальный делитель очередного числа больше значения специальной переменной
            max_d_max = d_max; // обновляем специальную переменную
            x_max = x; // запоминаем представителя
        }
    }
    printf("%d has the most divisor that has the same last number (%d)\n", x_max, max_d_max); // выписываем ответ
    return 0; // завершаем с кодом 0 - успех
}
Пример работы программы:
980 has the most divisor that has the same last number (490)

Process returned 0 (0x0)   execution time : 0.006 s
Press any key to continue.

8Задача №8*.

Пользователь вводит 10 натуральных чисел. Необходимо вывести такую сумму двух чисел среди введённых пользователем, что данная сумма максимальна и кратна трём. То есть среди 10 введённых чисел надо выбрать такие два, чтобы их сумма была максимально возможной и при этом была кратна трём.

Перед тем, как сверяться с решением, проверьте Вашу программу на числах: 12 9 10 18 40 21 11 18 50 15. Для них ответ — 90.
Решение:

Для достижения наилучшего результата и доступа ко всему курсу необходимо приобрести курс еженедельных индивидуальных или групповых занятий с преподавателем в режиме онлайн. Наши преподаватели обучат Вас создавать уникальные алгоритмы и самостоятельно реализовывать их в программном коде с соблюдением стандартов оформления.

Для записи на бесплатный пробный урок просто заполните форму ниже: