мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Следующая версия | Предыдущая версияСледующая версияСледующая версия справа и слева | ||
pascal4beginners-algorithm [24/01/2012 11:15] – создано oca | pascal4beginners-algorithm [24/01/2012 11:26] – oca | ||
---|---|---|---|
Строка 3: | Строка 3: | ||
=== Поиск в неупорядоченном массиве === | === Поиск в неупорядоченном массиве === | ||
+ | Источник [[http:// | ||
+ | |||
+ | Рассмотрим сначала нюансы реализации “технических” задач поиска, | ||
< | < | ||
+ | a: | ||
</ | </ | ||
+ | |||
+ | при этом собственно элементы массива, | ||
+ | < | ||
+ | i:=0; | ||
+ | repeat | ||
+ | i:=i+1 | ||
+ | until (i=N) or (a[i]=K); | ||
+ | |||
+ | if a[i]=K then write(i) | ||
+ | else write(0) | ||
+ | |||
+ | {следующее неверно (!!!): | ||
+ | if i=N then write(0) | ||
+ | else write(i) } | ||
+ | </ | ||
+ | |||
+ | |||
+ | При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, | ||
+ | < | ||
+ | a[0]:=K; | ||
+ | i:=N; | ||
+ | |||
+ | while (a[i]<> | ||
+ | i:=i-1; | ||
+ | | ||
+ | write(i) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку. | ||
+ | Другой полезный прием можно показать на задаче поиска максимального и минимального значения в массиве. Состоит он в том, что при любом поиске в массиве искать следует не значение искомого элемента, | ||
+ | < | ||
+ | imax:=1; | ||
+ | |||
+ | imin:=1; | ||
+ | |||
+ | for i:=2 to N do | ||
+ | |||
+ | if a[i]< | ||
+ | |||
+ | if a[i]> | ||
+ | </ | ||
+ | |||
+ | |||
+ | Заметим, | ||
+ | < | ||
+ | max: | ||
+ | min: | ||
+ | |||
+ | for i:=1 to N do | ||
+ | if a[i] | ||
+ | if a[i]>max then max:=i | ||
+ | </ | ||
+ | |||
+ | |||
+ | Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, | ||
+ | |||
+ | Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, | ||
+ | |||
+ | В данном контексте можно поставить также задачу поиска i-го по счету элемента, | ||
+ | |||
+ | Алгоритм Выбор(A, | ||
+ | {выбирает между L-ым и R-ым элементами массива A | ||
+ | i-ый по счету в порядке возрастания элемент} | ||
+ | 1. if L=R then результат – A[L], конец; | ||
+ | 2. Q: | ||
+ | {Q – случайный элемент между L и R} | ||
+ | 3. Переставляем элементы от L до R в A так, чтобы сначала шли элементы, | ||
+ | 4. if i<=(K-L) then Выбор(A, | ||
+ | else Выбор(A, | ||
+ | 5. конец. | ||
+ | |||
+ | Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки. | ||
+ | Наконец, | ||
+ | < | ||
+ | S:=0; | ||
+ | for i:=1 to N do | ||
+ | begin | ||
+ | read(a); S:=S+a | ||
+ | end; | ||
+ | writeln(N*(N + 1) div 2 – S) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, | ||
+ | |||
+ | Сноски: | ||
+ | Обозначение [] соответствует для неотрицательных чисел округлению до ближайшего целого числа, большего или равного выражению в указанных скобках, | ||
+ | |||
+ |