Top-office11.ru

IT и мир ПК
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Линейный поиск в массиве паскаль

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Pascal: Занятие № 5. Одномерные массивы в Паскале

Одномерные массивы в Паскале

Объявление массива

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

var dlina: array [1..3] of integer; begin dlina[1]:=500; dlina[2]:=400; dlina[3]:=150; .

Объявить размер можно через константу:

Инициализация массива

Кроме того, массив может быть сам константным, т.е. все его элементы в программе заранее определены. Описание такого массива выглядит следующим образом:

const a:array[1..4] of integer = (1, 3, 2, 5);

Заполнение последовательными числами:

Ввод с клавиатуры:

writeln (‘введите кол-во элементов: ‘); readln(n); <если кол-во заранее не известно, - запрашиваем его>for i := 1 to n do begin write(‘a[‘, i, ‘]=’); read(a[i]); . end; .


✍ Пример результата:

Вывод элементов массива

var a: array[1..5] of integer; <массив из пяти элементов>i: integer; begin a[1]:=2; a[2]:=4; a[3]:=8; a[4]:=6; a[5]:=3; writeln(‘Массив A:’); for i := 1 to 5 do write(a[i]:2); <вывод элементов массива>end.

Для работы с массивами чаще всего используется в Паскале цикл for с параметром, так как обычно известно, сколько элементов в массиве, и можно использовать счетчик цикла в качестве индексов элементов.

Функция Random в Pascal

Для того чтобы постоянно не запрашивать значения элементов массива используется генератор случайных чисел в Паскаль, который реализуется функцией Random . На самом деле генерируются псевдослучайные числа, но суть не в этом.

var f: array[1..10] of integer; i:integer; begin randomize; for i:=1 to 10 do begin f[i]:=random(10); < интервал [0,9] >write(f[i],’ ‘); end; end.

Для вещественных чисел в интервале [0,1):

var x: real; . x := random;

Числа Фибоначчи в Паскале

Наиболее распространенным примером работы с массивом является вывод ряда чисел Фибоначчи в Паскаль. Рассмотрим его.

Получили формулу элементов ряда.

var i:integer; f:array[0..19]of integer; begin f[0]:=1; f[1]:=1; for i:=2 to 19 do begin f[i]:=f[i-1]+f[i-2]; writeln(f[i]) end; end.

На данном примере, становится понятен принцип работы с числовыми рядами. Обычно, для вывода числового ряда находится формула определения каждого элемента данного ряда. Так, в случае с числами Фибоначчи, эта формула-правило выглядит как f[i]:=f[i-1]+f[i-2] . Поэтому ее необходимо использовать в цикле for при формировании элементов массива.

Максимальный (минимальный) элемент массива

Псевдокод:

Поиск максимального элемента по его индексу:

Пример:

Поиск в массиве

Рассмотрим сложный пример работы с одномерными массивами:

var f: array[1..10] of integer; flag:boolean; i,c:integer; begin randomize; for i:=1 to 10 do begin f[i]:=random(10); write(f[i],’ ‘); end; flag:=false; writeln(‘введите образец’); readln(c); for i:=1 to 10 do if f[i]=c then begin writeln(‘найден’); flag:=true; break; end; if flag=false then writeln(‘не найден’); end.

Рассмотрим эффективное решение:

Задача: найти в массиве элемент, равный X , или установить, что его нет.

Алгоритм:

  • начать с 1-го элемента ( i:=1 );
  • если очередной элемент ( A[i] ) равен X , то закончить поиск иначе перейти к следующему элементу.

решение на Паскале Вариант 2. Цикл While:

Поиск элемента в массиве

Предлагаем посмотреть подробный видео разбор поиска элемента в массиве (эффективный алгоритм):

Пример:

Циклический сдвиг

Программа:

Перестановка элементов в массиве

Рассмотрим, как происходит перестановка или реверс массива.

Решение:

Псевдокод:

Программа:

Выбор элементов и сохранение в другой массив

Решение:


Вывод массива B:

writeln(‘Выбранные элементы’); for i:=1 to count-1 do write(B[i], ‘ ‘)

Сортировка элементов массива

  • В таком типе сортировок массив представляется в виде воды, маленькие элементы — пузырьки в воде, которые всплывают наверх (самые легкие).
  • При первой итерации цикла элементы массива попарно сравниваются между собой:предпоследний с последним, пред предпоследний с предпоследним и т.д. Если предшествующий элемент оказывается больше последующего, то производится их обмен.
  • При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой. Значит, число сравнений будет на одно меньше. То же самое касается каждой последующей итерации.

Выполнение на Паскале:

for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; end;

  • в массиве ищется минимальный элемент и ставится на первое место (меняется местами с A[1]);
  • среди оставшихся элементов также производится поиск минимального, который ставится на второе место (меняется местами с A[2]) и т.д.
Читать еще:  Php if function

Выполнение на Паскале:

for i := 1 to N-1 do begin min:= i ; for j:= i+1 to N do if A[j] i then begin c:=A[i]; A[i]:=A[min]; A[min]:=c; end; end;

    Выбирается и запоминается средний элемент массива (присвоим X):

  • Инициализируем две переменные (будущие индексы массива): L:=1, R:=N (N — количество элементов).
  • Увеличиваем L и ищем первый элемент A[L], который больше либо равен X (в итоге он должен находиться справа).
  • Уменьшаем R и ищем элемент A[R], который меньше либо равен X (в итоге он должен находиться слева).
  • Смотрим, если L X do R:= R — 1; if L

    Posted in

    См. пузырьковая сортировка.
    При второй итерации цикла (согласно вашим рисункам и коду ) нет надобности сравнивать первый элемент со вторым. Снова вы всех путаете =)

    admin

    Именно поэтому в коде : for j:=N-1 downto i do

    downto i — то есть мы доходим сначала до первого элемента, потом до второго и т.д.

    Bronislav

    Смотрите. Ваш код работает. Но работает не так, как вы пишете перед этим. Он просеивает минимальный элемент с конца через весь массив до первой позиции (первого индекса если хотите). А не так как вы пишете: «При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой.» Соответственно вашему коду и вашим рисункам на второй итерации не сравнивается первый элемент (минимальный) со вторым, а не последний (который вообще не факт что максимальный) с предпоследним. Вот об чем речь. Или код меняйте или описание алгоритма перед кодом.

    Владимир

    А как насчёт странного способа поменки оандомням образом, конечно это долго , но все таки есть
    Var
    A: array[1..10] of integer;
    I,e,r,r1: integer;
    Begin
    While i at 02:05

    В сохранении в другой массив ошибка. Надо поменять местами счётчик и команду сохранения. В массиве В нет элемента 0.

    Поиск

    Пусть дан массив элементов A и ключ b. Для b необходимо найти совпадающий с ним элемент массива А. Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что достигается использованием стоппера (барьерного элемента). Рассмотрим 2 примера:

    1)без использования стоппера

    var A:array[0..N-1] of Any;

    writeln(‘Введите элементы массива:’);

    for i:=0 to N-1 do

    while (i<>N) and (A[i]<>b) do

    writeln(‘Элемент, совпадающих с ключом, найден. Позиция элемента -‘,i+1)

    writeln(‘Элементов, совпадающих с ключом, нет’);

    2) с использованием стоппера

    var A:array[0..N] of Any;

    writeln(‘Введите элементы массива:’);

    for i:=0 to N-1 do

    writeln(‘Элемент, совпадающих с ключом, найден. Позиция элемента -‘,i+1)

    writeln(‘Элементов, совпадающих с ключом, нет’);

    Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае, и затраты времени для больших массивов поэтому велики.

    Применяется данный алгоритм, если никакой дополнительной информации о данных массива нет.

    Бинарный поиск

    Очевидно, что нельзя каким-либо способом ускорить поиск, если отсутствует информация о данных, среди которых производится поиск. Также известно, что если данные упорядочены, то поиск можно сделать значительно эффективнее. Поэтому рассмотрим алгоритм, который основан на том, что массив A упорядочен (т. е. a[i-1]

    Суть: берут средний элемент массива и сравнивают его с ключом. В результате возможны 3 случая:

    1) если элемент массива равен ключу, то искомый элемент найден;

    2)если элемент массива меньше ключа, то все элементы массива с индексами, которые меньше N/2 исключаются из рассмотрения;

    3)если элемент массива больше ключа, то все элементы массива с индексами, которые больше N/2 исключаются из рассмотрения;

    Затем поиск продолжается в одной из половин массива аналогичным образом.

    var A:array[0..N] of Any;

    writeln(‘Введите упорядоченную последовательность эл-тов массива ‘);

    for i:=0 to N do readln(A[i]);

    m:=(Left+Right) div 2;

    if (Right<>N) or ((Right=N) and (a[N]=b)) then

    writeln(‘ Эл — т найден . Позиция эл-та: ‘,Right)

    writeln(‘ Элемента нет ‘);

    Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log2(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного — как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства этого приведу следующие характеристики линейного и бинарного поиска:

    Читать еще:  Как включить игру в безопасном режиме

    1) линейный поиск:

    среднее количество сравнений при наличии элемента:5

    количество сравнений при отсутствии элемента:10

    среднее количество сравнений при наличии элемента:500

    количество сравнений при отсутствии элемента:1000

    среднее количество сравнений при наличии элемента:500000

    количество сравнений при отсутствии элемента:1000000

    1) бинарный поиск:

    максимальное количество сравнений при наличии элемента:8

    максимальное количество сравнений при отсутствии элемента:8

    максимальное количество сравнений при наличии элемента:10

    максимальное количество сравнений при отсутствии элемента:10

    максимальное количество сравнений при наличии элемента:20

    максимальное количество сравнений при отсутствии элемента:20

    Интерполяционный поиск

    Представим себе поиск слова в словаре. Маловероятно, что мы сначала заглянем в середину словаря, затем отступим от начала на 1/4 или 3/4 и т.д, как в бинарном поиске.

    Если нужное слово начинается с буквы ‘А’, то и поиск имеет смысл начинать в начале словаря. Когда же найдена отправная точка для поиска, дальнейшие действия будут мало похожи на рассмотренные выше методы.

    Мы приходим к алгоритму, называемому интерполяционным поиском. Пусть задан массив записей R1,R2. Rk, снабженных соответственно ключами K1,K2. Kn. Необходимо найти запись с данным ключом K. Тогда, если известно, что K лежит между Kl и Ku, то следующую пробу делаем примерно на расстоянии (u-l)*(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно как арифметическая прогрессия.

    Интерполяционный поиск требует в среднем около log2 log2 N шагов, и поэтому он предпочтительнее бинарного при работе с большими массивами.

    Поиск подстроки в строке.

    Пусть дана строка s и подстрока p. Тогда для поиска подстроки p в строке s возможно использование следующего алгоритма:

    until (j=lp) or (i=lp-ls) or (i>ls);

    if (j=lp) and (lp<>1) then writeln(‘ Подстрока в строке есть ‘);

    if i<>ls then writeln(‘ Подстроки в строке нет ‘);

    Алгоритм является эффективным, если несовпадение символов строки и подстроки происходит после нескольких сравнений во внутреннем цикле. Но, если совпадение обнаружено в конце строки, то требуется lp*ls сравнений.

    Алгоритм Кнута, Морриса и Пратта (КМП)

    Этот алгоритм был создан в 1970 году и получил свое название от имен его разработчиков. Он состоит из двух этапов: подготовительного и основного.

    На подготовительном этапе учитывается структура подстроки. Для этого формируется массив D, в котором учитывается совпадения символов подстроки с началом подстроки следующим образом: нулевой элемент массива D получает значение равное -1. Далее для каждой позиции j, совпадающей с началом подстроки, вычисляется максимальное количество предшествующих ей символов. Если же совпадений нет, то соответствующий элемент массива D равен -1. Размерность массива D равна длине подстроки.

    Теперь рассмотрим основной этап. Поиск начинается со сравнения первого символа строки с первым символом подстроки. В случае несовпадения происходит сдвиг подстроки на количество символов, указанных соответствующим элементом массива D. Если совпадения подстроки со строкой не будет (то есть данной подстроки в строке нет), то программа выйдет из цикла для поиска подстроки, когда i будет равняться длине строки, то есть если ни один символ подстроки не совпадает ни с одним символом строки, то программа выполнит N сравнений, если же совпадения отдельных элементов подстроки(но не всей подстроки со строкой) будут найдены, то в наихудшем случае потребуется N+M сравнений. Если же совпадение подстроки со строкой обнаружится сразу, то потребуется M cравнений.

    Линейный поиск в массиве паскаль

    Продолжаем решать задачи с массивами, а точнее с поиском в массиве. Задачи в этой статье с сюжетом и требуют умелого использования циклов и условий. Добавилась задача с двумерным массивом. Если у вас свой взгляд на решение какой-либо задачи, не стесняйтесь, пишите!

    Задача 1.

    В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке вводится одно целое число x, не превосходящее по модулю 1000. Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.

    Число А называется ближайшим к Х , если модуль разности А-Х наименьший (|A-Х|). Если два числа будут находиться в одинаковой близости к числу Х, будем брать любой из них. В условии так и сказано.

    Когда решали задачу на нахождение максимального элемента массива, мы задавали «точку отсчета» (назову ее так), т.е. принимали первый элемент массива за максимальный. В этой задаче мы поступим аналогично, но таких «точек отсчета» будет две: 1. минимальный модуль разности; 2. Ближайший элемент массива.

    Рассмотрим код программы (Паскаль):

    В программе переменная raz отвечает за минимальный модуль разности — Первая «Точка отсчета», min — ближайший элемент массива к заданному числу X, вторая «Точка отсчета».

    Читать еще:  Html кавычки елочки

    Если найдется такой элемент массива, начиная со второго, который окажется меньше чем «точка отсчета», переменные raz и min переопределятся.

    Задача 2.

    В связи с визитом Императора Палпатина было решено обновить состав дроидов в ангаре 32. Из-за кризиса было решено новых дроидов не закупать, но выкинуть пару старых. Как известно, Палпатин не переносит дроидов с маленькими серийными номерами, так что все, что требуется — найти среди них двух, у которых серийные номера наименьшие.

    Формат входного файла

    Первая строка входного файла содержит целое число N – количество дроидов. (2 ≤ N ≤ 1000), вторая строка – N целых чисел, по модулю не превышающих 2*10 9 – номера дроидов

    Формат выходного файла

    Выведите два числа: первым – последний по величине из номеров дроидов (такого следует утилизировать в первую очередь), а вторым – предпоследний.

    После задания массива, состоящего из n элементов, мы проверяем: первый или второй элемент массива меньше. Это и есть наша «точка отсчета». Минимальный элемент — min. Min2 — элемент, стоящий после min (по условию задачи).

    Далее, в цикле от 3 до n мы проверяем: если элемент массива меньше чем min, то в переменную min2 мы записываем старое значение переменной min и переопределяем ее min:=mas[i]. Если это условие не выполняется (элемент массива больше min), мы проверим, может быть этот элемент меньше нашего второго значения min2.

    Линейный поиск в C++: подробное руководство

    Все программисты, при решении задач сталкивались с необходимостью проверить массив на наличие какого-то значения. Существует много алгоритмов для решения этой задачи. Все эти алгоритмы используются и в других языках программирования.

    Сегодня мы изучим самый простой для реализации алгоритм поиска (но и самый затратный по времени) — линейный поиск.

    Как работает линейный поиск

    Этот алгоритм перебирает все элементы в массиве, сравнивая их с заданным ключом, из-за полного перебора скорость поиска намного меньше, чем в других алгоритмах.

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

    Как создать линейный поиск

    Давайте посмотрим как работает линейный поиск на практике.В примере ниже мы создали массив на 20 элементов и заполнили его ячейки случайными числами с помощью функции rand .

    В строке 26 мы предлагаем пользователю с клавиатуры ввести ключ, а дальше мы проверим массив на наличие этого ключа. Если ключ совпал с какой-то ячейкой в массиве, то мы выведем индекс этой ячейки. Это типичный пример чтобы понять как работает алгоритм.

    Линейный поиск находится в строках 28 — 32.

    Давайте разберем этот пример:

    1. В строке 9 — 10: мы создали массив ans и переменную h (равную нулю).

    В массиве ans будут храниться все индексы.

    1. В строке 29: мы применили оператор ветвления if.
      • Если результат условия положительный , то в ячейку ans[h] присваиваем значение i , а переменную h увеличиваем на один.
    1. В строке 34: проверяем:
      • Если результат условия положителен , то выводим h первых элементов массива ans ;
      • Если же результат условия отрицателен , то выводим «Мы не нашли ключ key в массиве»

    Давайте выполним этот код:

    А если такого ключа нет в массиве :

    Использовать ли линейный поиск

    Из плюсов у этого алгоритма только одно — простая реализация.

    Минус один, но очень большой — код работает медленно.

    Мы советуем использовать его «чайникам» для решения их первых задач. Однако, если вы разрабатываете высоко нагруженное приложение или веб-сервер, такой поиск будет слишком затратным. Вам понадобятся более эффективные алгоритмы. Например, бинарный поиск. Он работает очень быстро и реализация не на много сложнее линейного поиска.

    Упражнение

    В качестве домашнего задания создайте массив из 10 ячеек заполнив его случайными числами от 1 до 10 (включительно). Предложите пользователю с клавиатуры ввести ключ и выведите сколько раз ключ совпадал со значением ячеек в массиве, используя при подсчете линейный поиск.

    Если вы будете использовать функцию rand для заполнения массива случайными числами, то чтобы после первого запуска программы случайные числа не повторялись, используйте функцию srand ( time(NULL) ) , перед тем как используете функцию rand .

    Надеемся, что эта статья помогла вам узнать, что такое линейный поиск и как он работает. Если вы нашли ошибки в статье или хотите задать вопрос, то пишите в комментарии. Удачи!

  • Ссылка на основную публикацию
    Adblock
    detector