Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2018-01-04 | 110 |
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), использованное в программировании, тесно связано с обычным, бытовым пониманием этого слова. Поток ввода можно сравнить с трубой, по которой вода (информация) поступает в бассейн (память компьютера), поток вывода - с трубой, по которой вода выходит из бассейна. Важной особенностью этой трубы является то, что в каждый момент времени данные могут двигаться только в одном направлении. Даже если одна и та же труба используется для ввода и вывода, это не может происходить одновременно: для переключения направления потока его нужно остановить, выполнить некие действия и лишь затем направить поток в обратном направлении. Другой особенностью потока является то, что он почти никогда не иссякает. Иногда он высыхает, но этот период не может быть долгим, если система функционирует нормально.
|
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!