10. Лабораторна робота №10

11. Мп Turbo Pascal. Одновимірні масиви. Пошук в одновимірному масиві.

11. Навчитися використовувати алгоритми пошуку в одновимірному масиві при розв’язуванні задач.

Завдання для лабораторної роботи

Скласти блок-схему алгоритму розв’язання задачі, зобразити її засобами Microsoft Word, написати програму мовою Pascal, відлагодити її та проаналізувати отримані результати

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

Задано масив цілих чисел X[1:N]. Задано ціле число a. Якщо в масиві Х є елемент, значення якого дорівнює a, то знайти суму всіх елементів, які слідують за першим таким елементом. Інакше відповіддю має бути число 10.

Розглянемо два способи розв’язання цієї задачі. За першим способом використовується так званий маркер ситуації f, який дорівнює 0, якщо немає жодного елемента x[i], значення якого дорівнює а. f=1, якщо є хоча б один такий елемент.

За другим способом застосовується метод простого перебору. Принцип пошуку елемента одновимірного масиву методом простого перебору розглядається в лекції №11.

Блок-схему алгоритму розв’язання задачі за першим способом наведено на рис.10.1, програму − на рис.10.2.

Блок-схему алгоритму розв’язання задачі за другим способом наведено на рис.11.3 (опорні конспекти лекцій), програму − на рис.10.4.

Результати роботи програм наведені на рис.10.3 і рис.10.5.

Самостійно пропонується розв’язати цю задачу за третім способом, використовуючи метод двійкового пошуку елемента одновимірного масиву.

1 Спосіб

Рис.10.1. Блок-схема алгоритму розв’язання задачі.

Рис.10.2. Програма розв’язання задачі

Рис.10.3. Отримані результати.

2 Спосіб Рис.10.4. Програма розв’язання задачі.

Рис.10.5. Отримані результати.

№10

Скласти блок-схеми алгоритмів розв’язання задач, зобразити їх засобами Microsoft Word, написати програми мовою Pascal, відлагодити їх та проаналізувати отримані результати.

Задача №1

Задано масив цілих чисел X[1:n], впорядкований за зростанням, а також ціле число Y. Присвоїти змінній К номер того елемента масиву Х, значення якого дорівнює числу Y. Якщо такого елемента немає, числу Y присвоїти значення 0.

Задача №2

Задано упорядкований за неспаданням масив цілих чисел A[1:n] і число B. Для числа B знайти таке місце серед елементів масиву А, щоб після вставки числа В на це місце впорядкованість масиву не порушилася. Якщо внаслідок рівності між собою значень елементів масиву А число В можна вставляти на різні місця, то слід визначити найближче до початку масиву місце. Ця задача називається задачею пошуку місця елемента.

Задача №3

Задано упорядкований за неспаданням масив цілих чисел A[1:n] і масив цілих чисел B[1:m]. Отримати натуральні числа такі, що — це результат пошуку місця серед елементів масиву А (i=1,2,…,m).

Задача №4

Таблиця виграшів грошової лотереї представлена масивом вигравших номерів A[1:n] і масивом виграшів (у гривнях) P[1:n], де — це виграш, випавший на номер (і=1,2,…,n). Визначити сумарний виграш, випавший на лотерейні квитки з номерами .

Задача № 5

Д ивись умову задачі №1. Нехай місце числа В серед упорядкованих за неспаданням елементів масиву А вибирається як найбільш віддалене від початку масиву місце.

Питання для самоконтролю

1. Які ви знаєте алгоритми пошуку в одновимірних масивах?

2. Поясніть принцип двійкового пошуку в одновимірному масиві.

3. Поясніть принцип методу пошуку шляхом простого перебору елементів одновимірного масиву.

4. Для яких масивів може бути застосований двійковий пошук?

5. Спробуйте пояснити, чому кількість зрівнянь, що потребує цей алгоритм, не перевищує величину , де n — кількість елементів масиву.