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

Алгоритмы перебора с возвратом

Выполнил:

Студент 2 курса группы 120811

Специальности 351500 – МОиАИС

Сафонов Алексей Александрович

Научный руководитель:

к.п.н., доцент,

Ваныкина Г.В.

Тула – 2013

Оглавление

Введение

Глава 1

1. Постановка задачи поиска данных

2. Классификация переборных алгоритмов

Глава 2

1. Постановка задачи о расстановки ферзей на шахматной доске

2. Общее и частное решение задачи о расстановки ферзей

3. Алгоритм перебора с возвратом

4. Разработка пв сфере разработки программ. Рекурсивные алгоритмы позволяют кратко и компактно разработать программный код. Однако рекурсивные алгоритмы не всегда эффективны. В настоящей работе рассматривается пример эффективного применения рекурсивного алгоритма.

Таким мы, реализующей перебор с возвратом в задаче о расстановке ферзей на шахматной доске.

· Необходимостью выполнить тестирование разработанного программного кода.

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

4. Выполнить тестирование проекта на компьютере и исправить выявленные в его ходе ошибки

Глава 1. Алгоритмы перебора данных их классификация

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

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

Можно классифицировать методы поиска несколькими спета на вопрос где искать, например, на числах надо приступить к тому, что надо искать и какой алгоритм применить. На примере в текущем случаи можно взять поиск простого числа с исходным кодом на языке программирования С:

#include "stdafx.h"

#include <stdiint argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"");

int N;

printf ("\nВведите целое число ");

scanf ("%d",&N);

if (opredelenie (N))

printf ("Число %d - составное \n", N);

else printf ("Число %d - простое \n", N);

system("pause");

return 0;

}

Но поисся с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

· Эвристика стоп-символа. Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней буквы «к».

· Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Поиск существует и в массивах. К основным алгоритмам поиска данных в массивах относятся: дихотомический поиск, двоичный (или бинарный) поиск, линейный поиск (или поиск лоб).

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

Линейный поиск. Алгоритм линейного поиска в массивах последовательно проверяет все элементы массива и сравнивает их с ключевым значением. Таким образом, в среднем необходимо проверить половину значений в массиве, чтобы найти искомое значение. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива [5].

Дата добавления: 2015-11-26