Алгоритми на пошук mах та min

Задачі на пошук максимального та мінімального

Задачі на знаходження найбільшого та найменшого числа серед декількох чисел мають простий стандартний алгоритм.

Правило знаходження max або min

При складанні програм на знаходження найбільшого або найменшого числа з декількох чисел, потрібно пам’ятати: Тип max (min) співпадає з типом чисел, серед яких обирають найбільше (найменше) Тип порядкових номерів nmax (nmin) завжди цілий Перед циклом потрібно присвоїти початкові значення max (min) та його порядковому номеру nmax (nmin). Ці значення повинні співпадати з першим числом. У циклі for i:=2 to n do: вводиться наступне число a; число a перевіряється таким чином: if a > max для знаходження першого max; if a >= max для знаходження останнього max; if a < min для знаходження першого min; if a <= min для знаходження останнього min. якщо умова вірна, то це число a та його порядковий номер запам’ятовують, тобто виконуються оператори max:=a (min:=a) та nmax:=i (nmin:=i). Якщо порядкові номери nmax (nmin) не потрібні, то їх не запам’ятовують. Після завершення циклу знайдені значення виводяться на екран.

Приклад 1

Дано n цілих чисел. Знайти серед них максимальне та його порядковий номер. Якщо є декілька таких чисел, то визначте порядковий номер першого такого числа.

Результат роботи програми

Ввід	Вивід	Пояснення
6 6 7 8 3 8 5	8 3	Перше число 6 це кількість чисел. Наступні числа мають порядкові номери: 6 – 1, 7 – 2, 8 – 3, 3 – 4, 8 – 5, 5 –6. Серед цих шістьох чисел найбільше 8. Одна 8 має порядковий номер 3. Друга 8 має порядковий номер 5. Нам потрібна перша, з порядковим номером 3.

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)
• a – число (цілого типу, за умовою)

Вихідні:

• max – максимальне число (цілого типу, тому що числа a цілі).
• nmax – порядковий номер максимального числа (номери завжди цілого типу)

Проміжні:

• i – параметр циклу (цілого типу)

Алгоритм

1. Спочатку потрібно ввести кількість чисел оператором read(n).
2. Потім потрібно встановити початкове значення змінним max та nmax. Будемо вважати, що перше число є найбільшим. Тому введемо його значення у змінну maxоператором read(max) та присвоїмо значення змінній nmax оператором nmax:=1. Після цього (для нашого прикладу) значення max буде 6.
3. У циклі for i:=2 to n do у операторних дужках будемо виконувати такі дії (цикл від 2, тому що перше число вже ввели):
   • Оператор read(a) вводить наступне число у змінну a.
   • Якщо введене число a > max, то змінюємо значення змінної max на a оператором max:=a та запам’ятовуємо порядковий номер числа оператором nmax:=i.
   • Якщо введене число a < = max, то нічого не робимо, тобто значення max та nmax не змінюється.
4. Коли цикл закінчиться, тобто будуть введені всі n чисел, у змінній max буде значення найбільшого з чисел, а у змінній nmax його порядковий номер. Ці дані виводяться на екран оператором writeln(max,' ',nmax).

Програма

var i,max,nmax,n,a:integer; begin  read(n); read(max);nmax:=1;  for i:=2 to n do  begin    read(a);      if a >max then begin max:=a; nmax:=i;end;  end;  writeln(max,' ',nmax); end.

Трасування програми

У приведеній нижче таблиці для нашого прикладу проводиться „трасування” програми, тобто програма виконується по крокам, вказуються оператори, що виконуються та відповідні зміни значень змінних.

Оператор	Пояснення	n	max	nmax	i	a
read(n)	Ввід кількості чисел	6
read(max)	Ввід першого числа у змінну max		6
nmax:=1	Початкове значення номеру			1
i:=2	Заголовок циклу				2
read(a)	Ввід другого числа					7
if a >max	Вірно, бо 7> 6
max:=a; nmax:=i;	Виконуються, бо вірно		7	2
i:=3	Заголовок циклу				3
read(a)	Ввід третього числа					8
if a >max	Вірно, бо 8> 7
max:=a; nmax:=i;	Виконуються, бо вірно		8	3
i:=4	Заголовок циклу				4
read(a)	Ввід четвертого числа					3
if a >max	Невірно, бо 3<8, тому на наступний виток циклу
i:=5	Заголовок циклу				5
read(a)	Ввід п’ятого числа					8
if a >max	Невірно, бо 8=8, тому на наступний виток циклу
i:=6	Заголовок циклу. Останній виток.				6
read(a)	Ввід шостого числа					5
if a >max	Невірно, бо 5<8, тому на кінець циклу
writeln(max,' ',nmax)	Вивід отриманих значень.

Приклад 2

Ввести з клавіатури n будь-яких дійсних чисел. Знайти максимальне та мінімальне числа.

У цій програмі потрібно одночасно знайти і найбільше і найменше числа. Тому початкове значення ми будемо встановлювати однакове для max і для min. У циклі кожне число будемо перевіряти і на „більше” і на „менше”. Порядкові номери непотрібні, тому їх не запам’ятовуємо.

Результат роботи програми

Ввід	Вивід	Пояснення
6 6 2 8 2 8 9	3	Перше число 6 це кількість чисел. Серед цих шістьох чисел найбільше 9, а найменше 2.

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)
• a – число (дійсного типу, за умовою)

Вихідні:

• max –максимальне число (дійсного типу, тому що числа a дійсні).
• min –мінімальне число (дійсного типу, тому що числа a дійсні).

Проміжні:

• i – параметр циклу (цілого типу)

Алгоритм

1. Спочатку потрібно ввести кількість чисел оператором read(n).
2. Потім потрібно встановити початкове значення змінним max та min. Це значення для обох змінних повинно співпадати з першим числом. Тому у першу змінну ми це значення введемо з клавіатури, а другій змінній присвоїмо.
3. У циклі for i:=2 to n do у операторних дужках будемо виконувати такі дії (цикл від 2, тому що перше число вже ввели):
   • Оператор read(a) вводить наступне число у змінну a.
   • Якщо введене число a > max, то змінюємо значення змінної max на a оператором max:=a.
   • Якщо введене число a < min, то змінюємо значення змінної min на a оператором min:=a.
4. Коли цикл закінчиться, тобто будуть введені всі n чисел, у змінній max буде значення найбільшого з чисел, а у змінній min буде значення найменшого з чисел. Ці дані виводяться на екран оператором writeln(max:1:2,' ', min:1:2). Числа дійсні, тому виводяться у форматованому вигляді.

Програма

var i,n:integer;max,min,a:real; begin  read(n); read(max);min:=max;  for i:=2 to n do  begin    read(a);    if a > max then max:=a;    if a < min then min:=a;  end;  writeln(max:1:2,' ',min:1:2); end.

Приклад 3

Ввести з клавіатури n будь-яких дійсних чисел. Визначте число, що найближче до цілого числа. Якщо таких чисел декілька, то визначте перше з них.

У цій програмі будемо знаходити мінімальне значення не для чисел a, а для модуля різниці між числом та числом округленим до цілого, тобто для чисел riz.

Результат роботи програми

Ввід	Вивід	Пояснення
4 4.3 5.9 3.1 2.6	5.9	4 це кількість чисел. Перше число 4.3, округлюється до 4, 4.3–4 =0.3 Друге число 5.9, округлюється до 6, 5.9-6=-0.1 Третє число 3.1, округлюється до 3, 3.1-3=0.1 Четверте число 2.6, округлюється до 3, 2.6-3=-0.4 Найближчі до цілого два числа: 5.9 до 6 і 3.1 до 3. Перше з них 5.9

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)
• a – число (дійсного типу, за умовою)

Вихідні:

• min – число найближче до цілого (дійсного типу, тому що числа a дійсні).

Проміжні:

• i – параметр циклу (цілого типу)
• riz – модуль різниці між введеним числом a та числом a округленим до цілого (дійсного типу, тому що числа a дійсні).
• minriz – мінімальне значення для чисел riz (дійсного типу, тому що числа riz дійсні).

Алгоритм

1. Спочатку потрібно ввести кількість чисел оператором read(n).
2. Потім вводимо перше число у змінну min.
3. Тепер потрібно встановити початкове значення змінній minriz:=abs(min-round(min)).
4. У циклі for i:=2 to n do у операторних дужках будемо виконувати такі дії (цикл від 2, тому що перше число вже ввели):
   • Оператор read(a) вводить наступне число у змінну a.
   • Для цього числа обчислюється різниця riz:=abs(a-round(a)).
   • Якщо обчислене значення riz < minriz, то змінюємо значення змінної minriz на riz оператором minriz:=riz та запам’ятовуємо число, для якого це сталося оператором min:=a.
5. Коли цикл закінчиться, тобто будуть введені всі n чисел, у змінній min буде значення числа найближчого до цілого. Це число виводиться на екран операторомwriteln(min:1:1).

Програма

var i,n:integer;minriz,min,riz,a:real; begin  read(n);  read(min); minriz:=abs(min-round(min));  for i:=2 to n do  begin    read(a); riz:=abs(a-round(a));    if riz < minriz then      begin minriz:=riz; min:=a; end;  end;  writeln(min:1:1); end.

Приклад 4

Дано n цілих чисел. Визначте максимальну кількість 0, що йдуть підряд.

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

Результат роботи програми

Ввід	Вивід	Пояснення
7 2 0 0 8 0 0 0	3	7 це кількість чисел. В першій групі 2 нулі, у другій групі 3 нулі, тому відповідь 3.

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)
• a – число (цілого типу, за умовою)

Вихідні:

• max – максимальна кількість нулів, що введені підряд (цілого типу, тому числа k цілі).

Проміжні:

• i  – параметр циклу (цілого типу)
• k – лічильник нулів, що йдуть підряд(цілого типу).

Алгоритм

1. Спочатку потрібно ввести кількість чисел оператором read(n).
2. Потім потрібно встановити початкове значення змінній max:=0, тобто вважаємо що нулів немає.
3. Встановлюємо початкове значення лічильника нулів k:=0.
4. У циклі for i:=1 to n do у операторних дужках будемо виконувати такі дії:
   • Оператор read(a) вводить наступне число у змінну a.
   • Якщо введене число 0, то:
     • збільшуємо лічильник нулів k:=k+1;
     • якщо цей лічильник k>max, то запам’ятовуємо його значення max:=k.
   • Якщо введено число не 0, встановлюємо значення лічильника у нуль k:=0.
5. Коли цикл закінчиться, тобто будуть введені всі n чисел, у змінній max буде максимальне значення серед лічильників нулів k. Це число виводиться на екран оператором writeln(max).

Програма

var i,max,k,n,a:integer; begin  read(n); max:=0;k:=0;  for i:=1 to n do  begin    read(a);    if a =0 then      begin        k:=k+1;        if k>max then max:=k;      end            else k:=0;  end;  writeln(max); end.

Трасування програми

У приведеній нижче таблиці для нашого прикладу проводиться „трасування” програми, тобто програма виконується по крокам, вказуються оператори, що виконуються та відповідні зміни значень змінних.

Оператор	Пояснення	n	max	k	i	a
read(n)	Ввід кількості чисел	7
max:=0	Початкове значення max		0
k:=0	Початкове значення лічильнику нулів			0
i:=1	Заголовок циклу				1
read(a)	Ввід першого числа					2
if a =0	Невірно, бо a=2
k:=0	Виконується, бо невірно			0
i:=2	Заголовок циклу				2
read(a)	Ввід другого числа					0
if a =0	Вірно, бо a=0
k:=k+1	Виконуються, бо вірно			1
if k>max	Вірно, бо 1>0
max:=k	Виконується, бо вірно		1
i:=3	Заголовок циклу				3
read(a)	Ввід третього числа					0
if a =0	Вірно, бо a=0
k:=k+1	Виконуються, бо вірно			2
if k>max	Вірно, бо 2>0
max:=k	Виконуються, бо вірно		2
i:=4	Заголовок циклу				4
read(a)	Ввід четвертого числа					8
if a =0	Невірно, бо a=8
k:=0	Виконується, бо невірно			0
i:=5	Заголовок циклу				5
read(a)	Ввід п’ятого числа					0
if a =0	Вірно, бо a=0
k:=k+1	Виконуються, бо вірно			1
if k>max	Невірно, бо 1<2
i:=6	Заголовок циклу				6
read(a)	Ввід шостого числа					0
if a =0	Вірно, бо a=0
k:=k+1	Виконуються, бо вірно			2
if k>max	Невірно, бо 2=2
i:=7	Заголовок циклу. Останній виток				7
read(a)	Ввід сьомого числа					0
if a =0	Вірно, бо a=0
k:=k+1	Виконуються, бо вірно			3
if k>max	Вірно, бо 3>2
max:=k	Виконується, бо вірно		3
writeln(max)	Вивід отриманого значення

Варіанти задач

1. Ввести з клавіатури n будь-яких чисел. Знайти серед них максимальне.
2. Ввести з клавіатури n будь-яких чисел. Знайти серед них мінімальне.
3. Ввести з клавіатури n будь-яких символів. Знайти „максимальний” символ.
4. Ввести з клавіатури n будь-яких символів. Знайти „мінімальний” символ.
5. Ввести з клавіатури n будь-яких чисел. Знайти мінімальне та його порядковий номер. Якщо є декілька таких чисел, то визначте порядковий номер першого такого числа.
6. Ввести з клавіатури n будь-яких чисел. Знайти максимальне та його порядковий номер. Якщо таких чисел декілька, то знайти порядковий номер останнього такого числа.
7. Ввести з клавіатури n будь-яких чисел. Знайти мінімальне та його порядковий номер. Якщо є декілька таких чисел, то визначте порядковий номер останнього такого числа.
8. Ввести з клавіатури n будь-яких символів. Знайти „максимальний” символ. Якщо таких символів декілька, то вивести порядковий номер першого з них.
9. Ввести з клавіатури n будь-яких символів. Знайти „максимальний” символ. Якщо таких символів декілька, то вивести порядковий номер останнього з них.
10. Ввести з клавіатури n будь-яких символів. Знайти „мінімальний” символ. Якщо таких символів декілька, то вивести порядковий номер першого з них.
11. Ввести з клавіатури n будь-яких символів. Знайти „мінімальний” символ. Якщо таких символів декілька, то вивести порядковий номер останнього з них.
12. Ввести з клавіатури n будь-яких символів. Знайти перший „мінімальний” та останній „максимальний” символи.
13. Ввести з клавіатури n будь-яких чисел. Знайти середнє арифметичне максимального та мінімального з них.
14. Ввести з клавіатури n будь-яких чисел. З’ясувати, яке число введено раніше, максимальне чи мінімальне?
15. Ввести з клавіатури n будь-яких чисел. Визначте мінімальну кількість від’ємних чисел, що йдуть підряд.
16. Ввести з клавіатури n будь-яких чисел та число k. Знайдіть число (його порядковий номер і значення) найдальший від k.