Контрольная работа по "Программированию"
Автор: Тима Астапенко • Ноябрь 19, 2023 • Контрольная работа • 797 Слов (4 Страниц) • 127 Просмотры
Задание №1
Составить алгоритм в виде блок-схемы, написать и отладить поставленную задачу с использованием рекурсивной и обычной функций. Сравнить полученные результаты.
В упорядоченном массиве целых чисел ai (i = 1, ..., n) найти номер находящегося в массиве элемента c, используя метод двоичного поиска.
Решение:
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <iomanip>
using namespace std;
void PrintArray(int *array, int n) { // вывод массива
for (int i = 0; i < n; i++)
cout << array[i] << " "; // выводим элементы массива
cout << endl;
}
// ввод массива с клавиатуры
void ReadArray(int *array, int n) {
cout << "Enter values of sorted array: ";
for (int i = 0; i < n; i++)
cin >> array[i]; // вводим элементы массива
}
// бинарный поиск
int BinarySearchArray(int *array, int n, int value) {
if (value < array[0] || value > array[n - 1]) // если элемента нет в массиве
return -1; // возвращаем -1
//левая и правая граница поиска
int left = 0;
int right = n;
// индекс элемента посередине
while (left < right) {
int mid = left + (right - left) / 2;
if (value <= array[mid]) { // если искомый элемент меньше или равен центральному
right = mid; // сдвигаем правую границу
}
else { // иначе
left = mid + 1; // сдвигаем левую границу
}
}
return array[right] == value ? right : -1; // возвращаем индекс элемента, если нашли
}
// рекурсивный бинарный поиск
int BinarySearchRecursiveArray(int *array, int left, int right, int value) {
if (left >= right)
return array[right] == value ? right : -1; // возвращаем индекс элемента, если нашли
int mid = left + (right - left) / 2; // находим индекс посередине
if (value <= array[mid]) { // если элемент меньше или равен центральному
...