Предисловие

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

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

Вашему вниманию предлагается практический курс для обучения программированию, основную часть которого составляет подборка задач, решение практически каждой из которых полезно при изучении той или иной темы. Именно это отличает данную публикацию от других задачников по программированию, где приводится много однотипных задач. Фактически делается попытка показать, как обучить программированию в школе за 16 часов :). Конечно, на самом деле это невозможно. Однако количество различных тем для изучения действительно не превышает 16. А наличие автоматизированной системы проверки позволяет вынести почти всю практическую часть курса на дом (ученики с удовольствием самостоятельно решают задачи, если могут сразу видеть результат их проверки).

Большинство представленных задач предполагают проверку их решений на системе тестов. Тесты к задачам, а также одну из систем для автоматической проверки решений можно будет скачать с сайта inf.1september.ru (раздел “Download”). Во втором из двух номеров будут разобраны решения принципиальных задач, а также обсуждена методика тестирования некоторых из них.

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

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

Введение

Словарь языка Pascal

Словарь любой программы на языке Pascal состоит из букв, цифр и специальных символов, комбинации которых являются знаками пунктуации в языке программирования.

Цифры: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0.

Буквы: _, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z.

Знаки операций: +, –, *, /, <, >, <= (меньше или равно), >= (больше или равно), =, <> (не равно).

Обратите внимание, что символ подчеркивания ‘_’ в языке Pascal, как и во многих других языках программирования, является буквой.

Знаки пунктуации:

Переменные

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

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

Имя (идентификатор) — это любое количество букв и цифр, начинающееся с буквы, кроме служебных слов. Хотя имена и могут быть очень длинными, в конкретных реализациях в них анализируется лишь несколько первых символов (например, 63, то есть имена, у которых первые 63 символа совпадают). Прописные и строчные буквы в именах не различимы. Так, имена My_Name, my_name и MY_NAME совпадают.

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

Общий вид программы

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

 

Урок 1

Простейшая программа на языке Pascal

Собственно программа на языке Pascal (как еще говорят, тело программы) должна начинаться со слова begin, а заканчиваться cловом end и знаком точки (см. синтаксическую диаграмму). То есть ее можно сравнить с законченным предложением. Программа, состоящая только из этих слов, разделенных пробелом или переводом строки, верна, но ничего не делает. Добавим в нее вызов процедуры печати каких-либо сообщений, например:

begin

write('Hello')

end.

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

begin write('Hello') end.

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

Теперь познакомимся с правилами вывода в языке Pascal подробнее.

Вывод данных

Стандартные процедуры write и writeln служат для вывода информации. Правило их использования одно и то же: после слова write или writeln в скобках через запятую перечисляются параметры, которые мы хотим напечатать. Число этих параметров не ограничено. Запятая служит разделителем между параметрами:

writeln(параметр,параметр,...,параметр)

Существует три вида параметров: константы, переменные и выражения (например, арифметические выражения). Константы бывают числовые (это просто различные числа — целые и вещественные), логические и строковые. Любой текст, набранный с клавиатуры и заключенный в апострофы (одиночные кавычки), называется строковой константой. Если в текст нам нужно поместить апостроф, например, в слове O'Key, на этом месте нужно набить два апострофа подряд вместо одного: write('O''Key').

При выполнении данных операторов все параметры будут напечатаны в одной строке в заданном порядке. Любая константа числовая или строковая будет напечатана так, как вы ее набили в вызове write или writeln (только в строковой константе начальный и конечный апострофы напечатаны не будут, а вместо двух апострофов, расположенных в строковой константе подряд, на экране появится в этом месте один); вместо переменной на экране появится ее значение, а вместо арифметического выражения — результат его вычисления. Все параметры в write или writeln независимы друг от друга, поэтому в одном и том же операторе могут встречаться параметры разных типов, в произвольном порядке.

Между write или writeln существует единственное различие: после (!!!) выполнения writeln курсор переходит на новую строку, а после выполнения write курсор остается в той же строке, и новая печать данных с помощью write или writeln или набивка данных для read или readln (процедур чтения данных) будет проходить в той же строке.

При печати параметров между ними пробелы автоматически не вставляются, например, при печати чисел 1, 2, 3 с помощью writeln(1,2,3) все они сольются в одно число — 123. Чтобы улучшить выдачу, можно поместить между числами символ пробел, например writeln(1,' ',2,' ',3), или отформатировать выдачу, поставив после каждого элемента списка вывода двоеточие и целое число, которое указывает, сколько позиций на экране должна занимать выводимая величина, например, writeln(1:3,2:3,3:3). Отметим, что элемент дополняется начальными пробелами слева с тем, чтобы соответствовать указанной после двоеточия величине. Результаты выполнения двух последних операторов будут выглядеть так:

1 2 3

     1 2 3

Если указанное в формате выдачи число меньше, чем необходимо, то Pascal при выводе увеличит это значение до минимального необходимого размера. При выдаче на экран значений вещественных переменных или выражений в формате выдачи следует указывать еще один параметр после второго двоеточия. Он будет обозначать количество символов после десятичной точки, которые мы хотим напечатать. Например, при печати результата стандартной функции pi, которая с машинной точностью выдает значение числа p, то оператор write(pi:0:0,pi:6:2,pi/2:2:0) выдаст на экран:

3 3.14 2

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

Примеры операторов вывода:

write('Нажмите любую клавишу');

writeln(2,'+',2,'=',4);

write('7+5','=');

writeln(7+5);

Задания

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

2. Напишите программу, которая семью различными способами будет выдавать на экран фразу “2 + 2 = 4” (без кавычек), воспользуйтесь для этого операторами writeln, которые следует разделять друг от друга знаком “точка с запятой” (;) — разделителем между операторами в языке Pascal.

Первый способ должен содержать всего один параметр в операторе writeln, второй — два, и т.д., пятый, шестой и седьмой — пять. При этом шестой оператор не должен содержать числа 4, а седьмой — числа 2.
В операторах печати должны использоваться все три вида параметров.

Урок 2

Целые и вещественные числовые типы данных

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

Основным типом для работы с целочисленными данными является тип integer. Значениями переменных этого типа являются целые числа от –32 768 до 32 767 в Borland Pascal и от –2 147 483 648 до 2 147 483 647 в Delphi (в Borland Pascal значения из этого диапазона принимают переменные типа longint). К переменным целочисленных типов применимы следующие арифметические операции:

+, –, * — сложение, вычитание и умножение;

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

mod — остаток от деления нацело:

a mod b = a – ((a div b) * b).

Приведем примеры выполнения двух последних операций для всех возможных знаков аргументов:

5 div 3 = 1; 5 mod 3 = 2;

-5 div 3 = -1; -5 mod 3 = -2;

5 div -3 = -1; 5 mod -3 = 2;

-5 div -3 = 1; -5 mod -3 = -2;

Основным типом для работы с вещественными (действительными) числами является тип real. Вещественных чисел, точно представимых в компьютере, конечное число. Остальные числа либо приближаются представимыми, либо оказываются непредставимыми. Последнее относится к слишком большим и к слишком маленьким вещественным числам ¹.

К числовым типам данных применимы стандартные функции, приведенные в таблице выше.

В программировании существует негласное правило, что имена целочисленных переменных начинаются с букв i, j, k, l, m, n, a вещественных — с остальных букв. Это правило не выполняется, если переменные имеют мнемоничные имена, то есть их названия отражают условие задачи.

Cчитывание значений переменных с клавиатуры

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

readln(идентификатор,..., идентификатор)

При вызове процедуры read или readln выполнение программы будет приостановлено до тех пор, пока пользователь не введет соответствующее количество значений, они должны быть того же типа, что и переменные. Если в read или readln переменных несколько, то они могут быть набиты в одной строке, но одно число от другого должно отделяться пробелом или переводом строки. Чтобы ввести набитые значения и выполнить оператор read или readln, нужно нажать клавишу . В результате переменные приобретут заданные вами значения. Между read и readln существует единственное различие: после выполнения readln курсор переходит на новую строку, а после выполнения read курсор остается в той же строке, и новая набивка данных для read или readln будет проходить в той же строке. Но, так как после нажатия клавиши курсор в любом случае переходит на новую строчку, для однократного ввода значений переменных разницу между операторами read и readln заметить невозможно. Тем не менее в данном случае лучше использовать readln. Оператор readln можно использовать и без параметров вообще. Тогда программа просто будет ждать, пока пользователь не нажмет клавишу . Такой оператор, например, удобно ставить в качестве самого последнего оператора в программе. Тогда можно сразу посмотреть результат работы программы, а потом нажать и только тогда работа программы завершится.

Замечание. Перед вводом данных с клавиатуры рекомендуется выдавать на экран приглашение, например:

write('Введите число a => ');

readln(a);

Но в программах для автоматической проверки лишние печати недопустимы.

Задания

1. Вычислите:

20 div 6 20 mod 4
20 mod 6 2 div 5
20 div 4 2 mod 5
trunc(6.9) round(-1.8)
round(6.9) round(0.5)
trunc(-1.8) round(-0.5)

2. Определите тип выражения (integer или real):

1+0.0 sqrt(16)

20/4 sin(0)

sqr(4) trunc(pi)

sqr(5.0) int(pi)

3. Напишите программу, в которой описана одна переменная — a. Программа выдает запрос:

Введите значение b =>

Далее вводится некоторое значение и программа выдает

b=…

Вместо многоточия должно стоять введенное значение.

4. Запишите по правилам языка Pascal следующие арифметические выражения:

5. Напишите программу, которая будет вычислять значения 2 в степени 16, 18 и 27 за минимально возможное число умножений.

Урок 3

Оператор присваивания

Синтаксическая диаграмма оператора присваивания:

Данный оператор указывает, что нужно вычислить значение выражения и присвоить полученное значение переменной (поместить его в соответствующую секцию памяти). Типы переменной и выражения должны совпадать. Исключение: переменной любого вещественного типа, например real, можно присвоить выражение любого целого типа.

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

var

a, b, c: real;
i, j, k: integer;

begin

a := 1;
b := 2.0;
write('i=');
read(i);
j := sqr(i);
i := i + 1;
c := sin(a + b);
writeln('a=',a,'b=',b,'c=',c,'i=',i,'j=',j)

end.

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

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

a1 := a div 100; {старшая цифра}

a2 := a div 10 mod 10; {средняя цифра}

a3 := a mod 10; {младшая цифра}

Задачи

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

На вход программе подается целое число k (0 k 9999). Выдайте сумму его цифр.

2. Идет k-я секунда суток. Определите, сколько целых часов h и целых минут m прошло с начала суток. Например, если k = 13 · 257 = 3 · 3600 + 40 · 60 + 57, то
h = 3 и m = 40.

На вход программе подается целое число k (0 k 86 399 ²). Выведите на экран фразу: It is ... hours ... minutes.

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

3. Часовая стрелка повернулась с начала суток на d градусов. Определите, сколько сейчас целых часов h и целых минут m.

На вход программе подается целое число d (0 d < 360). Выведите на экран фразу: It is ... hours ... minutes.

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

4. Определите, является ли не более чем четырехзначное число k симметричным (например, 1331 или 0550).

На вход программе подается целое число k (0 k 9999). Выдайте 1 при положительном ответе на вопрос задачи и любое другое целое число — в противном случае.

5. Пусть в школе пять дней в неделю ежедневно проходят шесть уроков. Тогда в неделе всего 30 уроков. По введенному номеру дня d и номеру урока l найдите порядковый номер этого урока в неделе.

На вход программе подаются номер дня d (от 1 до 5) и номер урока l (от 1 до 6). Выведите номер этого урока (от 1 до 30) в неделе.

6. В книге на одной странице помещаются k строк. Таким образом, на 1-й странице печатаются строки с 1-й по k-ю, на второй — с (k+1)-й по (2•k)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

На вход программе подаются число k — количество строк, которое печатается на странице, и число n — номер строки (1 k 200, 1 n 20 000). Выведите два числа — номер страницы, на которой будет напечатана эта строка, и номер строки на странице.

7. Обозначим дни недели числами от 1 — понедельник до 7 — воскресенье соответственно. По известному m — дню недели первого числа текущего месяца — определите день недели числа n.

На вход программе подаются 2 целых числа: 1 n 31, 1 m 7. Выведите день недели числа n.

8. Единица товара стоит a рублей b копеек. Было куплено n штук этого товара. Сколько рублей и копеек пришлось заплатить за всю покупку?

На вход программе подаются три целых числа:
0 a 30 000, 0 b < 100 и 0 n 30 000. Выведите два искомых числа.

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

10. Даны значения двух моментов времени: часы, потом минуты и секунды. Известно, что второй момент времени наступил не раньше первого и разница между ними менее суток. Определите, сколько секунд прошло между двумя моментами времени.

В первой строке входных данных находятся три целых числа — часы, минуты и секунды первого момента времени. Во второй строке три числа, характеризующие второй момент времени. Число часов лежит в диапазоне от 0 до 23, число минут и секунд — от 0
до 59. Выведите число секунд между двумя моментами времени.

1 3 20

Задачи повышенной сложности ³

1. На вход программе подаются два целых числа: m и n, по модулю не превосходящих 10⁶. Если m делится на n или n делится на m, то требуется вывести 1, в противном случае — любое другое число.

2. На вход программе подаются два целых числа: m, n. Если m n, то требуется вывести 1, в противном случае — любое другое число.

3. Определите, верно ли, что в не более чем четырехзначном числе ровно две одинаковые цифры.

На вход программе подается целое число k (0 k 9999). Выдайте 1 при положительном ответе на вопрос задачи и любое другое целое число — в противном случае.

4. На вход программе подаются 4 целых числа, по модулю не превосходящих 10⁶, m, n, k, l. Если остаток от деления m на n равен k или l, то выведите 1, в противном случае — любое другое число.

5. На вход программе подаются два целых числа:
0 m < 60, 0 < n 12, указывающие момент времени
“n часов m минут”. Определите наименьшее число полных минут, которое должно пройти до того момента, когда часовая и минутная стрелки на циферблате совпадут, не обязательно на каком-то делении. Вещественную арифметику не использовать.

6. На вход программе подаются два целых числа:
0 m < 60, 0 < n 12, указывающие момент времени
“n часов m минут”. Определите наименьшее число полных минут, через которое часовая и минутная стрелки на циферблате расположатся перпендикулярно друг другу. Вещественную арифметику не использовать.

7. На вход программе подаются два числа (не обязательно целые, но не более чем с двумя знаками после десятичной точки). Распечатайте их в порядке возрастания. Используйте только арифметические операции и, при необходимости, стандартные функции.

8. На вход программе подается вещественное число x. Получите и выведите целое значение функции sign(x) — знак числа x.

9. Квадратная таблица заполнена по спирали по часовой стрелке, начиная с левой верхней угловой клетки (1,1). По числу, записанному в некоторой клетке, определите значения строки и столбца этой клетки (они нумеруются, начиная с 1, сверху и слева соответственно).

На вход программе сначала подается значение N (1 N 30 000), а затем значение, стоящее в искомой клетке (от 1 до N²). Выведите значения строки и столбца этой клетки.

10. Квадратная таблица заполнена по спирали по часовой стрелке, начиная с левой верхней угловой клетки (1,1). По номерам строки и столбца некоторой клетки (они нумеруются, начиная с 1, сверху и слева соответственно) определите, какое число в ней записано.

На вход программе сначала подается значение N (1 N 30 000), а затем значения строки и столбца (от 1 до N). Выведите число, записанное в этой клетке.

Урок 4

Логический тип данных

Множество значений логического типа boolean содержит всего два элемента — false (ложь) и true (истина). Эти константы предопределены так, что false < true. Логические значения получаются также в результате выполнения операций сравнения числовых, символьных, строковых или логических переменных: =, <>, <, >, <=, >=. Такие сравнения представляют собой частный случай логических выражений — выражений со значениями типа boolean. Подобные выражения можно присваивать переменным типа boolean, а также печатать (на экран будет выведено слово false или true соответственно). Кроме операций сравнения, для построения логических выражений используются операции not, and, or, xor. Последняя операция при применении ее к логическим операндам совпадает с операцией “не равно”, то есть
(x xor y) = (x <> y). Приведем таблицы результатов этой и других логических операций для всех возможных значений операндов (в алгебре логики такие таблицы называются таблицами истинности):

Логический результат дает также стандартная функция odd(x), которая применяется к целочисленному аргументу х:

odd(x) = true, если х нечетно;

odd(x) = false, если х четно.

Логические выражения

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

1. not;

2. *, /, div, mod, and;

3. +, -, or, xor;

4. =, <>, <, >, <=, >=.

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

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

x := 0;

b := (x > 0) and (x < 10)

Уже после вычисления первого операнда операции and ясно, что результат всего выражения — false, поэтому второй операнд вычисляться не будет.

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

not not a = a;

not (a and b) = not a or not b;

not (a or b) = not a and not b.

Условный оператор

Синтаксическая диаграмма условного оператора:

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

Последний из приведенных в диаграмме операторов называется составным. Слова begin и end называются операторными скобками.

Полный условный оператор выполняется так: сначала проверяется условие (вычисляется значение логического выражения), если оно истинно (равно true), то компьютер выполняет оператор, стоящий после then, если же ложно (равно false), то есть справедливо противоположное условие, то компьютер выполняет оператор, стоящий после else. Семантику данного оператора можно проиллюстрировать следующей блок-схемой:

Здесь B — выражение булевского типа, которое стоит в условном операторе после слова if, а S₁ и S₂ — операторы, которые стоят после слов then и else соответственно.

Пример условного оператора:

if k mod 2 = 0 then writeln(k, ' четное')

else writeln(k, ' нечетное')

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

Приведем блок-схему, соответствующую семантике укороченного условного оператора:

Пример использования укороченного условного оператора:

x := 0;

if x > 0 then writeln('x = ', x);

В этом случае ничего напечатано не будет.

Согласно синтаксису условного оператора (см. синтаксическую диаграмму), как после then, так и после else может стоять только один оператор, поэтому если необходимо использовать не один оператор, а несколько, то используется составной оператор. Например:

if x < 0 then

begin

i := i + 1;
x := x – 1

end

else i := i – 1

Здесь для случая x < 0 будут выполнены два оператора, а для противоположного случая (x 0) — один оператор.

Если после then в качестве оператора стоит условный оператор, то возможна такая конструкция:

if условие1 then

if условие2 then оператор1

еlse оператор2

Здесь непонятно, к какому if относится else, то есть какой из условных операторов полный, а какой укороченный. Для таких случаев введено правило, по которому

Значит, в данной конструкции первый оператор укороченный (без else), а второй полный. Если же требуется, чтобы первый оператор был полным, а второй — укороченным, то следует использовать операторные скобки:

if ycловие1 then

begin

if ycловие2 then оператор1

end

else

оператор2

Благодаря операторным скобкам else стало относиться к первому if, а не ко второму. Другой способ решения данной проблемы — всегда использовать только полные условные операторы:

if условие1 then

if условие2 then оператор1

else {здесь стоит пустой оператор}

еlse оператор2

Такая конструкция всегда будет однозначной.

Примеры вложенных условных операторов:

1) if i = 1 then

if j = 1 then writeln('i = j')

else writeln('i = 1, j <> 1')

2) if i = 1 then

if j = 1 then writeln('i = j')

else writeln('i = 1, j <> 1')

else writeln('i <> 1')

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

Приведем еще несколько полезных правил применения условного оператора:

1.

2. Рассмотрим следующий фрагмент программы:

if b then ; begin s1; s2; s3 end

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

3. Пусть n условий исчерпывают все возможные случаи, например, x < 2, x = 2, x > 2. Тогда вызов операторов, соответствующих каждому из случаев, можно запрограммировать двумя способами:

if x < 2 then s1; ¦ if x < 2 then s1

if x = 2 then s2; ¦ else if x = 2 then s2

if x > 2 then s3 ¦ else s3

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

4. Рассмотрим следующий условный оператор

if a = c then b := true else b := false

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

b := a = c

Аналогично, вместо

if b = true then оператор

нужно писать

if b then оператор

Задачи

1. На выданном вам рисунке на координатной плоскости изображены окружности, прямые, параболы, ромбы, прямоугольники (некоторые из упомянутых линий могут отсутствовать). Несколько областей, ограниченных этими линиями, заштрихованы. Данные линии можно описать уравнениями в декартовой прямоугольной системе координат (x,y) на плоскости:

у = f(x), или x = f(y), или f(x, y) = 0.

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

Напишите программу, которая позволит определять, принадлежит ли точка с вещественными координатами (x₀,y₀) фигуре, состоящей из всех заштрихованных на рисунке областей, или нет. Точки на границах областей не рассматривать, то есть ваша программа может считать их как принадлежащими фигуре, так и не принадлежащими ей. Значения x₀,y₀ вводятся с клавиатуры. В качестве ответа программа выдает на экран true, если точка с введенными координатами (x₀,y₀) принадлежит заштрихованной фигуре, и false, если точка (x₀,y₀) не принадлежит ей. Условный оператор не использовать.

Пример рисунка:

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

3. Напишите программу, которая будет считывать значения целых переменных a, b и с и распечатывать их в порядке возрастания. Значения a, b и с по модулю не превосходят 30 000.

Решите задачу двумя способами:

1) не используя операторы присваивания и логическую операцию and;

2) используя операторы присваивания.

В первом случае нужно в зависимости от значений переменных печатать их в соответствующем порядке, а во втором — значения нужно переместить так, чтобы в переменной a оказалось минимальное значение, в с — максимальное, а в b — среднее. Оператор печати в этом случае должен быть только один: writeln(a,b,c).

4. Напишите программу для решения уравнения ax = b относительно х в целых числах. Учтите, что a может принимать любые значения, в том числе и 0.

На вход программе подаются целые числа a, b, по модулю не превосходящие 30 000. Требуется вывести целый корень уравнения, если он существует и единственный. Если уравнение не имеет корней, то вывести nosolution. Если уравнение имеет больше одного целого корня, то вывести many solutions.

5. Даны координаты двух точек на плоскости. Требуется определить, в какой координатной четверти они лежат. Вводятся 2 целых, не равных нулю числа, по модулю не превосходящие 30 000: координаты точки плоскости (x, y). Выведите номер координатной четверти, в которой лежит эта точка (1, 2, 3 или 4).

6. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8. По введенным координатам двух полей (k,?l) и (m, n) выясните, угрожает ли ферзь, находящийся на поле (k,?l), полю (m, n)?

На вход программе подаются 4 целых числа: k, l, m и n. Выведите YES или NO в зависимости от ответа на вопрос задачи.

7. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8. По введенным координатам двух полей (k,?l) и (m, n) выясните, являются ли эти поля полями одного цвета?

На вход программе подаются 4 целых числа: k, l, m и n. Выведите YES или NO в зависимости от ответа на вопрос задачи.

8. По введенному номеру года — положительному целому числу, не превосходящему 10   000, требуется определить, является ли данный год високосным. Напомним, что високосными являются года, номера которых кратны 4, но не кратны 100, а также года, номера которых кратны 400. Выведите YES или NO в зависимости от ответа на вопрос задачи.

9. Узник замка Иф.

За многие годы заточения узник замка Иф проделал вилкой в стене прямоугольное отверстие размером D x E. Замок Иф сложен из кирпичей размером A x B x C. Узник хочет узнать, сможет ли он выкидывать кирпичи в море из этого отверстия, для того чтобы сделать подкоп. Помогите ему, считая, что стороны кирпича будут параллельны сторонам отверстия.

На вход программе подаются 5 чисел: A, B, C,
D, E. Все числа натуральные, не превосходящие 10 000. Выведите YES или NO в зависимости от ответа на вопрос задачи.

10. Даны три натуральных числа — длины сторон треугольника. Определите, существует ли треугольник с такими сторонами, и если “да”, то определите его тип (остроугольный, тупоугольный, прямоугольный).

На вход программе подаются 3 натуральных числа, не превосходящих 10 000. Необходимо вывести одно из слов: rectangular — для прямоугольного треугольника, acute — для остроугольного треугольника, obtuse — для тупоугольного треугольника или impossible, если входные числа не образуют треугольника.

11. Решить в действительных числах уравнение ax² + bx + c = 0.

На вход программе подаются a, b, c (a, b, c целые, по модулю не превосходят 100). Выдать код ситуации и значения корней:

• –1 — бесконечное множество решений;
• 0 — нет действительных корней;
• 1 — уравнение вырождается в линейное, выдать x;
• 2 — уравнение квадратное, два различных корня, выдать x₁ и x₂;
• 3 — уравнение квадратное, кратный корень, выдать x.

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

Задачи повышенной сложности

1. На столе лежат коробка размера A₁ x B₁ x C₁ и коробка размера A₂ x B₂ x C₂. Выясните, можно ли одну из этих коробок положить в другую, если разрешены повороты коробок вокруг любого ребра на угол 90?.

Первая строка входных данных содержит три целых числа: A₁, B₁ и C₁. Вторая строка входных данных содержит три целых числа: A₂, B₂ и C₂. Все числа положительны и не превосходят 1000.

Если коробки одинаковы, выведите

Boxes are equal

Если первая коробка может быть положена во вторую, выведите

The first box is smaller than the second one

Если вторая коробка может быть положена в первую, выведите

The first box is larger than the second one

В остальных случаях выведите

Boxes are incomparable

2. Яша плавал в бассейне размером N x M метров и устал. В этот момент он обнаружил, что находится на расстоянии x метров от одного из длинных бортиков (не обязательно от ближайшего) и y метров от одного из коротких бортиков. Какое минимальное расстояние должен проплыть Яша, чтобы выбраться из бассейна на бортик?

На вход программе подаются 4 натуральных числа: N, M, x, y (N M), разделенные пробелами. Все числа не превосходят 100. Требуется вывести одно число — минимальное расстояние, которое должен проплыть Яша, чтобы выбраться на бортик.

3. Узник замка Иф-2.

За многие годы заточения узник замка Иф проделал вилкой в стене прямоугольное отверстие размером D x E. Замок Иф сложен из кирпичей размером
A x B x C. Узник хочет узнать, сможет ли он выкидывать кирпичи в море из этого отверстия, для того чтобы сделать подкоп. Помогите ему, считая, что стороны кирпича могут произвольно располагаться относительно сторон отверстия.

На вход программе подаются 5 чисел: A, B, C, D, E. Все числа натуральные, не превосходящие 10 000. Выведите YES или NO в зависимости от ответа на вопрос задачи.

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

На ввод программе подаются 6 чисел: x₁, y₁, x₂, y₂, x₃, y₃. Все числа целые, по модулю не превосходят 100. Они задают 3 точки плоскости: a(x₁, y₁), b(x₂, y₂), c(x₃, y₃). Следует определить взаимное расположение точек и выдать на экран код ситуации:

0 — 3 точки совпадают;

1 — ровно 2 точки из трех совпадают;

2 — точки не совпадают, лежат на одной прямой;

3 — точки образуют остроугольный треугольник;

4 — точки образуют прямоугольный треугольник;

5 — точки образуют тупоугольный треугольник.

Постарайтесь использовать как можно меньше логических операций (операций сравнения и логических связок).

5. Задана система двух линейных уравнений относительно x и y:

Требуется решить данную систему. На вход программе подаются 6 чисел: a, b, c, d, e, f (все числа целые, по модулю не превосходят 100; обратите внимание, что сначала вводятся значения a, b, c, d, а потом e и f). Выдать на экран описание решения в следующем виде:

• 0 — решений нет.
• 1 — решение имеет вид y = kx + b, k 0.
• 1X c — решение представляет собой пары вида
  (x, c), c фиксированно, x любое. Вывести с с точностью до двух знаков после десятичной точки.
• 1Y с — решение представляет собой пары вида
  (c, y), c фиксированно, y любое. Вывести с с точностью до двух знаков после десятичной точки.
• 2 x y — решение системы единственно, вывести x и y с точностью до двух знаков после десятичной точки.
• 2XY — любая пара (x, y) является решением данной системы.

Урок 5

Цикл с предусловием

Многократно повторяемые действия могут быть заданы с помощью оператора цикла. Рассмотрим синтаксическую диаграмму одного из таких операторов — оператора цикла с предусловием:

Выполнение оператора цикла сводится к повторному выполнению оператора S (тела цикла), пока значение логического выражения B истинно (до тех пор, пока оно не станет ложным). Фактически подобные операторы цикла реализуют повторное выполнение условных операторов if B then S, пока истинно условие B. Если выполняемый оператор не изменяет значения переменных, входящих в условие, то условие будет истинным всегда и цикл будет выполняться вечно, при этом говорят, что программа зацикливается. Если же при первой проверке условия оно сразу оказывается ложным, то оператор цикла не выполняется вообще.

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

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

while x <= 0 do x := x + 1

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

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

s = 1 + 2 + 3 + 4 + ... + n:

readln(n);
s := 0;
i := 0;

while x < n do

begin

i := i + 1;
s := s + i

end

В таких задачах очень важно правильно задать до цикла значения изменяемых в цикле переменных и проконтролировать, нужное ли количество раз выполнится цикл. Так, если в рассмотренной задаче заменить условие x < n на x <= n, то на последнем шаге цикла к s прибавится значение n + 1, что неверно. Заметим, что приведенная в качестве решения задачи программа автоматически работает верно и для случая n = 0. Цикл при этом просто не будет выполняться. При других же вариантах решения данный случай скорее всего придется рассматривать отдельно.

Пример 2. С клавиатуры вводятся натуральные числа. Последовательность этих чисел заканчивается нулем (в данном случае 0 — признак окончания ввода). Найти их сумму:

read(a);
s := 0;

while a <> 0 do

begin

s := s + a;
read(a)

end

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

Цикл с постусловием

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

В данном операторе слова repeat и until служат операторными скобками и begin end использовать не требуется. На первом шаге цикла операторы, заключенные между repeat и until, выполняются в любом случае, дальше же цикл будет повторяться, пока значение булевского выражения ложно. То есть цикл закончится, когда оно станет истинным. В отличие от цикла с предусловием здесь В — это условие окончания цикла.

Пример 3. Решить задачу из примера 2 с помощью цикла с постусловием:

s := 0;

repeat

read(a);
s := s + a

until a = 0;

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

Задачи

1. По заданным вещественному значению x и целому значению n вычислите xⁿ (операция возведения в степень в языке Pascal отсутствует). Для решения задачи используйте последовательное домножение результата на x.

На вход программе подаются вещественное x, по модулю не превосходящее 10, и целое n, по модулю не превосходящее 20. Выведите значение xⁿ с точностью до трех цифр после десятичной точки.

2. Найдите сумму цифр введенного целого числа. (На каждом шаге выделяется последняя цифра числа, а затем число делится на 10. Процесс повторяется, пока число не станет равным 0.)

На вход программе подается целое неотрицательное число n 10⁹. Выведите сумму его цифр.

3. На вход программе подается натуральное число n 10⁹. Проверьте, является ли оно простым. Выведите YES или NO в зависимости от ответа на вопрос задачи. Максимальное время работы программы на одном тесте — 0,1 секунды.

4. На вход программе подается натуральное число  n 30 000. Выведите количество делителей числа n, включая 1 и само число n.

5. Найдите все целочисленные решения уравнения ax³ + bx² + cx + d = 0 и выведите их в произвольном порядке. На вход программе подаются 4 целых числа:
a, b, c и d, по модулю не превосходящие 10⁹, a 0. Максимальное время работы программы на одном тесте — 1 секунда.

Указание. При d 0 все корни уравнения, отличные от 0, являются делителями числа d. Для вычислений используйте схему Горнера ⁴.

6. На вход программе подается натуральное число  n 10⁹. Проверьте, можно ли представить его в виде суммы двух квадратов натуральных чисел. Выведите YES или NO в зависимости от ответа на вопрос задачи. В случае положительного ответа во второй строке выведите два числа, сумма квадратов которых равна n. Числа следует выводить в порядке неубывания. Максимальное время работы программы на одном тесте — 0,1 секунды.

7. Вкладчик положил на банковский счет n рублей. Каждый год на сумму вклада начисляется k процентов годовых (будем считать, что процент всегда округляется до целого числа рублей по формуле [xk/100], где x — сумма вклада на начало года). Начисленные проценты добавляются к сумме вклада. Через сколько лет сумма вклада станет не менее m рублей?

На вход программе подаются три натуральных числа: n 10⁶, k 100, m 1000^n. Выведите одно число — искомое количество лет.

8. Вкладчик положил на банковский счет некоторую сумму. Каждый год на сумму вклада начисляется k процентов годовых (будем считать, что процент всегда округляется до целого числа рублей по формуле [xk/100], где x — сумма вклада на начало года). Начисленные проценты добавляются к сумме вклада. Через сколько лет сумма вклада как минимум удвоится?

На вход программе подается натуральное число k 100. Выведите одно число — искомое количество лет.

9. На вход программе подаются два натуральных числа: n, m 10⁹. Выведите их наибольший общий делитель. Для решения задачи используйте алгоритм Евклида, основанный на следующем тождестве: НОД(n, m) = НОД(m, r), где r — остаток от деления n на m. Если r = 0, то m = НОД(n, m).

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

При решении задачи массив использовать нельзя.

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

При решении задачи массив использовать нельзя.

12. Программа получает на вход последовательность целых чисел, по модулю не превосходящих 10⁹. Признак окончания последовательности — число –2x10⁹. Программа должна определить вид последовательности — возрастающая, убывающая, случайная или постоянная.

Ответ следует выдать в следующем формате — в 1-й строке напечатать количество элементов последовательности (без учета –2x10⁹), во 2-й строке — тип последовательности:

• SCENDING (строго возрастающая);
• WEAKLY ASCENDING (нестрого возрастающая, т.е. неубывающая);
• DESCENDING (строго убывающая);
• WEAKLY DESCENDING (нестрого убывающая, т.е. невозрастающая);
• CONSTANT (постоянная);
• RANDOM (случайная).

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

Урок 6

Оператор цикла с параметром

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

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

2. Оба выражения вычисляются до выполнения оператора цикла и впоследствии не перевычисляются!!!

3. Идентификатор является параметром цикла и по стандарту не должен изменяться внутри оператора цикла (данное требование стандарта поддерживается в языке Delphi). Однако изменение параметра цикла внутри цикла не противоречит синтаксису Borland Pascal, но может приводить к непредсказуемым последствиям, например, зацикливанию.

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

Оператор цикла выполняется так: сначала вычисляются значения выражений, обозначим их A и B. Они являются начальным и конечным значениями параметра цикла соответственно. Если для цикла с to A B, то параметр цикла последовательно будет принимать значения, равные A, A + 1, A + 2, ..., B. То есть цикл будет выполняться ровно B – A + 1 раз. Если A > B, то цикл не будет выполняться совсем. Если при входе в цикл с downto выполняется неравенство A B, то параметр цикла последовательно будет принимать значения, равные A, A – 1, A – 2, ..., B. То есть цикл будет выполняться ровно A – B + 1 раз. Если A < B, то цикл не будет выполняться совсем.

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

Пример 1. По заданному целому неотрицательному значению n и вещественному значению x вычислить xⁿ:

p := 1;

for i := 1 to n do p := p * x;

Пример 2. По заданному целому неотрицательному значению n вычислить n!:

f := 1;

for i := 2 to n do f := f * i;

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

Пример 3. По заданному натуральному значению n вычислить 1 – 1/2 + 1/3 – 1/4 + ... 1/n:

k := 1;
s := 1;

for i := 2 to n do

begin

{в переменной k имеем знак очередного слагаемого}
k := -k;
s := s + k/i

end;

Пример 4. По заданному натуральному значению n и вещественному значению x вычислить

x + x² + x³ + … + xⁿ:

s := 0;
z := 1;

for i := 1 to n do

begin

{в переменной z - очередное слагаемое}
z := z * x;
s := s + z

end;

Задачи

1. По заданному натуральному значению n вычислить 1 – 1/3 + 1/5 – 1/7 + ... 1/(2n + 1). На вход программе подается натуральное число n 10 000. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

2. В последовательности a₁, a₂, ..., a_n найти номер самого большого числа. На вход программе сначала подается натуральное число n 10⁶. Далее следуют n целых чисел, по модулю не превосходящих 30 000, — сами члены последовательности. Выведите номер максимального числа. Если таких чисел несколько, то выведите номер последнего из них. Нумерация чисел начинается с единицы.

Массив в программе не использовать.

3. Дана последовательность, состоящая из n чисел. Выяснить, сколько раз в ней встречается минимальное число. На вход программе сначала подается натуральное число n 10⁶. Далее следуют n целых чисел, по модулю не превосходящих 30 000, — сами члены последовательности. Выведите число, которое является ответом на вопрос задачи.

Массив в программе не использовать.

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

На вход программе сначала подается натуральное число 3 n 100 — количество судей. Далее следуют n натуральных чисел, не превосходящих 100, — оценки, выставленные судьями одному из спортсменов. Выведите оценку, которая пойдет в зачет данному спортсмену, с точностью до двух значащих цифр после десятичной точки.

Массив в программе не использовать.

5. По заданному натуральному числу n и вещественному x вычислить

.

На вход программе подаются натуральное n 100 и вещественное x, по модулю не превосходящее 10. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

6. По заданному натуральному числу n и вещественному x вычислить

.

На вход программе подаются натуральное n 100 и вещественное x, по модулю не превосходящее 10. Выведите значение указанного выражения с точностью
6 значащих цифр после десятичной точки.

7. По заданным натуральным числам n и m вычислить

.

На вход программе подаются натуральные n  100 и m 100. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

8. Числа Фибоначчи определяются следующими формулами: f₀ = f₁ = 1; f_n = f_n–1 + f_n–2, при n 2.

На вход программе подается целое неотрицательное n 40. Выведите n-е число Фибоначчи. Массив в программе не использовать.

9. Дана последовательность, состоящая из n чисел. Найти в ней два самых маленьких числа. На вход программе сначала подается натуральное число n 10⁶. Далее следуют n целых чисел, по модулю не превосходящих 30000, — сами члены последовательности. Выведите минимальное число и второе по величине число (оно может совпадать с минимальным).

Массив в программе не использовать.

10. Вычислите по схеме Горнера значение полинома a_nxⁿ + a_n–1x^n–1 + … + a₁x + a₀ в точке x₀.

На вход программе сначала подается целое неотрицательное число n 20. Затем вещественное число x₀, по модулю не превосходящее 10. Далее следуют n + 1 вещественных чисел, по модулю не превосходящих 10. Выведите значение полинома с точностью до трех значащих цифр после десятичной точки.

При решении задачи массив использовать нельзя.

Урок 7

Вложенные циклы

Пример 1. Для заданного натурального числа n найти все тройки натуральных чисел a, b, c таких, что a + b + c = n:

for a := 1 to n - 2 do
for b := 1 to n - 2 do

begin

c := n – a - b;
if c > 0 then writeln(a,'+',b,'+',c,'=',n)

end

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

Пример 2. Распечатать все трехзначные числа, в которых есть две одинаковые цифры:

 

for j := 1 to 9 do
for i := 0 to 9 do
for k := 0 to 9 do
if (j = i) or (j = k) or (i = k) then writeln(j, i, k);

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

for j := 1 to 9 do

begin

writeln(j,0,0,' ',j,j,0,' ',j,0,j);
for i := 1 to 9 do writeln(i,i,j,' ',j,i,i,' ',i,j,i)

end

Пример 3. Распечатать все трехзначные числа, в которых вторая цифра больше первой, а третья больше второй.

for i := 1 to 7 do
for j := i + 1 to 8 do
for k := j + 1 to 9 do writeln(i,j,k);

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

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

Задачи

1. (Модифицированная задача из примера 1.) Для заданного натурального числа n найти все тройки натуральных чисел a, b, c таких, что a + b + c = n и a b c. Минимизируйте количество условий, которые используются в программе.

На вход программе подается натуральное число n 30 000. Выведите количество искомых троек ⁵.

2. a) Автобусный билет считается счастливым, если в его шестизначном номере сумма первых трех цифр равна сумме трех последних цифр. Подсчитайте и выведите число счастливых билетов с различными номерами (от 000001 до 999?999).

б) Билет считается счастливым, если в его n-значном номере сумма первых [n/2] цифр равна сумме [n/2] последних цифр (при нечетном n центральная цифра в “проверке на счастье” не участвует и может быть любой). Подсчитайте число счастливых билетов с различными n-значными номерами (ведущие нули в номерах возможны, но номера, состоящего из одних нулей, не существует).

На вход программе подается натуральное n 15. Выведите количество n-значных счастливых билетов.

3. Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль. Так, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

На вход программе подается натуральное n < 100 — сумма сдачи, которую необходимо выплатить. Выведите искомое количество способов выплаты.

4. Напишите программу, которая будет разлагать натуральное число n > 1 на простые множители.

На вход программе подается натуральное n 30 000. Выведите его разложение на простые множители, располагая их в порядке неубывания так, как показано в примерах.

5. Дано число n. Найдите число из диапазона от 1 до n с максимальной суммой своих делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите минимальное из них.

На вход программе подается натуральное n 10 000. Выведите искомое число.

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

На вход программе подается натуральное число n 10⁹. Выведите его цифровой корень.

7. Напишите программу для подсчета числа точек c целочисленными координатами, находящихся внутри и на границе круга c центром в начале координат и заданным радиусом r.

На вход программе подается целое неотрицательное число r 1 000 000. Выведите количество искомых точек в этом круге.

8. Экспериментальным путем определите, факториал каких чисел может быть точно вычислен в 32-битном целом типе (integer в Delphi и longint в Borland Pascal), 64-битном целом типе (int64 в Delphi и comp в Borland Pascal) и типе extended. Затем напишите программу, которая будет работать следующим образом.
Сначала запрашивается число K — количество факториалов, которые надо вычислить (K 100). Затем K раз считывается значение N (N 100), для очередного N сразу вычисляется значение N!, если это можно точно сделать хотя бы в одном из указанных типов данных, и выводятся в строке через пробел найденное значение факториала и число 1, 2 или 3 соответственно в зависимости от типа данных, в котором можно это значение посчитать точно (выводится минимально возможное значение). Если точно факториал в стандартной компьютерной арифметике вычислить невозможно, то выводится только 0.

Пример диалога программы:

3 {введено значение K}

3 {введено первое значение N}

6 1 {это вывод результата для первого факториала}

15 {введено второе значение N}

1307674368000 2 {это вывод результата для второго факториала}

100 {введено третье значение N}

0 {это вывод результата для третьего факториала}

9. По заданным вещественному значению x и целому неотрицательному значению n вычислите xⁿ (операция возведения в степень в языке Pascal отсутствует). Для решения задачи используйте алгоритм эффективного возведения в степень.

Алгоритм основан на тождестве x²ⁿ = xⁿxⁿ. Тогда, если n = 2^k, то значение xⁿ можно получить из x, домножая результат сам на себя (таким образом мы будем последовательно получать значения 2-, 4-, 8-й и т.д.
2^k-й степеней числа x). В свою очередь, произвольное n можно представить как сумму степеней двойки (фактически перевести в двоичную систему счисления):
n = 2^k1 + 2^k2 + … Соответственно, Фактически алгоритм быстрого возведения в степень сводится к последовательному получению 2-, 4-, 8-й и т.д. степеней числа x и перемножению необходимых степеней.

На вход программе подаются вещественное x, по модулю не превосходящее 10, и целое неотрицательное n, не превосходящее 100. Выведите значение xⁿ с точностью до трех цифр после десятичной точки. Для вычислений используйте тип extended.

10. По заданным натуральным числам n и m вычислите .
На вход программе подается натуральное m 100. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки (известно, что это выражение, состоящее из бесконечного числа вложенных корней, для всех указанных значений m конечно).

Урок 8

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

Помимо стандартных типов для работы с числовыми и логическими переменными, в языке Pascal существует тип для обработки переменных символьного типа. Данный тип называется char — от английского слова character — символ. Интересно, что транскрипция этого слова начинается со звука к, а не ч, так что устоявшееся в русском языке произношение названия символьного типа — “чар”, по-видимому, является некорректным и может быть непонято программистами из англоязычных стран.

Значениями символьного типа char являются элементы конечного и упорядоченного множества символов, зависящего от текущей кодовой таблицы.
В языке Pascal это множество состоит из 256 символов, пронумерованных от 0 до 255. В число этих символов входят все символы, которые вы можете получить на экране с помощью нажатия какой-либо клавиши или комбинации клавиш, а также некоторые другие символы, в том числе и невидимые. Какие именно символы являются константами данного типа, зависит от того, какая кодовая таблица используется в момент выполнения (а не написания) программы. То есть одна и та же программа, например печатающая изображение всех символов кодовой таблицы, на компьютерах с различными текущими кодировками будет иметь различные результаты работы. Обычно первые 128 символов с кодами от 0 до 127 всегда соответствуют так называемым “ASCII-символам”, а остальные 128 в различных таблицах используются для кодирования букв того или иного национального алфавита, символов псевдографики и т.п. Кроме того, первые 32 символа считаются управляющими, а остальные — изображаемыми, т.е. имеющими графическое изображение (пробел, имеющий код 32, относится уже к изображаемым символам). Управляющие символы должны восприниматься устройствами вывода и ввода текста как команды, например:

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

В тексте программы константы символьного типа записываются двумя способами. Наиболее наглядный из них — это заключение любого изображаемого символа в апострофы. Например: '*', 'F', '1'. Для того чтобы таким способом представить сам символ апостроф, его записывают внутри апострофов же дважды: '''' (на клавиатуре для этого надо четыре раза подряд нажать клавишу, соответствующую апострофу). Второй способ позволяет задавать любые символьные константы, в том числе и соответствующие управляющим символам, по их кодам. В этом случае обозначение константы начинается с символа ?“#”, за которым следует десятичный код (т.е. номер от 0 до 255) соответствующего символа. Например, #13, #65. Если же мы считываем значение символьной переменной с клавиатуры или из файла, то соответствующий символ должен быть набит уже без апострофов. А если считывается последовательность символов (текст), то они набиваются все подряд, без разделителей, так как и пробел, и другие разделители числовых констант также являются значимыми символами.

Множество символьных констант является упорядоченным так, что символ “c1” считается меньше символа “c2”, если код первого символа соответственно меньше кода второго. Строчные и прописные буквы являются различными символами, то есть 'a' <> 'A', объясняется это тем, что в любой кодовой таблице каждой из них соответствует свой символ. Все строчные и прописные английские буквы, а также символы для десятичных цифр упорядочены между собой, то есть

'0' < '9', 'A' < 'Z' и 'a' < 'z', но 'Z' < 'a'.

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

Символ '0' в таблице ASCII имеет код 48, символ 'A' (английская) — 64.

Рассмотрим операции, применимые к переменным и константам символьного типа. Во-первых, как уже следует из сказанного выше, значения символьных переменных можно считывать, а значения символьных выражений — печатать. Во-вторых, в силу наличия отношения порядка, над символьными выражениями определены все операции отношения: <, >, =, <>, <=, >=. Арифметические действия над данным типом не определены.

С символьным типом связаны следующие функции:

1) функция chr(i) выдает по порядковому номеру символа в кодовой таблице соответствующий символ, следовательно, на месте i может стоять целочисленное выражение, значение которого находится в диапазоне от 0 до 255; если номер является константой, можно использовать также символ "#":#65 означает то же самое, что и chr(65);

2) функция ord(с), наоборот, выдает номер символа с в кодовой таблице, здесь с — или переменная символьного типа, или символьная константа, или функция, результатом выполнения которой является символ (например, chr);

3) функция succ(с) выдает символ, следующий в кодовой таблице за символом “с”. Для последнего символа кодовой таблицы эта функция не определена. То есть с точки зрения данной функции символы не считаются расположенными по кругу, они имеют только линейный порядок; эта функция позволяет обрабатывать символы в циклах;

4) функция pred(с) выдает символ, предшествующий в кодовой таблице символу “с”. Для символа с кодом 0 значение этой функции также не определено;

5) функция upcase(с) переводит символы, обозначающие строчные английские буквы, в прописные, остальные символы (в том числе и соответствующие русским буквам) она оставляет неизменными. Например, upcase('f') есть 'F', а upcase('*') есть '*'. Обратной функции, т.е. функции, переводящей прописные буквы в строчные, в стандартной библиотеке не существует.

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

1) if c in ['a'..'z','A'..'Z'] then writeln('letter');

2) if c in ['1','3','5','7','9'] then writeln('odd digit')

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

Перечислимый тип данных

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

В тексте программы все константы данного типа употребляются непосредственно, без апострофов. Все константы пронумерованы, согласно описанию, начиная с 0, следовательно, определены все операции отношения над переменными и константами данного типа и можно использовать функцию ord. Ввод и вывод для данного типа не допускается.

Уже знакомый вам тип boolean фактически является стандартным предопределенным перечислимым типом:

type boolean = (false, true);

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

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

Примеры описания порядковых типов:

type week = (mon, tues, wed, thur, fri, sat, sun);

operators = (plus, minus, times, divide);

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

boolean(0) означает false;

week(1) означает tues;

operators(2) означает times.

Ограниченный тип (диапазон)

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

Допустимость операций над значениями ограниченного типа определяется базовым типом. А директива компилятора {$R+} позволяет контролировать выход за границу диапазона описанных значений во время выполнения программы.

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

type age = 0..120;

digit = 0..9;

temperature = -50..50;

letter = 'a'..'z';

work = mon..fri;

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

Порядковые типы данных

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

1. Все целые типы: integer, byte, shortint, smallint, word, longint (64-битный целый тип int64 в Delphi в полном смысле слова порядковым не является).

2. Логический тип boolean.

3. Символьный тип char.

4. Определяемые программистом перечислимые типы.

5. Ограниченный тип.

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

1) ord(a) — выдает “порядковый номер” a среди констант соответствующего типа. Для целых типов, в том числе и знаковых, это будет само число, для остальных — номер в нумерации значений типа, начиная с нуля. Данная функция, по сути, позволяет производить преобразование любого порядкового типа в числовой, что иногда очень удобно при решении задач;

2) succ(a) — выдает следующее по порядку значение за значением а (не определена для максимального значения типа);

3) pred(a) — выдает предшествующее значению а значение (не определена для минимального значения типа);

4) получение по номеру элемента типа: <имя типа>(i), по-другому это называют приведением к типу.

Переменные любого порядкового типа можно употреблять в качестве параметров цикла for. То есть в цикле можно перебирать значения не только числовых, но и символьных, логических и других параметров порядкового типа. Кроме того, для обработки различных значений порядковых типов в языке Pascal определен так называемый “оператор варианта” — case. Рассмотрим его подробнее.

Оператор варианта case

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

case <выражение порядкового типа> of

константа1: оператор1;

константа2,константа3, …,константа10:

оператор2;

константа11..константа15: оператор3;

else оператор4

end

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

Приведем примеры нескольких различных операторов варианта:

1) case n mod 7 of

1: writeln('Понедельник');

2: writeln('Вторник');

3: writeln('Среда');

4: writeln('Четверг');

5: writeln('Пятница');

6: writeln('Суббота');

0: writeln('Воскресенье');

end;

2) case c of

'+': x := x + y;

'-': x := x - y;

'*': x := x * y;

else writeln('error')

end;

3) case c of

'a'..'z','A'..'Z': writeln('letter');

'0'..'9': writeln('digit')

end;

Синтаксис данного оператора опровергает ряд утверждений, справедливых для конструкций языка, рассматривавшихся ранее, а именно: “перед else точка с запятой не ставится”; и “каждому слову end соответствует слово begin”.

Задачи

1. Выдайте на экран все символы, по порядку их номеров, помещая по 60 символов в строке (в первой строке — символы с 0-го по 59-й, во второй — с 60-го по 119-й и т.д.). На эффект от спецсимволов, таких, как звуковой сигнал и перевод строки, не обращайте внимания. Вложенные циклы или несколько последовательных циклов не использовать.

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

Пример диалога программы:

A

65

1

49

1

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

4. Выведите на экран последовательность символов:

a

ab

abc

abcd

— и т.д. до строки, заканчивающейся символом “z”.

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

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

6. Дана непустая последовательность слов, состоящих из латинских букв. Соседние слова отделены друг от друга символом запятой, за последним словом следует точка. Определите количество слов, которые начинаются с буквы “a” (как строчной, так и заглавной).

На вход программе подается последовательность слов, разделенных запятыми. Последовательность заканчивается точкой. Выведите количество слов этой последовательности, начинающихся с буквы “a” (как строчной, так и заглавной).

7. Для введенного натурального числа k от 1 до 120 напечатайте фразу:

Мне k лет

Учтите, что при некоторых значениях k слово лет надо заменить на слово год или года. В программе обязательно использовать оператор case. Фразу надо выводить в кодировке Windows-1251. Соблюдайте регистр при выводе символов и разделяйте слова ровно одним пробелом.

8. Напишите программу, вычисляющую значение простейшего арифметического выражения. Пользователь вводит выражение, такое, как 1+2 или 7*8, без пробелов (цифра, знак операции: +, – или *, цифра) и программа печатает результат.

9. Дана следующая программа:

type

direction = (north, east, south, west);
curs = (forwrd,left,right,back);

var

k1,k2: direction;
p: curs;
n: integer;

begin

write('Введите номер направления корабля','(0-север, 1-восток, 2-юг, 3-запад) =>');
readln(n);
k1:=direction(n);
write('Введите номер изменения курса','(0-прямо, 1-налево, 2-направо, 3-назад) =>');
readln(n);
p:=curs(n);
...
writeln('Новый курс ',ord(k2));

end.

Корабль шел по курсу k1 (тип direction), ему был дан приказ p (тип curs). Определить значение курса (тип direction), которое получит корабль в результате выполнения приказа.

Замените многоточие на операторы, решающие описанную задачу.

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

10. Подсчитайте число пятниц, приходящихся на 13-е числа в XX веке, если известно, что 13 января 1901 года было воскресенье. Выдайте полученное значение.

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

Урок 9

Одномерные массивы

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

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

Массив — это составной объект, образованный из элементов (компонент) одного и того же типа. Такой тип данных применяется в программировании для обозначения объектов, аналогичных числовым последовательностям в математике, где сразу целая группа чисел обозначается одним именем (чаще всего буквой), а для обращения к каждому отдельному числу данной последовательности используются различные индексы (номера элементов). В математике это выглядит, например, так: a₁, a₂, a₃, ..., a_n.

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

Данная диаграмма соответствует не только одномерным, но и многомерным массивам.

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

Помимо ограниченных типов, это могут быть непосредственно типы byte, char, boolean и введенные программистом перечислимые типы. В последних трех случаях индексами будут являться не числа, а символы или соответствующие константы перечислимого типа. Такие возможности иногда оказываются чрезвычайно полезными, см., например, задачу 5 к материалам данного урока. Такие типы, как integer, word и longint, не используются в аналогичных целях лишь потому, что в этом случае количество описанных элементов массива превышает возможности по резервированию памяти компилятором или операционной системой. Так, в языке Borland Pascal на все переменные, описанные в одном блоке (в частности, на все глобальные переменные), отводится 64 Кб, а именно столько однобайтовых значений содержал бы массив, проиндексированный числами типа integer или word, и никакой другой переменной описать уже было бы невозможно, т.е. обработать подобный массив нельзя. В языке Delphi, согласованном с моделью памяти Windows, данное ограничение на размер данных снято, но и тип integer определяет уже 2³² ~ 4x10 ⁹ различных значений, что все же слишком много по современным меркам.

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

максимальное значение индекса – минимальное значение индекса + 1.

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

const nmax = 100;

type aa = array[1..nmax] of real;

var a: aa;

То есть мы создали массив, состоящий из 100 вещественных чисел. Меняя значение константы n, мы можем изменять количество элементов в массиве.

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

type bb = array[-5..3] of boolean;

Массивы данного типа будут содержать 9 логических переменных, пронумерованных от –5 до 3.

Над переменными типа массив возможна только операция присваивания. То есть содержимое одного массива может быть присвоено содержимому другого массива того же самого типа. Например, если мы добавим в описание переменных переменную b того же типа aa, то в программе будет возможно использовать следующий оператор присваивания:

b := a;

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

С элементами же массива можно осуществлять все те действия, которые допустимы с обыкновенными переменными соответствующего типа (real, integer и т.д.). Чтобы обратиться в программе к конкретному элементу массива, после имени переменной типа массив в квадратных скобках должно стоять выражение для соответствующего индекса элемента. Это может быть константа, входящая в диапазон констант, указанный при описании, это может быть переменная того же самого порядкового типа (если в качестве индексов используется конкретный диапазон целых значений, то переменная может принадлежать любому целому типу), наконец, это может быть произвольное выражение, значение которого также принадлежит указанному типу. Например, a[5], a[i], a[i+1], a[2*k–1]. При использовании переменных для обозначения индекса их значения к моменту использования должны быть определены, а в случае арифметических выражений их результат не должен выходить за границы массива (минимальное и максимальное значения индекса).

Чаще всего массив обрабатывается в цикле for. Так, для того чтобы считать c клавиатуры описанный выше массив а, следует написать следующее:

readln(n);

for i := 1 to n do read(a[i]);

readln;

Здесь n — реальный размер массива, который часто является параметром задачи, он не должен превышать значения nmax, использованного при описании данного массива.

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

Аналогично производится распечатка массива. Но просто заменить read на write здесь недостаточно. Для того чтобы печатаемые значения не сливались между собой, надо явным образом вставлять между ними разделитель — пробел или перевод строки. Приведем два возможных способа распечатки массива:

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

writeln;

2) for i := 1 to n do writeln(a[i]);

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

Вводить значения элементов с клавиатуры не всегда удобно. Более того, часто при отладке программы нам надо сделать так, чтобы она работала на произвольных массивах. В этом случае очень удобно задавать значения элементов массива случайным образом, с использованием встроенного в язык программирования так называемого датчика псевдослучайных чисел. Для этого используются функция random и процедура randomize. Если использовать первую из них без параметров, то при очередном обращении она будет выдавать в качестве результата некоторое псевдослучайное вещественное число из диапазона [0; 1). Процедура randomize предназначена для задания первого значения в данной последовательности. Обращаться к процедуре randomize имеет смысл только один раз — в начале работы программы. Для получения целых случайных чисел из диапазона [0; n–1] используется вызов функции random с параметром n: random(n). Приведем пример заполнения случайным образом целочисленного массива m, состоящего из n элементов, десятичными цифрами:

randomize;

for i := 1 to n do m[i] := random(10);

Обратите внимание: ни один из элементов этого массива не может оказаться равным 10.

Приведем пример работы с массивом. Пусть заданы массив a введенного ранее типа aa и его реальная размерность n (под словом “задан” здесь и далее мы будем понимать, что массив не только описан, но и значения его элементов определены тем или иным способом). Требуется сдвинуть элементы массива на одну позицию влево, а первый элемент поставить на последнее место. Следующий фрагмент решает данную задачу:

с := a[1];

for i := 1 to n - 1 do a[i] := a[i + 1];

a[n] := c;

Переменная с здесь должна быть того же типа, что и элементы массива. В нашем случае — real.

Задачи

1. Заполните числовой массив так, чтобы

а) значениями элементов оказались случайные целые числа от a до b включительно;

б) значениями элементов были случайные вещественные числа от 0 до 10;

в) значения элементов совпадали с их индексами;

г) значения элементов были равны квадратам индексов.

В последнем случае на вход программе подаются два целых числа — a и b, по модулю не превосходящие 100, a b. Требуется вывести массив с индексами от a до b, элементы которого равны квадратам своих индексов.

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

На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте значения элементов массива после выполнения указанной операции.

3. Найдите максимальный и минимальный элементы в массиве и поменяйте их местами.

На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте значения элементов массива после выполнения указанной операции.

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

На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 10 000. Выдайте значения искомых элементов массива в том же порядке, в каком они располагались во входных данных.

5. Текст на английском языке записан в массиве a[1..1000] of char. Помимо английских букв, в нем могут встречаться пробелы и знаки препинания. В массиве b['A'..'Z'] of integer получите сведения о том, сколько каких букв встречается в этом тексте. При подсчете строчные и прописные буквы не различать.

На вход программе сначала подается значение n 1000 — количество букв в тексте. В следующей строке входных данных расположены сами буквы (без разделителей). Выдайте 26 чисел — значения элементов массива b.

6. На вход программе подается последовательность чисел от 1 до 9, заканчивающаяся нулем. Всего будет введено не более 100 000 чисел. Подсчитайте в этой последовательности количество единиц, количество двоек, количество троек и так далее и выдайте результат. В выходных данных всегда должно быть 9 чисел.

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

На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте количество искомых элементов массива.

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

На вход программе сначала подается значение
n 10 000 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте два искомых числа в порядке неубывания.

9. На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Распечатайте только те значения элементов массива, которые встречаются в нем ровно один раз. Элементы следует распечатывать в том порядке, в котором они встречаются в массиве.

10. На вход программе сначала подается значение  n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Распечатайте только те значения элементов массива, которые встречаются в нем более одного раза, при этом каждое найденное значение должно быть распечатано только один раз. Элементы следует распечатывать в том порядке, в котором они встречаются в массиве.

Задачи повышенной сложности

1. По введенному натуральному числу k, не превосходящему 100 000, выдать k-е по счету простое число. Используйте массив для запоминания уже найденных простых чисел.

2. Определите, сколько раз число n! (факториал n) нацело делится на натуральное число k (1 < n, k < 2³¹).

На вход программе подаются целые числа n и k, выведите количество раз, которое n! нацело делится на k.

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

На вход программе сначала подается значение n 10 000 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте значения ненулевых элементов массива после выполнения указанной операции.

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

4. Дан массив натуральных чисел a₁, a₂, …, a_n, по модулю не превосходящих 100, и натуральные числа k и m.
Укажите минимальное значение i такое, что a_i + a_i+1 + … + a_i+k = m (т.е. сумма k + 1 подряд идущих элементов массива равна m 10 000, 0 < k < n 30 000). Если такого значения нет, то выведите 0. Вложенные циклы не использовать.

5. В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна ⁶.

Фактически требуется найти такие i и j (i j), что сумма всех элементов массива от a_i до a_j включительно будет максимальна.

На вход программе сначала подается значение n 10 000 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным.

6. Заданы два неупорядоченных массива целых чисел, по модулю не превосходящих 10 000. Будем рассматривать их как множества с повторяющимися элементами. Не используя дополнительной памяти, требуется распечатать пересечение двух множеств. Так, массивы
{2, 1, 2, 3} и {2, 4, 2, 2} имеют пересечение {2, 2}. По окончании работы программы сами массивы должны быть такими же, какими они были после заполнения.

На вход программе сначала подается значение n 100 — количество элементов в первом массиве.
В следующей строке входных данных расположены сами элементы массива. Далее на вход программе подается значение m 100 — количество элементов во втором массиве. В следующей строке входных данных расположены сами элементы второго массива. Элементы в обоих массивах — целые числа, по модулю не превосходящие 10000.

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

7. Напишите эффективную программу, которая будет циклически сдвигать заданный массив на k элементов вправо ⁷. Дополнительные массивы и рекурсию не использовать.

На вход программе сначала подаются значения n 100 — количество элементов в массиве и k 100. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Выдайте значения элементов массива после выполнения указанной операции.

8. Числовая последовательность называется пилообразной, если каждый ее элемент (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

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

На вход программе сначала подаются значения n (1 n 100 000) — количество членов последовательности. Во второй строке записано n натуральных чисел, не превосходящих 10 000, — члены последовательности.

Выведите одно число — минимальное количество элементов, которые необходимо вычеркнуть.

Урок 10

Двумерные массивы (матрицы)

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

const n = 10; m = 20;

type aa2 = array[1..n] of

array[1..m]

of real;

var a: aa2;

Это описание соответствует таблице (матрице) вещественных чисел, состоящей из 10 строк и 20 столбцов. Каждый элемент таблицы имеет два индекса, и обратиться к конкретному элементу матрицы из программы можно, например, следующим образом: a[5][3], — что соответствует элементу, стоящему в пятой строке и третьем столбце.

Более распространенным является другое описание двумерных массивов. В нашем примере оно будет выглядеть так:

type bb2 = array[1..n,1..m] of real;

var b: bb2;

При таком описании обращение к конкретному элементу выглядит следующим образом: b[5,3]. Обработка таких массивов производится с помощью двух вложенных циклов. Например, считать элементы массива и распечатать их в виде таблицы можно следующим образом:

for i := 1 to n do
for j := 1 to m do read(b[i,j]);
readln;
for i := 1 to n do
begin

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

end;

Сказанное выше распространяется и на массивы большей размерности. Элементы многомерных массивов в памяти компьютера располагаются “по строкам” ⁸. То есть сначала расположены все элементы первой строки (первый индекс фиксирован и равен своему минимальному значению), затем второй и т.д. Таким образом, при равноправном расположении вложенных циклов для обработки многомерного массива сначала следует организовать цикл по первому индексу, потом по второму и т.д. (так, как это и сделано в приведенном выше примере).

Наибольший интерес представляют квадратные матрицы, то есть двумерные массивы, у которых оба измерения совпадают, например:

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

Рассмотрим, как эффективно обрабатывать различные части матриц.

Проведем в таблице так называемую “главную диагональ” — линию, соединяющую левый верхний и правый нижний угол квадратной матрицы. Пометим все элементы цифрами 0, 1 или 2 в зависимости от расположения элемента матрицы относительно главной диагонали:

Элементы, стоящие на главной диагонали матрицы, обозначены цифрой 0. У произвольного элемента квадратной матрицы a[i,j] i — это номер строки, а j — это номер столбца. Тогда принадлежность элемента главной диагонали описывается условием i = j. А для обработки всех элементов, находящихся на главной диагонали, достаточно одного цикла:

for i := 1 to n do

…a[i,i]…

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

for i := 1 to n - 1 do

{это цикл по всем строкам}

for j := i + 1 to n do

{цикл по столбцам: от диагонали до n}

…a[i,j]…

Наконец, элементы нижнего треугольника, помеченные цифрой 2, описываются так:

for i := 2 to n do

for j := 1 to i - 1 do

…a[i,j]…

Задачи

1. a) Заполните и выведите двумерный массив 5 ? 5 символами пробел и “*” так, чтобы получилась “снежинка”:

б) Заполните и выведите двумерный массив 8 ? 8 так, чтобы получилась шахматная доска. Белые клетки заменяйте пробелами, а черные — символами “*”:

2. Разделим квадратную матрицу диагональю, обычно называемой “побочной”:

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

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

3. В кинотеатре n рядов по m мест в каждом. В соответствующем двумерном массиве хранится информация о проданных билетах на определенный сеанс (единицы означают, что на данные места билеты уже проданы, нули — что данные места еще свободны). Поступил запрос на продажу k билетов на соседние места в одном ряду. Определить, можно ли удовлетворить такой запрос.

В первой строке входных данных находятся числа n, m, k 100. В следующих n строках входных данных расположены по m чисел (0 и 1), разделенных пробелами. Выведите YES или NO в зависимости от ответа на вопрос задачи.

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

По введенному n 30 выведите n первых строк треугольника Паскаля.

5. Во входных данных описан план комнаты. Сначала дано количество строк n, затем — количество столбцов m (1 n 20, 1 m 20). Затем записано n строк по m чисел в каждой — количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число x — сколько клеток обошел мудрец. Далее записаны координаты этих клеток (координаты клетки — это два числа: первое определяет номер строки, второе — номер столбца, верхняя левая клетка на плане имеет координаты (1, 1), правая нижняя — (n, m)).

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

6. По введенным значениям n, m (1 n 20, 1 m 20) заполните массив размерностью n ? m числами от 1 до mn, расположив их горизонтальной “змейкой” так, как показано в примере.

7. По введенным значениям n, m (1 n 20, 1 m 20) заполните массив размерностью n m числами от 1 до mn, расположив их по спирали, закрученной по часовой стрелке, так, как показано в примере.

8. Дан квадратный массив. Требуется повернуть его на 90° по часовой стрелке (результат можно записать в другой массив).

На вход программе сначала подается значение n 20 — размер массива. В следующих n строках входных данных расположены сами элементы массива — натуральные числа, меньшие 100. Выведите массив, полученный после поворота исходного.

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

В первой строке входных данных находятся числа n, m, k 100. В следующих n строках входных данных расположены по m натуральных чисел, не превосходящих 10000. Выведите пары индексов искомых элементов, каждую в отдельной строке. Нумерация строк и столбцов начинается с единицы.

Если искомых элементов нет, то выведите 0.

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

В первых восьми строках входных данных описывается шахматная доска. Первые восемь символов каждой из этих строк описывают состояние соответствующей горизонтали: символ “B” (заглавная латинская буква) означает, что в клетке стоит слон, символ “R” — ладья, символ “*” — что клетка пуста.

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

Урок 11

Строки

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

Значениями данного типа в Borland Pascal являются различные последовательности символов длиной от 0 до 255 символов. При описании строковой переменной в квадратных скобках может быть указан ее максимальный размер, не превосходящий 255. Если такой размер опущен, то считается, что длина строки может достигать 255 символов. Указание размера строки влияет только на распределение памяти для хранения соответствующих переменных. Все переменные строковых типов совместимы между собой при выполнении различных операций над строками.

Примеры описания строк:

var

s1, s2: string;
name: string[20];
group: string[3];
txt: array[1..25] of string[80];

Cтроку почти всегда можно рассматривать как массив символов, то есть обращаться из программы к отдельным символам строки: s1[1], s2[i], txt[1][10] (в последнем случае имеется в виду десятый символ первой строки). Нумерация символов в строке всегда начинается с 1. Однако присваивание отдельным элементам строки конкретных символьных значений может не привести к желаемому результату. Чтобы понять, почему это иногда происходит, необходимо рассмотреть принципы организации подобных строковых переменных в памяти компьютера. Дело в том, что для хранения любой строки отводится на 1 байт больше, чем указано при ее описании (256 байт для строк, размерность которых не указана явно). Причем этот вспомогательный байт располагается в самом начале строки, фактически это ее нулевой байт. В нем хранится текущая реальная длина строки. Собственно говоря, такой механизм и накладывает максимальные ограничения на возможную длину строк в Borland Pascal, так как максимальное число, представимое в одном байте, равно 255. Значение этого байта автоматически изменяется программой при выполнении стандартных операций над строками: считывании, присваивании строковой переменной строкового выражения, обращении к стандартным процедурам и функциям, работающим со строковыми выражениями. Рассмотрим на примере, как меняется содержимое памяти и реальное значение строки при выполнении тех или иных операций (см. таблицу).

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

В отличие от массивов над строковыми переменными определены операции считывания и печати. К строкам применима операция сложения. При сложении двух строк к концу первой из них приписывается вторая (по-другому эту операцию называют конкатенацией строк). Над строками реализованы и все операции сравнения. Сравнение строк между собой производится согласно так называемому лексикографическому порядку. Строка s1 считается меньше строки s2, если существует такая позиция k, что s1[1..k–1] = s2[1..k–1] и s1[k] < s2[k], или такой позиции не существует, но строка s1 короче строки s2. Например:

'abracadabra' < 'baobab' (здесь k = 1);

'abba' < 'abra' (здесь k = 3);

'abb' < 'abba' (здесь строки сравнивались по длине).

Приведем также основные процедуры и функции для работы со строками:

length(s) — функция, определяющая реальную длину строки;
сopy(s,i,n) — функция, выделяющая из строки s подстроку длиной n, начиная с символа i;
delete(s,i,n) — процедура, удаляющая из строки s n символов, начиная с символа с номером i;
pos(s1,s) — функция, в качестве результата выдающая номер позиции в строке s, с которой начинается подстрока s1; если подстрока не найдена, то результат равен 0;
insert(s1,s,i) — процедура, вставляющая в строку s подстроку s1, перед символом с номером i;
val(s,n,i) — процедура, переводящая строку s в число (вещественное или целое), согласно типу переменной n, если строка s не является изображением числа соответствующего типа по правилам Паскаля, то значение переменной i будет отлично от 0, при удачной конвертации значение i равно 0;
str(i,s) — процедура, переводящая число в его строковое представление, у числа можно указать формат, аналогично тому, как это делается в операторе write.

В языке Delphi, помимо паскалевских “коротких” строк, реализованы и динамические “длинные” строки, размер которых ограничен только возможностями операционной системы. Описываются эти строки так же, как и короткие, с помощью слова string, без указания размера. Память под такие переменные выделяется по мере необходимости в процессе выполнения программы. Обращение к несуществующим элементам такой строки, то есть к элементам, чей индекс превосходит текущую длину строки, эквивалентно выходу за границу массива (с короткими строками в пределах 255 символов это не так).

Какие именно строки имеются в виду, определяется с помощью директивы компилятора H. Так, директива {$H+}, записанная в начале программы, означает, что строки будут “длинные”, а {$H–} — короткие.

Кроме того, в модуле SysUtils языка Delphi реализовано много дополнительных по отношению к стандартным паскалевским функций над строками. Наиболее часто употребимыми из них являются удобные функции перевода чисел в строки и обратно. Приведем некоторые из них:

IntToStr(i) — функция, переводящая целое число в строку;
StrToInt(s) — функция, переводящая строку в целое число;
FloatToStrF(s,ffFixed,d,p) — функция, переводящая целое число в строку по формату :d:p, аналогичному форматной печати;
StrToFloat(s) — функция, переводящая строку в вещественное число.

Задачи

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

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

В примере пробельные символы изображаются с помощью .

2. Фраза называется палиндромом (перевертышем), если после удаления пробелов и замены всех букв на заглавные она читается одинаково как слева направо, так и справа налево. Требуется определить, является ли введенная фраза палиндромом.

На вход программе подается строка, состоящая не более чем из 255 символов. Выведите YES или NO в зависимости от ответа на вопрос задачи.

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

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

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

4. Строка состоит из двух слов. Поменяйте эти слова местами.

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

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

На вход программе сначала подается число 0 < M 255. В следующей строке находится исходный текст. Длина слов в нем не превышает M, слова разделены ровно одним пробелом. Выведите разбиение этого текста на строки длиной не более чем M символов (слово переносится на следующую строку только если в текущей строке его разместить уже невозможно). Новая строка не должна начинаться с пробела.

6. Определить, сколько букв содержит самое длинное слово во введенной строке символов.

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

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

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

8. Напишите модификацию функции pos, которая находит все вхождения искомой подстроки в данной строке. В первой строке вводится исходная строка, в следующей — подстрока. В качестве ответа выведите в порядке возрастания все такие числа i, что, начиная с i-го символа, начинается некоторое вхождение подстроки в исходную строку.

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

9. Дана последовательность символов, имеющая следующий вид: P₁*P₂*P₃ …*P_n, где P_i — цифра. Вычислите значение выражения.

На вход программе подается строка указанного вида, состоящая не более чем из 9 цифр, разделенных символами умножения ‘*’. Выведите результат перемножения этих цифр.

10. Даны два “длинных” целых неотрицательных числа. Требуется найти результат их сложения. В качестве типа данных для хранения чисел используйте строки.

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

Задачи повышенной сложности

1. Даны два “длинных” целых неотрицательных числа. Требуется найти результат их умножения. В качестве типа данных для хранения чисел используйте строки.

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

2. Дана последовательность символов, имеющая следующий вид: p₁q₁p₂q₂p₃…q_n-1p_n, где p_i — цифра, а q_i — знак арифметического действия из набора {+, –, *}. Вычислите значение выражения, предполагая, что действия выполняются согласно правилам арифметики.

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

3. Текст был зашифрован следующим образом. Сначала определяется количество букв в самом длинном слове, его длину обозначим К (словом называется непрерывная последовательность английских букв, слова друг от друга отделяются любыми другими символами, длина слова не превышает 20 символов). Затем каждая английская буква заменяется на букву, стоящую в алфавите на K букв ранее (алфавит считается циклическим, то есть перед буквой A стоит буква Z), оставив другие символы неизменными. Строчные буквы при этом остаются строчными, а заглавные — заглавными. Расшифруйте введенную шифровку.

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

4. У Васи на клавиатуре не работает клавиша пробел. Поэтому все тексты он теперь набирает слитно. Напишите программу, которая будет разделять набранный Васей текст на слова из данного словаря.

На вход программе сначала подается текст, введенный Васей, — строка из не более чем 100 латинских строчных букв. В следующей строке записано количество слов в словаре N — натуральное число, не превосходящее 2000. В следующих N строках записаны слова из словаря?— по одному слову в каждой строке, каждое слово длиной не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.

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

Время работы программы на одном тесте — 1 секунда.

5. Определите, является ли введенная строка символов записью оператора присваивания с точки зрения языка Паскаль для типа integer. Причем функции и арифметические операции, в том числе унарные, не используются (то есть производится присваивание константы или переменной).

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

Урок 12

Функции

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

В заголовке функции определяется имя функции, формальные параметры (если они имеются) и тип результата функции (см. диаграмму внизу).

Результат функции может быть любого скалярного типа, а также типа string, в Delphi результат может быть и сложного типа. Формальное описание блока (в данном случае его еще называют тело функции) можно найти во введении. В операторной части блока функции задаются операторы, которые будут выполняться при вызове (активизации) функции. Среди них должен содержаться по крайней мере один оператор присваивания, в котором идентификатору функции присваивается значение, тип которого совпадает с типом результата функции. Результатом функции является последнее присвоенное значение. Если такой оператор присваивания отсутствует или он не был выполнен, то значение, возвращаемое функцией, не определено.

В языке Delphi существует и другой, более удобный способ обозначения результата функции — это стандартная переменная с именем result. Эта переменная того типа, который указан в качестве типа результата. При использовании в описании функции такой предопределенной переменной результатом функции является последнее значение, присвоенное этой переменной.

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

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

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

var x, y, z: integer;

function max(a, b: integer): integer;

begin

if a > b then max := a else max := b

end;

begin

readln(x, y, z);
writeln(max(max(x,y),z))

end.

Процедуры

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

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

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

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

type aa = array[1..100] of integer;

var

a: aa;
i: integer;

procedure print(n: integer; var m: aa);

var i: integer;

begin

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

end;

begin

for i := 1 to n do a[i] := random(100);
for i := 1 to n do print(a,i)

end.

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

Параметры процедур и функций

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

Существуют два основных типа параметров: параметры-значения и параметры-переменные. При описании они обозначаются следующим образом:

1) группа параметров, перед которыми отсутствует ключевое слово var, является списком параметров-значений;

2) группа параметров, перед которыми следует ключевое слово var, является списком параметров-переменных.

Формальный параметр-значение обрабатывается как локальная по отношению к процедуре или функции переменная, а свое начальное значение он получает из соответствующего фактического параметра при активизации процедуры или функции. Изменения, которые претерпевает формальный параметр-значение, не влияют на значение фактического параметра. Соответствующее фактическое значение параметра-значения должно быть выражением типа, совместимого по присваиванию с типом формального параметра-значения (в том числе оно может быть константой или переменной).

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

Локальные параметры-значения, ссылки на параметры-переменные и все локальные переменные, описанные непосредственно в подпрограмме, располагаются в специальной области оперативной памяти, называемой стеком. Размер стека определяется заранее, например, с помощью директив компилятора. В Borland Pascal он не может превышать 65?520 байт, в Delphi он ограничен лишь возможностями используемого компьютера и операционной системы. Так, в системе UNIX максимальный размер стека, выделяемого одной программе, устанавливается в операционной системе, а установки самой программы игнорируются.

Рассмотрим механизм передачи параметров на примере.

var a,b: integer;

procedure ab(a: integer; var b: integer);

begin

a := a + 1;
b := b + 1;
writeln(a,' ',b)

end;

begin

a := 1;
b := 2;
ab(a + 2,b);
ab(b,a);
writeln(a,' ',b)

end.

Попробуйте, не запуская эту программу на выполнение, разобраться, что она выдаст в качестве результата своей работы, а потом сравните с результатом ее выполнения на компьютере. Давайте разберемся, почему результат получается именно такой. При первом обращении к процедуре ab формальный параметр a примет значение выражения a + 2 (оно равно 3), где a — это уже глобальная переменная. Второй параметр b в данном случае означает, что под переменной b в подпрограмме будет подразумеваться глобальная переменная b. Совпадение имен здесь никакой роли не играет. При выполнении процедуры локальная переменная a станет равна 4, а локальная переменная b, она же глобальная переменная b, станет равна 3. Оператор вывода при этом напечатает:

4 3

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

4 2

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

2 3

Попробуем теперь сформулировать правила, по которым следует определять вид того или иного параметра процедуры или функции:

* входные параметры, значения которых не должны измениться в программе, скалярных и строковых типов должны быть параметрами-значениями, в этом случае при обращении к соответствующей процедуре или функции можно использовать не только имена переменных, но и константы, и выражения; в большинстве стандартных функций, таких, например, как sin(x), параметры описаны именно как параметры-значения;

* выходные (результирующие) параметры должны быть параметрами-переменными;

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

* переменные файловых типов (см. урок 14) могут передаваться только как параметры-переменные.

Задания

1. Напишите функцию для нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида и используйте ее в программе для нахождения НОД уже N чисел.

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

3. Напишите функцию, вычисляющую площадь треугольника по целочисленным координатам трех его вершин. Стандартные вещественные функции, такие, как sin, cos, sqrt и другие, не использовать.

4. Напишите процедуру печати двумерного массива. В программе задайте массив случайным образом, распечатайте его с использованием процедуры, затем поверните данный массив на 180^о и распечатайте его еще раз.

5. Напишите процедуру, которая по входному параметру n — нечетному числу, не превосходящему 21, будет печатать с помощью символов “*” равнобедренный треугольник следующего вида:

*

***

*****

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

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

7. Напишите процедуру swap обмена местами значений двух целочисленных переменных без использования вспомогательной переменной. Объясните, почему данная процедура работает некорректно при обращении к ней с одной и той же переменной, например, swap(a,a).

8. Напишите функцию, вычисляющую значение интеграла функции f(x) на интервале [a; b] (или площадь под графиком функции) одним из численных методов (например, методом трапеций, прямоугольников или методом “Монте-Карло”). Параметрами такой функции должны быть сама функция f (функцию тоже можно передавать как параметр), вещественные значения a и b, а также точность вычислений e. Результатом является значение площади.

9. Напишите функцию, решающую уравнение f(x) = 0 на интервале [a; b] в предположении, что на этом интервале функция непрерывна и уравнение содержит ровно один корень. Используйте один из численных методов (например, метод деления пополам или метод хорд). Параметрами такой функции должны быть сама функция f, вещественные значения a и b, а также точность вычисления корня e. Результатом является искомый корень.

10. Напишите процедуру, рисующую график непрерывной функции f(x) на интервале [a; b]. Параметрами такой процедуры должны быть сама функция f, вещественные значения a и b, а также координаты левого верхнего и правого нижнего углов прямоугольной части экрана (окна), в которой должен быть нарисован график.

Урок 13

Рекурсия

Рекурсия является средством программирования, при котором процедура или функция прямо или косвенно вызывает сама себя. То есть либо при описании функции или процедуры используется обращение к ней же самой, но с другим набором параметров, либо подпрограмма вызывает какую-либо другую подпрограмму, в описании которой содержится вызов исходной (например, процедура A вызывает процедуру В, а процедура В вызывает процедуру А). Косвенный вызов может быть организован и более сложным образом, т.е. в рекурсию могут быть вовлечены несколько подпрограмм. Покажем, как на языке Pascal можно описать подобную систему подпрограмм (без специальных средств это сделать невозможно, так как при описании процедуры A процедура В уже должна быть описана, и наоборот):

procedure Carl(N: integer); forward;

procedure Clara(X, Y: real);

begin

...

Carl(5);

...

end;

procedure Carl;

begin

...

Clara(8.3, 2.4);

...

end;

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

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

f₀ = 1, f_n = f_n–1 · n.

Соответствующая данному описанию функция на языке Pascal выглядит так:

function f(n: integer): longint;

begin

if n = 0 then f := 1 else f := f(n-1)*n

end;

Совершить ошибку при подобном способе вычисления факториала практически невозможно. Рекурсивный вариант реализации алгоритма обычно выглядит изящнее и дает более компактный текст программы, но исполняется медленнее. Кроме того, при каждом рекурсивном вызове (в приведенном примере их n + 1) локальные переменные и параметры рекурсивной подпрограммы размещаются в стеке, то есть в данном случае используется значительно больше памяти, чем при нерекурсивном вычислении того же факториала. Часто такое избыточное использование ресурсов компьютера может оказаться критичным для работы программы, и она заканчивает свою работу с сообщением Stack overflow (переполнение стека) или зависает. В книге
Н.И. Вьюковой, В.А. Галатенко, А.Б. Ходулева “Систематический подход к программированию” приведена интересная иллюстрация, показывающая разницу между рекурсивным и нерекурсивным алгоритмом. Приведем ее с небольшими изменениями.

Пусть у нас имеется N человек, причем k-й (0 < k < N) знает только телефон следующего (k+1)-го человека, а N-й знает только то, что он последний. Пусть далее некто, знающий телефон первого человека, решил выяснить, чему равно N. Если он будет действовать нерекурсивно, то он запасется бумагой, на которой будет вести подсчеты, напишет на ней 0 и позвонит первому. Затем он сотрет 0, напишет 1 и спросит у первого телефон второго человека, повесит трубку, наберет номер второго, исправит 1 на 2, спросит телефон третьего
и т.д., пока не доберется до человека, который сообщит, что он последний. Число, записанное в этот момент на бумаге, и будет служить ответом.

Если же упомянутый некто захочет действовать рекурсивно, он позвонит первому и прикажет: “Алло, не вешайте трубку! Сообщите мне, сколько вас”. Поскольку первый не знает, сколько их, а трубку вешать нельзя, ему придется пойти к соседям и позвонить второму, сказав те же слова и оставшись ждать ответа. Второй также отправится к соседям и т.д., пока, наконец, последний не сообщит предпоследнему, что он один. Предпоследний прибавит к ответу последнего 1 и скажет, что их двое, и т.д. Наконец, заждавшийся первый услышит в трубке голос второго, прибавит к услышанному числу 1 и пойдет к себе домой, чтобы сообщить результат.

Таким образом, при нерекурсивном способе в каждый момент соединена только одна пара абонентов и используется один листок бумаги, при рекурсивном — до N пар и N листков бумаги. Переполнение стека можно сравнить в данном случае с ситуацией, когда АТС окажется перегруженной и к очередному человеку дозвониться не удастся.

Тем не менее рассмотрим примеры уместного использования рекурсивных алгоритмов. В задаче 9 к уроку 7 был приведен пример алгоритма эффективного возведения вещественного числа x в целую неотрицательную степень n. Соответствующая программа не является достаточно прозрачной. Рассмотрим рекурсивный алгоритм решения этой же задачи, основанный на следующих очевидных соотношениях:

x⁰ = 1; если n — нечетное, то xⁿ = x^n–1?n, в противном случае xⁿ = (x²)^n/2.

Зададим по данному описанию рекурсивную функцию:

function power(x:real; n:integer):integer;

begin

if n = 0 then power := 1
else if n mod 2 = 0 then
power := power(x*x,n div 2)
else power := power(x,n-1)*x

end;

В качестве другой иллюстрации приведем решение известной головоломки “Ханойские башни”. В этой задаче имеются три стержня, обозначенных буквами А, В и С. На стержне А, как на детской пирамидке, надеты n колец в порядке убывания диаметров. Требуется переложить все кольца на стержень С, используя стержень В как вспомогательный. За один ход разрешается переложить верхнее кольцо с любого стержня на любой другой, при этом большее кольцо нельзя класть на меньшее.

Будем рассуждать так. Для одного кольца задачу мы заведомо решить можем. Пусть мы умеем решать задачу для n – 1 колец. Тогда сначала переложим их с А на В, используя стержень С как вспомогательный (это можно сделать, так как n-е кольцо больше всех остальных и процессу перекладывания не мешает). Затем переложим N-е кольцо на стержень С и снова выполним процедуру перекладывания N – 1 колец, но теперь уже с В на С, используя стержень А как вспомогательный.

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

var n: integer;

procedure ABC(n: integer; a,b,c: char);
{a-исходный,b-вспомогательный,с-целевой}

begin

if n = 1 then writeln(a,' -> ',c)

else

begin

abc(n-1,a,c,b);
writeln(a,' -> ',c);
abc(n-1,b,a,c)

end

end;

begin

readln(n);
abc(n,'A','B','C');

end.

Так, для трех колец данная программа выдаст следующий план перекладываний:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

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

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

а) почему программа заканчивает работу;

б) почему она работает правильно?

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

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

Задачи

1. Числа Фибоначчи задаются следующими соотношениями:

f₀ = f₁ = 1; f_n = f_n–1 + f_n–2, n >1.

Напишите рекурсивную и нерекурсивную функции, вычисляющие n-е число Фибоначчи, и сравните скорость их работы. Попробуйте объяснить результаты сравнения.

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

На вход программе сначала подается искомое число K, затем количество элементов в массиве N 10 000, затем сами N элементов упорядоченного массива целых чисел, по модулю не превосходящих 30 000. Выведите 0, если искомый элемент в массиве отсутствует, или номер этого элемента. Нумерация элементов ведется с единицы. Если искомых элементов несколько, то выведите номер первого из них.

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

На вход программе в первой строке подается количество элементов N (N 10 000). Далее следуют N элементов массива — целые числа, по модулю не превосходящие 30000. Выдайте этот же массив чисел после сортировки по неубыванию.

4. Опишите рекурсивную функцию, которая определяет, является ли симметричной часть строки S, начиная с i-го элемента и заканчивая j-м. Решите с помощью этой функции задачу 3 к уроку 11.

5. Напишите рекурсивную функцию для перевода десятичного числа в P-ичную систему счисления, не использующую в своей работе массив.

На вход программе сначала подается значение Р (1 < P < 10), а во второй строке — десятичное число. Вывод осуществляйте следующим образом: сначала выведите введенное число в десятичной системе счисления, за ним укажите его систему счисления в круглых скобках, то есть (10), затем ставится знак “=” и аналогично выводится результат работы вашей программы — число в Р-ичной системе счисления. Весь вывод осуществляется без пробелов.

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

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

На вход программе подаются натуральные числа n (n 17) и k (k n). Выведите все k-элементные подмножества множества {1, 2, 3, …, n}. Каждое подмножество выводите в отдельной строке. Числа внутри одного подмножества упорядочивайте по возрастанию.

8. В первой строке входных данных записано n — число строчек и m — число столбцов в двумерном массиве. В последующих n строчках записано m чисел, каждое из которых равно либо 0, либо 1. Числа разделены пробелами. Требуется вывести количество объектов, состоящих из единичек. Если две единички являются соседями по вертикали или горизонтали, то они принадлежат одному и тому же объекту.

9. Дана шахматная доска nxn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.

На вход программе подается натуральное число n (n 8). Если обход невозможен, то выведите в выходной файл 0. Если возможен, то 1, а на следующих строчках выведите матрицу n x n, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.

10. Дана шахматная доска nxn. Найти количество всевозможных различных расстановок n ферзей на этой доске. При этом никакие два ферзя не должны “бить” друг друга. Две расстановки считаются различными, если существует такое поле, что в первой расстановке на нем есть ферзь, а во второй — нет.

На вход программе подается натуральное число n (n 10). Выведите количество всевозможных расстановок n ферзей на этой доске.

Урок 14

Файловые переменные

Словом “файл” в программировании называется сразу несколько несовпадающих понятий. Во-первых, это файл операционной системы — “поименованная часть диска”. Во-вторых, это абстрактная структура данных с последовательным доступом, и, в-третьих, переменные файловых типов, реализующие данную структуру данных в конкретном языке программирования.

В данном уроке мы подробно рассмотрим лишь один из файловых типов — text. Стандартный файловый тип text определяет файл, содержащий символы, упорядоченные в строки. Переменная типа text называется файловой переменной. Перед использованием файловой переменной она должна быть связана с внешним файлом операционной системы с помощью вызова процедуры assign. Во внешних файлах сохраняется записанная в файл информация, или они служат источниками информации, которая считывается из файла.

Когда связь с внешним файлом установлена, для подготовки ее к операции ввода или вывода файловая переменная должна быть “открыта” либо только на чтение, либо только на запись. На чтение можно открыть только реально существующий файл. Делается это с помощью процедуры reset, а новый файл можно создать и открыть на запись с помощью процедуры rewrite. Если же на запись открывается уже существующий файл, то он автоматически становится пустым в момент открытия, т.е. его старое содержимое оказывается безвозвратно утерянным.

С большинством правил чтения данных из текстовых файлов и записи в них результатов работы программы вы знакомы с момента написания самых первых программ. Дело в том, что в момент начала выполнения программы всегда автоматически открываются стандартные текстовые файловые переменные input и output. input — это доступный только для чтения файл, связанный с клавиатурой, а output — это открытый на запись файл, связанный с дисплеем. И хорошо знакомые вам процедуры read и write — это процедуры чтения данных из файла и записи данных в файл соответственно. Если имя файловой переменной при этом не указывается, то считается, что чтение происходит из стандартного файла input, а запись — в стандартный файл output.

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

При открытии текстового файла внешний файл интерпретируется особым образом: считается, что он представляет собой последовательность символов, сгруппированных в строки, где каждая строка заканчивается символом конца строки (end-of-line), который представляет собой символ перевода каретки, за которым в Windows следует еще и символ перехода на новую строку.

Когда программа завершает обработку файла, он должен закрываться с помощью процедуры close. Только после полного закрытия файла связанный с ним файл операционной системы обновляется. Затем файловая переменная может быть связана с другим внешним файлом.

Приведем пример работы с текстовыми файлами.

var

n: integer;
f,g: text;

begin

assign(f,'input.txt');
reset(f);
read(f, n);
…
assign(g, 'output.txt');
rewrite(g);
writeln(g, n);
close(g)

end.

Стандартные процедуры и функции, использующиеся для текстовых файлов

Процедура assign(файловая переменная, строка) — ставит в соответствие имя файловой переменной имени внешнего файла, которое задается в строковой переменной или константе.

Процедура rеset(файловая переменная) — открывает существующий файл на чтение.

Процедура rewritе(файловая переменная) — открывает файл на запись.

Процедура append(файловая переменная) — открывает существующий (!!!) файл для дописывания — записи информации после уже имеющейся.

Процедура close(файловая переменная) — закрывает открытый файл. Функция eоf(файловая переменная):boolean — проверяет, достигнут ли при чтении из файла конец файла (end-of-file).

Функция eoln(файловая переменная):boolean — проверяет, достигнут ли при чтении из текстового файла конец строки (end-of-line).

Функция

SeekEof(файловая переменная):boolean

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

Функция SeekEoln(файловая переменная):boolean — проверяет, достигнут ли при чтении из файла конец строки, пропуская при этом пробелы и символы табуляции.

Процедура read — считывает одно или более значений из файла в одну или более переменных.

Процедура readln — выполняет те же действия, что и процедура read, а затем делает пропуск до начала следующей строки текстового файла.

Процедура write — записывает в файл одно или более значений.

Процедура writeln — выполняет те же функции, что процедура write, а затем добавляет к файлу метку конца строки (один или два символа).

Ввод и вывод данных с использованием текстовых файлов

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

while not seekeof(f) do

begin

n := 0;
s := 0;
while not seekeoln(f) do

begin

read(f,a);
s := s + a;
n := n + 1

end;

readln(f);

if n > 0 then writeln(s/n:0:2) else writeln

end;

Заметим, что обычно применяемые в таких случаях функции eof и eoln заменены на seekeof и seekeoln соответственно. Только при показанном способе ввода чисел не возникают ошибки в работе подобной программы, связанные с наличием пробелов в конце строк и пустых строк в конце файла, так как для корректного использования функции eof требуется, чтобы признак конца файла стоял непосредственно после последнего числа в файле. То же требование относится к признаку конца строки при использовании функции eoln. Отметим, что техническую проблему, связанную с обработкой заранее неизвестного количества чисел в строке или в файле в целом, разрешить на языке программирования Си несколько сложнее. Там приходится проверять корректность завершения очередного обращения к функции scanf.

Наоборот, если во входном файле находится текст, размер которого неизвестен, то поступать следует несколько по-другому. Использование seekeoln может привести к ошибке, так как в тексте пробел уже является значимым символом. С другой стороны, служебные символы, обозначающие конец строки в файле и перевод на новую строку в Windows (их коды 13 и 10), не могут считаться частью текста и не должны анализироваться алгоритмом его обработки. Поэтому, если известно, что длина каждой строки текстового файла не превосходит 255 символов (при использовании директивы компилятора {$H+} в языке Delphi это ограничение снимается), то удобнее всего считывание производить с использованием переменной типа string:

while not eof(f) do

begin

readln(f, s);
if s <> '' then... {обработать строку s}

end;

В этом примере использование readln, а не read является принципиальным. Если же ограничения на количество символов в одной строке нет, то считывание данных на языке Borland Pascal следует производить посимвольно. Пример посимвольного считывания текста из файла:

while not eof(f) do

begin

n := 0;
s := 0;

while not eoln(f) do

begin

read(f, с);
…{запись символа с в массив или его обработка}
n := n + 1

end;

readln(f);{!!!}

if n > 0 then …{обработка строки} else …{строка пустая}

end;

Именно использование оператора readln позволяет и в данном случае автоматически исключить из рассмотрения символы перевода строки.

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

При решении таких задач удобно (но не обязательно!) использовать переменные типа record (запись). Структура записи содержит фиксированное число компонент, называемых полями. В отличие от массивов компоненты не обязательно одного типа и непосредственно индексировать их нельзя. Область действия имени поля — запись, в которой оно определяется. Имена полей можно использовать в качестве имен других переменных вне записи. Все имена полей должны быть различными.

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

var

person: record

S: string;
n: integer;
c: char

end;

Описание записи начинается со слова record и заканчивается словом end.

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

while not seekeof(f) do

begin

read(f, c);{вспомогательный символ}
person.S := '';
{формируем строку с фамилией}

while c <> ' ' do

begin

person.S := person.S + c;
read(f, с)

end;

read(f, person.n);{считываем год рождения}
readln(f, c, c);{считываем пол}
person.c := c;
…{обработка считанной информации}

end;

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

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

Задачи

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

1234 кукла 137.50 5 12

Запросите с клавиатуры возраст ребенка и сумму денег, которую покупатель может потратить на покупку. Запишите в файл g.txt следующую информацию: названия и цену игрушек, которые подходят детям указанного возраста, а цена каждой из них не превышает сумму денег, указанную пользователем.

2. Сведения об ученике, записанные в файле f.txt, состоят из его фамилии и названия класса (год обучения и буква), а также оценок, полученных за четверть. Число оценок в разных классах может быть разным. Запишите в файл g.txt фамилии тех учеников, которые не имеют двоек и троек, а их средний балл больше, чем 4,5.

3. Дан файл f.txt, содержащий некоторый текст. Требуется подсчитать количество строк со словами (непробельными символами, отличными от пробелов, разделенными пробелами или символами перевода строки), а также количество слов в этом тексте. Результат выдайте в файл g.txt.

4. Даны два файла: f1.txt и f2.txt. Файл f1.txt — инвентаризационный файл, содержащий сведения о том, сколько изделий каких видов продукции хранится на складе. Файл f2.txt — вспомогательный файл, содержащий сведения о том, на сколько уменьшилось или увеличилось количество изделий по некоторым видам продукции. f2.txt может содержать несколько сообщений по продукции одного вида или не содержать ни одного такого сообщения о некоторых видах продукции. Обновите f1.txt на основе f2.txt. Запросы, содержащиеся в этом файле, обрабатываются последовательно. Если какого-то товара на базе первоначально не было, то запрос просто игнорируется, даже если такой товар на базу “возвращают”. Если же товара меньше, чем просит покупатель, то он получит лишь имеющийся товар и запрос оказывается выполнен частично (при дальнейшем возврате аналогичного товара на склад данный запрос довыполняться не будет). Если же товар изначально был, а сейчас его нет, то запрос игнорируется. Товара, который после выполнения запросов на складе отсутствует, в обновленном файле также быть не должно.

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

5. В файле f.txtсодержится запись клиентов на стрижку по формату:

<фамилия> <название стрижки>

В файле g.txt для каждого из мастеров парикмахерской записано, сколько минут он делает ту или иную стрижку по формату

<фамилия> <название стрижки> <время>

<название стрижки> <время> …

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

<фамилия> HH:MM

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

6. В файле f.txt записаны команды, которые поступали в автоматизированную систему управления лифтом.

Команды бывают двух типов: внешние (вызов лифта) и внутренние (нажатие кнопок внутри кабины). Внешние команды имеют формат

<номер этажа><пробел><U или D>,

а внутренние — или <номер этажа>, или U, или D. Буквы U и  D обозначают направление поездки вверх или вниз. Внутренняя команда U обозначает поездку на последний этаж, а  D — на первый. Каждая команда находится в отдельной строке. Известно, что в здании 28 этажей, а каждая новая команда поступает в устройство управления только если предыдущая команда уже выполнена.

Запишите в файл g.txt последовательность этажей, на которых останавливался лифт.

7. Во входном файле meteo.dat находятся 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен.

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

<номер месяца> <среднемесячная температура>

<отклонение от среднегодовой>

Средние значения выводить с точностью до одного знака после десятичной точки.

Массив для хранения всех введенных значений не использовать.

8. Даны 2 текстовых файла: f1.txt и f2.txt. В каждом из файлов находится неотрицательное количество целых чисел, отсортированных по неубыванию. Каждое из чисел по модулю не превосходит 10⁶. Числа разделены между собой пробелами и/или символами перевода строки. Получите новый текстовый файл output.txt слиянием двух исходных в отсортированном виде.

Пример работы программы:

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

В синтаксически верной программе ключевое слово оператора перехода goto может стоять или в начале строки, или после пробела, или после одного из символов — ‘;’ , ‘:’, ‘}’, а после него может стоять или пробел, или перевод строки, или символ ‘{’.

Напомним, что, кроме обозначения действительно оператора перехода, слово goto может встречаться в тексте программы в строковых константах, заключенных в апострофы, или в комментариях, причем для простоты будем считать, что комментарий всегда начинается с символа ‘{’, а заканчивается первым встретившимся после этого символом ‘}’. Будем считать, что это единственный вид комментариев. В этих случаях слово goto подсчитывать не нужно. Строчные и прописные буквы в Pascal не различимы.

Во входном файле goto.in находится текст программы на языке Pascal без синтаксических ошибок. Размер программы не превосходит 64 Кб. В выходном файле goto.out должно оказаться одно число — количество операторов goto в этой программе.

10. Дан текстовый файл f.txt. В каждой строке имеется по крайней мере два слова, разделенных как минимум одним пробелом. За счет изменения количества пробелов между словами добейтесь того, чтобы пробелы в начале и в конце каждой строки отсутствовали. Количество пробелов между словами должно отличаться не более чем на один (см. задачу 7 к уроку 11). Количество символов в каждой строке должно равняться количеству символов в самой длинной строке файла. Результат работы запишите в файл g.txt.

Послесловие

Представленный вашему вниманию задачник, снабженный теоретическим и практическим материалами по языку Pascal, фактически может рассматриваться как учебник по программированию в школьном курсе информатики. Дополнить его можно отдельно сгруппированными задачами по теме “Сортировка массивов” и задачами на системы счисления. Их можно взять из материалов курса повышения квалификации “Методика преподавания программирования на уроках информатики”.

---

¹ Подробнее о представлении чисел в компьютере можно прочитать, например, в книге Е.Андреевой, И.Фалиной “Системы счисления и компьютерная арифметика”. М.: БИНОМ. Лаборатория знаний, 2004.

² В сутках 86 400 секунд.

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

⁴ См., например, книгу Е.В. Андреевой, Л.Л. Босовой, И.Н. Фалиной “Математические основы информатики”. М.: Бином, 2007.

⁵ Эта задача имеет и математическое решение: можно вывести формулу, дающую ответ на поставленную задачу.

⁶ Решение этой задачи см. в брошюре Я.Н. Зайдельмана “Эффективность алгоритмов. Простые задачи и наглядные примеры”. М.: Библиотечка “Первого сентября”.

⁷ Эта задача эквивалентна следующей: поменять первые n – k элементов с последними k элементами. Ее решение см., например, в книге А.Шеня “Программирование. Теоремы и задачи”. М.: МЦНМО, 2005.

⁸ Это справедливо не для всех языков программирования. Например, в Фортране элементы двумерных массивов располагаются в памяти “по столбцам”.