Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Оснащения врачебно-сестринской бригады.
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2018-01-04 | 109 |
5.00
из
|
Заказать работу |
|
|
/*
Функции поиска в массивах
*/
#pragma once
#include "stdafx.h"
//
// Прототипы функций
//
int Find1_1(int A[], int n, int Val);
// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)
// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует
int Find1_2(int A[], int n, int Val);
// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)
// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует
int Find2(int A[], int n, int Val);
// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений
// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует
//
// Реализация
//
int Find1_1(int A[], int n, int Val)
// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)
{
int i = 0;
while (i < n)
{
if (A[i] == Val)
return i;
++i;
}
return -1;
}
int Find1_2(int A[], int n, int Val)
// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)
// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует
{
for (int i = 0; i < n; ++i)
if (A[i] == Val)
return i;
return -1;
}
int Find2(int A[], int n, int Val)
// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений
// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует
{
if ((Val < A[0]) || (Val > A[n - 1])) // Отсеиваем заведомо не входящие в массив значения
return -1;
int a = 0, b = n - 1, c;
while (b >= a)
{
c = (a + b) / 2; // Находим в интервале [а, b] индекс срединного элемента - с
if (Val > A[c]) // Искомое значение справа от с
a = c + 1; // Заменяем левую границу интервала поиска
else
if (Val < A[c]) // Искомое значение слева от с
b = c - 1; // Заменяем правую границу интервала поиска
|
else // Val == A[c]
return c; // Индекс искомого элемента - с
}
return -1;
}
Программа для проверки функций поиска в массивах:
/*
Find.cpp: определяет точку входа для консольного приложения.
Заголовочные файлы arr_common.h, arr_sort.h и my_rand.h должны находиться в папке этого проекта, либо путь к ним должен быть указан в настройках параметров проекта:
Меню среды: Проект – Свойства – Свойства конфигурации – Каталоги VC++ - Каталоги включения и добавляем здесь путь к нашим заголовочным файлам
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include "arr_common.h"
#include "arr_sort.h"
#include "arr_find.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0, "");
const int N = 1000;
int M[N], V, Ind;
setlocale(0, "");
RandInit(); // Инициализируем датчик случайных чисел (#include "my_rand.h")
cout << " Проверка алгоритма бинарного поиска.\n";
cout << " ------------------------------------\n";
RandMakeArr(M, N, 1, 1000); // Заполняем массив случайными чиселами (#include "my_rand.h")
Sort2(M, N, 1); // Сортируем массив М из N элементов (#include "arr_sort.h")
ArrOut(M, N); // Выводим отсортированный массив на экран
for (char b = '1'; b!= 27; cout << "\n\t\t\tПродолжим? (нет - Esc)",
b = _getch(), cout << endl)
{
cout << "\nКакое значение надо найти? ";
cin >> V; // Вводим значение для поиска
Ind = Find2(M, N, V); // Поиск V в массиве М из N элементов бинарным поиском
if (Ind!= -1)
cout << "Индекс значения " << V << " равен " << Ind << endl;
else
cout << "Значение " << V << " не найдено" << endl;
}
return 0;
}
Приложение 2. Функции стандартного ввода/вывода в стиле C (printf, scanf)
Автор: Бардин П.Б.
Введение
Стандартная библиотека C/C++ включает ряд функций для чтения и записи на консоли (клавиатура и монитор). Эти функции читают и пишут данные, как простой поток символов.
Понятие потока (stream), использованное в программировании, тесно связано с обычным, бытовым пониманием этого слова. Поток ввода можно сравнить с трубой, по которой вода (информация) поступает в бассейн (память компьютера), поток вывода - с трубой, по которой вода выходит из бассейна. Важной особенностью этой трубы является то, что в каждый момент времени данные могут двигаться только в одном направлении. Даже если одна и та же труба используется для ввода и вывода, это не может происходить одновременно: для переключения направления потока его нужно остановить, выполнить некие действия и лишь затем направить поток в обратном направлении. Другой особенностью потока является то, что он почти никогда не иссякает. Иногда он высыхает, но этот период не может быть долгим, если система функционирует нормально.
|
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!