Объектно-ориентированное программирование» для студентов специальности 5В070300 «Информационные системы» идля оп 6В06120 «Информационные системы» Шымкент 2022
Поиск элементов в массиве по значению
жүктеу/скачать 1,44 Mb.
|
ООП ЛЕКЦИОННЫЙ КОМПЛЕКС 2022рус (1)
| Поиск элементов в массиве по значению
Половину книги «Искусство программирования» (том 3 посвящен вопросам «сортировки и поиска») Д. Кнут посвятил вопросам поиска элементов по значению в некотором множестве однотипных элементов (массив, файл , так далее.). Это показывает, насколько важно знать алгоритм поиска при изучении программирования. Среди различных методов поиска мы рассмотрим алгоритмы и программную реализацию только трех из них — бинарного, блочного и цепного методов поиска по значению элемента в массиве. Мы рассматриваем метод поиска перемешиванием только на уровне алгоритма. Нам нужен только алгоритм нахождения значений элементов массива, поэтому мы рассматриваем все алгоритмы для целочисленных элементов. Мы представляем целое число для поиска в «массиве поиска», т.е. массиве случайно сгенерированных целых чисел - «ключе поиска». 6.3.1 Алгоритм поиска последовательности. Алгоритм поиска цепочки элементов основан на последовательном сравнении искомого ключа со всеми элементами массива, то есть от первого элемента до последнего элемента. Если был просмотрен последний элемент массива, то поиск завершается. Для демонстрации этого алгоритма его сравнивают с алгоритмом нахождения нужной страницы книги, например, трехсотой страницы, путем последовательного перелистывания каждой страницы от первой до трехсотой страницы. Недостатком этого алгоритма является то, что при большом количестве элементов массива поиск занимает много времени. Время поиска пропорционально числу N, где N — количество элементов массива. Преимущество алгоритма в том, что он позволяет размещать элементы в массиве в любом порядке или не по порядку. Задача 6.2. Массив поиска состоит из 20 случайных целых чисел от 0 до 99. В диалоговом режиме в качестве ключа для поиска задается любое целое число. Вам нужно найти, сколько раз это число (и его индексы) встречается в массиве поиска. Использование алгоритма цепного поиска. Поскольку алгоритм известен, приступаем к созданию программного кода. using System; namespace ConsoleApplication1 { class Program { static void Main() { int i,k,n; int[] a = new int[20]; int[] p = new int[20]; Random rnd = new Random(); string buf; // создать массив и вывести на экран Console.WriteLine("Izdestiry massivi: "); for (i=0;i<10;i++) Console.Write(" {0}", i); for (i=10;i<20;i++) Console.Write(" {0}", i); Console.WriteLine(); for (i = 0; i < 20; i++) { a[i] = rnd.Next()%100; if (a[i]>9) Console.Write(" {0}", a[i]); else Console.Write(" {0}", a[i]); } Console.WriteLine(); Console.WriteLine("Izdey kiltin engiziniz "); buf = Console.ReadLine(); k = Convert.ToInt32(buf); n=0; // поиск элементов массива по ключу поиска for (i=0;i<20;i++) if (k == a[i]) {p[n]=i; n++;} if (n==0) Console.WriteLine("Izdey kiltine saikes element jok!!"); else { Console.WriteLine("Izdey kiltine saikes keletin elementter sani = {0}",n); Console.WriteLine("Tabilgan indexter: "); for (i=0;i Console.WriteLine(); } Console.ReadLine(); } } } Работа программы: Izdestiry massivi: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 43 68 85 72 14 44 45 55 57 30 94 83 52 72 77 92 0 91 29 97 Izdey kiltin engiziniz 91 Izdey kiltine saikes keletin elementter sani = 1 Tabilgan indexter: Алгоритм поиска блоков. Алгоритм блочного поиска требует, чтобы элементы поискового массива располагались упорядоченно, например, элементы узлов в порядке возрастания или убывания, в алфавитном порядке и т. д. Поиски могут выполняться только с использованием элемента узла массива поиска, где элемент узла управляет массивом поиска. Предположим, что элементы массива поиска расположены в порядке возрастания значения. Весь поисковый массив условно разбивается на блоки, например, один блок содержит сто элементов. Ключ поиска запроса последовательно сравнивается с последним элементом каждого блока, начиная с первого блока. Если искомый ключ запроса больше, чем последний элемент следующего блока массива, то необходимо перейти к последнему элементу следующего блока, в противном случае необходимо выполнить цепной поиск в блоке, где последний сравнение было выполнено. Преимущество этого алгоритма в том, что поиск занимает меньше времени, чем предыдущий алгоритм. Время поиска пропорционально сумме блоков в массиве поиска и количеству элементов в одном блоке. Изменяя размер блока, вы можете регулировать скорость поиска на определенном уровне. Недостатки алгоритма: большое время поиска, подготовка массива поиска, т.е. сортировка по элементу узла. жүктеу/скачать 1,44 Mb. Достарыңызбен бөлісу:
|