Данное учебное пособие предназначено для изучения курса алгоритмизации и программирования в 8 классах школ с углубленным изучением предметов физико-математического цикла. Изложение материала, представленного в данной книге, опирается на ранее изученный материал предыдущего пособия и предполагает знание, изложенных в нем тем. Учебное пособие состоит из трех основных частей, которым предшествует краткий курс повторения. Основное содержание книги – это ознакомление с новыми типами данных и применение их в решении задач. В первой части учебного пособия вы узнаете: - что такое массив; - какие задачи можно решать, используя этот тип данных. Вторая часть посвящена такому важному вопросу как сортировка массивов данных. В ней излагаются два самых распространенных метода сортировки. В третьей части рассмотрены задачи на символьный и строковый типы данных.

Основы программирования на языке Паскаль

для учащихся 8 класса

составитель Волкова Е. И.

2005 г.

Содержание

	Введение	3
	Повторение	4
	Часть I
I. 1.	Структурированный тип данных. Особенности работы с одномерными массивами	15
I. 2.	Формирование одномерных массивов	22
I. 3.	Еще задачи на одномерные массивы	25
I. 4.	Двумерные массивы. Особенности работы с двумерными массивами	27
I. 5.	Формирование двумерных массивов	34
I. 6.	Еще задачи на двумерные массивы	39
	Часть II
II. 1.	Сортировка массивов. Сортировка элементов одномерного массива методом простого выбора	42
II. 2.	Сортировка массивов. Сортировка элементов одномерного массива методом «пузырька»	44
	Часть III
III. 1.	Символьный тип данных	47
III. 2.	Строковый тип данных	49
III. 3.	Процедуры и функции работы со строковыми величинами	52
III. 4.	Использование массивов в решении задач на обработку строк	55

Введение

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

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

- что такое массив;

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

Вторая часть посвящена такому важному вопросу как сортировка массивов данных.

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

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

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

Вопросы и задания в конце каждого параграфа скомпонованы по нарастающей сложности и, в некоторых параграфах разбиты на блоки.

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

 - задание для выполнения в классе с помощью учителя;

- задание для самостоятельного решения во время урока;  - задание повышенной сложности.

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

Повторение

Тема: Информация

Справочная информация

Ø Сообщение, уменьшающее неопределенность знаний в два раза, несет 1 бит информации.

Ø Информативность сообщения (i) о том, что произошло одно из N равновероятных событий, можно вычислить из формулы N=2ⁱ.

Ø Для вычисления информативности текста (I), состоящего из K символов, каждый из которых имеет информативность i , применяется формула I=K * i . Для вычисления информативности символа нужно воспользоваться предыдущей формулой, учитывая, что N – мощность алфавита, в котором напечатан текст.

Задачи

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

2. Какое количество информации получит второй игрок при игре в крестикинолики на поле 8х8, после первого хода первого игрока, играющего крестиками?

3. В рулетке общее количество лунок равно 128. Какое количество информации мы получаем в зрительном сообщения об остановке шарика в одной из лунок?

4. В корзине 16 разноцветных шариков. Сколько бит информации несет сообщение о том, что вытянут красный шарик?

5. В мешках лежат фишки: в первом – 8 штук, а во втором – 32 штуки. Известно, что в каждом из мешков нет одинаковых фишек. Какое сообщение несет информации больше: «Из первого мешка достали черную фишку!» или «Из второго мешка достали черную фишку!»? Ответ обосновать.

6. Заполнить пропуски числами.

а) 5 Кбайт = __ байт = __ бит, г) __Гбайт =1536 Мбайт = __ Кбайт;

б) __ Кбайт = __ байт = 12288 бит; д) 512 Кбайт = 2__ байт = 2__ бит.

в) __ Кбайт = __ байт = 213 бит;

7. Найти x из следующих соотношений:

а) 16x бит = 32 Мбайт;

б) 8x Кбайт = 16 Гбайт.

8. Сколько бит информации несет текст «Казнить нельзя, помиловать!», если текст написан в компьютерном алфавите (256 символов)?

9. В результате преобразования графического изображения 20х40 пикселей количество цветов уменьшилось с 256 до 4. Во сколько раз уменьшится объем видеопамяти, занимаемый этим изображением?

10. Какова мощность алфавита, с помощью которого записано сообщение, содержащее 2048 символов, если его объем составляет 1/512 часть одного мегабайта.

11. Пользователь компьютера, хорошо владеющий навыками ввода информации с клавиатуры, может вводить в минуту 100 знаков. Мощность алфавита, используемого в компьютере равна 256. Какое количество информации в байтах может ввести пользователь в компьютер за 8 минут?

12. * Два текста содержат одинаковое количество символов, но информативность первого текста в 1.5 раза больше. Известно, что мощности алфавитов обоих текстов не превышают 10 символов, и символы кодируются целым числом битов. Каковы мощности алфавитов?

Тема: Системы счисления

Справочная информация

Ø Система счисления – это способ изображения чисел и соответствующие ему правила действия над числами.

Ø В позиционных системах счисления от позиции цифры в числе зависит величина, которую она обозначает.

Ø Количество используемых цифр в позиционной системе счисления называется основанием, а сами цифры - алфавитом.

Алгоритм перевода чисел из системы с новым основанием в десятичную систему

1. Нумеруем цифры числа от запятой справа налево, начиная с 0;

2. Составляем сумму произведений цифр, на степени основания системы соответствующие номерам;

3. Выполняем арифметические операции.

Например: А216 Х10

А¹2⁰₁₆ =10*16¹+2*16⁰=160+2=162₁₀

Алгоритм перевода чисел из десятичной системы в систему с новым основанием

1. Делим число на основание новой системы счисления, записывая остаток – младший разряд целой части числа в новой системе;

2. Полученное частное снова делим, выписывая остаток;

3. И так до тех пор, пока последнее частное не станет меньше основания – старший разряд числа.

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

126₁₀=1111110₂

i в двоичную систему Алгоритм перевода чисел из системы с основанием 2 счисления

1. Переводим по отдельности цифры числа по правилам перевода из десятичной системы в двоичную систему;

2. Запись каждой цифры должна состоять из i бит. В случае недостающих битов, дописываем незначащие нули;

3. Объединяем переводы в одно число. Приписываем индекс 2.

Например: 65₈ Х₂

А теперь переведем цифры восьмеричного числа по отдельности как десятичные числа в двоичную систему счисления.

6:2=3(ост. 0) 5:2=2(ост. 1) 3:2=1(ост. 1) 2:2=1(ост. 0)

110₂ 101₂ Ответ: 110101₂.

Алгоритм перевода чисел из двоичной системы счисления в систему с

i основанием 2

1. Разбиваем число, начиная с конца по i символов. В случае недостающих битов, дописываем незначащие нули;

2. Переводим по отдельности группы в десятичную систему; 3. Объединяем переводы в одно число. Приписываем индекс системы. Осуществим перевод: 111000100₂ Х₈.

7 0 6

Ответ:706₈.

Задачи

1. Верно ли записаны числа: В8₁₆, 61₆, 19₈, 12₃, А3₁₃?

2. Осуществите перевод: А216 Х10 , 23610 Х8 , 4513 Х7 .

3. Осуществите перевод, минуя десятичную систему:

F8316 Х2 , 10100112 Х8 , 456378 Х4 .

4. Решите уравнения:

252₇-140₆Х₃=1111₂; 1B₁₂Х₅-110₃=321₄.

5. * Выполните действия в предложенной системе счисления:

2345₈+4531₈-2451₈=?; FB5₁₆+A34C₁₆+138E₁₆-66AF₁₆=?; 11100₂-10001₂+1110₂=?

Тема: Представление чисел в памяти компьютера. Числовые типы данных

Справочная информация

Алгоритм кодирования чисел без учета знака

1. Перевести число в двоичную систему;

2. Дополнить незначащими нулями до байта (или машинного слова).

Алгоритм кодирования чисел с учетом знака

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

Если число отрицательное, то:

1. Переводим в двоичную систему модуль числа;

2. Дополняем до байта (слова);

3. Инвертируем (единицы заменяем нулями, а нули единицами); 4. Прибавляем единицу по правилам двоичной арифметики. Например, закодируем –126 в одном байте.

Получили 1111110.

2) Дополним до байта: 01111110. 3) Инвертируем: 10000001 4) Прибавим 1:

10000001

+ 1

10000010

Ответ: 10000010.

 В закодированном виде целые числа по знаку различаются: у неотрицательных слева – 0. а у отрицательных – слева 1.

Алгоритм декодирования неотрицательных чисел

1. Перевести число в десятичную систему.

Алгоритм декодирования отрицательных чисел

1. Инвертируем число (меняем единицы на нули, а нули на единицы);

2. Прибавляем единицу;

3. Переводим в десятичную систему;

4. Перед результатом ставим знак минус.

Например. Декодировать число 10011011.

01100101

=64+32+4+1=101₁₀ Ответ: -101.

Задачи

1. Закодируйте в одном байте числа 15, 45, 138.

2. Почему число 256 нельзя закодировать в одном байте?

3. Закодируйте в одном байте числа -78, 39 и -128 с учетом их знака.

4. Чем отличаются типы byte и shortint? Определите диапазон значений этих типов.

5. Даны коды чисел типа shortint : 10000011, 11110000 и 00001100. Что это за числа?

6. Сложите два числа: 11001101 и 01100011 с учетом их знака. Раскодируйте слагаемые и результат и убедитесь в правильности сложения.

7. Определите диапазон типа word.

8. Докажите, что диапазон типа integer от -32768 до 32767.

Тема: Начала программирования на языке Паскаль

Справочная информация

Структура программы на языке Паскаль

Uses <раздел описания модулей>;

Label <раздел описания меток>;

Описательная

часть Const < раздел описания констант>;

Type <раздел описания типов>;

Var <раздел описания переменных>;

Procedure <раздел описания процедур>;

Function <раздел описания функций>;

Исполнительная Begin часть <тело программы, состоящее из операторов>;

End.

Разделы описательной части программы, которые мы ранее использовали:

Uses -для подключения модуля текстового режима CRT ;

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

Предназначение остальных разделов будет раскрыто постепенно.

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

Отдельная команда языка называется оператором. В каком порядке написаны операторы, в том порядке они и будут выполнены. Исполнительная часть заключается в операторные скобки: Begin и End. Сущность операторных скобок такая же, как и у математических,– в них заключаются операторы, которые будут выполняться в первую очередь. Операторные скобки (Begin…End) мы использовали и будем использовать в условных и циклических операторах чтобы выделить их тело.

Запомните:

! После каждого оператора или указателя типа в разделе Var ставится “;”.

! В конце программы ставится точка.

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

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

Для любознательных

Модуль – это отдельно хранящийся программный объект. Он содержит в себе множество подпрограмм, каждая из которых выполняет определенную роль. Использовать подпрограммы модуля можно тогда, когда он подключен, то есть его имя указано в разделе Uses. Модули бывают пользовательские (можно написать самому) и стандартные (входящие в состав системы программирования). Начинающие программисты чаще всего используют модули CRT и GRAPH. В модуле CRT собраны подпрограммы, позволяющие оформлять текст на экране, а в модуле GRAPH подпрограммы рисования. Чтобы познакомиться с их возможностями подробно, нужно обратиться к специальной литературе. Мы будем использовать две процедуры модуля CRT: Clrscr (чистка экрана), Readkey (прерывание выполнения программы, пока не будет нажата клавиша).

! Имя переменной или другого программного объекта называется идентификатором.

Идентификатор – это слово, состоящее из латинских букв (в слове могут быть использованы цифры и знак _ , но только в конце или средине). Размер переменной, диапазон значений и набор операций, которые с ней можно осуществить характеризуется типом. ! Чтобы написать программу нужно:

1. Внимательно прочитать задачу;

2. Определить исходные данные и дать идентификаторы переменным, в которые они будут помещены;

3. Определиться с идентификаторами результатов;

4. Определить типы переменных, в которых будут храниться данные и результаты;

5. Оформить описательную часть;

6. Оформить исполнительную часть по следующей схеме: Begin

<ввод данных>; - помещаем данные в переменные

<обработка данных>; - набор операторов, выполняя которые, компьютер из переменных-данных заполнит переменные-результаты <вывод результатов>; - печатаем содержимое переменных-результатов на экран End.

7. Дополнить описательную часть, если при обработке данных вы использовали промежуточные переменные.

Краткий обзор операторов языка Паскаль

Формат		Назначение				Правила использования
Read(<список ввода>); Read(a,b,c); Readln(a,b);		Процедура ввода данных в память компьютера..				Данные вводятся в порядке перечисления их идентификаторов, с учетом типа.
write(<список вывода>); write(„сумма:‟,sum); writeln(a,b,c); Write(р:6:4); -для переменных вещественного типа.		Процедура вывода на экран. Происходит вывод значений указанных переменных и текста.				Значения выводятся в порядке перечисления в списке. Элементы списка вывода отделяются друг от друга запятой. Текст заключается в апострофы.
Окончание ln означает, что после выполнения оператора курсор перейдет в новую строку.
«переменная»:= «выражение».			Оператор присваивания. Происходит присвоение переменной значения указанного выражения.		Необходимо, чтобы значение выражения и переменная были совместимы по типу.
If <условие>then begin <операторы1> end else begin <операторы2> end; - полная форма If <условие>then begin <операторы> end;			Условный оператор. В зависимости от истинности условия выполняет ту или иную серию операторов.		Then – тогда , else - иначе. Перед else ; не ставится. Если по той или иной ветви оператор один, то его можно не заключать в операторные скобки. Если условие сложное то используются логические операции and, or, not и части условия берутся в алгебраические скобки.
	- краткая форма
	Формат			Назначение			Правила использования
	Case <выражение> of <значение1>: begin <операторы1> end; <значение2>: begin <операторы2> end; . . <значениеN>: begin <операторыN> end else begin <операторы> end; end;			Оператор выбора. Находит значение выражения, ищет его в списке вариантов значений и выполняет соответствующую серию операторов.			Если по ветви оператор один, то операторные скобки можно не писать. Веточку «иначе» иногда не используют.
	While <условие>do begin <тело цикла> end;			Оператор цикла с предусловием. Пока условие истинно повторяется тело цикла.			Условие может быть простым и сложным. Если тело цикла состоит из одного оператора, то операторные скобки не пишут.
	Repeat <тело цикла> Until<условие>;			Оператор цикла с постусловием. Повторяй тело цикла, до выполнения условия.			Те же правила. Тело цикла хоть раз да выполнится.
	For<пар.>:=<н.з.>to(downto)<к.з.> do begin <тело цикла> end;			Оператор цикла с параметром. Повторяй тело цикла, пока параметр цикла не достигнет конечного значения.			to – увеличить параметр на 1, downto – уменьшить параметр на 1. Параметр цикла не может быть вещественного типа. Если тело цикла состоит из одного оператора, то операторные скобки не пишут.

 Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Оно составляется из чисел, переменных, арифметических операций, функций, скобок.

В среде BorlandPascal выполнимы следующие арифметические операции:

+, -, *, /, div (деление нацело: 26 div 7=3), mod (деление с остатком: 26 mod 7=5). Если эти операции выполняются над целыми числами, то результатом будет целое число (! Исключение составляет операция / - результат, при выполнении этой операции- вещественное число real).

Операции div и mod выполнимы только с целыми числами.

В среде BorlandPascal выполнимы следующие арифметические функции:

Abs(x)-модуль числа х, sqr(x)- квадрат числа х, sqrt(x)-квадратный корень из числа х, tranc(x)- целая часть числа х, round(x)- округление числа х до целого.

Правила записи арифметических выражений:

1. Выражение записывается в строчку без пробелов и переносов.

2. Не допускается следование двух знаков подряд.

3. Выражения в скобках выполняются в первую очередь.

4. Операции выполняются в порядке приоритета: - функция - *, /, div, mod - +, -.

Задачи

1. Составить программу, вычисляющую значение арифметического выражения:

x⁴.

2. Составить программу к решению задачи: «Дано пятизначное число. Посчитать сумму его цифр».

3. Составить программу к решению задачи: «Дано пятизначное число. Если первые две его цифры четные, а последняя ноль, или первая и последняя нечетные, то выведите на экран его среднюю цифру, а иначе посчитать сумму цифр».

4. Определить результат выполнения программы, составив таблицу истинности условия:

Var a, b, c:integer;

Begin

A:=10; b:=2; c:=6;

If ((a mod 2=0) or (a mod 3=0)) and (not(b>c) and (a>b)) then write(a) else write(b); End.

5. Составить программу к решению задачи: «Дано число a. Вывести ответ: каким будет значение выражения (a+2)²-24 (отрицательным, положительным, нулем)».

6. Составить программу к решению задачи: «Дано трехзначное число. Найти в нем максимальную цифру».

7. Составить программу к решению задачи: «Даны четыре различных числа. Найти сумму не максимального и не минимального из них».

8. Составить программу к решению задачи: «По номеру дня недели вывести его название».

10. * Составить программу к решению задачи: «Попадет ли точка в заштрихованную

Комментарий:

Точка попадет в заштрихованную область, если она будет расположена над прямыми L и осью X, правее оси У и внутри окружности. y=kx+b – уравнение прямой, проходящей через две точки.

То есть точка лежит на прямой, если выполняется равенство: y=kx+b.

А если точка лежит под прямой, то должно выполняться неравенство y<kx+b. А если точка лежит над прямой, то должно выполняться неравенство y>kx+b.

y²R² - уравнение окружности с центром в начале координат и радиусом R.

То есть точка лежит на окружности, если выполняется равенство: y²x²R² А если точка лежит внутри окружности, то должно выполняться неравенство y²x²R².

А если точка лежит вне окружности, то должно выполняться неравенство y²x²R². Осталось найти уравнения линий и составить условие.

11. Составить программу к решению задачи: «Попадет ли точка в заштрихованную область?»

12. Составить программу к решению задачи: «Вывести на экран 100 раз «Привет!»».

13. Составить программу к решению задачи: «Вывести на экран n раз «Привет!»».

14. Составить программу к решению задачи: «Ввести с клавиатуры n чисел».

15. Составить программу к решению задачи: «Найти среднее арифметическое n чисел, введенных с клавиатуры».

16. Составить программу к решению задачи: «Найти количество четных положительных чисел из n чисел, введенных с клавиатуры».

17. Составить программу к решению задачи: «Найти максимальное число из n чисел, введенных с клавиатуры».

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

19. Составить программу к решению задачи: «Найти факториал заданного числа».

20. Составить программу к решению задачи: «Найти а^х».

21. Составить программу к решению задачи: «Найти делители числа n».

22. Составить программу к решению задачи: «Определить, является ли число простым».

23. Составить программу к решению задачи: «Вводить числа с клавиатуры, пока не будет введено задуманное число, при этом выводить сообщение «много» или «мало».

24. Составить программу к решению задачи: «Вводить числа с клавиатуры, пока они следуют по возрастанию».

25. Составить программу к решению задачи: «Вводить числа, пока их сумма не превысит заданное число».

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

27. Составить программу к решению задачи: «Вывести все простые числа из диапазона от 2 до n».

28. Составить программу к решению задачи: «Напечатать в возрастающем порядке все трехзначные числа в записи которых нет одинаковых цифр».

29. Составить программу к решению задачи: «Вам выдали зарплату х рублей, купюрами по 100, 50, 10 и 1 рублю. Какие возможны варианты выдачи зарплаты». Ответ выводить в форме:

По 100р – а купюр.

По 50р – b купюр.

По 10р – с купюр.

По 1р – d купюр.

30. Составить программу к решению задачи: «Дано число n. Найти сумму и количество его цифр».

31. Составить программу к решению задачи: «Дано число n. Убрать его первую и последнюю цифры».

32. Составить программу к решению задачи: «Дано число n. Поменять местами его первую и последнюю цифры».

33. Составить программу к решению задачи: «Дано число n. Найти его максимальную цифру».

34. Составить программу к решению задачи: «Дано число n. Перевернуть число».

35. Составить программу к решению задачи: «Дано число n. Дописать к нему цфру k в начало и конец».

36. Составить программу к решению задачи: «Дано число. Возвести его в степень. Равную последней цифре».

37. Составить программу к решению задачи: «Даны числа n и k. И дана цифра m. Проверить, есть ли в записи числа n^k цифра m».

38. Составить программу к решению задачи: «Дано число n. Поменять местами максимальную цифру с минимальной».

39. * Составить программу к решению задачи: «Дано число n. Проверить, будут ли все цифры различными».

Часть I

I.1. Структурированный тип данных – массив. Особенности работы с одномерными массивами

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

Массивы бывают одномерные, двумерные и т.д. n-мерные. Это зависит от нумерации. Наиболее используемыми являются одномерные и двумерные массивы. Разберемся сначала с одномерными массивами.

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

Пример. Представьте себе поезд «Москва – Петербург», в состав которого входят n вагонов одинаковой вместимости, с различным количеством пассажиров. Данные об этом можно было бы представить в следующей таблице:

Поезд «Москва – Петербург»
№ вагона	1	2	3	4	……………..	n-1	n
Количество пассажиров	20	35	12	50	……………..	52	12

Таблица имеет имя «Москва – Петербург», элементами таблицы являются количества пассажиров в вагонах. Количества пассажиров – это данные целого типа. Чтобы узнать, сколько человек находится в том или ином вагоне, необходимо указать название поезда и номер вагона.

Чтобы выполнить с помощью компьютера математическую обработку данных такой таблицы, ее имя следует заменить идентификатором (например, Mosk_Peter, или M_P, или A, или tab и т.п.). К данным таблицы следует обращаться по номерам вагонов (например, если задали имя M_P, то M_P[1], M_P[n], и т.д.).

Номер элемента – не может быть вещественным числом!

Тип элементов массива, может быть и не целым. Например, таблица, содержащая данные о росте учеников класса в метрах:

Rost
№	1	2	3	4	……………………..	N
рост	1,56	1,70	1,48	1,69	…………………….	1,65

Пусть x – номер ученика, тогда все Rost[x] будут типа real.

Описание массивов

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

Var <идентификатор>: array[<тип индекса>] of <тип элементов>;

Идентификатор – имя переменной-массива.

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

Пример.

Var M_P: array[1..100] of byte;

Rost: array[1..50] of real;

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

1) Массив, максимальное количество элементов которого 100 штук, и все они являются данными целого типа byte;

2) Массив, максимальное количество элементов которого 50 штук, и все они являются данными вещественного типа real.

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

В первом случае, ячейка памяти M_P разобьется на 100 подряд идущих разделов, размером по одному байту каждый. В них, после ввода массива, будут расположены данные M_P[1], M_P[2] и т.д. Сама переменная-массив будет занимать 100 байтов памяти.

Во втором случае, ячейка Rost разобьется на 50 подряд идущих разделов, размером по 6 байт каждый. В них, после ввода массива, будут расположены данные Rost[1], Rost[2] и т.д. Весь массив будет занимать 300 байтов памяти.

Не обязательно, что все ячееки памяти будут заполнены. Это зависит от того, как будет вводиться массив.

Ввод массива

Ввод массива осуществляется по-элементно. Каждый элемент массива вводится процедурой read. Таким образом, если нужно ввести n элементов массива, то следует использовать оператор цикла.

Var A:array[1..100] of integer;

I,n: integer;

Begin

Read(n); {ввели количество элементов массива}

For i:=1 to n do read(a[i]); {от 1 до последнего каждый элемент вводится с клавиатуры}

End.

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

Вывод массива осуществляется по-элементно. Каждый элемент массива выводится процедурой write.

Var A:array[1..1000] of integer;

I,n: integer;

Begin

Read(n); {ввели количество элементов массива}

For i:=1 to n do read(a[i]); {от 1 до последнего каждый элемент вводится с клавиатуры}

For i:=1 to n do write(a[i],’ ‘); {от 1 до последнего каждый элемент выводится на экран}

End.

Действия над массивом как единым целым

1. Можно значения одного массива присвоить другому (при этом массивы должны быть однотипны):

Var A,B:array[1..500] of integer;

I,n: integer;

Begin

Read(n); {ввели количество элементов массива}

For i:=1 to n do read(a[i]); {от 1 до последнего каждый элемент массива А

вводится с клавиатуры }

For i:=1 to n do read(b[i]); {от 1 до последнего каждый элемент массива В

вводится с клавиатуры} A:=B; {все элементы массива А станут равны

соответствующим элементам массива В} For i:=1 to n do write(a[i],’ ‘); {от 1 до последнего каждый элемент массива А выводится на экран} End.;

2. Можно массивы сравнивать на «равно» и «не равно».

Const t=100;

Var A,B:array[1..t] of integer;

I,n: integer;

Begin

Read(n); {ввели количество элементов массива}

For i:=1 to n do read(a[i]); {от 1 до последнего каждый элемент массива А

вводится с клавиатуры}

For i:=1 to n do read(b[i]); {от 1 до последнего каждый элемент массива В

вводится с клавиатуры}

if A=B then wrte(‘все элементы массива А равны соответствующим элементам

массива В’);

if A<>B then wrte(‘среди элементов массивов А и В есть хотябы одна пара не

совпавших’);

End.

Работа с элементами массива

Каждый элемент массива имеет свое уникальное имя, которое складывается из имени массива и порядкового номера элемента: A[1], A[2], A[i], A[n div 2], A[n-2], A[n] и т.д. Так к ним и надо обращаться в программе.

Пример. Составить программу к решению задачи: «В состав поезда «Москва – Петербург» входят n вагонов одинаковой вместимости, с различным количеством пассажиров. Определить:

а) количество пассажиров поезда;

б) количество пустых вагонов;

Здесь предложен другой способ описания массива и использован новый раздел описательной части программы. Раздел Const предназначен для описания постоянных величин. Ячейка памяти t на протяжении всей программы будет хранить значение 100 и ее нельзя изменить при помощи операторов в исполнительной части программы. Константы могут быть и вещественными и структурированными – их тип определяется написанием. Например. Const r =56.89;

t=10;

Massiv : array[1..t] of integer=(4, 8, 0, 123, 0, 8, 5, 34, 4, 4);

Здесь описаны одна константа вещественного типа, одна – целого и одна константа-массив, элементы которого перечислены в круглых скобках.

в) номера пустых вагонов;

г) наибольшее количество пассажиров в вагоне;

д) номера вагонов с наибольшим количеством пассажиров».

Дано: M_P – массив, значениями которого будут количества пассажиров поезда

(элементы типа byte); n – количество вагонов в поезде( integer).

а) Найти: Sum - количество пассажиров поезда ( integer).

Решение.

Чтобы найти количество пассажиров поезда, нужно сложить количества пассажиров в каждом из вагонов, то есть, найти сумму элементов массива. Пусть i – номера элементов массива, т.е. переменная, принимающая целые значения от 1 до n (integer). Если перебирать с помощью цикла с параметром i номера элементов массива, к самим элементам можно обращаться по именам M_P[i] и добавлять их к общей сумме Sum. Программа к решению такой задачи будет выглядеть так:

Var M_P:array[1..100] of byte; n, i, Sum:integer; Begin

Writeln(‘введите количество вагонов поезда’);

Read(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(M_P[i]);

end;

Sum:=0;

For i:=1 to n do Sum:=Sum+M_P[i];

Writeln(‘Количество пассажиров поезда ’,Sum,’ человек’); End.

б) Найти: kol - количество пустых вагонов поезда ( byte).

Решение.

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

Программа к решению такой задачи будет выглядеть так:

Var M_P:array[1..100] of byte; n, i:integer; kol:byte; Begin

Writeln(‘введите количество вагонов поезда’);

Readln(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(M_P[i]);

end; kol:=0;

For i:=1 to n do if M_P[i]=0 then kol:=kol+1; Writeln(‘В данном поезде ’,kol,’ пустых вагонов’); End.

в) Найти: i - номера пустых вагонов поезда ( integer).

Решение.

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

Var M_P:array[1..100] of byte;

n, i:integer;

Begin

Writeln(‘введите количество вагонов поезда’);

Readln(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(M_P[i]); end;

For i:=1 to n do if M_P[i]=0 then Writeln(‘Вагон с номером ’,i,’ пустой’); End.

г) Найти: max – наибольшее количество пассажиров в вагоне ( byte).

Решение.

Чтобы найти наибольшее количество пассажиров в вагоне поезда, нужно определить максимальный элемент массива. Примем за «максимальный» первый элемент массива (занесем его значение в переменную max). Остальные будем с ним сравнивать (если элемент массива больше, чем max, то его значение будет занесено в переменную max). В итоге, когда будут просмотрены все элементы массива, в переменной max окажется максимальный элемент.

Программа к решению такой задачи будет выглядеть так:

Var M_P:array[1..100] of byte;

n, i:integer; max:byte; Begin

Writeln(‘введите количество вагонов поезда’);

Readln(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(M_P[i]);

end;

max:=M_P[1];

For i:=2 to n do if M_P[i]>max then max:=M_P[i];

Writeln(‘Максимальное количество пассажиров в одном вагоне этого поезда’,max,’ человек’); End.

д) Найти: i – номера вагонов с наибольшим количеством пассажиров (integer). Решение.

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

Var M_P:array[1..100] of byte;

n, i:integer; max:byte; Begin

Writeln(‘введите количество вагонов поезда’);

Readln(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(M_P[i]);

end;

max:=M_P[1];

For i:=2 to n do if M_P[i]>max then max:=M_P[i];

For i:=1 to n do if M_P[i]=max then Writeln(‘В ’,i,’-ом вагоне проезжает максимальное количество пассажиров’); End.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение одномерных массивов?

Где и как описывать одномерный массив?

Как производить ввод и вывод одномерного массива?

Какие операции можно производить над одномерными массивами? В каком случае эти операции выполнимы?

Как производится обращение к элементам одномерного массива?

Составить программу к решению задачи: «Дан одномерный массив целых чисел. Вывести на экран его элементы а) кратные 5;

б) неотрицательные;

в) четные;

г) с четными номерами;

д) однозначные;

е) номера, которых являются степенями 2».

Составить программу к решению задачи: «Дан одномерный массив целых чисел. Посчитать количество элементов массива а) кратных 3;

б) отрицательных;

в) нечетных».

Второй блок

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

Составить программу к решению задачи: «Дан одномерный массив целых чисел. Заменить четные элементы массива единицей, а нечетные нулем».

§ Составить программу к решению задачи: «Дан одномерный массив целых чисел, состоящий из n элементов (n>8). Вывести элементы массива с третьей позиции по восьмую».

Составить программу к решению задачи: «Дан одномерный массив целых чисел, состоящий из n элементов и целые числа a и b. Если a и b, могут быть номерами элементов данного массива, то вывести элементы массива с апозиции до b-позиции».

 Составить программу к решению задачи: «Вывести на экран все элементы начиная с позиции минимального до позиции максимального».

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

Третий блок

 Составить программу к решению задачи: «Дан массив, элементами которого являются средние температуры, за каждый день в июле месяце нынешнего года. Найти и вывести на экран среднемесячную температуру».

Составить программу к решению задачи: «Дан массив, элементами которого являются средние температуры, за каждый день в июле месяце нынешнего года. Найти и вывести на экран количество дней, когда температура превышала х градусов».

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

Составить программу к решению задачи: «Дан массив, элементами которого являются данные о росте учеников класса. Найти рост самого высокого и самого низкого учеников класса».

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

I.2. Формирование одномерных массивов

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

Пример 1. «На начальной станции производится посадка на поезд «МоскваПетербург». По приказу начальника станции состав следует укомплектовать следующим образом: посадку пассажиров производить только в вагоны с нечетными номерами; в первый вагон посадить 40 человек, а в каждый последующий на два человека меньше, чем в предыдущий. Вывести на экран распределение пассажиров, если поезд состоит из n вагонов».

Дано: n – количество вагонов поезда (integer).

Найти: M_P – массив, элементами которого будут количества пассажиров поезда.

Решение: Чтобы заполнить массив, необходимо обратиться к каждому из его элементов M_P[i], где i – номер элемента (от 1 до n). Это можно осуществить посредством оператора цикла с параметром. Заполнять M_P[i] мы будем только тогда, когда i – нечетное число. Следовательно, в теле цикла будет условный оператор. Каждому элементу массива с нечетным номером будет присвоено определенное значение. Пусть это значение формируется в переменной k. Первоначальное значение этой переменной 40, но после каждого присваивания значение переменной должно уменьшаться на 2. Но может оказаться так, что вагонов с нечетными номерами слишком много и пассажиров на всех не хватит. Тогда, уменьшая переменную k на 2, мы в конце-концов начнем получать отрицательные числа. Такого быть не должно. Поэтому процесс заполнения элементов массива должен продолжаться только в случае положительного значения переменной k.

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

Var n,i:integer; k:byte;

M_P:array[1..100] of byte;

Begin

Writeln(‘введите количество вагонов поезда’);

Read(n);

K:=40;

For i:=1 to n do if (i mod 2=1) and (k>0) then begin

M_P[i]:=k; k:=k-2; end;

Writeln(‘пассажиры распределятся следующим образом:’); for i:=1 to n do write(M_P[i],’ ‘); End.

Пример 2. «Из товарного состава, везущего уголь, следует сформировать новый, исключив пустые вагоны. Каков будет новый состав, если первый состоял из n вагонов, по-разному загруженных углем?».

Дано: n – количество вагонов поезда (integer).

U1 – массив, элементами которого будут массы угля в тоннах в каждом из вагонов

(real).

Найти: U2 – массив, элементами которого будут массы угля в тоннах в каждом из вагонов, после исключения пустых вагонов (real).

Решение: Чтобы заполнить массив U2, необходимо обратиться к каждому из элементов U1[i], где i – номер элемента (от 1 до n). Это можно осуществить посредством оператора цикла с параметром. Заполнять U2[i] мы будем только тогда, когда U1[i] – число не равное 0. Следовательно, в теле цикла будет условный оператор. Чтобы вывести на экран полученный массив, необходимо знать количество элементов в нем. Пусть k – количество элементов массива U2. Вначале значение этой переменной равно 0. Перед каждым присваиванием элементу массива U2 его значения, значение переменной k должно увеличиваться на 1. Программа к решению задачи может выглядеть так:

Var n, i, k: integer;

U1, U2:array[1..100] of real;

Begin

Writeln(‘введите количество вагонов первого состава’);

Read(n);

For i:=1 to n do begin

Writeln(‘введите вес угля в ‘,i,’-ом вагоне’);

Read(U1[i]);

end;

k:=0;

For i:=1 to n do if U1[i] <>0 then begin

k:=k+1; U2[k]:=U1[i];

end;

Writeln(‘новый состав будет следующим:’);

for i:=1 to k do write(U2[i],’ ‘); End.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение одномерных массивов?

Как производить ввод и вывод одномерного массива?

Какими способами можно сформировать одномерный массив?

Составить программу к решению задачи: «Сформировать массив: 1 2 3 4…n».

Составить программу к решению задачи: «Сформировать массив из n элементов: 5 0 5 0…».

§ Составить программу к решению задачи: «Сформировать массив из степеней числа 2 с первой по десятую степень».

§ Составить программу к решению задачи: «Сформировать массив:

1 1 1 2 2 2 3 3 3…n n n».

Составить программу к решению задачи: «Сформировать массив из степеней числа 3 с первой по 15-ую, исключив числа кратные 9.

Второй блок

§ Составить программу к решению задачи: «Дан массив, элементами которого являются данные о количестве конфет в новогодних подарках. Сформировать новый массив, исключив из исходного массива данные о подарках, где меньше 10 конфет или больше 150».

Составить программу к решению задачи: «Получить массив b, выбросив из массива a все элементы, совпадающие с заданным числом k».

Составить программу к решению задачи: «Получить массив С, записав на четные места элементы массива А, а на нечетные – элементы массива В».

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

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

Составить программу к решению задачи: «Сформировать массив из чисел Фибоначчи». Последовательность чисел Фибоначчи: 1 1 2 3 5 8 13 … (каждое последующее число равно сумме предыдущих двух).

I.3. Еще задачи на одномерные массивы

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

Пример. Составить программу к решению задачи: «Чтобы не нарушить равновесие товарного состава, необходимо поменять местами вагоны с максимальной и минимальной массой груза».

Дано: Sostav – массив, значениями которого будут массы груза в каждом из вагонов

(элементы типа real); n – количество вагонов в составе( integer).

Найти: Sostav – массив, в котором переставили два элемента местами.

Решение.

Чтобы поменять местами два элемента массива, необходимо знать их места, то есть номера этих элементов. Чтобы найти максимальный элемент массива и его номер, примем за «максимальный» первый элемент массива (занесем его значение в переменную max). Номер «максимального» элемента соответственно равен единице (занесем его значение в переменную nommax). Остальные элементы будем сравнивать с переменной max и при необходимости менять ее значение и значение переменной nommax. В итоге, когда будут просмотрены все элементы массива, в переменной max окажется максимальный элемент, а в переменной nommax его номер. Аналогично отыщем значения переменных min и nommin. Теперь осталось поставить на место максимального элемента минимальный (Sostav[nommax]:=min), а на место минимального – максимальный (Sostav[nommin]:=max) или поменять местами значения переменных Sostav[nommax] и Sostav[nommin] используя третью переменную.

Программа к решению такой задачи может выглядеть так:

Var Sostav:array[1..100] of real; Nommax, nommin, n, i:integer;

max, min:real; Begin

Writeln(‘введите количество вагонов поезда’);

Readln(n);

For i:=1 to n do begin

Writeln(‘введите количество пассажиров в ‘,i,’-ом вагоне’);

Read(Sostav[i]);

end;

max:= Sostav[1]; nommax:=1; min:= Sostav[1]; nommin:=1;

For i:=1 to n do begin

If Sostav[i]>max then begin max:= Sostav[i]; nommax:=i; end;

If Sostav[i]<min then begin min:= Sostav[i]; nommin:=i; end;

End;

Sostav[nommax]:=min;

Sostav[nommin];:=max;

Writeln(‘После перемены вагонов местами, состав примет вид:’);

For i:=1 to n do write(Sostav[i]:4:2); End.

Вопросы и задания:

Первый блок

Дайте определение одномерного массива.

Как производится обращение к элементам одномерного массива?

Что необходимо знать, чтобы поменять местами два элемента одномерного массива?

Составить программу к решению задачи: «Дан одномерный массив. Поменять местами первый и последний элементы массива».

Составить программу к решению задачи: «Дан одномерный массив и число k. Если среди его элементов есть число k, то поменять его местами с максимальным элементом».

Составить программу к решению задачи: «Дан одномерный массив и число k. Заменить каждый его элемент, меньший числа k, числом a[i] k.

Второй блок

v Составить программу к решению задачи: «Определить количество одинаковых элементов в массиве (считается, что повторяющийся элемент один)».

v Составить программу к решению задачи: «В массиве а найти размер группы (группа одна)».

v Составить программу к решению задачи: «В массиве а найти самую длинную группу».

I.4. Двумерные массивы. Особенности работы с двумерными массивами

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

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

Данные о весе учащихся восьмой параллели
	1	2	3	4	……………………………………….	n-1	n
8a	50.8	55.9	40.3	45.8	……………………………………….	45.8	50.9
8б	45.6	43.0	50.8	48.7	……………………………………….	49.0	47.7
8в	50.7	48.9	45.8	44.9	………………………………………..	45.0	45.0
8г	54.0	56.9	45.7	40.7	………………………………………..	43.8	54.0

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

Описание массивов

Описание двумерных массивов аналогично описанию одномерных.

Var <идентификатор>: array[<типы индексов>] of <тип элементов>;

Идентификатор – имя массива.

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

Например:

Var Ves: array[1..4,1..35] of real;

Здесь описан массив, максимальное количество элементов которого 4*35=140 штук, и все они являются данными вещественного типа real. Такой массив как раз подойдет для хранения таблицы данных о весе учащихся восьмой параллели. В памяти компьютера выделится ячейка, которая разобьется на 140 разделов, размером по 6 байт. В них, после ввода массива, будут расположены данные

Ves[1,1], Ves[1,2], ….Ves[1,n], Ves[2,1], Ves[2,2] и т.д. Весь массив будет занимать 840 байтов памяти.

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

Ввод массива

Ввод массива осуществляется покомпонентно. Каждый элемент массива вводится оператором read.

Var A:array[1..10,1..10] of integer;

I,j,n,m: integer;

Begin

Read(n,m); {ввели количество строк и столбцов массива}

For i:=1 to n do {перебираем номера строк}

For j:=1 to m do read(a[i,j]); {от 1 до последнего каждый элемент вводится с клавиатуры: вначале элементы первой строки, затем второй и т.д.}

End.

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

Вывод массива осуществляется покомпонентно. Каждый элемент массива выводится оператором write.

Const t=100;

Var A:array[1..t,1..t] of integer;

I,j,n,m: integer;

Begin

Read(n,m); {ввели количество элементов массива}

For i:=1 to n do For j:=1 to m do read(a[i,j]); { ввод массива с клавиатуры} For i:=1 to n do begin

For i:=1 to n do write(a[i,j],’ ‘); {вывод элементов i-ой строки} Writeln; {переход на новую строку} end;

End.

Двумерные массивы часто называют матрицами.

Действия над элементами массива

Каждый элемент массива имеет свое уникальное имя, которое складывается из имени массива и порядкового номера элемента: A[1,6], A[4,2], A[i,j], A[n div 2,4], A[n-2,m-7], A[n,m] и т.д. Так к ним и надо обращаться в программе.

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

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

Необходимо посчитать:

а) общий балл, набранный в параллели;

б) средний балл по параллели;

в) количество учеников в параллели, не набравших ни одного балла;

г) максимальный балл по параллели;

д) номера победителей по параллели;

е) номера победителей в каждом из классов.

Дано: A – массив, значениями которого будут баллы участников олимпиады

(элементы типа byte);

n – количество классов в восьмой параллели ( byte); m – количество представителей от класса (byte).

а) Найти: Oball – общий балл, набранный в параллели ( integer).

Решение.

Чтобы найти общий балл, нужно сложить баллы, набранные каждым из учеников, то есть, найти сумму элементов массива. Пусть i – номера строк массива, т.е. переменная, принимающая целые значения от 1 до n (byte), а j – номера столбцов массива, т.е. переменная, принимающая целые значения от 1 до m (byte). Если перебирать с помощью цикла с параметром i номера строк массива, а с помощью вложенного цикла с параметром j номера столбцов, то к самим элементам можно обращаться по именам А[i,j] и добавлять их к общей сумме Oball. Программа к решению такой задачи будет выглядеть так:

Var A:array[1..10,1..35] of byte;

n, m, i, j:byte; Oball:integer; Begin

Writeln(‘введите количество классов в параллели’);

Read(n);

Writeln(‘введите количество участников от каждого из классов’);

Readln(m);

For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’, j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end;

Oball:=0;

For i:=1 to n do For j:=1 to m do Oball:=Oball+A[i,j];

Writeln(‘Общий балл по параллели- ’,Oball); End.

б) Найти: Sball – средний балл по параллели ( real).

Решение.

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

Var A:array[1..10,1..35] of byte;

n, m, i, j:byte; Oball:integer; Sball:real; Begin

Writeln(‘введите количество классов в параллели’); Read(n);

Writeln(‘введите количество участников от каждого из классов’); Read(m); For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’, j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end;

Oball:=0;

For i:=1 to n do For j:=1 to m do Oball:=Oball+A[i,j]; Sball:=Oball/(n*m);

Writeln(‘Средний балл по параллели- ’,Sball:4:2); End.

в) Найти: Kol - количество учеников в параллели, не набравших ни одного балла

(byte). Решение.

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

Var A:array[1..10,1..35] of byte;

n, m, i, j, kol:byte;

Begin

Writeln(‘введите количество классов в параллели’);

Read(n);

Writeln(‘введите количество участников от каждого из классов’);

Read(m);

For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’,j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end; kol:=0;

For i:=1 to n do For j:=1 to m do if A[i,j]=0 then kol:=kol+1; Writeln(‘Ни одного балла не набрали ’, kol,’ учеников’); End.

г) Найти: Max – максимальный балл по параллели (byte).

Решение.

Решение задачи сводится к нахождению максимального элемента массива. Примем за «максимальный» первый элемент массива (занесем его значение в переменную max). Остальные будем с ним сравнивать (если элемент массива больше, чем max, то его значение будет занесено в переменную max). В итоге, когда будут просмотрены все элементы массива, в переменной max окажется максимальный элемент. Программа к решению такой задачи будет выглядеть так:

Var A:array[1..10,1..35] of byte; n, m, i, j, max:byte; Begin

Writeln(‘введите количество классов в параллели’);

Read(n);

Writeln(‘введите количество участников от каждого из классов’);

Read(m);

For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’,j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end;

max:=A[1,1];

For i:=1 to n do For j:=1 to m do if A[i,j]>max then max:=a[i,j];

Writeln(‘Максимальный балл по параллели - ’, max); End.

д) Найти: i , j – номера победителей по параллели (byte).

Решение.

Пусть max – максимальный балл по параллели. Это переменная типа byte, значение которой мы уже умеем находить. Чтобы найти номера победителей, достаточно вывести на экран номера строк и столбцов элементов массива равных значению переменной max.

Программа к решению такой задачи будет выглядеть так:

Var A:array[1..10,1..35] of byte; n, m, i, j, max:byte; Begin

Writeln(‘введите количество классов в параллели’);

Read(n);

Writeln(‘введите количество участников от каждого из классов’);

Read(m);

For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’,j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end;

max:=A[1,1];

For i:=1 to n do For j:=1 to m do if A[i,j]>max then max:=a[i,j];

Writeln(‘Номера победителей’);

Writeln(‘N группы N ученика ’);

For i:=1 to n do For j:=1 to m do if A[i,j]=max then writeln( ‘ ’, i, ‘ ’, ‘ ’,j); End.

е) Найти: i, j – номера победителей в каждом из классов.

Решение.

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

*************************************************************************

{обрабатываем первую строку}

i:=1;

{в качестве «максимального» выбираем первый элемент в рассматриваемой строке}

max:=A[i,1]; {перебираем номера элементов в рассматриваемой строке с номером i, равным 1}

For j:=1 to m do

if A[i,j]>max then max:=a[i,j]; { ищем максимальный элемент в строке}

Writeln(‘Номера победителей ’,i, ‘-ой строки’);

{выводим номера

элементов, равных по величине значению переменной max}

For j:=1 to m do if A[i,j]=max then writeln( ‘ ’, j);

************************************************************************* Аналогичным образом, необходимо обработать все строки массива. Переменная i , отвечающая за номер строки, должна постепенно принять все свои значения от 1 до n. Предложенный фрагмент следует сделать телом цикла по параметру i .

Программа к решению такой задачи будет выглядеть так:

Var A:array[1..10,1..35] of byte; n, m, i, j, max:byte; Begin

Writeln(‘введите количество классов в параллели’);

Read(n); Writeln(‘введите количество участников от каждого из классов’);

Read(m);

For i:=1 to n do For j:=1 to m do begin

Writeln(‘введите балл ’,j, ‘-го ученика в ’, i, ‘-ой группе’);

Read(A[i,j]); end;

For i:=1 to n do begin

max:=A[i,1];

For j:=1 to m do if A[i,j]>max then max:=a[i,j];

Writeln(‘Номера победителей ’,i, ‘-ой строки’);

For j:=1 to m do if A[i,j]=max then writeln( ‘ ’, j); end;

End.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение двумерных массивов?

Где и как описывать двумерный массив?

Как производить ввод и вывод двумерного массива?

Как производится обращение к элементам двумерного массива? Составить программу к решению задачи «Дан двумерный массив целых чисел. Найти произведение его элементов».

Составить программу к решению задачи «Дан двумерный массив целых чисел и число х. Найти количество четных элементов массива больших по модулю числа х».

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

Второй блок

Составить программу к решению задачи «Дан двумерный массив вещественных чисел. Найти среднее арифметическое элементов его первой строки». Составить программу к решению задачи «Дан двумерный массив целых чисел. Найти сумму четных элементов его k-го столбца».

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

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

Третий блок

§ Составить программу к решению задачи «Дан двумерный массив целых чисел (квадратная матрица). Посчитать количество отрицательных элементов на главной диагонали. Если таких элементов нет, то сообщить об этом».

§ Составить программу к решению задачи «Дана квадратная матрица целых чисел. Найти количество нулей на ее побочной диагонали».

Составить программу к решению задачи «Дана квадратная матрица целых чисел. Найти сумму положительных элементов, расположенных над главной диагональю и сумму отрицательных, расположенных под главной диагональю».

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

I.5. Формирование двумерных массивов

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

Пример 1. Сформировать таблицу умножения, имеющую вид:

1	2	3	..	m
2	4	6	..	2m
3	6	9	..	3m
. .	. .	. .	. .	. .
n	2n	3n	..	mn

Дано: n – количество строк массива (integer); m – количество столбцов массива (integer). Найти: А – массив-«таблица умножения».

Решение: Чтобы заполнить массив, необходимо обратиться к каждому из его элементов A[i,j], где i – номер строки (от 1 до n), а j – номер столбца (от 1 до m). Это можно осуществить с помощью вложенных циклов с параметром. Заполнять А[i,j] мы будем произведением его номера строки и столбца. Программа к решению задачи может выглядеть так:

Var n, m, i, j:integer;

A:array[1..30,1..30] of integer;

Begin

Writeln(‘введите количество строк и столбцов’);

Read(n,m);

For i:=1 to n do

For j:=1 to m do A[i,j]:=i*j; Writeln(‘Таблица умножения’); for i:=1 to n do begin

for j:=1 to m do write(A[i,j],’ ‘);

writeln; end;

End.

Пример 2. Сформировать таблицу степеней, имеющую вид:

1	2	3	….	m
1	4	9	….	m²
1	8	27	….	m³
1	16	81	….	m⁴
. .	. .	. .	….	….
1ⁿ	2ⁿ	3ⁿ	….	mⁿ

Дано: n – максимальный показатель степени в таблице (integer); m – максимальное основание степени (integer).

Найти: А – массив, элементами которого будут степени чисел (longint).

Решение: Чтобы заполнить массив A, необходимо обратиться к каждому из элементов A[i,j]. Очевидно, что элементы заполняются по формуле A[i,j]:=i ^j. Такой массив удобно заполнять по столбцам. Если рассматривать отдельный столбец массива, то можно заметить, что в нем каждый последующий элемент равен предыдущему, умноженному на номер столбца. Для заполнения фиксированного столбца с номером j можно применить следующий фрагмент программы.

*************************************************************************

{первый элемент столбца равен номеру столбца}

A[1,j]:=j;

{остальные элементы заполняются по выше сказанному принципу}

For i:=2 to n do A[i,j]:=A[i-1,j]*j

*************************************************************************

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

Var A:array[1..10,1..10] of longint; n, m, i, j:byte;

Begin

Read(n);

Read(m);

For j:=1 to m do begin

A[1,j]:=j;

For i:=2 to n do A[i,j]:=A[i-1,j]*j;

end;

For i:=1 to n do begin

For j:=1 to m do Write(A[i,j],’ ‘); writeln;

end;

End.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение двумерных массивов?

Где и как описывать двумерный массив?

Как производить ввод и вывод двумерного массива? Как производится обращение к элементам двумерного массива?

Составить программу формирования массива:

а)

1	2	...	.. n
2	0	0	0 n-1
.. .	0	0	0 …
.. .	0	0	0 …
n б)	n-1	…	… 1
1	1	...	.. 1
2	0	0	0 2
.. .	0	0	0 …
.. .	0	0	0 …
n в)	n	n	n n
1	2	...	.. n
2	3	…	n 0
3	4	…	0 0
.. .	…	…	… …
n Второй блок	0	…	… 0
Составить программу формирования массива:  г) 0 0 ... .. 1 0 0 … 2 0 .. … … 0 0 . 0 n-1 … 0 0 n 0 … … 0

д)
1 2			...	.. n
n n-1			…	… 1
1 2			…	… n
n n-1			…	… 1
… …			…	… …
е)			…	… …
n		0	...	.. 0
0		n-1	…	0 0
.. .		…	…	… …
0		0	…	2 0
0 ж)		0	…	… 1
	1	1	...	1 1
	1	0	…	0 1
	.. .	…	…	… …
	1	0	…	0 1
	1	1	…	1 1
	з)
	1	1	...	1 1
	0	1	…	1 0
	.. .	…	1	… …
	0	1	…	1 0
	1	1	…	1 1
	и)
	1	0	...	0 1
	1	1	…	1 1
	.. .	…	1	… …
	1	1	…	1 1
	1	0	…	0 1
Третий блок		0	…	0 1
Составить программу формирования массива:  к) 1 1 ... .. 1 2 2 … 2 0 ... … … 0 0 n- n-1 … 0 0 1 n 0 … … 0

л)

11…..1122..…22

11…..1122…..22 n

………….………

11…..1122..…22

33…..3344..…44

33..…3344…..44

……….…………

33…..3344…..44

Составить программу к решению задачи: «Дано целое число х. Сформировать массив:

1	Х¹	Х²	…	Xⁿ
X¹	0	0	0	…
X²	0	0	0	X²
…	…	…	…	X¹
Xⁿ	Xn-1	…	X¹	1

I.6. Еще задачи на двумерные массивы

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

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

Дано: Z – массив, значениями которого будут данные о заработной плате

(элементы типа real); m – количество строк таблицы ( byte); n – количество столбцов таблицы (byte); n1, n2 – номера столбцов, подлежащих обмену (byte).

Результат: Z – измененный массив.

Решение.

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

Необходимо поменять местами Z[1,n1] c Z[1,n2], Z[2,n1] c Z[2,n2] и т.д., Z[m,n1] c Z[m,n2]. Нетрудно заметить, что эти пары отличаются номером строки, который изменяется с шагом +1. Следует повторять один и тот же процесс (менять две переменные местами) при этом изменять номер строки. Пусть i – номер строки, который изменяется от 1 до m, при этом производим обмен переменных Z[i,n1] и Z[i,n2] с помощью третей переменной x ( типа real, как и элементы массива). Программа к решению такой задачи будет выглядеть так:

Var Z:array[1..10,1..10] of real;

n, m, i,j, n1,n2 : byte; x : real;

Begin

Writeln(‘введите количество строк и столбцов’);

Read(m,n);

Writeln(‘введите таблицу’);

For i:=1 to m do For j:=1 to n do Read(Z[i,j]);

Writeln(‘введите номера столбцов для обмена’);

Read(n1,n2);

For i:=1 to m do begin x:=Z[i,n1]; Z[i,n1]:=Z[i,n2]; Z[i,n2]:=x; end;

Writeln(‘измененный массив’);

For i:=1 to m do begin

For j:=1 to n do write(Z[i,j],’ ‘);

Writeln;

End;

End.

Пример 2. Для финансового отчета бухгалтеру требуется обработать таблицу ежемесячных отчислений в пенсионный фонд работников предприятия. Для этого ему следует организовать в таблице две дополнительные колонки: «среднее арифметическое» и «всего». См. пример таблицы:

Табельный номер работника	номер месяца						дополнение
Табельный номер работника	1	2	3	4	…	n	Ср.ар.	Всего
1	$	$	$	$	…	$
2	$	$	$	$	…	$
3	$	$	$	$	…	$
:	:	:	:	:	:	:
m	$	$	$	$	…	$

В столбец «Ср.ар.» необходимо занести среднее арифметическое каждой строки, а в столбец «Всего» - сумму данных каждой строки.

Дано: P – массив, значениями которого будут данные об отчислениях в пенсионный фонд (элементы типа real); m – количество строк таблицы ( byte); n – количество столбцов таблицы (byte); Результат: P – дополненный массив.

Решение.

Для решения задачи необходимо заполнить столбцы с номерами n+1 и n+2. А следовательно, для каждой строки необходимо найти сумму (S) и среднее арифметическое (Ar) ее элементов. S и Ar переменные типа real.

В первой строке элементы имеют номера P[1,j], где j принимает значения от 1 до n.

Во второй строке элементы имеют номера P[2,j], где j принимает значения от 1 до n.

И т.д.

В m-ой строке элементы имеют номера P[m,j], где j принимает значения от 1 до n. Опять мы приходим к необходимости осуществлять одинаковый процесс, при этом меняя номер строки. Т.е. будем использовать вложенные циклы. При выводе результата следует не забывать, что в дополненном массиве будет на два столбца больше.

Программа к решению такой задачи может выглядеть так:

Var P:array[1..10,1..10] of real;

n, m, i,j, n1,n2 : byte; S,Ar : real; Begin

Writeln(‘введите количество строк и столбцов’);

Read(m,n);

Writeln(‘введите таблицу’);

For i:=1 to m do For j:=1 to n do Read(P[i,j]);

For i:=1 to m do begin

S:=0;

Ar:=0;

For j:=1 to n do S:=S+P[I,j];

Ar:=S/n;

P[i,n+1]:=Ar;

P[i,n+2]:=S; end; Writeln(‘измененный массив’);

For i:=1 to m do begin

For j:=1 to n+2 do write(P[i,j],’ ‘);

Writeln;

End;

End.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение двумерных массивов?

Где и как описывать двумерный массив?

Как производить ввод и вывод двумерного массива?

Как производится обращение к элементам двумерного массива?

Дан двумерный массив. Поменять строку с номером к1 со строкой с номером к2.

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

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

Второй блок

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

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

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

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

Вывести его минимальный элемент с указанием его местоположения в массиве.

Дан массив. Найти максимальный элемент на его главной диагонали.

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

Дан массив. Доказать, что он содержит нечетное количество максимальных элементов.

Дан массив. Проверить, есть ли в нем одинаковые элементы.

Часть II

II.1. Сортировка массивов. Сортировка элементов одномерного массива методом простого выбора

Сортировка – один из наиболее распространенных процессов современной обработки данных.

 Сортировкой называется расстановка данных по определенному признаку.

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

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

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

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

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

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

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

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

Дано: A – массив, значениями которого будут целые числа (элементы типа integer); n – количество элементов массива (byte); Результат: A – отсортированный массив.

Решение.

Рассмотрим наиболее простой метод сортировки – метод простого выбора. Суть: Среди элементов массива находится минимальный и меняется местами с первым. Затем, среди элементов кроме первого, снова находится минимальный и меняется местами со вторым и т.д.

Пусть наш массив состоит из пяти элементов (n=5): 5 8 3 9 1. Первый шаг: 5 8 3 9 1 В результате: 1 8 3 9 5.

Второй шаг: 1 8 3 9 5 В результате: 1 3 8 9 5.

Третий шаг: 1 3 8 9 5 В результате: 1 3 5 9 8.

Четвертый шаг: 1 3 5 9 8 В результате: 1 3 5 8 9.

Вывод: при количестве элементов 5 штук, массив сортируется за четыре шага. Значит, при количестве элементов n штук – массив будет отсортирован за n-1 шаг. При этом, каждый шаг, минимальный элемент меняется местами с элементом, номер которого совпадает с номером шага. Причем, сам минимальный следует искать, начиная с этого элемента.

Пусть i – номер шага (от 1 до n-1), j- номера элементов, среди которых будет отыскиваться минимальный. Тогда j будет изменяться от i до n. Программа сортировки будет следующей:

Const t=50;

Var A: array[1..t] of integer; i,j,n,min,nom: integer;

Begin

Read(n);

For i:=1 to n do read(A[i]);

For i:=1 to n-1 do

Begin

Min:=A[i]; nom:=i;

For j:=i to n do if A[ j]<min then begin min:=A[ j]; nom:=j end;

A[nom]:=A[i]; A[i]:=min; end;

for i:=1 to n do write(A[i],’ ‘); end.

Вопросы и задания:

Дайте определение массива.

Каково предназначение массивов?

Что такое сортировка? Приведите примеры.

В чем заключается суть сортировки методом простого выбора?

Проиллюстрируйте на примере массива: 5 78 3 9 14 25 14 5

Закройте учебник и восстановите программу сортировки элементов массива по возрастанию.

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

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

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

II.2. Сортировка массивов. Сортировка элементов одномерного массива методом «пузырька»

Несмотря на простоту предыдущего метода сортировки, в кругу программистов особой популярностью пользуется «пузырьковый» метод. Рассмотрим его программную реализацию на примере той же задачи.

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

Решение.

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

Пусть наш массив состоит из пяти элементов (n=5): 5 8 3 9 1.

Первый шаг.

1 пара: 5 8 3 9 1 В результате: 5 8 3 9 1.

2 пара: 5 8 3 9 1 В результате: 5 3 8 9 1.

3 пара: 5 3 8 9 1 В результате: 5 3 8 9 1.

4 пара: 5 3 8 9 1 В результате: 5 3 8 1 9– всплыл первый пузырек!

Второй шаг:

1 пара: 5 3 8 1 9 В результате: 3 5 8 1 9.

2 пара: 3 5 8 1 9 В результате: 3 5 8 1 9.

3 пара: 3 5 8 1 9 В результате: 3 5 1 8 9 – всплыл второй пузырек!

Третий шаг:

1 пара: 3 5 1 8 9 В результате: 3 5 1 8 9.

2 пара: 3 5 1 8 9 В результате: 3 1 5 8 9- всплыл третий пузырек!

Четвертый шаг:

1 пара: 3 1 5 8 9 В результате: 1 3 5 8 9- всплыл четвертый пузырек!

Массив отсортирован!

Вывод: при количестве элементов 5 штук, массив сортируется за четыре шага. Значит, при количестве элементов n штук – массив будет отсортирован за n-1 шаг. Каждый шаг количество рассматриваемых пар уменьшается на 1: вначале n-1 пара, затем n-2 пары и т.д. до 1 пары. Следовательно, каждый шаг количество пар равно (n-номер шага).

Пусть i – номер шага (от 1 до n-1), j- количество пар. Тогда j будет изменяться от 1 до n-i.

Программа сортировки будет следующей:

Const t=50;

Var A: array[1..t] of integer;

I,j,n,x: integer;

Begin

Read(n);

For i:=1 to n do read(A[i]);

For i:=1 to n-1 do

For j:=1 to n-i do if A[ j]>A[ j+1] then begin x:=A[ j]; A[ j]:=A[ j+1]; A[ j+1]:=x; end; for i:=1 to n do write(A[i],’ ‘); end.

Вопросы и задания:

Первый блок

Дайте определение массива.

Каково предназначение массивов?

Что такое сортировка? Приведите примеры.

В чем заключается суть сортировки методом «пузырька»? Проиллюстрируйте на примере массива: 5 78 3 9 14 25 14 5

Закройте учебник и восстановите программу сортировки элементов массива по возрастанию методом «пузырька».

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

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

Второй блок

§ Дан массив. Отсортировать по возрастанию до позиции максимального элемента.

§ Дан массив. Отсортировать по возрастанию его часть после минимального элемента.

Дан массив. Отсортировать по убыванию от позиции максимального до позиции минимального.

Дан массив. Отсортировать по убыванию до позиции максимального (минимального) и после позиции минимального (максимального).

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

Третий блок

§ Объединить в один массив два отсортированных по возрастанию массива.

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

Четвертый блок

§ Дан двумерный массив. Отсортировать элементы в его строках по возрастанию.

Дан двумерный массив. Отсортировать по возрастанию элементы четных строк массива.

Дан двумерный массив. Отсортировать по убыванию элементы нечетных столбцов массива.

Задача: Дан массив. Отсортировать элементы его первого столбца по убыванию.

Дан массив. Отсортировать элементы его первой строки по возрастанию.

Часть III

III.1. Символьный тип данных

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

 Символьный тип данных – это один из простых (скалярных) типов языка Паскаль.

Переменная символьного типа занимает один байт памяти и может принимать одно из 256 значений (символов компьютерного алфавита).

В компьютерном алфавите 256 символов, они занесены в специальную таблицу кодировки ASCII, имеющую мировой стандарт. В первой части этой таблицы перечислены специальные символы, цифры и символы латинского алфавита. Вторая часть является альтернативной и содержит символы национального алфавита. Все символы в таблице пронумерованы от 0 до 255. Каждому символу сопоставлен двоичный код его номера.

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

Переменная символьного типа в разделе описания переменных идентифицируется служебным словом char.

Формат: <идентификатор> : char;

Пример.

Var a,b:char; Begin

A:=’t’;

B:=’+’; A:=b;

…. и т.д.

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

Для работы с этими переменными существуют функции:

Y:=Ord(a), где a-величинна символьного типа.

Результат Y – целое число в диапазоне от 0 до 255 (номер символа в таблице кодировки).

B:=Pred(a), где a- величина символьного типа. Результат B – предыдущий символ из таблицы кодировки.

B:=Succ(a), где a-величина символьного типа. Результат – последующий символ таблице кодировки.

A:=Chr(Y), где Y-величина целочисленного типа в диапазоне от 0 до 255. Результат A – символьная величина, где Y – номер ее символа в таблице кодировки.

Вопросы и задания:

Для чего используется символьный тип данных?

Как хранится символ в памяти компьютера?

Что собой представляет таблица кодировки ASCII?

Какие действия можно осуществлять над переменной символьного типа?

Какие функции работы с переменной символьного типа вы знаете? Как они выполняются?

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

§ Написать программу вывода на экран символов латинского алфавита.

Написать программу вывода на экран цифр.

Написать программу вывода на экран русский алфавит в форме АаБбВв….

Написать программы перехода заданной цифры а (величина целого типа) в символ ‟a‟ и обратно.

III.2. Строковый тип данных

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

Ø Строка – это последовательность символов таблицы кодировки компьютера.

Строковый тип данных относится к числу структурированных типов. Частично ее можно сравнить с одномерным массивом, элементы которого имеют тип char. Однако количество элементов массива мы обязаны четко оговаривать в описательной части программы, а количество символов в строке может изменяться в ходе выполнения программы от 0 до 255.

Ø Количество символов в строке называют ее длиной. Длина может лежать в диапазоне от 0 до 255.

Переменные строкового типа описывают в разделе описания переменных служебным словом string. Для экономии памяти после этого слова указывают в квадратных скобках максимальную длину строки. Если максимальная длина не будет указана, то подразумевают длину 255. Каждый символ занимает один байт памяти (код ASCII). Для строки из k символов в памяти компьютера отводится k+1 байт (k байт для хранения символов строки, а один байт для значения текущей длины строки).

текущая длина строки символы строки

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

Формат: <идентификатор> : string[максимальная длина строки];

Пример. Var S : string[20] ; Str : string;

В этом примере строка S займет в памяти компьютера 21 байт, а строка Str по умолчанию займет 256 байт.

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

Пример.

Var S : string[20] ;

Begin

S :=’computer’; строковые константы

Writeln(S,’- компьютер’);

Для обозначения пустой строки ставится два апострофа подряд (S:=‟‟; –пустая строка).

В отличие от массива строка вводится в память компьютера и выводится на экран целиком, а не поэлементно. Для ввода строки используется процедура ввода (readln). Название переводится как «читай строку».

Для вывода на экран используют процедуру вывода write (или writeln).

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

Строки можно соединять друг с другом, используя операцию сцепления «+».

Пример.

Var S : string[20] ; S1, S2 : string;

Begin

S :=’computer’;

S1 :=’IBM PC’;

S2 :=S+’ ‘+S1+’-популярный компьютер’; Writeln(S2); End.

В результате на экран будет выведена строка:

computer IBM PC-популярный компьютер

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

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

(=, <>, <, >, >=, <=).

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

Пример.

‘abc1’<’abc2’ ‘abc1bbbb’<’abc2’ ‘AAA’<’aaa’ ‘123’=’123’

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

Пример.

Var S : string[20] ; S1, S2 : string;

Begin

S :=’ДОМ’; S1 :=’САД’;

S2 :=S[1]+S1[2]+S[3]; Writeln(S2, S1[2]); End.

В результате на экран будет выведено: ДАМА

Пример. Составить программу, формирующую строку, состоящую из n „*‟.

Дано: n – количество звездочек (byte); Найти: S – строка (string);

Решение:

Пусть S – пустая строка, „*‟ – символ или строка, состоящая из одного символа. Если n раз к строке S прицепить строку „*‟, то получим то что требовалось.

Используем оператор цикла с параметром i. Где i – количество сцеплений(byte).

Программа решения задачи может быть такой:

Var S : string; n, i : byte;

Begin

S :=’’;

For i :=1 to n do S:=S+’*’;

Writeln(S, ‘-строка из звездочек’); End.

Для определения текущей длины строки существует функция:

Y:=Length(s)

S – величина строкового типа. Результат Y– текущая длина строки.

Пример. Дана строка. Подсчитать сколько в ней цифр.

Дано: S – строка (string);

Найти: k – количество цифр (byte); Решение:

Для решения задачи необходимо просмотреть все символы строки и выяснить расположены ли они в таблице ASCII в промежутке от „0‟ до „9‟. Для этого могут быть использованы операции отношения. Прежде чем просмотреть все символы нужно узнать длину строки (y).

Программа решения задачи может быть такой:

Var S : string; k, y, i : byte;

Begin

Readln(S);

Y:=length(S);

For i :=1 to y do if (‘0’<=S[i]) and (S[i]<=’9’) then k:=k+1;

Writeln(k, ‘-количество цифр в строке’); End.

Вопросы и задания:

Что такое строка?

Как производится описание строки?

Что называют длиной строки?

Как хранится строка в памяти компьютера?

Что такое строковая константа? Каково правило ее написания?

Как осуществить ввод и вывод строки?

Какие операции допустимы над строковыми величинами?

Как производится сравнение строк?

Как обратиться к символам строки?

Дана строка определить сколько в не знаков „*‟, „;‟ и „:‟.

 Составить программу, которая дублирует символы в строке („abc‟ – „aabbcc‟).

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

Составить программу, проверяющую является ли строка «перевертышем».

III.3. Процедуры и функции работы со строковыми величинами

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

Для работы с величинами строкового типа существуют функции:

S1 :=Copy(S, Poz, N)

S – величина строкового типа.

Poz, N – значения целого типа.

Результат S1– подстрока, длиной в N символов, выделенная из строки S, начиная с позиции Poz.

Пример. Получить из слова «дисковод» слово «воск».

Дано: «дисковод» – строковая константа, которую можно сохранить в переменной S1 (типа string);

Получить: «воск» – строковую константу, которую можно разместить в переменной

S2 (string);

Решение:

С помощью функции Copy вырежем из данной строки две подстроки «во» и «ск» и сцепим их операцией сцепления.

Программа решения задачи может быть такой:

Var S1, S2 : string; Begin

S1 :=’дисковод’;

S2:=copy(S1,6,2)+copy(s1,3,2); Writeln(S2); End.

Y :=Pos(S1, S)

S1,S – величины строкового типа.

Результат Y– целое число, равное номеру позиции, с которой строка S1 располагается в строке S. Если S1 не является подстрокой S, то результат равен 0.

Пример. Даны строка S и подстрока St. Выяснить входит ли эта подстрока в данную строку. Если входит, то напечатать номер символа строки S, с которого подстрока St входит в эту строку.

Дано: S, St– строки (типа string);

Найти: k – номер позиции, с которой строка St располагается в строке S. В противном случае распечатать сообщение.

Решение:

С помощью функции pos определим номер вхождения.

Если St не является подстрокой S, то результат равен 0. Программа решения задачи может быть такой:

Var St, S : string; k:byte;

Begin

Readln(S); Readln(St); k:=pos(St,S);

if k<>0 then writeln(‘подстрока ‘,St, ‘ входит в строку ‘,S,’ начиная с позиции ’,k) else writeln(‘подстрока ‘,St, ‘ не входит в строку ‘,S); End.

Для работы с переменными строкового типа существуют процедуры:

Delete(S, Poz, N) – удаляет из строки S подстроку, длиной в N символов, начиная с позиции Poz.

S – величина строкового типа.

Poz, N – значения целого типа.

Insert(S1, S2,Poz) – вставка строки S1 в строку S2 начиная с позиции Poz.

S1,S2 – величины строкового типа. Poz – значение целого типа.

Пример. Дана строка, состоящая из строчных букв, не содержащая знаков препинания. Составить программу, которая заменяет в строке S все комбинации символов S1 на комбинацию символов S2 и подсчитывает количество замен.

Дано: S, S1, S2– строки (типа string);

Найти: S – измененная строка (string), kol – количество замен (byte).

Решение:

Рассмотрим строку S. С помощью функции pos определим номер вхождения k (byte) строки S1 в строку S. Если S1 не является подстрокой S, то значение функции Pos станет равным 0. При выполнении условия k<>0 следует удалить слово S1 (Delete(S,k,y), где y – длина слова S1) и вставить слово S2 на его место

(Insert(S2,S,k)). При этом следует увеличить значение счетчика замен на единицу (kol :=kol+1).

Такую операцию нужно повторить столько раз, сколько слово S1 встречается в строке S. Но именно это нам неизвестно. Следовательно, операцию нужно повторять до k=0.

Программа решения задачи может быть такой:

Var S,S1,S2 : string; kol, k,y : byte;

Begin

Readln(S);

Readln(S1); Readln(S2); y :=Length(S1); Repeat k :=Pos(S1,S);

if k<>0 then begin Delete(S,k,y); Insert(S2,S,k); kol:=kol+1; end;

Until (k=0); writeln(S); writeln(kol,’-замен’); End.

Вопросы и задания:

Что такое строка?

Как хранится строка в памяти компьютера?

Какие операции допустимы над строковыми величинами?

Как производится сравнение строк?

Как обратиться к символам строки?

Назовите процедуры и функции обработки строк. Каковы их формат и назначение?

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

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

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

Составить программу, которая считает количество символов в строке до первого символа „!‟.

 Составить программу, считающую, сколько букв «к» встречается в последнем слове строки. Составить программу, считающую, сколько букв «к» встречается в первом слове строки.

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

Усложним предыдущую задачу.

Пример. Дана строка, состоящая из строчных букв, не содержащая знаков препинания и содержащая произвольное количество пробелов. Составить программу, которая заменяет в строке S все слова S1 словом S2 и подсчитывает количество замен.

Дано: S, S1, S2– строки (типа string);

Найти: S – измененная строка (string), kol – количество замен (byte).

Решение:

В этом случае, функция Pos нам вряд ли поможет. S1 может оказаться не словом, а подстрокой (например, слово «бам» в слове «Алабама»), тогда такая комбинация символов не требует замены.

Одним из выходов в данной ситуации может быть составление одномерного массива A, элементами которого будут слова slov (string) строки S и группы, разделяющих их пробелов probel (string). Слово собираем до пробела.

slov:=’’;

While (S[i]<>' ')and(i<=y) do begin slov:=slov+S[i]; i:=i+1; end;

Затем заносим слово в массив и пропускаем пробелы.

A[k]:=slov; k:=k+1;

Probel :=’’;

While S[i]=' ')and(i<=y)do begin probel :=probel+’ ‘; i:=i+1; end;

Этот процесс повторяем пока не будет достигнут конец строки.

Полученный массив состоит из k слов.

Последовательно сравниваем элементы массива со словом S1 и, при совпадении, заменяем на слово S2 и считаем замены.

Обнуляем строку S. Заново собираем строку S из элементов массива A. Программа решения задачи может быть такой:

Var S,S1,S2, slov, probel : string; kol, y, i, k : byte;

A : array[1..100] of string;

Begin

Readln(S);

Readln(S1); Readln(S2);

y :=Length(S);

i:=1; k:=1; Repeat

slov:=’’;

While (S[i]<>' ')and(i<=y) do begin slov:=slov+S[i]; i:=i+1; end;

A[k]:=slov; k:=k+1;

Probel :=’’;

While S[i]=' ')and(i<=y)do begin probel :=probel+’ ‘; i:=i+1; end;

A[k]:=probel; k:=k+1;

Until (i>y);

For i:=1 to k do if A[i]=S1 then begin A[i]:=S2; kol:=kol+1; end;

S:=’’;

For i:=1 to k do S:=S+A[i]; writeln(S); writeln(kol,’-замен’); End.

Вопросы и задания:

Первый блок

Что такое строка?

Как хранится строка в памяти компьютера?

Как обратиться к символам строки?

Как производится сравнение строк?

Какие операции, процедуры и функции допустимы над строковыми величинами?

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

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

Составить программу, которая из заданной строки заменяет все слова состоящие из k букв на слово «три».

Второй блок

 Составить программу, упорядочивающую слова в строке по алфавиту.

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

Основы программирования на языке