Линейный поиск заданного значения в массиве

45-46 урок, 9 класс

Учитель: Брух Т.В.

Дата:____________

Тема урока: Линейный поиск заданного значения в массиве.

Цели:

- предметные – представления о понятиях «одномерный массив», «значение элемента массива», «индекс элемента массива»; умение исполнять готовые и записывать на языке программирования простые циклические алгоритмы обработки одномерного массива чисел (суммирование всех элементов массива; суммирование элементов массива с определенными индексами; суммирование элементов массива, с заданными свойствами; определение количества элементов массива с заданными свойствами; поиск наибольшего (наименьшего) элементов массива и др.);

- метапредметные – умение самостоятельно планировать пути достижения целей; умение соотносить свои действия с планируемыми результатами, осуществлять контроль своей деятельности, определять способы действий в рамках предложенных условий, корректировать свои действия в соответствии с изменяющейся ситуацией; умение оценивать правильность выполнения учебной задачи;

- личностные – алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе; представление о программировании как сфере возможной профессиональной деятельности.

Ход урока:

1. Организационный момент

Приветствие учащихся, сообщение темы и целей урока.

2. Повторение

проверка выполнения домашнего задания

3. Изучение нового материала

Новый материал излагается в сопровождении презентации «Последовательный поиск в массиве».

1 слайд — название презентации;
2 слайд — ключевые слова;

- массив

- описание массива таблица

- заполнение массива

- вывод массива

- обработка массива

- последовательный поиск

3 слайд — типовые задачи поиска (схема);

В программировании поиск — одна из наиболее часто встречающихся задач не вычислительного характера.

Можно выделить следующие типовые задачи поиска:

1) найти наибольший (наименьший) элемент массива;

2) найти элемент массива, значение которого равно заданному значению.

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

4 слайд — Нахождение наибольшего элемента в стопке карточек с записанными числами (схема);

Рассмотрим подробно решение задач первого типа (нахождение наибольшего (наименьшего) элемента).

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

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

2) возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и запишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;

3) повторим действия, описанные в п. 2, для всех оставшихся карточек в стопке.

В итоге на доске будет записано самое большое значение просмотренного массива.

5 слайд — программа поиска наибольшего элемента в массиве;

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

program n_3;

  var s, i, imax: integer;

      a:array[1...10] of integer;

begin 

  s:=0;

  for i:=1 to 10 do a[i]:=random(50);

  for i:=1 to 10 do write (a[i],` `);

  imax:=1

  for i:=2 to 10 do

  if a[i]>a[imax] then imax:=i;

  write ('Наибольший элемент a[',imax,']=', a[imax])

end.

7 слайд — поиск элемента, равного 50;

Алгоритм поиска в сформированном нами массиве а значения, равного 50, может выглядеть так:

program n_4;

  var n, i: integer;

      a:array[1...10] of integer;

begin 

  for i:=1 to 10 do a[i]:=random(60);

  for i:=1 to 10 do write (a[i],` `);

  n:=0;

  for i:=1 to 10 do

   if a[i]=50 then n:=i;

   if n=0 then write('Нет') else write (i)

end.

В программе найден последний из элементов, удовлетворяющих условию.

8 слайд — поиск элемента, равного 50;

program n_5;

  var n, i: integer;

      a:array[1...10] of integer;

begin 

  for i:=1 to 10 do a[i]:=random(60);

  for i:=1 to 10 do write (a[i],` `);

  i:=0;

     repeat

    i:=i+1;

  until (a[i]=50) or (i=10);

  if a[i]=50 then write(i) else write('Нет')

end.

В программе найден первый из элементов, удовлетворяющих условию.

9 слайд — подсчет количества элементов;

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

program  n_6;

  var k, i: integer;

      a:array[1...10] of integer;

begin 

  for i:=1 to 10 do a[i]:=random(60);

  for i:=1 to 10 do write (a[i],` `);

  k:=0;

     for i:=1 to 10 do

  if a[i]>50 then k:=k+1;

  write('k=', k)

end.

10 слайд — сумма значений элементов, удовлетворяющих условию;

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

  program n_7;

  var s, i: integer;

      a:array[1...10] of integer;

begin 

  for i:=1 to 10 do a[i]:=random(60);

  for i:=1 to 10 do write (a[i],` `);

  s:=0;

     for i:=1 to 10 do

   if a[i]>10 and (a[i]<30 then s:=s+a[i];

  write(‘s=', s)

end.

11 слайд — самое главное.

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

Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива:

var <имя_массива>: array [<мин_знач_индекса> …

<макс_знач_индекса>] of тип_элементов;

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

Решение разнообразных задач, связанных с обработкой массивов, базируется на таких типовых задачах, как:

- суммирование элементов массива;

- поиск элемента с заданными свойствами.

4. Практическая часть

5. Подведение итогов урока. Сообщение домашнего задания.