Помощь студентам в учебе и написании работ. Заказать дипломную, курсовую, работу. Никольский Помощь

Готовая лаб. работа: Битовые операции и сортировка

Загружена: 19.02.2026 11:58

Руководство по работе с битовыми масками и реализации внешней сортировки на основе битового массива. Описаны примеры установки/снятия битов, сортировка наборов через битмап для 8/64 элементов и внешний алгоритм сортировки файла до 10^7 чисел. Практическая ценность — готовые C++‑реализации с измерением памяти и времени, а также примеры работы с бинарными файлами и индексным поиском.

Содержание

Задание 1.1

Описание подхода к решению

Определение структуры записи файла

Размер записи в байтах можно определить с помощью оператора sizeof

Организация прямого доступа к записям в бинарном файле

Алгоритмы, которые реализуются в форме функций

Код программы

Пример тестирования программы отображен на рисунке 1

Задание 1.2

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

Алгоритм линейного поиска записи в файле можно представить в виде следующего псевдокода

Код функции линейного поиска выглядит следующим образом

Полный код программы с функцией линейного поиска выглядит следующим образом

Результат тестирования программы для 100 записей

Результаты с замерами времени поиска записи по заданному ключу для файла из 100 и 1000 записей

Задание 1.3

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

Описание алгоритма доступа к записи в файле посредством таблицы

Алгоритм поиска записи с указанным ключом в файле может быть представлен в виде следующего псевдокода

Код функции поиска записи в файле выглядит следующим образом

Полный код программы с реализацией поиска записи в бинарном файле

Результат тестирования программы для 100 записей

Результаты замеров времени поиска записи по заданному ключу для файла из 100 и 10000 записей

Анализ эффективности рассмотренных алгоритмов поиска в файле



Задание 1.а: Реализуйте вышеприведённый пример, проверьте правильность результата в том числе и на других значениях х.

Задание 1.б: Реализуйте по аналогии с предыдущим примером установку 7-го бита числа в единицу.

Задание 1.в: Реализуйте код листинга 1, объясните выводимый программой результат.

Задание 2.а: Реализуйте вышеописанный пример с вводом произвольного набора до 8-ми чисел (со значениями от 0 до 7) и его сортировкой битовым массивом в виде числа типа unsigned char. Проверьте работу программы.

Задание 2.а: Адаптируйте вышеприведённый пример для набора из 64-х чисел (со значениями от 0 до 63) с битовым массивом в виде числа типа unsigned long long.

Задание 2.в: Исправьте программу задания 2.б, чтобы для сортировки набора из 64-х чисел использовалось не одно число типа unsigned long long, а линейный массив чисел типа unsigned char.

Задание 3.а: Реализуйте задачу сортировки числового файла с заданными условиями. Добавьте в код возможность определения времени работы программы.

Задание 3.б: Определите программно объём оперативной памяти, занимаемый битовым массивом.



Цель работы: Целью данной работы является разработка приложения на языке C++, которое использует хеш-таблицу с открытой адресацией и квадратичным пробированием для организации прямого доступа к элементам динамического множества полезных данных о владельцах телефонов. Программа должна реализовать основные операции: вставку, удаление, поиск и вывод данных, а также обеспечивать возможность взаимодействия с пользователем через текстовый интерфейс.

Ход работы:
a. Формулировка задачи
b. Математическая модель решения (описание алгоритма)
c. Код программы с комментариями
d. Результаты тестирования


Цель работы: Целью данной программы является разработка приложения на языке C++, которое выполняет поиск заданной подстроки в тексте, считывая данные из текстового файла. Программа реализует два основных функционала:

Поиск всех слов в тексте, которые заканчиваются на заданную подстроку.

Подсчет количества вхождений данной подстроки в тексте с использованием эффективного алгоритма Рабина-Карпа.

Подробное описание

📘 О чем эта работа

В работе подробно рассматриваются приёмы работы с битовым представлением беззнаковых целых чисел и реализуется эффективный алгоритм внешней сортировки на основе битового массива. Кроме того, приводится набор программ на C++ для работы с бинарными файлами записей (структура Enterprise), реализованы линейный поиск и поиск по индексу.

📚 Что внутри

Материалы содержат конкретные примеры кода и пояснения:

Примеры побитовых операций: установка 5‑го бита в 0 (x = x & ~(1<
Программа‑пример для ввода до 8 чисел (0..7) и хранения набора в одном unsigned char с последующей сортировкой и выводом битовой последовательности (bitset<8>).
Адаптация для 64 чисел: использование unsigned long long и альтернативно — массива unsigned char для представления непрерывного битового вектора (разбиение по байтам и индексирование input/8 и input%8).
Реализация внешней сортировки файла чисел до MAX_NUMBERS = 10^7: расчёт размера битового массива, хранение в векторе unsigned int, установка битов при чтении входного файла и последовательный проход по битовому массиву для записи отсортированных индексов в выходной файл.
Подсчёт занимаемой памяти: формулы и вывод size_t memorySizeInBytes = (MAX_NUMBERS + 7) / 8; практические комментарии по объёму в байтах.
Работа с бинарными записями: структура Enterprise { int licenseNumber; char name[50]; char founder[50]; } (размер записи 104 байта), запись в enterprises.dat через outFile.write(reinterpret_cast(&enterprise), sizeof(enterprise)).
Алгоритмы поиска: линейный поиск по файлу с измерением времени (chrono) и индексный поиск с предпостроенной таблицей (std::unordered_map) ключ→смещение и чтением записи через seekg.

📊 Для кого подходит

Материал полезен студентам кафедр программирования и информатики (2–4 курсы), слушателям курсов по системному программированию, разработчикам, работающим с низкоуровневой обработкой данных и созданием быстрых сортировок для больших объёмов чисел.

✨ Особенности

В комплекте — конкретные рабочие листинги на C++ (работают в среде Windows с SetConsoleCP/SetConsoleOutputCP), тестовые примеры и скриншоты результатов. Приведены методы оптимальной упаковки набора данных в битовый вектор, инструкция по переходу от одного целого для 64 бит к массиву байтов для произвольных объёмов, а также рекомендации по оценке и оптимизации потребления памяти и времени выполнения.

❓ Частые вопросы

Подойдет ли для моего ВУЗа?
Структура лабораторной работы соответствует стандартным требованиям: цель, математическая модель, листинги, тесты и выводы — легко адаптируется под локальные методички.

Можно адаптировать?
Да — код модульный: заменой константы MAX_NUMBERS и типа контейнера можно расширять диапазон, подключать многопоточную обработку или заменять формат ввода/вывода.

Практическая выгода: готовые реализации позволяют быстро получить рабочую лабораторную работу с демонстрацией принципов битовой маскировки, эффективной внешней сортировки и быстрых методов доступа к бинарным записям (индексация для O(1) чтения по ключу).