Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define CRT_SECURE_NO_WARNINGS
- #include "pch.h"
- #include <iostream>
- #include <limits.h>
- using namespace std;
- struct Result *s_search(int arr[], int K);
- struct Result *q_search(int arr[], int K);
- struct Result *t_search(int arr[], int K);
- struct Result *bin_search(int arr[], int N, int K);
- void sort(int arr[]);
- void initialize_result(struct Result *result);
- struct Result
- {
- int count;
- int index[21];
- int oper_count[21];
- int cycle_count[21];
- };
- int main()
- {
- int i;
- int N = 21;
- int arr[] = { 23, 74, 52, 11, 23, 9, 67, 48, 12, 23, 64, 73, 6, 29, 97, 34, 76, 23, 15, 49, 5 };
- int K;
- K = 23;
- struct Result result;
- result = *s_search(arr, K);
- if (result.count >= 0)
- {
- for (i = 0; i <= result.count; i++)
- {
- printf("Algorithm S: found at position %d, %d operations were required, %d cycle runs.\n", result.index[i], result.oper_count[i], result.cycle_count[i]);
- }
- }
- else
- {
- printf("Algorithm S: not found, %d operations were required, %d cycle runs.\n", result.oper_count[0], result.cycle_count[0]);
- }
- result = *q_search(arr, K);
- if (result.count >= 0)
- {
- for (i = 0; i <= result.count; i++)
- {
- printf("Algorithm Q: found at position %d, %d operations were required, %d cycle runs.\n", result.index[i], result.oper_count[i], result.cycle_count[i]);
- }
- }
- else
- {
- printf("Algorithm Q: not found, %d operations were required, %d cycle runs.\n", result.oper_count[0], result.cycle_count[0]);
- }
- sort(arr);
- printf("Array was sorted.\n");
- result = *t_search(arr, K);
- if (result.count >= 0)
- {
- for (i = 0; i <= result.count; i++)
- {
- printf("Algorithm T: found at position %d, %d operations were required, %d cycle runs.\n", result.index[i], result.oper_count[i], result.cycle_count[i]);
- }
- }
- else
- {
- printf("Algorithm T: not found, %d operations were required, %d cycle runs.\n", result.oper_count[0], result.cycle_count[0]);
- }
- result = *bin_search(arr, N, K);
- if (result.count >= 0)
- {
- for (i = 0; i <= result.count; i++)
- {
- printf("Algorithm B: found at position %d, %d operations were required, %d cycle runs.\n", result.index[i], result.oper_count[i], result.cycle_count[i]);
- }
- }
- else
- {
- printf("Algorithm B: not found, %d operations were required, %d cycle runs.\n", result.oper_count[0], result.cycle_count[0]);
- }
- }
- struct Result *s_search(int arr[], int K)
- {
- struct Result result;
- int i;
- int oper_count = 0, cycle_count = 0;
- initialize_result(&result);
- for (i = 0; i < 21; i++)
- {
- cycle_count++;
- oper_count++; //Проверка условия
- if (arr[i] == K)
- {
- oper_count++; //Запись в result (считаем за одну операцию)
- result.count++;
- result.oper_count[result.count] = oper_count;
- result.index[result.count] = i;
- result.cycle_count[result.count] = cycle_count;
- }
- oper_count++; //Увеличение i
- oper_count++; //Проверка i < 21
- }
- if (result.count < 0) //Если не найдено
- {
- result.oper_count[0] = oper_count;
- result.cycle_count[0] = cycle_count;
- }
- return &result;
- }
- struct Result * q_search(int arr[], int K)
- {
- int i;
- int oper_count = 0, cycle_count = 0;
- struct Result result;
- initialize_result(&result);
- int farr[22]; //Фиктивный массив
- for (i = 0; i < 21; i++) //Добавление фиктивной записи
- {
- farr[i] = arr[i];
- }
- farr[21] = K;
- i = 0;
- while (1)
- {
- cycle_count++;
- oper_count++; //Проверка условия
- if (farr[i] == K)
- {
- oper_count++; //Проверка условия
- if (i <= 20)
- {
- oper_count++; //Запись в result (считаем за одну операцию)
- result.count++;
- result.oper_count[result.count] = oper_count;
- result.index[result.count] = i;
- result.cycle_count[result.count] = cycle_count;
- }
- else
- {
- if (result.count < 0) //Если не найдено
- {
- result.oper_count[0] = oper_count;
- result.cycle_count[0] = cycle_count;
- }
- return &result; //Пройдены все элементы массива
- }
- }
- i++;
- oper_count++; //Увеличение i
- }
- }
- struct Result *t_search(int arr[], int K)
- {
- struct Result result;
- int oper_count = 0, cycle_count = 0;
- int i;
- initialize_result(&result);
- int farr[22]; //Фиктивный массив
- for (i = 0; i < 21; i++) //Добавление фиктивной записи
- {
- farr[i] = arr[i];
- }
- farr[21] = INT_MIN;
- i = 0;
- while (1)
- {
- cycle_count++;
- oper_count++; //Проверка условия
- if (K >= farr[i])
- {
- oper_count++; //Проверка условия
- if (K == farr[i]) {
- oper_count++; //Запись в result (считаем за одну операцию)
- result.count++;
- result.oper_count[result.count] = oper_count;
- result.index[result.count] = i;
- result.cycle_count[result.count] = cycle_count;
- }
- else
- {
- break;
- }
- }
- i++;
- oper_count++; //Увеличение i
- }
- if (result.count < 0) //Если не найдено
- {
- result.oper_count[0] = oper_count;
- result.cycle_count[0] = cycle_count;
- }
- return &result;
- }
- struct Result *bin_search(int arr[], int N, int K)
- {
- int first_upper_index = -1;
- int first_left_index = -1;
- int oper_count = 0, cycle_count = 0;
- int mid, left = 0, right = N - 1;
- struct Result result;
- initialize_result(&result);
- //Поиск самого левого подходящего элемента
- while (left <= right)
- {
- cycle_count++;
- oper_count++; //Проверка условия цикла
- mid = (left + right) / 2;
- oper_count++; //Операция присваивания
- oper_count += 2; //Проверка условия и операция присваивания (ниже)
- if (K >= arr[mid])
- {
- right = mid - 1;
- }
- else //K < arr[mid]
- {
- left = mid + 1;
- }
- }
- first_left_index = mid;
- oper_count++; //Запись в result (считаем за одну операцию)
- result.count = 0;
- result.oper_count[0] = oper_count;
- result.index[0] = first_left_index;
- result.cycle_count[0] = cycle_count;
- if (first_left_index < 0) //Если не найдено
- {
- result.count = -1;
- return &result;
- }
- //Поиск первого неподходящего элемента справа
- left = 0;
- right = N - 1;
- while (left <= right)
- {
- cycle_count++;
- oper_count++; //Проверка условия цикла
- mid = (left + right) / 2;
- oper_count++; //Операция присваивания
- if (K <= arr[mid])
- {
- left = mid + 1;
- oper_count += 2; //Проверка условия и операция присваивания
- }
- else //K > arr[mid]
- {
- right = mid;
- oper_count += 2; //Проверка условия и операция присваивания
- oper_count++; //Проверка условия
- if (right == left) //Предотвращает бесконечный цикл; TODO: постараться убрать
- {
- break;
- }
- }
- }
- first_upper_index = mid;
- result.count = (first_upper_index - first_left_index - 1);
- for (int i = 1; i <= result.count; i++)
- {
- result.index[i] = first_left_index + i;
- result.cycle_count[i] = cycle_count;
- result.oper_count[i] = oper_count + i; //Запись в result (считаем за одну операцию)
- }
- return &result;
- }
- void sort(int arr[]) //Сортировка по убыванию пузырьком
- {
- int i, j, temp;
- for (i = 0; i < 21; i++)
- {
- for (j = i; j < 21; j++)
- {
- if (arr[i] < arr[j])
- {
- temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- }
- }
- }
- }
- void initialize_result(struct Result *result)
- {
- int i;
- result->count = -1;
- for (i = 0; i < 21; i++)
- {
- result->index[i] = 0;
- result->oper_count[i] = 0;
- result->cycle_count[i] = 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement