АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Задачи четвертого класса

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. Ситуационные задачи и тестовые задания.
  3. II. Основные задачи и функции
  4. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  5. II. Цель и задачи государственной политики в области развития инновационной системы
  6. III. Цели и задачи социально-экономического развития Республики Карелия на среднесрочную перспективу (2012-2017 годы)
  7. VI. ДАЛЬНЕЙШИЕ ЗАДАЧИ И ПУТИ ИССЛЕДОВАНИЯ
  8. Активные интегрированные антенны для усилителей класса F
  9. Аналитические возможности, задачи и основные направления анализа СНС
  10. Б. Рішення на застосування четвертого або п'ятого режимів радіаційного захисту
  11. БАЛАНС КОММЕРЧЕСКОГО БАНКА, ЦЕЛИ И ЗАДАЧИ ЕГО АНАЛИЗА
  12. Билет 1. Предмет истории как науки: цели и задачи ее изучения

Часто в программировании возникает задача отыскать первый элемент, совпадающий с заданным x. Для решения этой задачи могут быть предложены следующие варианты:

* линейный поиск;

* поиск с барьером;

* двоичный поиск.

Линейный поиск

Алгоритм такого поиска был рассмотрен при решении типовых задач на построение циклических алгоритмов. Напомним, что особенностью такого поиска является две причины прекращения поиска: 1) элемент найден (это программируется с помощью логической переменной) и 2) просмотрены все элементы, но заданный элемент так и не нашли (i > n).

const n = 20; {количество элементов в массиве}

var a: array [1..n] of integer; {исходный массив}

i, x: integer;

f: boolean;

begin

write (‘задайте искомый элемент’);

readln (x);

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

for i:= 1 to n do

readln (a[i]);

f:= false; {элемент еще не найден}

i:= 1;

while (i <= n) and not f do

if a[i] = x then f:= true {нашли}

else i:= i + 1; {переходим к следующему элементу}

if f then writeln (‘нашли элемент с номером ’, i)

else writeln (‘такого элемента нет’);

end.

Поиск с барьером

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

const n = 20; {количество элементов в массиве}

var a: array [1..n + 1] of integer; {исходный массив}

i, x: integer;

begin

write (‘задайте искомый элемент’);

readln (x);

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

for i:= 1 to n do

readln (a[i]);

a[n + 1]:= x; {установлен барьер, равный x, в конец массива}

i:= 1;

while a[i] <> x do

i:= i + 1; {переходим к следующему элементу}

if i <> n + 1 then writeln (‘нашли элемент с номером ’, i)

else writeln (‘такого элемента нет’);

end.

Двоичный поиск (поиск элемента в упорядоченном массиве)

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

const n = 20; {количество элементов в массиве}

var a: array [1..n] of integer; {исходный массив}

i, x, k, m: integer;

left, right, mid: integer; {левая, правая граница и середина отрезка}

f: boolean;

begin

write (‘задайте искомый элемент’);

readln (k);

for i:= 1 to n do

readln (a[i]);

{упорядочивание массива по возрастанию}

for i:= 1 to n - 1 do

begin

m:= i;

for j:= i + 1 to n do

if a[j] < a[m] then m:= j;

x:= a[i];

a[i]:= a[m]; a[m]:= x

end;

{поиск элемента}

f:= false; {элемент не найден}

left:= 1; right:= n;

repeat {поиск элемента в части массива от элемента[left] до

элемента[rigth]}

mid:= (left + right) div 2;

if k < a[mid] then right:= mid - 1 {элемент в левой части}

else if k > a[mid] then left:= mid + 1 {элемент в правой части}

else f:= true; {нашли}

until f or (left > rigth);

if f then writeln (‘элемент с номером ’,mid:2, ‘совпадает с искомым ’, k)

else writeln (‘не нашли’);

end.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)