отчет по с. Отчёт. Напишите программу, находящую значение из заданного интервала, отсутствующее в массиве

Название	Напишите программу, находящую значение из заданного интервала, отсутствующее в массиве
Анкор	отчет по с
Дата	20.06.2022
Размер	47.76 Kb.
Формат файла
Имя файла	Отчёт.docx
Тип	Документы #605517

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

Напишите программу, находящую значение из заданного интервала, отсутствующее в массиве.

Исходные данные

(Консоль) В качестве исходных данных пользователь должен ввести интервал для чисел, которые будут сравниваться, затем указать размер массива и ввести элементы.

(Файл) Первые два числа – интервал сравнения, все последующие – массив для сравнения.

Особые ситуации

Полное имя файла не должно содержать пробелы и кириллицу;

Нижняя граница не может быть “больше” верхней;

Обработка ввода через консоль и проверка имени файла.

Математические методы и алгоритмы решения задач

Сортировка пузырьком.

Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:

если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним.

В результате наибольший элемент оказывается в самом верху массива. Сложность:

Бинарный поиск.

Бинарный поиск производится в упорядоченном массиве.

При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.

Подготовка. Перед началом поиска устанавливаем левую и правую границы массива:

left = 0, right = 19

Шаг 1. Ищем индекс середины массива (округляем в меньшую сторону):

mid = (19+0)/2=9

Сравниваем значение по этому индексу с искомым:

69 < 82

Сдвигаем левую границу:

left = mid = 9

Шаг 2. Ищем индекс середины массива (округляем в меньшую сторону):

mid = (9+19)/2=14

Сравниваем значение по этому индексу с искомым:

84 > 82

Сдвигаем правую границу:

right = mid = 14

Шаг 3. Ищем индекс середины массива (округляем в меньшую сторону):

mid = (9+14)/2=11

Сравниваем значение по этому индексу с искомым:

78 < 82

Сдвигаем левую границу:

left = mid = 11

Шаг 4. Ищем индекс середины массива (округляем в меньшую сторону):

mid = (11+14)/2=12

Сравниваем значение по этому индексу с искомым:

80 < 82

Сдвигаем левую границу:

left = mid = 12

Шаг 5. Ищем индекс середины массива (округляем в меньшую сторону):

mid = (12+14)/2=13

Сравниваем значение по этому индексу с искомым:

82 = 82

Сложность:

Форматы представления данных

Программа использует следующие переменные:

Таблица 1 – Переменные, используемы в программе

Имя	Тип	Описание
arr	int*	Массив для сравнения
size	size	Размер массива
file_name	сhar[]	Имя файла
is_successful	bool	Корректность тестов
a,b	int	Интервал от a до b

Cтруктура программы

Таблица 2 – Функции, составляющие программу

Имя	Описание
SortedArr	Сортировка по не убыванию
BinSearch	Бинарный поиск
ArrayCompare	Проверка вхождения числа из интервала в заданный массив
InputArrConsole	Ввод массива через консоль
InputArrFile	Ввод массива через файл
SaveResult	Сохранить результат в файл
CheckFileName	Проверка имени файла

Описание хода выполнения лабораторной работы

Для осуществления быстрого поиска в заданном массиве необходимо было его отсортировать.
После через отдельную функцию мы сравниваем число из интервала с заранее заданным массивом. Если число из интервала не было найдено, то оно отсеивалось в отдельный массив, который передавался во внешнюю функцию.
Далее предлагается повторить программу или же сохранить результат.

Результаты работы программы

В результате вычислений программа выводит список чисел, которые не входят в заданный массив. Данный список можно сохранить в отдельный файл.

Исходный текст программы

[ Начало программы ---]

#include

#include

#include

#include "Algol.h"

#include "Test.h"
using namespace std;
// Команды программы;

enum YesNo { YES = 1, NO = 0 };

enum DilogResault { Console = 1, File, Unit_Test };

enum End { Exit, Restart, SaveRes };
struct File_path;
//!!!! Нельзя указывать файл, в пути которого есть кириллица или пробелы !!!!
// Сохранение результата

bool SaveResult(int *arr, int size, int a, int b)

{

//char file_name[255];

cin.ignore();

cout << "Input file name:";
char file_name[255];

gets_s(file_name);
ifstream temp_file;

ofstream fileToSave;

temp_file.open(file_name);

temp_file.seekg(0, ios::end);

int lenght = temp_file.tellg();

temp_file.close();

if (lenght > 0)

{

// Если файл не пустой.

cout << "Want overwrite a file ? Yes-1, No-0" << endl;

while (true)

{

int result = ValNum();

if (result == YES)

{

fileToSave.open(file_name, ios::out);

if (fileToSave.is_open() && CheckFileName(file_name)) {

fileToSave << "Range: " << a << "..." << b << endl;

if (size > 0) {

fileToSave << "Missing items:" << endl;

for (int i = 0; i < size; i++)

fileToSave << arr[i] << " ";

}

else

{

fileToSave << "Missing items: Empty!" << endl;

}

cout << "Done!" << endl;
fileToSave.close();

return true;

}

else {

fileToSave.close();

cout << "Error file name!";

return false;

}

break;

}

else if (result == NO)

{

return false;

}

}

}

else if (lenght <= 0) {
fileToSave.open(file_name, ios::out);

if (fileToSave.is_open() && CheckFileName(file_name)) {

fileToSave << "Range: " << a << "..." << b << endl;

if (size > 0) {

fileToSave << "Missing item:" << endl;

for (int i = 0; i < size; i++)

fileToSave << arr[i] << " ";

}

else

{

fileToSave << "Missing items: Empty!" << endl;

}

cout << "Done!" << endl;

fileToSave.close();

return true;

}

else {

fileToSave.close();

cout << "Error file name!";

return false;

}

}

fileToSave.close();

temp_file.close();

}
// Проверка ввода

int ValNum() {

int num = 0;

do {

cin >> num;

if (cin.fail()) {

cin.clear();

cin.ignore(INT_MAX, '\n');

cout << "Input error, enter the number:" << endl;

}

else

return num;

} while (true);

}
int main() {
int *arr;

int global_size = 0;

int a, b;

while (true) {

for (int i = 0; i < 1;) {

cout << "Input: Console-1, File-2, Modul test-3" << endl;

int result = ValNum();

switch (result) {

case Console: {

for (;;) {

int size;

cout << "Input lower limit :";

a = ValNum();

cout << "Input upper limit :";

b = ValNum();

if (a <= b) {

cout << "Input array size: ";

size = ValNum();

if (size > 0) {

arr = new int[size];

InputArrConsole(arr, size);

if (size > 0) {

SortedArr(arr, size);

arr = ArrayCompare(arr, size, a, b);

cout << "Missing items: " << endl;

for (int j = 0; j < size; j++)

cout << arr[j] << " ";

cout << endl;

global_size = size;

i++;

}

else {

global_size = 0;

cout << "Missing items: Empty!" << endl;

i++;

}

break;

}

else cout << "The size of the array to be compared should be> 0!" << endl;

}

else cout << "The lower limit can not be greater than the upper limit!" << endl;

}

break;

}

case File: {

int size;

bool is_okey = false;

cin.ignore();

cout << "Input file name:";

char file_name[255];

gets_s(file_name);

ifstream file(file_name);

if (file.is_open() && CheckFileName(file_name)) {

file.close();

arr = new int[1];

try {

arr = InputArrFile(arr, size, file_name, a, b, is_okey);

if (is_okey) {

if (size > 0)

{

SortedArr(arr, size);

arr = ArrayCompare(arr, size, a, b);

cout << "Missing items: " << endl;

for (int j = 0; j < size; j++)

cout << arr[j] << " ";

cout << endl;

global_size = size;

i++;

}

else {

global_size = 0;

i++;

}

}

}

catch (exception e) {
}

}

else

{

cout << "Can not open file!" << endl;

}

break;

}

case Unit_Test: {

ModulTest();

break;

}

default: cout << "No such command, please try again!" << endl;

}

}

for (int j = 0; j < 1;) {

cout << "Input : Exit-0, Repeat-1, Save result-2" << endl;

int result = ValNum();

switch (result) {

case Restart: {

j++;

}break;

case SaveRes: {

SaveResult(arr, global_size, a, b);

}break;

case Exit: {

exit(1);

}

default: cout << "No such command, please try again!" << endl;

}

}

}

}
// Сортировка массива

void SortedArr(int *arr, int size)

{

for (int i = size - 1; i >= 1; i--)

for (int j = 0; j < i; j++) {

if (arr[j] > arr[j + 1]) {

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}
// Бинарный поиск в массиве;

// Работает только в отсортированном массиве по не убыванию!;

int BinSearch(int* arr, int count, int key)

{

//for (int i = 0; i < count; i++)

// cout << arr[i] << " ";

int qwqr = _msize(arr) / sizeof(arr[0]);
int l = 0; // нижняя граница

int u = count - 1; // верхняя граница

while (l <= u) {

int m = (l + u) / 2;

int temp = arr[m];

if (arr[m] == key) return m;

if (arr[m] < key) l = m + 1;

if (arr[m] > key) u = m - 1;

}

return -1;

}
// Сравнение интервала с массивом;

int* ArrayCompare(int *arr, int &size, int a, int b)

{

int *notExistNum = new int[abs(a - b) + 1];

try {

int key = a;

int i = 0;

for (i = 0; key <= b; key++) {

if (BinSearch(arr, size, key) == -1) {

notExistNum[i] = key;

i++;

}

}

size = i;

return notExistNum;

}

catch (exception)

{

cout << "Error!" << endl;

return notExistNum;

}

}
// Ввод массива через консоль

void InputArrConsole(int *arr, int size)

{

for (int i = 0; i < size; i++) {

cout << "arr[" << i << "] = ";

arr[i] = ValNum();

}

}
// Ввод массива через файл

int* InputArrFile(int *arr, int &size, char *name, int &a, int &b, bool &is_ok)

{

is_ok = true;

ifstream file(name);

if ((int)file.tellg() == -1) is_ok = false;

int *temp_arr = new int[10];

char *temp = new char;

int value = 0;

int count = 0;

int i = 0;

bool is_sign = false;

for (i = 0; !file.eof() && is_ok;)

{

file >> temp;

if (!strcmp(temp, "") && count == 0) {

is_ok = false;

break;

}

else

{

count++;

}

char ch = temp[0];

if (ch == '-') is_sign = true;

if (strlen(temp) != 1)

while (value < strlen(temp))

{

if (is_alpha(temp[value]))

{

is_ok = false;

break;

}

else

value++;

}

if (is_ok)

{

try

{

if (isdigit(ch) && strlen(temp) == 1)

continue;

else

{

if (is_sign) continue;

if (!isdigit(ch) && strlen(temp) == 1)

{

is_ok = false;

break;

}

}
for (int j = 1; j < strlen(temp); j++)

{

if (!isdigit(temp[j]))

{

is_ok = false;

break;

}

if (!is_ok)

break;

}

}

catch (exception e)

{

is_ok = false;

}

}

}

file.close();
if (is_ok)

{

file.open(name);

file >> a;

file >> b;

if (a <= b)

{

for (i = 0; !file.eof();)

{

file >> temp;

if (!strcmp(temp, "")) break;

value = atoi(temp);

temp_arr[i] = value;

i++;

}

size = i;

if (size > 0)

{

cout << "Range: " << a << "..." << b << endl;

cout << "Items from file: " << endl;

for (i = 0; i < size; i++)

cout << "arr[" << i << "] = " << temp_arr[i] << endl;

is_ok = true;

return temp_arr;

}

else

{

if (a <= b && size == 0) {

cout << "Missing items: Empty!" << endl;

is_ok = true;

}

else

{

cout << "File is empty!" << endl;

is_ok = false;

}

}

}

else

{

cout << "The lower limit can not be greater than the upper limit!" << endl;

is_ok = false;

}

file.close();

}

else

{

cout << "The file contains incorrect data!" << endl;

is_ok = false;

}

}
// Функция проверки символа;

// Параметры: t - символ для проверки;

bool CheckChar(char t) {

if ((t >= '0' && t <= '9') ||

(t >= 'A' && t <= 'Z') ||

(t >= 'a' && t <= 'z') ||

(t >= 'А' && t <= 'Я') ||

(t >= 'а' && t <= 'я'))

return 1;

else

return 0;

}
bool is_alpha(char t)

{

if ((t >= 'A' && t <= 'Z') ||

(t >= 'a' && t <= 'z') ||

(t >= 'А' && t <= 'Я') ||

(t >= 'а' && t <= 'я'))

return 1;

else

return 0;

}

// Структура пути файла;

struct File_path {

char *full_name = new char;

char name[255] = {};

char *expansion = new char;

};
// Функция проверки корректности имени файла;

// Параметры: path - путь файла;

bool CheckFileName(char path[]) {

setlocale(LC_ALL, "Russian");

char *reserved_names[] = { "CON", "PRN", "AUX", "NUL", "COM1",

"COM2", "COM3", "COM4", "COM5", "COM6", "COM7", "COM8",

"COM9", "LPT1", "LPT2", "LPT3", "LPT4", "LPT5", "LPT6",

"LPT7", "LPT8", "LPT9" };

File_path file;

bool is_correct_name = true;

int index_rslash = 0;

int index_dot = 0;

// Длина строки пути файла;

int length = strlen(path) - 1;

// Индексы последнего вхождения '/' и '.';

for (index_rslash = length; path[index_rslash] != '\\'

&& index_rslash > 0; index_rslash--);

for (index_dot = length; path[index_dot] != '.'

&& index_dot > 0; index_dot--);

// Парсинг пути файла;

if (index_rslash != index_dot &&

index_rslash < index_dot &&

CheckChar(path[0])) {

// Решение: относительно какого индекса выделять имя

if (index_rslash == 0)

file.full_name = &path[0];

else

file.full_name = &path[index_rslash + 1];

// Формируем имя файла;

for (int i = 0; i < strrchr(file.full_name, '.') - file.full_name; i++)

file.name[i] = file.full_name[i];

// Формируем расширение файла;

file.expansion = &path[index_dot + 1];

for (int i = 0; i < sizeof(reserved_names) / sizeof(*reserved_names); i++) {

if (!_stricmp(file.name, reserved_names[i])) {

is_correct_name = false;

break;

}

}

if (is_correct_name == 1) return 1;

else return 0;

}

else return 0;

}

[--- Конец программы.]

отчет по с. Отчёт. Напишите программу, находящую значение из заданного интервала, отсутствующее в массиве

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

Исходные данные

Особые ситуации

Математические методы и алгоритмы решения задач

Форматы представления данных

Cтруктура программы

Описание хода выполнения лабораторной работы

Исходный текст программы