Аннотация: Используя типовые алгоритмы можно решить любую задачу. В лекции очерчен круг НЕОБХОДИМЫХ ТИПОВЫХ АЛГОРИТМОВ (для обработки одномерных массивов и обработки строк), рассмотрены некоторые олимпиадные задачи, которые решаются с использованием этих алгоритмов. Цель лекции: научиться применять изученные типовые алгоритмы при решении классических задач.
Ключевые слова: элемент цикла
Типовые алгоритмы обработки одномерных массивов
В данной теме будут рассматриваться такие типовые алгоритмы обработки одномерных массивов:
- Заполнение, вывод элементов массива
- Сумма, произведение элементов
- Выбор по условию
- Максимальный (минимальный) элемент
- Вставка, удаление элементов
- Инвертирование (изменения порядка следования элементов заданного массива на обратный)
Программные реализации типовых алгоритмов обработки одномерных массивов приведены в таблице 2.1:
input n dim a(n) for i=1 to n input a(i) next i
const n=10; Var a: array [1..n] of integer; begin for i:=1 to n do readln (a[i]); …
…for i=1 to n print a(i) ; » » ; next i
… for i:=1 to n do write (a[i]); …
… p=1 for i=1 to n s=s + a(i) p=p * a(i) next i
… s:=0; p:=1; for i:=1 to n do begin s:=s+a[i]); p:=p*a[i]); end; …
… p = 1 for i = 1 to n if then k=k+1:s=s+a(i):p=p*a(i) next i
… k:=0; s:=0; p:=1; for i:=1 to n do if then begin k:=k+1; s:=s+a[i]; p:=p*a[i]; end; …
… max = a(1): min = a(1) for i = 2 to n if a(i) > max then max = a(i) if a(i) < min then min = a(i) next i
… max:=a[1]; min:=a[1]; for i:=1 to n do begin if a[i] > max then max:=a[i]; if a[i] < min then min:=a[i]; end;
dim a(n + 1) … for i = n to k step -1 a (i + 1) = a(i) next a(k) = x
Var a: array [1..n+1] of… … for i:=n downto k do a[i+1]:=a[i]; a[k]:=x; …
. . . for i = k to n — 1 a(i) = a(i + 1) next
Python #20 Алгоритмы обработки массива
… for i:=k to (n-1) do a[i]:= a[i+1]; …
. . . for i = 1 to n/2 swap a(i), a(n-i+1) next
… for i:=1 to (n div 2) do begin х:=a[i]; a[i]:= a[n-i+1]; a[n-i+1] :=х; end …
Ключевые моменты в типовых алгоритмах:
- Выбор по условию. В качестве условия может проверяться значение элемента массива на четность, кратность элемента какому-либо числу, положительность, отрицательность, равенство нулю. Может проверяться также и значение индекса элемента массива (например, элементы, стоящие на четных местах и др.).
- Максимальный (минимальный) элемент. Кроме максимального элемента часто требуется найти и индекс максимального элемента:
if a[i]>max then begin max:=a[i]; imax:=i; end;
Задачи использованием типовых алгоритмов обработки одномерных массивов
Задача: На плоскости изображено N прямоугольников (рис. 2.1). Каждый прямоугольник задан координатами левой нижней и правой верхней вершин. Определить, имеют ли прямоугольники общую площадь .
Рис. 2.1.
Информатика 9 класс: Обработка массивов в языке Паскаль
Идея решения:
- максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и …
- …максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то …
- …общая площадь есть.
В задаче необходимо использовать типовой алгоритм нахождения МАКСИМАЛЬНОГО (МИНИМАЛЬНОГО) ЭЛЕМЕНТА МАССИВА.
Для вычисления общей площади необходимо найти произведение разности:
- максимальной координаты по оси Х левых нижних вершин прямоугольников и минимальной координаты правых верхних вершин и …
- …максимальной координаты по оси У левых нижних вершин прямоугольников и минимальной координаты правых верхних вершин.
Программа на Бейсике:
input «введите количество прямоугольников»; n dim x1(n), x2(n),y1(n), y2(n) for i=1 to n input x1(i), x2(i), y1(i), y2(i) next xmax=x1(1) xmin=x2(1) ymax=y1(1) ymin=y2(2) for i=1 to n if x1(i) > xmax then xmax=x1(i) if x2(i) < xmin then xmin=x2(i) if y1(i) >ymax then ymax=y1(i) if y2(i) < ymin then ymin=y2(i) next if xmax
Программа на Паскале:
var x1, x2, y1, y2: array [1..10] of integer; n, i, xmax, xmin, ymax, ymin: integer; begin writeln (‘введите количество прямоугольников’); readln (n); for i:=1 to n do readln (x1[i], y1[i], x2[i], y2[i]); xmax:=x1[1]; xmin:=x2[1]; ymax:=y1[1]; ymin:=y2[2]; for i:=1 to n do begin if x1[i] > xmax then xmax:=x1[i]; if x2[i] < xmin then xmin:=x2[i]; if y1[i] >ymax then ymax:=y1[i]; if y2[i] < ymin then ymin:=y2[i]; end; if (xmax
Задача: Латинским квадратом называется массив, в строках и столбцах которого нет одинаковых элементов. Вывести на экран латинский квадрат размером NxN .
Идея решения: Заполнить 1 строку квадратного массива ( NxN ) числами от 1 до N . Вторая строка массива получается путем циклического сдвига элементов первой строки и т. д. (табл. 2.2). Циклический сдвиг можно реализовать, используя типовой алгоритм ВСТАВКИ-УДАЛЕНИЯ (в зависимости от направления циклического сдвига).
| 1 | 2 | 3 | 4 | 5 |
| 5 | 1 | 2 | 3 | 4 |
| 4 | 5 | 1 | 2 | 3 |
| 3 | 4 | 5 | 1 | 2 |
| 2 | 3 | 4 | 5 | 1 |
Решение на Бейсике:
input «размерность http://www.intuit.ru/2010/edi» >
Решение на Паскале:
<
div xmlns_edi=»http://www.intuit.ru/2010/edi» >
var a: array [1..10,1..10] of integer; n,i,j,x: integer; begin writeln (‘размерность=’); readln (n); for j:=1 to n do a[1,j]:=j; for i:=2 to n do begin for j:=1 to n do a[i,j]:=a[i-1,j]; x:=a[i,n]; for j:=n downto 2 do a[i,j]:=a[i,j-1]; a[i,1]:=x; end; for i:=1 to n do begin for j:=1 to n do write(a[i,j]); writeln; end; end.
Источник: intuit.ru
Разработка программ для обработки одномерных массивов
- Повторить основные понятия, определения, алгоритмы обработки одномерных массивов; правила описания одномерных массивов на языке программирования;
- Выполнить упражнения на составление программ обработки массивов; провести компьютерный эксперимент.
Помните: программы пишутся для машин, а читаются людьми
Из фольклора программистов
Алгоритм – это четкая последовательность действий для определенного исполнителя, приводящая к выполнению поставленной цели.
Базовые структуры
разветвляющиеся,
циклические.
Циклические алгоритмы это алгоритмы, последовательность действий в которых повторяется многократно.
Типы данных:
действительные.
Массив – последовательность данных одного и того же типа, количество которых заранее известно.
Источник: kopilkaurokov.ru
Создание программ для обработки одномерных массивов
На уроке учащиеся повторяют основные понятия, определения, алгоритмы обработки одномерных массивов; правила описания одномерных массивов на языке программирования; выполняют упражнения на составление программ обработки массивов.
Лукьянчикова Елена Александровна, Донецкий учебно-воспитательный комплекс №114
Описание разработки
Цель урока:
Повторить основные понятия, определения, алгоритмы обработки одномерных массивов; правила описания одномерных массивов на языке программирования;
Выполнить упражнения на составление программ обработки массивов; провести компьютерный эксперимент.
Задачи урока:
- образовательные:
- усвоение и закрепление учащимися правил описания одномерных массивов на языке программирования;
- выработка навыков составления программ, реализующих обработку одномерных массивов;
Тип урока: комбинированный.
Формы и методы обучения: словесный, наглядный, практический, проблемный, мозговой штурм, индивидуальная работа.
- Организационный момент. (2 мин.)
- Индукция. (2 мин.)
- Повторение и актуализация знаний, умений и навыков.(7 мин)
- Изучение нового материала с поэтапным закреплением. (10 мин)
- Компьютерный эксперимент.(15 мин)
- Физкультпауза. (3 мин)
- Рефлексия. (3 мин.)
- Домашнее задание. (1 мин)
- Подведение итогов урока. (2 мин)
Инструктаж по технике безопасности в компьютерном классе.
Оглашение темы и цели урока, мотивация учеников.
Для создания позитивного эмоционального настроения, включения чувственного аппарата, создания личностного позитивного отношения к предмету обсуждения, ученикам предлагается высказать свои надежды и ожидания от работы на уроке и указать свое эмоциональное состояние по методике Лукашина О.М. Учащиеся заполняют «таблицу-экран», высказывая при этом свои надежды и ожидания от работы на уроке, оставляя в клеточках экрана карточку соответствующего цвета.
Повторение и актуализация знаний, умений и навыков.
Алгоритм – это четкая последовательность действий для определенного исполнителя, приводящая к выполнению поставленной цели.
Базовые структуры алгоритмов: линейные, разветвляющиеся, циклические.
Циклические алгоритмы – это алгоритмы, последовательность действий в которых повторяется многократно.
Типы данных: целые и действительные.
Массив – последовательность данных одного и того же типа, количество которых заранее известно.
- Последовательность действий, допустимых для исполнителя – это…
- программа
- алгоритм
- команда
- система команд
- Выявление ошибок и их устранение – это…
- отладка задачи
- отладка исполнителя
- отладка алгоритма
- отладка программы
- оператор организации диалога с пользователем
- условный оператор
- оператор цикла
- подпрограмма
- оператор ввода и оператор вывода
- условный оператор
- оператор цикла
- оператор графики
- оператор организации диалога с пользователем
- условный оператор
- оператор цикла
- подпрограмма
- с постусловием (REPEAT) и с предусловием (WHILE)
- с предусловием (WHILE) и с заданным числом повторений (FOR)
- с заданным числом повторений (FOR) и с постусловием (REPEAT)
- вычисление сотой степени числа К (S=К 100 )
- подсчитывание суммы ста чисел, введенных пользователем
- подсчитывание суммы первых ста натуральных чисел
- Назначением фрагмента программы
S:=0; k:=0;
Repeat
- вычисление суммы квадратов четных чисел первого десятка
- вычисление суммы четных чисел первого десятка
- вычисление произведения квадратов четных чисел первого десятка
Таблица ответов
Номер вопроса
Номер ответа
Изучение нового материала с поэтапным закреплением.
— Описание типов массивов:
1-вариант
Для описания массива можно использовать заранее определенную константу:
A: array[1..G] of integer;
B: array[1..20] of real;
2 – вариант
Massiv = array [1..20 ] of integer;
Организация обработки линейных массивов
- Выбрать правильно описанные фрагменты программ для задания элементов массива.
- BEGIN
FOR I:=1 TO 10 DO
BEGIN
WRITE(‘A[‘,I,’]=’);
READLN(A[I])
END
END;
FOR I:=1 TO 10 DO
BEGIN
WRITE(‘A[‘,I,’]=’);
END
END;
FOR I:=1 TO 10 DO
BEGIN
READLN(A[I])
END
END;
END;
END;
- Выбрать правильно описанные фрагменты программ, где перебираются все элементы массива, описание которого имеет вид
CONST N=1; K=100;
VAR A: ARRAY[N..K] OF REAL;
и каждому элементу массива присваивается значение, которое соответствует номеру элемента в массиве:
REPEAT
UNTIL I
REPEAT
UNTIL I>K;
WHILE I
BEGIN
END;
WHILE I
BEGIN
END;
Таблица ответов
Номер задания
Номер правильных ответов
1, 3, 4, 5
1, 2, 4, 6
Дан массив целых чисел от 1 до N.
-Есть ли в этом массиве отрицательные элементы;
-Номер первого отрицательного элемента;
— Номер последнего отрицательного элемента;
Учащиеся имеющие нечетный номер конспекта работают с нечетными числами, а четный – с четными.
Дан массив целых чисел от 1 до N.
— Есть ли в этом массиве четные (нечетные) элементы;
— Номер первого четные (нечетные) элемента;
— Номер последнего четные (нечетные) элемента;
Для организации данного этапа урока используются упражнения 2 типов:
1 тип: Методика «palming»: учащиеся должны ладонями закрыть область открытых глаз так, чтобы свет не попадал на них. Задержаться в таком положении на 1-2 минуты. Эта методика эффективно позволяет снять напряжение с глаз.
2 тип. Учитель называет предметы, находящиеся в классе последовательно на русском, украинском и английском языках. Ученики должны найти глазами названный предмет, и задержать на нем внимание на несколько секунд.
Учитель предлагает учащимся высказаться по поводу полученных в практической работе результатов (или проведенного урока, полученных или нет знаниях, практической ценности их и т.д.). Заполняют таблицу эмоционального состояния на конец урока. Высказываются по поводу получения или нет ожидаемых результатов урока.
Повторить теоретический материал из опорного конспекта. Решить задачи.
Дан массив целых чисел от 1 до N.
-Есть ли в этом массиве элементы кратные 7;
-Номер первого элемента кратного 7;
— Номер последнего элемента кратного 7;
Итогом урока является количество баллов, полученное учащимися на протяжении урока, а определение каждым своего эмоционального состояния на конец урока является показателем удовлетворенности ученика проведенным уроком.
-80%
Источник: videouroki.net