#define _CRT_SECURE_NO_WARNINGS #include #include #include // Функция сортировки извлечения void extractionSort(int arr[], int n) { int i, ind, min, j, a; for (i = 0; i < n; i++) { min = arr[i]; ind = i; for (j = i + 1; j < n; j++) { if (arr[j] < min) { min = arr[j]; ind = j; } } a = arr[i]; arr[i] = min; arr[ind] = a; } } // сортировка слиянием void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; //временные массивы для левой и правой части int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); //копирование данных во временные массивы for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; // Слияние временных массивов обратно в основной массив arr[] i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } //копирование оставшихся элементов из L[], если они есть while (i < n1) { arr[k] = L[i]; i++; k++; } //копирование оставшихся элементов из R[], если они есть while (j < n2) { arr[k] = R[j]; j++; k++; } free(L); free(R); } // Функция сортировки слиянием void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; //находим середиену // Рекурсивно сортируем левую и правую половины //делим пока не останется по одному элементу mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); // Слияние отсортированных частей } } //Дихотомический поиск int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (x < arr[mid]) return binarySearch(arr, l, mid - 1, x); else return binarySearch(arr, mid + 1, r, x); } return -1; // Если элемент не найден } // Главная функция программы int main() { setlocale(LC_ALL, "Russian"); int N, M; // Ввод размера последовательности и размера группы printf("Введите размер последовательности (N): "); scanf("%d", &N); printf("Введите размер группы (M): "); scanf("%d", &M); // Выделение памяти под массив int* sequence = (int*)malloc(N * sizeof(int)); // Заполнение массива случайными числами printf("Сгенерированная последовательность:\n"); for (int i = 0; i < N; i++) { sequence[i] = rand() % 100; printf("%d ", sequence[i]); } // Разбиение на группы и сортировка методом извлечения for (int i = 0; i < N; i += M) { extractionSort(sequence + i, (i + M > N) ? N - i : M); } // Удваивание и сортировка методом слияния for (int size = M; size < N; size *= 2) { for (int left = 0; left < N; left += 2 * size) { int mid = left + size - 1; int right = (left + 2 * size - 1 < N) ? left + 2 * size - 1 : N - 1; // Сортировка от left до right методом слияния mergeSort(sequence, left, right); } } // Вывод отсортированной последовательности printf("\nОтсортированная последовательность:\n"); for (int i = 0; i < N; i++) { printf("%d ", sequence[i]); } // Ввод элемента для поиска int x; printf("\nВведите элемент для поиска: "); scanf("%d", &x); // Поиск элемента методом дихотомического поиска int result = binarySearch(sequence, 0, N - 1, x); // Вывод результатов if (result != -1) { printf("Элемент %d найден на позиции %d в упорядоченной последовательности.\n", x, result + 1); } else { printf("Элемент %d не найден в упорядоченной последовательности.\n", x); } // Освобождение выделенной памяти free(sequence); return 0; } 1 Словесная постановка задачи. Написать программу, которая разбивает всю числовую последовательность случайных чисел из N элементов на группы по M записей (N , M – входные параметры, задаваемые пользователем). Внутри каждой группы применить сортировку методом извлечения, а затем, последовательно удваивая группы, сортировать методом слияния до тех пор, пока не получится полностью отсортированный массив. Методом дихотомического поиска найти заданный элемент и вывести на экран его порядковый номер в упорядоченной последовательности. 1.1 Суть задачи Программа должна выполнить следующие шаги: 1. Сгенерировать N случайных чисел. 2. Разбить последовательность чисел на группы по M записей. 3. Применить сортировку методом извлечения внутри каждой группы. 4. Последовательно удваивать группы и сортировать методом слияния до тех пор, пока не получится полностью отсортированный массив. 5. Использовать метод дихотомического поиска для нахождения заданного элемента. 6. Вывести на экран порядковый номер найденного элемента в упорядоченной последовательности. 1.2 Анализ входящих величин: В программу вводятся следующие величины: － N: Количество случайных чисел в последовательности. － M: Количество записей в каждой группе. 1.3 Область допустимых значений: N и M должны быть положительными целыми числами (N, M > 0). 1.3 Возможные ограничения: В программе возможны следующие ограничения: － ограничения на объем доступной памяти для обработки больших N и M; － ограничения на время выполнения программы. 1.4 Анализ условий решения: Программа может успешно выполняться при следующих условиях: － N и M удовлетворяют ограничениям памяти и времени; － для выполнения сортировки слиянием, M должно быть степенью двойки. 1.5 Ожидаемые результаты: Ожидаемым результатом программы является: － упорядоченная последовательность чисел с применением сортировки методом слияния. － порядковый номер заданного элемента в упорядоченной последовательности. 2 Математическая модель Пусть: － N - количество случайных чисел в последовательности. － M - количество записей в каждой группе. Генерация случайных чисел Пусть A={a1, a2,…, aN} - последовательность случайных чисел. Ai ∈ R,i = 1, 2, … , N. Разбиение на группы : дописать Сортировка методом извлечения внутри каждой групп: Дописать Сортировка методом слияния дописать . Метод дихотомического поиска Обозначим P - множество порядковых номеров, соответствующих упорядоченной последовательности P={1,2,…,N}. Для заданного элемента x, пусть rank(x) - его порядковый номер в упорядоченной последовательности. Поиск rank(x)=дихотомический поиск в Sk для k=1,2,…,log2 (N/M) Ограничения и уточнения: － Обозначение N/M используется для учёта последней группы, которая может содержать менее M элементов. － Процесс слияния будет выполняться до тех пор, пока не будет получен полностью упорядоченный массив. Ожидаемые результаты: － Полностью упорядоченная последовательность чисел. － Порядковый номер заданного элемента в упорядоченной последовательности. 3 Алгоритм решения задачи В программе используется следующий алгоритм решения задачи: 1. Сгенерировать N случайных чисел и создать последовательность A. 2. Разделить последовательность A на группы G_k по M элементов. 3. Для каждой группы G_k, применить сортировку методом извлечения. 4. Повторять: a. Для каждой пары соседних групп G_{2i-1} и G_{2i}, выполнить слияние и сохранить результат в S_i. b. Обновить последовательность групп G_k как S_i. c. Если последовательность полностью упорядочена, завершить цикл. 5. Для заданного элемента x: a. Для каждой последовательности S_i: i. Выполнить дихотомический поиск для элемента x. ii. Если x найден, вывести порядковый номер. 6. Вывести упорядоченную последовательность и порядковый номер заданного элемента.