Теория:
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.
Среди семи введённых пользователем целых чисел найти минимальное чётное число.
2Задача №2.
Среди восьми введённых пользователем целых чисел найти число, имеющее максимальную последнюю цифру.
3Задача №3.
Среди десяти введённых пользователем целых чисел найти число, имеющее максимальную сумму двух последних цифр, и саму максимальную сумму. В случае если число состоит менее чем из двух цифр, считать недостающие цифры нулями.
4Задача №4.
Выписать на экран отчёт о том, какие делители есть у чисел от 1 до 30 включительно.
5Задача №5.
Найти, какое число от 1 до 100 имеет больше всего различных натуральных делителей, кроме единицы и самого себя. Выписать на экран это число, всех его делителей и их количество.
6Задача №6.
Найти максимальный натуральный делитель введённого пользователем числа, кроме самого числа. Выписать этот делитель на экран.
7Задача №7.
Найти, какое число среди чисел от 1 до 999 имеет самый большой максимальный натуральный делитель, отличный от самого числа, и оканчивающийся той же цифрой, что и само число. Выписать это число и его делитель, удовлетворяющий условию задачи.
8Задача №8*.
Пользователь вводит 10 натуральных чисел. Необходимо вывести такую сумму двух чисел среди введённых пользователем, что данная сумма максимальна и кратна трём. То есть среди 10 введённых чисел надо выбрать такие два, чтобы их сумма была максимально возможной и при этом была кратна трём.