Размещено на http://www.allbest.ru/

Факультатив

по основам программирования для 10-11класса

Тема факультатива: «Методы решения олимпиадных задач по программированию»

Симонова Ольга Юрьевна

учитель информатики ЭУВК «Школа будущего»

специалист высшей категории, учитель-методист

Пояснительная записка

метод решение задача программирование

Целью факультативного курса «Методы решения олимпиадных задач по программированию» является:

1) Правильная постановка задач, формализованное описание моделей и методов решения задач;

2) Построение и описание алгоритмов решения прикладных задач;

3) Тщательное планирование и логическое объяснение методов решения задач;

4) Составление и отладка программ, решение прикладных задач;

5) Составление программ обработки данных общего предназначения;

6) Использование современных компьютеров для решения задач.

Изучение курса рассчитано на 2 года (10-11 класс) по 1 часу на неделю, всего 72 часов.

Главной целью факультатива является - овладение учениками техникой алгоритмического мышления при анализе алгоритмов и построении планов решения задач.

Структура программы:

Курс разделён на две части:

1) Введение в программирование, методы решения олимпиадных задач.

2) Анализ алгоритмов и решение олимпиадных задач последних лет.

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

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

В результате обучения учащиеся должны знать:

o базовые алгоритмические структуры, понятие математической модели задачи, алгоритма, программы;

o алгоритмическое решение базовых задач;

o приёмы эффективного использования компьютерных ресурсов при решении ряда олимпиадных задач.

Учащиеся должны уметь:

o строить математическую модель задачи;

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

o формулировать технические условия для решения задач;

o отлаживать и тестировать программы.

Ориентировочный перечень программного обеспечения, необходимого для выполнения программы факультатива

Тип программного обеспечения	Название программы
Операційна система з графічним інтерфейсом	Windows XP, Linux
Програма для роботи з електронною поштою	Outlook Express, The Bat
Веб-браузер	Internet Explorer, Opera
Текстовий процесор	MS Word
Визуальная среда программирования	Borland Delphi 7.0
Среда программиования	Borland Pascal7.0, FreePascal.
Среда программиования	С++.

Тематическое планирование

№ роздела	Роздел учебной программы	Количество часов
10 клас (32 годин + 4 години резервного часу)
1	Введение. Цель факультатива.	1
2	Числовые массивы. Задачи с массивами чисел "пузырьковая" сортировка массива.	3
3	Поиск и перестановка элементов массива	2
4	Упорядочивание элементов массива	2
5	Двумерные массивы. Наибольший и наименьший элементы. Матрицы, строк, столбцов.	2
6	Методика полного перебора	3
7	Размещения с повторениями	3
8	Решение олимпиадных задач	16
9	Резерв времени	4
11 клас (32 годин + 4 години резервного часу)
10	Разбор задач Всеукраинских Интернет олимпиад NetOI (http://www.olymp.vinnica.ua).	17
11	Разбор задач II и III этапов Всеукраинской олимпиады по информатике в АРКрым.	15
12	Резерв времени	4

Часть I

Урок № 1. Введение. Цель факультатива

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

В самом начале я хотела бы определить некоторые элементарные методы решения задач:

· вычислительная геометрия;

· длинная арифметика;

· и рекурсия.

Но прежде всего я хочу заметить, что решение задач олимпиадного уровня по информатике часто требует особых усилий и знаний. И владение этими знаниями и навыками помогают решению различных проблем в информационной сфере. Недаром многие известные фирмы, такие как Intel, Microsoft, IBM, Sun HP и другие, при наборе специалистов проводят тестирование по олимпиадным задачам.[1]

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

Обычно членами жюри все решения оцениваются тремя характеристиками:

· время работы,

· краткость кода

· и необходимыми требованиями.

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

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

Так что при написании программы надо узнать следующее:

· идея решения программы (т.е. ваше представление о задачи и основные подходы к ней);

· четкое представление о параметрах ввод и вывод (какие данные и как вам понадобится (или вывести) ввести, где их хранить и какой их максимальный размер);

· приблизительное время выполнения самого сложного теста (ну это можно и отбросить, только зная, что ваша программа не будет работать 20 минут или дольше при ограничении времени 5 секунд);

· четкое понимание условия(это самое сложное, потому условие может быть совершенно коротким, но сложным к пониманию, так что лучше перечитает его раза три).

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

И хоть за всем не уследишь, но все же за основными переменными необходимо следить четко, иначе при выполнении у вас будет такая ерунда на выходе, что можно округлить глаза. Или порой компьютер просто повиснет (хорошо, если это будет многозадачная операционка, а если старый DOS ?).[3]

Урок №2-4. Тема: Числовые массивы. Задачи с массивами чисел "пузырьковая" сортировка массива

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

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

1. Мы приступаем к изучение массивов - одного из структурированных типов

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

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

Массивы - формальное объединение нескольких однотипных объектов (чисел, символов, строк и т.п.), рассматриваемое как единое целое.

К необходимости применения массивов мы приходим, когда требуется связать и использовать целый ряд родственных величин.

Рассмотрим это подробнее на примере числовых массивов. [2]

Пример 1. Предположим, что перед вами возникла следующая задача:

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

Например, ему хотелось бы знать:

а) среднюю температуру в июне;

б) число дней, в которых температура была выше 23 градусов.

Решим эту задачу, используя числовые массивы. Что же мы будем понимать под числовым массивом?

Числовой массив - это набор чисел, которому дано одно общее имя.

Каждое число в массиве называется элементом.

Набор температур образует массив. Дадим этому массиву имя t. Тогда массив t содержит 30 элементов, при этом каждый элемент представляет собой температуру одного из дней июня.

Элементы массива t можно записать в таком виде:

t[1], t[2], t[3], t[4], ..., t[29], t[30].

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

Дата	Температура	Элемент
1 ИЮНЯ	15	t[1]
2 ИЮНЯ	18	t[2]
3 ИЮНЯ	23	t[3]
4 ИЮНЯ	25	t[4]
5 ИЮНЯ	24	t[5]
. . . . . .	. . . . . . .	. . . . . .
29 ИЮНЯ	20	t[29]
30 ИЮНЯ	21	t[30]

Например, значение элемента t[3]=23, а значению элемента t[29]=20.

Важно помнить, что элементы t[1], t[2], t[3], ..., t[30] представляют собой просто отдельные числа.

Теперь напишем программу для нахождения среднего значения температуры и числа дней с температурой большей 23 градусов, используя массив t для хранения набора температур.

В программе мы должны описать массив. Это делается в разделе описаний. Для этого существует два способа.

1-й способ выполняется по следующей форме:

var

<имя массива> : array[n1. . n2] of <тип элементов массива>.

Придерживаясь такой схемы, заданный массив будет описан так:

var

t : array[1..30] of integer;

Теперь становится понятным, что означает в описании <имя массива> - это идентификатор, удовлетворяющий всем требованиям, предъявляемым к нему (вам уже известных); после этого обязательно записывается служебное (зарезервированное) слово: array; за ним в квадратных скобках указывается тип-диапазон, с помощью которого компилятор определяет общее число элементов массива, тип-диапазон является левой и правой границами изменения индексов массива:

[n1..n2] - тип-диапазон; n1 - левая граница, n2 - правая граница;

для нашего примера [1..30] т.е. индексы элементов нумеруются от 1 до 30 (1 - левая граница, 30 - правая), всего элементов в массиве - 30;

далее указывается тип элементов массива (заметьте, не тип индексов, а тип значения элементов).

Массив описан. Теперь продолжаются другие описания переменных, задействованных в программе. [6]

Мы должны будем организовывать цикл, а значит потребуется счетчик, обозначим его традиционно i - тип целый; потребуется счетчик числа дней с температурой выше 23 градусов, для него заведем переменную k - тип целый; для подсчета среднего значения температуры придется находить ее сумму, для этого укажем переменную s, а так как в ней будет получаться и среднее значение, то тип должен быть вещественным (деление суммы чисел на 30 может привести к дробному результату). [4]

Таким образом, всё описание получится таким:

var

t : array[1. . 30] of integer;

i, k : integer;

s : real;

После чего начинается основная программа, в которой, прежде всего, надо присвоить элементам массива их значения.

Для этого организуется цикл от 1 до 30, где выдается на экран запрос о вводе нужного элемента (процедура write) и занесение этого элемента в соответствующую ячейку памяти (процедура readln).

Эта часть программы будет выглядеть так:

for i := 1 to 30 do

begin

write('Введите температуру в ', i, ' - день ');

readln(t[i])

end;

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

Следующий этап - это суммирование температуры и определения числа дней с температурой выше 23 градусов. Конечно, это надо сделать с помощью цикла, в котором наряду с суммированием, надо ввести условный оператор, которым определяются элементы массива, большие 23 и при этом счетчик k увеличивается на 1.

Разумеется перед началом цикла надо не забыть "обнулить" счетчики s и k.

Этот участок программы будет таким:

s := 0; k := 0;

for i := 1 to 30 do

begin

s := s + t[i];

if t[i] > 23 then k := k + 1

end;

Остался последний шаг - вывод результатов на экран. При этом надо не забыть разделить сумму s на 30 (ведь находим среднюю температуру).

Это выполняется следующими командами:

writeln('Средняя температура в июне ', s/30:4:2);

writeln('Число дней с температурой больше 23 град. ', k)

Осталось записать всю программу и выполнить ее.

Program Temperature;

uses WinCrt;

var

t : array[1..30] of integer;

i, k : integer;

s : real;

begin

for i := 1 to 30 do

begin

write('Введите температуру в ',i,' - день '); readln(t[i])

end;

s := 0; k := 0;

for i := 1 to 30 do

begin

s := s + t[i];

if t[i] > 23 then k := k + 1

end;

writeln('Средняя температура в июне ', s/30:4:2);

writeln('Число дней с температурой больше 23 град. ', k)

end.

2-й способ записи массива чисел может быть выполнен в такой форме:

type

<имя типа> = array[n1. . n2] of <тип элементов массива>;

var

<имя массива> : <имя типа>;

Для нашего примера это может быть записано так:

type

a= array[1..30] of integer;

var

t : a;

И тогда вся программа может быть записана немного иначе:

Program Temperature;

uses WinCrt;

type

a = array[1..30] of integer;

var

t : a; i, k : integer; s : real;

begin

for i := 1 to 30 do

begin

write('Введите температуру в ', i, ' - день '); readln(t[i])

end;

s := 0; k := 0;

for i := 1 to 30 do

begin

s := s + t[i];

if t[i] > 23 then k := k + 1

end;

writeln('Средняя температура в июне ', s/30:4:2);

writeln('Число дней с температурой больше 23 град. ', k)

end.

Урок №4-5. Поиск и перестановка элементов массива

Рассмотрим пример. В одномерном массиве необходимо найти номер заданного пользователем числа и переставить его на первое место в массиве, последовательно переставляя с соседними элементами Для решения этой задачи, после вывода массива, созданного с помощью генератора случайных чисел, надо запросить пользователя, какой элемент он желает переставить в начало массива. [7]

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

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

Итак, новое в этой задаче - это поиск номера заданного элемента.

Сделать это достаточно просто, надо организовать цикл по числу элементов и сравнивать каждый элемент массива с заданным числом, если наступит равенство, тогда в какую-то переменную "запомнить" номер этого элемента массива. Мы приходим к следующей процедуре поиска номера элемента в массиве: [6]

Procedure search_number(d : integer; a : t; var k : integer);

begin

k := 0;

repeat

k := k + 1

until a[k] = d

end;

Полностью программу можно составить из трех процедур: создание массива - create; поиска номера элемента - search_number и перестановки элемента в начало массива - transp_begin.

Она получится такой:

Program Problem5;

uses WinCrt;

const

n = 20;

type

t = array[1..n] of integer;

var

a : t;

i, k, d : integer;

Procedure create(n : integer; var a : t);

var

i : integer;

begin

randomize;

writeln('Заданный массив целых чисел');

for i := 1 to n do

begin

a[i] := random(201) - 100; write(a[i], ' ')

end;

writeln

end;

{----------------------------------------------------------------------------------------}

Procedure search_number(d : integer; a : t; var k : integer);

var

i : integer;

begin

i := 0;

repeat

i := i + 1

until a[i] = d;

k := i

end;

{----------------------------------------------------------------------------------------}

Procedure transp_begin(n, k : integer; var a : t);

var

i, p : integer;

begin

for i := k downto 2 do

begin

p := a[i-1];

a[i-1] := a[i];

a[i] := p

end

end;

{----------------------------------------------------------------------------------------}

begin

create(n, a);

write('Введите переставляемый элемент '); readln(d);

search_number(d, a, k);

transp_begin(n, k, a);

writeln('Массив после перестановки элемента в начало');

for i := 1 to n do write(a[i], ' ');

writeln

end.

Домашнее задание

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

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

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

Урок №6-7. Упорядочивание элементов массива

Что значит упорядочить элементы массива? Это значит расположить числа - элементы массива в порядке возрастания или в порядке убывания. Иногда этот процесс называют сортировкой массива.

Рассмотрим на одном из примеров, как будет происходить упорядочивание числового массива.

Пусть у нас имеется массив из 10 следующих чисел:

5, 10, 7, 9, 14, 6, 3, 8, 2, 5.

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

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

5 10 7 9 14 6 3 8 2 5

Будем придерживаться такого способа сортировки. Начнем сравнение с последнего элемента. Сравним его с предпоследним, если он меньше предпоследнего, тогда переставим их, а если больше или равен, тогда продолжим сравнение. [9]

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

Более подробно этот процесс будет выглядеть так.

Сравним последний элемент a[10] с предпоследним a[9]:

a[10] < a[9], 5 < 2,

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

Сравниваем 9-й и 8-й элементы a[9] = 2 и a[8] = 8:

a[9] < a[8], 2 < 8,

условие выполняется, значит надо переставить эти элементы:

p := a[9], p := 2,

a[9] := a[8], a[9] := 8,

a[8] := p, a[8] := 2.

После перестановки этих двух элементов массив станет таким:

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

5 10 7 9 14 6 3 2 8 5

Когда перестановка выполнена, процесс "проверки" продолжается, сравниваются элементы a[8] и a[7], a[8] < a[7], 2 < 3, - условие выполняется, значит и эти элементы надо переставить и так далее до первого элемента a[1].

Затем весь этот процесс повторяется и снова начинается с последнего элемента, но уже будет продолжаться до второго элемента a[2], затем до третьего, четвертого и так далее до n-го.

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

Составим программу по этому принципу.

Прежде надо создать или сформировать массив. Снова это сделаем с помощью функций случайных чисел.

Для самого процесса сортировки необходимо устроить два цикла. Один - внешний, обеспечивающий постепенное "перемещение" к началу, т. е. к первому элементу, а второй - внутренний, в котором происходит последовательное сравнение элементов и их перестановка в необходимых случаях. [11]

Последним этапом является вывод элементов уже отсортированного массива на экран. Это делается с помощью цикла по числу элементов.

Получим следующую процедуру:

Procedure bubble(n : integer; var a : t);

var

i, j, p : integer; {Сортировка элементов массива}

begin

for i := 2 to n do

for j := n downto i do

if a[j] < a[j - 1] then

begin

p := a[j];

a[j] := a[j-1];

a[j - 1] := p

end;

writeln('Упорядоченный по не убыванию массив');

for i := 1 to n do write(a[i], ' ');

writeln

end;

Программа

Program Problem; {Пузырьковая сортировка}

uses WinCrt;

const

n = 100;

type

t = array[1..n] of integer;

var

a : t;

{----------------------------------------------------------------------------------------}

Procedure create(n : integer; var a : t);

var

i : integer;

begin

randomize;

writeln('Заданный массив целых чисел');

for i := 1 to n do

begin

a[i] := random(201) - 100;

write(a[i], ' ')

end;

writeln

end;

{----------------------------------------------------------------------------------------}

Procedure bubble(n : integer; var a : t);

var

i, j, p : integer; {Сортировка элементов массива}

begin

for i := 2 to n do

for j := n downto i do

if a[j] < a[j-1] then

begin

p := a[j];

a[j] := a[j-1];

a[j-1] := p

end;

writeln('Упорядоченный по не убыванию массив');

for i := 1 to n do write(a[i], ' ');

writeln

end;

{----------------------------------------------------------------------------------------}

begin

create(n, a);

bubble(n, a)

end.

Домашнее задание

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

Урок №8-9. Двумерные массивы. Наибольший и наименьший элементы. Матрицы, строк, столбцов

1. Двумерные массивы

Обратите внимание на следующие таблицы чисел:

1-я таблица:

2-я таблица:

3-я таблица:

Первая таблица чисел состоит из одной строки. Вторая и третья таблицы состоят из строк и столбцов чисел. Так во второй таблице две строки и 7 столбцов.

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

Например: 3-й элемент равен 15. Если обозначить этот массив переменной a[1..n], тогда можно записать: a[3] = 15.

4-й элемент равен 36, a[4] = 36. 5-й элемент равен 47, a[5] = 47.

Чтобы найти элементы в двух других массивах уже одного номера недостаточно. Надо указывать номер строки, в которой находится элемент и номер столбца. Элементы второй таблицы будут пронумерованы так. (Массив обозначим переменной a).

a[1, 1] a[1, 2] a[1, 3] a[1, 4] a[1, 5] a[1, 6] a[1, 7]

12 16 34 53 62 19 51

a[2, 1] a[2, 2] a[2, 3] a[2, 4] a[2, 5] a[2, 6] a[2, 7]

25 41 59 44 82 53 97

Как вы заметили первый индекс обозначает номер строки, а второй номер столбца.

Итак, для определения элементов в этих массивах надо указывать два индекса, номер строки и номер столбца.

Именно поэтому второй и третий массивы называются - двумерными.

Запишите следующие элементы третьего массива:

a[1, 3]=

a[3, 3]=

a[2, 4]=

a[4, 1]=

a[5, 2]=

Элементы двумерного массива обозначаются a[n, m], где a - имя массива, n - номер строки, m - номер столбца.

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

Числа такой матрицы называются элементами матрицы.

2. Ввод и вывод элементов двумерных массивов

Прежде, в разделе описаний, массив надо описать. Как описывается двумерный числовой массив?

Первый способ

type

t = array[1..m, 1..n] of integer;

var

a : t;

Второй способ

var

a : array[1..m, 1..n] of integer;

Третий и четвертый способы

Еще два способа описания массивов основываются на следующих соображениях.

В описании массива t = array[n1..n2] of s; в качестве базового типа s может выступать не только один из стандартных типов, т.е. real, integer, longint, но и ранее описанный в программе тип. Пусть тип s, в свою очередь, был описан как массив: s = array[m1..m2] of integer;

и пусть переменная a - это переменная типа t, тогда a[k] - это переменная типа s, а a[i][j] - переменная типа integer.

Отсюда вытекает такой способ описания:

type

s = array[1..m] of integer; {Описание массива строки}

t = array[1..n] of s; {Описание таблицы}

var

a : t; {Описывается имя массива}

Таким образом, здесь мы видим последовательное описание, вначале строк, потом всей таблицы и наконец имени массива.

Такую запись можно сократить и сделать более компактной, например:

type

t = array[1..m] of array[1..n] of integer;

var

a : t;

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

Так, третий массив может быть описан следующим способом:

const

m = 4; n = 5;

type

s = array[1..m] of integer;

t = array[1..n] of s;

var

a : t;

1. Ввод элементов массива с клавиатуры. Для ввода массива необходимо организовать два цикла. Один цикл по количеству строк, а второй - по количеству элементов в строке, т.е. по количеству столбцов.

Пример 1. Рассмотрим программу ввода с клавиатуры третьего массива чисел с последующим выводом в виде таблицы на экран.

Program Problem1;

uses WinCrt;

const

m = 4; n = 5;

type

s = array[1..m] of integer;

t = array[1..n] of s;

var

a : t;

i, j : integer;

begin

for i := 1 to n do

for j := 1 to m do

begin

write('Введите элемент ', i, '-й строки ');

write(j, '-го столбца '); readln(a[i, j])

end;

writeln('Заданный двумерный числовой массив');

for i := 1 to n do

begin

for j := 1 to m do write(a[i, j]:6, ' ');

writeln

end

end.

Цикл по i, задает номера строк массива. После этого начинает работать цикл по j - по количеству элементов в строке, т. е. по количеству столбцов. Операторы write выдают запрос о вводе элементов. После ввода элементов одной строки, цикл по i повторяется и вводятся элементы следующей строки и так далее.

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

2. С другим способом ввода элементов массива вы уже знакомились при изучении работы с одномерными массивами.

Это - создание элементов с помощью функций случайных чисел: random(n) - для целых чисел или random*x - для вещественных.

Составим процедуру ввода двумерного массива, аналогичную той, которая была выполнена для одномерного массива.

Procedure create_two(n, m : integer; var a : t);

var

i, j : integer;

begin

writeln('Заданный двумерный массив целых чисел');

randomize;

for i := 1 to n do

begin

for j := 1 to m do

begin

a[i, j] := random(201) - 100;

write(a[i, j]:6, ' ')

end;

writeln

end

end;

Пример 2. В двумерном массиве a(n, m) найдите номер и значение наибольшего элемента.

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

Алгоритм

1. Создание двумерного массива с помощью функции случайных чисел с одновременным выводом на экран.

2. Задать первоначальное значение для наибольшего элемента, в качестве такого значения можно взять значение любого элемента массива. Чаще всего в качестве наибольшего элемента принимают элемент первой строки первого столбца, т.е. a[1, 1].

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

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

Циклы заканчиваются.

4. На экран выводится максимальный элемент, номер строки и номер столбца, в которых он находится.

Составим процедуру определения наибольшего элемента двумерного массива.

Procedure maximum_two(n, m :integer; var max, k, p : integer);

var

i, j : integer;

begin

max := a[1, 1];

for i := 1 to n do

for j := 1 to m do

if a[i, j] > max then

begin

max := a[i, j];

k := i;

p := j

end

end;

Программа

Program Problem2;

uses WinCrt;

const

n = 5; m = 6;

type

t = array[1..m,1..n] of integer;

var

a : t;

k, p, max : integer;

{----------------------------------------------------------------------------------------}

Procedure create_two(n, m : integer; var a : t);

var

i, j : integer;

begin

writeln('Заданный двумерный массив целых чисел');

randomize;

for i := 1 to n do

begin

for j := 1 to m do

begin

a[i, j] := random(201) - 100;

write(a[i, j]:6, ' ')

end;

writeln

end

end;

{----------------------------------------------------------------------------------------}

Procedure maximum_two(n, m :integer; var max, k, p : integer);

var

i, j : integer;

begin

max := a[1, 1];

for i := 1 to n do

for j := 1 to m do

if a[i, j] > max then

begin

max := a[i, j];

k := i;

p := j

end

end;

{----------------------------------------------------------------------------------------}

begin

create_two(n, m, a);

maximum_two(n, m, max, k, p);

writeln('Наибольший элемент массива ', max);

writeln('Находится в ', k, '-й строке ', p, '-ом столбце')

end.

Пример 3. В двумерном массиве найдите наибольшие элементы каждой строки.

Вот здесь уже необходим одномерный массив по количеству строк массива. Каждый его элемент, в конечном итоге, даст нам значение максимального элемента каждой строки.

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

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

После завершения работы циклов, одномерный массив, в котором накопились наибольшие элементы строк вывести на экран.

Вот в этой программе удобно описать массив так (подумайте почему?):

const

n = 4; m = 5;

type

s = array[1..m] of integer;

t = array[1..n] of s;

var

a : t;

b : s;

Составим процедуру определения наибольшего элемента в каждой строке:

Procedure maxim_line(n, m : integer; a :t; var b : s);

var

i, j : integer;

begin

for i := 1 to n do

begin

b[i] := a[i, 1];

for j := 1 to m do

if a[i, j] > b[i] then b[i] := a[i, j];

end;

writeln('Наибольшие элементы каждой строки массива');

for i := 1 to n do write(b[i]:6, ' ');

writeln

end;

Программа

Program Problem3;

uses WinCrt;

const

n = 4; m = 5;

type

s = array[1..m] of integer;

t = array[1..n] of s;

st = array[1..n] of integer;

var

a : t;

b : st;

{----------------------------------------------------------------------------------------}

Procedure create_two(n, m : integer; var a : t);

var

i, j : integer;

begin

writeln('Заданный двумерный массив целых чисел');

randomize;

for i := 1 to n do

begin

for j := 1 to m do

begin

a[i, j] := random(201) - 100;

write(a[i, j]:6, ' ')

end;

writeln

end

end;

{----------------------------------------------------------------------------------------}

Procedure maxim_line(n, m : integer; a : t; var b : st);

var

i, j : integer;

begin

for i := 1 to n do

begin

b[i] := a[i, 1];

for j := 1 to m do

if a[i, j] > b[i] then b[i] := a[i, j];

end;

writeln('Наибольшие элементы каждой строки массива');

for i := 1 to n do write(b[i]:6, ' ');

writeln

end;

{----------------------------------------------------------------------------------------}

begin

create_two(n, m, a);

maxim_line(n, m, a, b)

end.

Домашнее задание.

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

2. Составьте программу нахождения наибольших элементов каждого столбца двумерного массива.

Урок №10-12. Методика полного перебора

1. Сочетания

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

С подсчетом числа сочетаний мы уже сталкивались и знаем, что, если существует M - конечное (не обязательно упорядоченное) множество, состоящее из n элементов, тогда:

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

Так, например, из множества M = {1, 2, 3, 4, 5} можно составить десять различных сочетания из 5 по 3:

{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},

{2, 3, 4}, {2, 3, 5}, {1, 4, 5}, {2, 4, 5}, {3, 4, 5}

Мы научились подсчитывать число сочетаний из n элементов по k элементов.

Математическая формула для подсчета числа сочетаний следующая:

. Если k = 0, тогда

Программными средствами подсчитать число сочетаний можно, используя следующую процедуру:

Procedure combination(n, k : integer; var s : longint);

var

i : longint;

begin

s := 1;

if k = 0 then s := 1

else for i := 1 to n - k do s := s*(k + i) div i

end;

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

Именно в этом и будет состоять первый пример. [12]

Пример 1. Составить программу выборки всевозможных различных трех элементов из массива, состоящего из 5 элементов.

Для простоты рассуждений зададим массив из пяти последовательных натуральных чисел: 1 2 3 4 5

Какой способ выборки по 3 элемента из 5 надо избрать? Конечно, можно вообще не изобретать никакого способа, а выбрать произвольно по 3, наблюдая лишь за тем, чтобы не было повторений. Такое возможно, если число элементов небольшое - 5, 6, 7 ... Но если число элементов превышает 10 и вам надо выбрать по 3 элемента, то мы наверняка запутаемся, потому, что число способов резко возрастает, так из 10 по 3 число способов будет равно 120.

Итак, система выборки совершенно необходима!

Не будем изобретать велосипед и возьмем за основу, так называемый "словарный" способ расположения элементов, т. е. похожий на расположения слов в словаре. Этот процесс будет таким:

1 2 3

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

1 2 4

1 2 5

Теперь увеличим на 1 второй элемент, а третий должен быть равен 4, получим:

1 3 4

Снова увеличим последний элемент на 1 до максимального значения - 5. В данном случае это можно сделать только один раз:

1 3 5

Увеличиваем второй элемент на 1, третий элемент может быть только равен максимальному - 5, иначе может быть повторение, что недопустимо:

1 4 5

Второй элемент увеличивать нельзя, значит увеличиваем на 1 первый элемент, он станет равным 2, второй может быть равен 3 или 4, берем наименьший - 3, тогда третий элемент может быть 4 или 5, снова берем наименьший - 4, получаем:

2 3 4

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

2 3 5

Увеличиваем второй элемент на 1, получаем 4, тогда третий элемент может быть только 5:

2 4 5

Дальнейшее увеличение второго элемента невозможно, значит увеличиваем на 1 первый элемент, он станет равным 3, значит второй элемент может быть равен только 4, а третий только 5:

3 4 5

Дальнейшее увеличение ни третьего, ни второго, ни первого элемента невозможно (элементы будут повторяться), значит перебор закончен. Действительно, все варианты исчерпаны, их получено 10, что равно числу сочетаний из 10 элементов по 3. (Мы знаем из предыдущего материала, что число сочетаний из n элементов по k подсчитывается по формуле:

Выпишем все полученные сочетания и еще раз сравним их получение и расстановку с расположением слов в словаре:

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

Теперь подумаем, как реализовать этот процесс программными средствами.

Во-первых, обратим внимание на последние элементы в полученных сочетаниях, это 5, 4 и 3. Назовем эти элементы - верхними границами подмножеств и обозначим max[1], max[2] и max[3].

Сразу надо заметить очень важное обстоятельство, как только третий (последний) элемент подмножества становится равным самому большому значению из всех max[i], т. е. max[1] = 5, то происходит увеличение на 1 второго (предыдущего) элемента, которое, в свою очередь, может происходить до значения max[2] = 4, а когда станет равным max[2], тогда произойдет увеличение первого элемента на 1 и будет продолжаться до значения max[3] = 3.

Таким образом, верхние границы подмножеств "контролируют" "сверху" словарное построение сочетаний.

Во-вторых, надо завести и нижние границы подмножеств, значения которых, как видно из построения подмножеств будут равны (начиная с последней границы): min[1] = 3, min[2] = 2, min[3] = 1.

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

Так, значение первого элемента подмножества не может быть меньше (нумерация идет справа налево, поэтому меньший 1-й элемент подмножества будет под номером 3 - min[3], второй под номером 2 - min[2], третий под номером 1 - min[1]).

Итак, наименьшие элементы каждого элемента: второго слева - третьего слева - min[1] = 3.

Чтобы посмотреть, как будет происходить изменение элементов подмножества, давайте посмотрим саму программу и проанализируем ее работу. [7]

Программа

Program Generator_combination; {Генератор сочетаний}

uses WinCrt;

const

n = 5; k = 3; n1 = 100;

type

t = array[1..n1] of integer;

var

x, min, max : t;

i, j, r : integer;

begin

for j := 1 to k do

begin

max[j] := n - j + 1; min[j] := k - j + 1; x[j] := min[j]

end;

writeln('Сочетания из ',n,' элементов по ', k, ' элементов');

while i <= k do

begin

for j := k downto 1 do write(x[j], ' '); writeln;

r := r + 1; i := 1;

while (i <= k) and (x[i] = max[i]) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

for j := i - 1 downto 1 do

begin

min[j] := x[j + 1] + 1;

x[j] := min[j]

end

end;

writeln('Общее число сочетаний равно r = ', r)

end.

Работа программы

С помощью цикла:

for j := 1 to k do

begin

max[j] := n - j + 1; min[j] := k - j + 1; x[j] := min[j]

end;

задаются первоначальные значения max[j], min[j] и x[j], которые получают следующие значения (для n = 5, k = 3):

max[1] = 5, max[2] = 4, max[3] = 3;

min[1] = 3, min[2] = 2, min[3] = 1;

x[1] = 3, x[2] = 2, x[3] = 1.

Начинается основной цикл "пока", (while i <= k do). Первым оператором цикла является вывод на экран первой тройки значений x[j]. Это делается с помощью цикла:

for j := k downto 1 do write(x[j]:8); writeln;

С помощью этого же цикла будут выводиться на экран и следующие сочетания.

Итак, первоначальный вывод элементов будет таким:

1 2 3

Счетчик числа сочетаний - r получает первое значение - 1. Что делается следующим циклом?

i := 1;

while (i <= k) and (x[i] = max[i]) do i := i + 1;

Во-первых, он проверяет значение i, выполняется, если i <= k и При первом шаге значение i = 1, что меньше 3, x[1] = 3, max[1] = 5, значит равенство x[i] = max[i] не выполняется, а значит цикл выполняться не будет и значение i остается равным 1.

Следуем дальше по программе. Мы видим условие:

if i <= k then x[i] := x[i] + 1;

Условие i <= k выполняется (1 <= 3), тогда значение x[1] становится равным:

x[1] := x[1] + 1, x[1] := 3 + 1 = 4.

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

Следующий цикл:

for j := i - 1 downto 1 do

begin

min[j] := x[j+1] + 1; x[j] := min[j]

end

будет выполняться только тогда, когда значение i будет больше 1. В данном случае i = 1, первоначальное значение j равно 0 и цикл выполняться не будет.

Основной цикл while i <= k do (1 <= 3) повторяется.

На экран выдается следующая группа сочетаний:

1 2 4.

r = 2,

i = 1, x[1] = 4, max[1] = 5, x[1] = 5.

Основной цикл выполняется, на экран выдается:

1 2 5.

r = 3.

Цикл while (i <= k) and (x[i] = max[i]) do i := i + 1; будет выполняться, так как (1 <= 3) и (5 = 5). Он будет выполнен только один раз. Почему? Значение i при первом его выполнении получит значение: i := i + 1, i = 2. При последующей проверке условия этого цикла оказывается, что оно не выполняется. В самом деле: (2 <= 3), но x[2] = 2 не равно max[2] = 4.

Следующий оператор: if i <= k then x[i] := x[i] + 1 будет выполняться, но уже x[2] увеличиться на 1 и станет равным: x[2] = 2 + 1 = 3. Как видите, когда последний элемент сочетания стал наибольшим, начинает увеличиваться на 1 предпоследний элемент.

Здесь мы видим словарный принцип построения сочетаний.

Далее будет выполнен и цикл по j только один раз (j := i - 1, j = 2 - 1 = 1). В результате выполнения этого цикла, нижняя граница min[1] станет равна:

min[1] = [2] + 1 = 3 + 1 = 4, а x[1] = min[1] = 4.

В результате, при последующем выполнением основного цикла на экран будут выданы элементы:

1 3 4.

Все остальные операторы основного цикла, кроме условного выполняться не будут. В результате выполнения условного оператора if i <= k then x[i] := x[i] + 1, x[1] получит значение: x[1] := 4 + 1 = 5.

Дальнейший процесс повторяется и на экран последовательно будут выданы сочетания:

1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5.

* * *

В предыдущем примере мы выбирали только по 3 элемента из заданного множества элементов. Давайте немного усложним задачу и составим программу, которая выводила бы на экран всевозможные сочетания из n элементов, т.е. по одному элементу, по два, три четыре и т.д. Как вам уже известно, всевозможных сочетаний из n элементов будет 2ⁿ, считая и число сочетаний из n по 0 элементов, но мы не будем выводить по 0 элементов, поэтому всех сочетаний должно быть Так для 5 элементов их будет

Для 4-х элементов их будет 15. Если элементами этого множества будут числа 1, 2, 3, 4, тогда все сочетания получатся следующие:

1

2

3

4

1 2

1 3

1 4

2 3

2 4

3 4

1 2 3

1 2 4

1 3 4

2 3 4

1 2 3 4

Такой процесс выбора всех сочетаний и будет называться полным перебором элементов массива.

Для составления программы вывода всех сочетаний, достаточно предыдущую программу сделать процедурой, а в основной программе организовать цикл от 1 до n и в качестве входного параметра для количества выбираемых элементов k вводить значение параметра цикла.

Процедура названа gen_comb, входными параметрами которой являются массивы чисел (x: t), массивы нижних и верхних границ (min, max:t), хотя можно обойтись и без указания массивов в качестве входных параметров, но общее число элементов массива n и количество выбираемых элементов - k вводить надо обязательно. В качестве выходного параметра - число всех сочетаний r.

Процедура

Procedure gen_comb(x, min, max : t; n, k : integer; var r : integer);

var

i, j : integer;

begin

for j := 1 to k do

begin

max[j] := n - j + 1; min[j] := k - j + 1; x[j] := min[j]

end;

i := 0;

while i <= k do

begin

for j := k downto 1 do write(x[j]:8); writeln;

r := r + 1; i := 1;

while (i <= k) and (x[i] = max[i]) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

for j := i - 1 downto 1 do

begin

min[j] := x[j+1] + 1; x[j] := min[j]

end

end

end;

В основной программе описан один массив на 100 элементов:

const

n1 = 100;

type

t = array[1..n1] of integer;

var

x, min, max : t;

i, n, r : integer;

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

Основная программа

begin

write('Введите число элементов массива n = '); readln(n);

writeln('Всевозможные сочетания из ', n, ' элементов');

for i := 1 to n do gen_comb(x, min, max, n, i, r);

writeln('Число всех сочетаний равно r = ', r)

end.

Вся программа полного перебора будет следующей:

Program generator_combination; {Генератор всех сочетаний}

uses WinCrt;

const

n1 = 100;

type

t = array[1..n1] of integer;

var

x, min, max : t;

i, n, r : integer;

{----------------------------------------------------------------------------------------}

Procedure gen_comb(x, min, max : t; n, k :integer; var r : integer);

var

i, j : integer;

begin

for j := 1 to k do

begin

max[j] := n - j + 1; min[j] := k - j + 1; x[j] := min[j]

end;

i := 0;

while i <= k do

begin

for j := k downto 1 do write(x[j]:8); writeln;

r := r + 1; i := 1;

while (i <= k) and (x[i] = max[i]) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

for j := i - 1 downto 1 do

begin

min[j] := x[j+1] + 1; x[j] := min[j]

end

end

end;

{----------------------------------------------------------------------------------------}

begin

write('Введите число элементов массива n = '); readln(n);

writeln('Всевозможные сочетания из ', n, ' элементов');

for i := 1 to n do gen_comb(x, min, max, n, i, r);

writeln('Число всех сочетаний равно r = ', r)

end.

Пример 2. Программа вывода всех сочетаний из n элементов произвольно заданного массива a(n).

Если в первых примерах мы, образно говоря, перебирали натуральные числа, т.е. делали выборки из массивов 1, 2, 3, 4 и т. д., то теперь задача несколько усложнена - массив может состоять из любых чисел ...