Введение
Данное методическое пособие посвящено лабораторным работам по курсу «Программирование». Его содержание разбито на три части. В первой части сосредоточена информация о принципах разработки программ, алгоритмизации и среде программирования. Вторую часть составляют описания тем и задания лабораторных работ. И, наконец, заключительная часть посвящена стилю кодирования, обзору наиболее популярных ошибок и отладке, как средству для их ликвидации.
В конце каждого раздела, посвященного непосредственно той или иной лабораторной работе, помещен типичный пример задания с его решением и список из тридцати заданий, которые взяты (некоторые с изменениями) из [1].
Пособие ориентировано на Turbo Pascal Version 7.0 (Copyright (c) 1983, 92 by Borland International, Inc.) и везде далее, где так или иначе встречаются термины Borland Pascal, Pascal, и другие ссылки на язык, нужно иметь в виду, что речь идет именной об этой версии языка.
Принципы разработки программ
Понятие жизненного цикла программных изделий
В основе деятельности по созданию и использованию программного обеспечения лежит понятие жизненного цикла, который является моделью создания и использования программного обеспечения, отражающей его различные состояния, начиная с момента возникновения необходимости в данном программном изделии и заканчивая моментом его полного выхода из употребления у пользователей. Для каждого конкретного программного изделия количество, состав и последовательность этапов жизненного цикла определяется на ранних стадиях его создания. Непосредственный выбор определяется различными ограничениями и особенностями предметной области. В рамках настоящих лабораторных работ выделяются:
- этап постановки задачи, на котором необходимо сформировать представление о том, в создании какого вычислительного процесса, с использованием каких данных состоит цель работы;
- этап проектирования, в рамках которого необходимо принять решение о составе данных и их типах и представить вычислительный процесс в терминах граф-схемы алгоритма;
- этап кодирования, на котором необходимо отобразить данные в соответствующих разделах программы и представить алгоритм в виде операторов языка программирования;
- этап тестирования и отладки, в рамках которого предполагается использование средств отладки программной среды для локализации ошибок в коде.
Понятие алгоритма
Под алгоритмом, как правило, понимается точное предписание, которое задает вычислительный процесс, начинающийся из некоторой совокупности исходных данных и направленный на получение полностью определяемого исходными данными результата. Обосновывать принципы алгоритмизации целесообразно в рамках анализа свойств алгоритмов. Выделяют следующие свойства алгоритмов.
1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.
2. Детерминированность – свойство, означающее, что на каждом шаге любой полученный результат определяется результатами, полученными на предшествующих шагах.
3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.
4. Направленность – свойство, обуславливающее необходимость указания, что является результатом того шага, на котором нельзя выполнить определенную в нем операцию.
5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.
Одной и той же задаче может соответствовать множество алгоритмов, поэтому, для обоснования выбора одного из них для решения конкретной задачи, применяют совокупность показателей, основными из которых являются следующие.
1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.
2. Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.
3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.
Для представления алгоритма используют различные средства, в том числе граф-схемы алгоритмов, каждая из которых представляет собой граф. Понятие элементарного графа дополнено введением надстройки, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных. В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».
Таблица 1
| Символ | название | интерпретация |
| данные | данные, носитель данных неопределен |
| процесс | функция обработки данных любого вида (выполнение определенной операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться) |
| предопределенный процесс | предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле) | |
 
| Подготовка | модификация команды или группы команд с целью воздействия на некоторую последующую функцию |
| Решение | решение или функция переключательного типа, имеющая один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа; соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути |
 
| граница цикла | начало и конец цикла; обе части имеют один и тот же идентификатор; условия инициализации, приращения, завершения, и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие |
| соединитель | выход в часть схемы и вход из другой части этой схемы; используется для обрыва линии и продолжения ее в другом месте; соответствующие символы-соединители должны содержать одно и то же уникальное обозначение |
| терминатор | выход во внешнюю среду и вход из внешней среды (начало и конец программы) |
| линия | поток данных или управления; для направлений справа-налево и снизу-вверх добавляются стрелки |
| пунктирная линия | используется для обведения аннотируемого участка |
| комментарий | пояснительные записи и примечания |
| пропуск | пропуск символа или группы символов, в которых не определены ни тип, ни число символов; используется только в символах линии или между ними; служит для отображения общих решений с неизвестным числом повторений |
Приведем основные свойства граф-схем.
1. Графическое представление.
2. Поддержка описания управляющей части алгоритма.
3. Возможность реализации синтаксического контроля.
4. Возможность проверки управляющей части алгоритма.
5. Отсутствие возможности верификации информационной части.
Необходимо отметить, что по граф-схеме алгоритма можно произвести оценку таких характеристик алгоритма, как временная сложность и сложность описания, однако, возможность оценки емкостной сложности отсутствует. На рис. 1 представлен пример граф-схемы алгоритма.
Среда программирования
Borland Pascal представляет собой интегрированную среду программирования. Термин «интегрированная» используется для указания того, что данная система организована как совокупность компонент, каждая из которых предназначена для решения отдельной задачи в рамках жизненного цикла программы. Такими компонентами являются: текстовый редактор, компилятор, загрузчик, исполняющая система и отладчик. Компоненте «отладчик» посвящен отдельный раздел, а в данном будут рассмотрены остальные компоненты, с помощью которых решаются две основные задачи: создание и редактирование кода и его компиляция и выполнение.
На рис.2 изображено главное окно системы. Управление поведением системы осуществляется посредством меню, активизация которого осуществляется мышью или функциональной клавишей <F10>. Команды главного меню являются составными, то есть активизация любой из них приводит к появлению подменю, которое содержит конкретизацию назначения команды главного меню.
Рис.2. Главное окно среды Turbo Pascal.
Создание и редактирование текста программы
Для создания новой программы необходимо через пункт главного меню «File» получить и активизировать пункт «New» соответствующего ему подменю. При этом происходит активизация редактора, признаком которой является цветовое выделение рамки окна и наличие в нем курсора. Набранный текст программы содержится во временном файле, создаваемом системно, а для его сохранения на диске необходимо воспользоваться командой «Save» (<F2>). В появившимся в результате активизации этой команды окне необходимо указать имя и местоположение созданного файла. Содержимое ранее созданного файла с помощью команды «Open» подменю «File» можно открыть в окне текстового редактора для внесения изменений. При редактировании удобно пользоваться командами подменю «Edit» или «горячими клавишами», обеспечивающими удобство использования стандартных операций редактирования.
Компиляция и выполнение программы
Вся работа по созданию или редактированию файла в окне текстового редактора производится с временной копией файла. Для компиляции кода, который содержится в этой копии, используется команда «Compile» подменю «Compile» (<Alt>+<F9>). При этом в случае наличия в коде ошибок, произойдет активизация текстового редактора, и курсор будет установлен в позицию, в которой транслятор зафиксировал ошибку, а в верхней части окна будет содержаться сообщение об ошибке. В противном случае, в зависимости от настроек, система создаст временный исполняемый модуль и выдаст специальное окно, сигнализирующее об отсутствии синтаксических ошибок в коде. Для создания не временного исполняемого файла используется команда «Make» подменю «Compile». Запуск исполняемого файла осуществляется командой «Run» подменю «Run» или комбинацией клавиш <Сtrl>+<F9>. При этом, сначала транслятор производит контроль ошибок, в случае отсутствия которых компилятор создаст исполняемый модуль, запуск которого будет осуществлен исполняющей системой.
Лабораторные работы
В данной главе сосредоточены необходимые сведения для выполнения каждой из лабораторных работ, примеры типичных заданий и их решения и, наконец, списки заданий.
Итерационные вычисления
Реализация итерационных вычислительных процессов может быть основана на использовании оператора перехода или операторов цикла.
Оператор перехода
Оператор перехода осуществляет передачу управления в некоторую точку программы, таким образом, управление получает фактический или пустой оператор, имеющий соответствующую метку. Данный оператор универсален в том смысле, что на его основе может быть осуществлена реализация любого итерационного процесса. Синтаксическая схема оператора перехода имеет следующий вид:
<оператор перехода>::= goto <метка>
В качестве примера рассмотрим фрагмент программы, связанный с выводом чисел, соответствующим степеням числа 3 из диапазона [3, n]. Данный итерационный процесс с помощью оператора перехода мог бы быть реализован одним из следующих образов
(1)
...
GradeOfThree:= 3;
1: if GradeOfThree<= n then
begin
write (GradeOfThree);
GradeOfThree:= GradeOfThree * 3;
goto 1
end
...
(2)
...
GradeOfThree:= 3;
if n>= 3 then
begin
1: write (GradeOfThree);
GradeOfThree:= GradeOfThree * 3;
if GradeOfThree<= n then goto 1
end
...
Необходимо отметить существование следующих ограничений на использование оператора перехода:
1) запрещается переход внутрь любого производного оператора;
2) запрещается переход с одной альтернативы на другую в выбирающем операторе.
Несмотря на простоту и универсальность реализации итерационных вычислений оператором перехода его использования следует избегать, так как потенциально, использование конструкций передачи управления в любую точку программы усложняет ее интерпретацию человеком, что может привести к ошибкам. Поэтому в рамках структурного программирования данный оператор, как правило, не используется, что и позволяет говорить о таких плюсах структурного программирования, как увеличение надежности и легкости сопровождения, упрощение модификации программных изделий. Сам структурный подход основан на применении следующих правил:
1) программа должна составляться последовательными шагами;
2) сложные задачи делятся на простые, каждая из которых имеет один вход и один выход;
3) логика программы должна базироваться на минимальное число базовых управляющих структур.
При этом для реализации итерационных процессов в рамках структурного программирования, в соответствии с п.3 сформированы специальные управляющие структуры - три оператора цикла.
Операторы цикла
Оператор цикла с предусловием
Синтаксис данного оператора имеет следующий вид:
<оператор цикла с предусловием>::= while <логическое выражение> do <оператор>
Итерационный процесс, задаваемый следующим фрагментом кода на базе оператора перехода
...
1: if not (P) then goto 2
S; goto 1;
2:;
...
Может быть реализован на базе оператора цикла с предусловием следующим образом
...
while P do S
...
Данный оператор задает итерационный процесс, обладающий двумя свойствами:
1) в зависимости от условия процесс может не выполниться вообще;
2) количество итераций процесса заранее не известно, зависит также от условия.
Для реализации конечного итерационного процесса, в теле цикла должны присутствовать операторы, изменяющие значение переменных, входящих в условие.
Попытаемся реализовать пример со степенями числа три на базе оператора цикла с предусловием. Такая реализация будет по смыслу близка к варианту 1) в примере с оператором перехода:
...
GradeOfThree:= 3;
while GradeOfThree<= n do
begin
write (GradeOfThree);
GradeOfThree:= GradeOfThree * 3
end
...
Оператор цикла с постусловием
Оператор цикла с постусловием является частным случаем оператора цикла с предусловием и отличается от него тем, что процесс, задаваемый под управлением данного оператора, выполнится хотя бы один раз. Реализуется это путем осуществления проверки на необходимость продолжения в конце тела цикла. Поэтому для реализации процесса, задаваемого оператором
while P do S
с помощью оператора цикла с предусловием требуется дополнительный условный оператор:
if P then
repeat S until not P
Синтаксис данного оператора имеет следующий вид:
<оператор цикла с постусловием>::= repeat <оператор> until <логическое выражение>
Необходимо также обратить внимание на то, что условием выхода из цикла с предусловием является ложность, тогда как условием выхода из цикла с постусловием является истинность значения предиката.
Реализация примера со степенями числа три на базе оператора цикла с постусловием по смыслу более близка к варианту 2) в примере с оператором перехода:
...
GradeOfThree:= 3;
if n>= GradeOfThree then
repeat
write (GradeOfThree);
GradeOfThree:= GradeOfThree * 3
until GradeOfThree> n
...
Анализ реализаций данного процесса на базе операторов цикла с пред- и постусловиями приводит к выводу о том, что применение оператора while в данном случае оптимальнее по показателю сложности алгоритма, которая связана с дополнительным условным оператором, который появляется в примере с оператором цикла с постусловием. Это также очевидно для варианта 2) примера с оператором перехода и связано с тем, что значение n не определено. Наоборот, если бы имелась гарантия того, что n заведомо >= 3, то реализация данного итерационного процесса на базе цикла с постусловием, но уже без условного оператора, была бы предпочтительней. Это является хорошей иллюстрацией того, что цикл с постусловием реализует частный случай цикла с предусловием.
Оператор цикла с параметром
С помощью данного оператора осуществляется дальнейшая конкретизация итерационного процесса, которая связана с тем, что до начала цикла число его итераций известно. Тогда каждая итерация будет связана с приращением (или уменьшением) параметра - переменной порядкового типа - в рамках, устанавливаемых границами цикла - выражениями того же типа, что и параметр. Приведем синтаксис данного оператора.
<оператор цикла с параметром>::= for <параметр>:= <нижняя граница> to <верхняя граница> do <оператор> | for <параметр>:= <верхняя граница> downto <нижняя граница> do <оператор>
Необходимо обратить внимание на два обстоятельства:
1) значение параметра цикла по нормальном его завершении не определено;
2) значение параметра цикла не должно изменяться в процессе выполнения операторов тела цикла.
Первая позиция связана с тем, что в различных реализациях соотнесение параметра с граничным значением происходит в различные моменты - до или после очередного его приращения (уменьшения). Сам параметр может как использоваться, так и не использоваться в операторах тела цикла, однако, изменяться ими он не должен.
Ниже представлена реализация вычислительных процессов, задаваемых циклами с постусловием и предусловием, циклом с параметром.
1) цикл с предусловием
Parametr:= LowPoint;
while Parametr<= LowPoint do
begin
S;
Parametr:= Succ (Parametr)
end
2) цикл с постусловием
if HightPoint>= LowPoint then
begin
Parametr:= LowPoint;
repeat
S;
Parametr:= Succ (Parametr)
until Parametr> HightPoint
end
3) соответствующий им цикл с параметром
for Parametr:= LowPoint to HightPoint do S
Наличие трех управляющих конструкций для реализации итерационных процессов обуславливается, с точки зрения структурного программирования, необходимостью представления различных по степени детерминированности процессов, соответствующими средствами. Три цикла направлены на реализацию трех типов итерационных процессов:
1) процесс, число повторений которого заранее известно;
2) процесс, который выполнится хотя бы один раз;
3) процесс, число повторений которого заранее не известно.
Необходимо также отметить наличие стандартных процедур Break и Continue, которые позволяют управлять итерациями циклов. При этом Break завершает оператор цикла, а Continue продолжает его со следующей итерации.
В рамках повышения эффективности вычислительных процессов, создаваемых на базе циклических структур применяют различные преобразования, основными из которых являются следующие:
1) Исключение инвариантных выражений. Основополагающий принцип - вынесение возможно большего числа операций за границы цикла.
for i:= 1 to 1000 do e:= b * c;
for j:= 1 to 1000 do => for i:= 1 to 1000
a:= b * c + d(i, j) for j:= 1 to 1000
a:= e + d(i, j)
2) Сжатие циклов. Основной принцип - объединение тел двух циклов с одинаковыми параметрами.
for i:= 1 to 1000 do for i:= 1 to 1000 do begin
a(i):= i; => a(i):= i;
for j:= 1 to 1000 do b(j):= 10 * j
b(j):= 10 * j end
3) Разъединение циклов. Бывает полезно в случаях, подобных следующему:
{условный оператор выполняется 1000 {условный оператор
выполняется
раз, хотя логическая переменная c не 1 раз}
изменяется} if c then
for i:= 1 to 1000 do => for i:= 1 to 1000 do
if c then b(i):= a(i) + b(i) b(i):= a(i) + b(i)
else b(i):= a(i) – b(i) else
for i:= 1 to 1000 do
b(i):= a(i)–b(i)
Пример использования операторов цикла
Разберем решение типичной задачи, связанной с итерационными вычислениями.
Текст задания
Пусть необходимо определить k – количество трехзначных натуральных чисел, сумма цифр которых равна n (1 <= n <= 27). При этом операции деления (/, div, mod) не использовать.
Решение
Организуем три цикла – по одному на каждую из цифр числа. Задача – перебрать все возможные комбинации из трех цифр. Каждая цифра может принимать значение от 0 до 9 – ти, что позволяет в качестве управляющих конструкций для организации трех итерационных процессов воспользоваться циклом с параметром. Будем складывать счетчики этих циклов и сравнивать с заранее введенным n. В случае равенства, будем инкриминировать счетчик k – количества трехзначных чисел.
program CycleSample;
var
n, k, Digit1, Digit2, Digit3: Integer;
begin
writeln(‘Введите n’);
repeat
readln(n);
until (n>= 1) and (n<= 27);
k:= 0;
for Digit1:= 1 to 9 do {цикл по 1-ой цифре числа}
for Digit2:= 0 to 9 do {цикл по 2-ой цифре числа}
for Digit3:= 0 to 9 do {цикл по 3-ей цифре числа}
if Digit1 + Digit2 + Digit3= n then k:= k + 1;
writeln(‘Результат - ’, k);
end.
На рис. 1 изображена граф-схема алгоритма данной задачи.
 |
Рис.1. Граф-схема алгоритма.
Варианты заданий
1. Дано 20 целых чисел. Определить, сколько из них принимает наибольшее значение.
2. Дано натуральное k. Вывести k-ую цифру последовательности 1123581321…, в которой выписаны подряд все числа Фибоначчи.
3. Дана последовательность из не менее чем 2-х натуральных чисел, за которой следует 0. Вычислить сумму тех из них, порядковые номера которых - простые числа.
4. Дано натуральное k. Вывести k-ую цифру последовательности 149162536…, в которой выписаны подряд квадраты всех натуральных чисел.
5. Дана непустая последовательность из натуральных чисел, за которой следует 0. Вычислить сумму тех из них, порядковые номера которых - числа Фибоначчи.
6. Вывести все простые делители заданного натурального числа.
7. Дано целое n>2. Вывести все простые числа из диапазона [2,n].
8. Дано 10 натуральных чисел. Найти их наибольший общий делитель.
9. Определить, является ли заданное натуральное число совершенным, т.е. Равным сумме всех своих (положительных) делителей, кроме самого этого числа (напр. Число 6 совершенно: 6=1+2+3).
10. Дана непустая последовательность ненулевых чисел, за которой следует 0. Определить, сколько раз в этой последовательности меняется знак (напр., в последовательности 1, -34, 8, 14, -5 знак меняется 3 раза).
11. Дано 20 вещественных чисел. Определить, сколько из них больше своих "соседей", т.е. Предыдущего и последующего чисел.
12. Дано не менее 3-х различных натуральных чисел, за которыми следует 0. Определить 3 наибольших числа среди них.
13. Определить число, получаемое выписыванием в обратном порядке цифр заданного натурального числа.
14. Дана последовательность из 20 целых чисел. Определить количество чисел в наиболее длинной подпоследовательности из подряд идущих нулей.
15. Дано 20 вещественных чисел. Найти порядковый номер того из них, которое наиболее близко к какому-нибудь целому числу.
16. Вывести в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр (операции деления не использовать).
17. Дано 10 вещественных чисел. Вычислить разность между максимальным и минимальным из них.
18. Дано натуральное k. Вывести k-ую цифру последовательности 12345678910111213…, в которой выписаны подряд все натуральные числа.
19. Дана последовательность из 20-ти целых чисел. Определить, со скольких отрицательных чисел она начинается.
20. Определить, является ли заданное натуральное число палиндромом, т.е. Таким, десятичная запись которого читается одинаково слева направо и справа на лево.
21. Дано 20 вещественных чисел. Определить, образуют ли они возрастающую последовательность.
22. Даны целое n>0 и последовательность из n вещественных чисел, среди которых есть хотя бы одно отрицательное число. Найти величину наибольшего среди отрицательных чисел этой последовательности.
23. Найти сумму цифр заданного натурального числа.
24. Дана непустая последовательность различных натуральных чисел, за которой следует 0. Определить порядковый номер наименьшего из них.
25. Дано 20 вещественных чисел. Вычислить разность между максимальным и минимальным из них.
26. Логической переменной t присвоить значение true или false. в зависимости от того, можно или нет натуральное число n представить в виде суммы трех полных квадратов.
27. Логической переменной p присвоить значение true, если целое n (n > 1) – простое число, и значение false иначе.
28. Подсчитать k – количество цифр в десятичной записи целого неотрицательного числа n.
29. Логической переменной t присвоить значение true или false, в зависимости от того, является ли заданное натуральное число k степенью 3 или нет.
30. Вычислить: y= sin1 + sin1.1 + sin1.2 + …+ sin2.
Регулярные структуры данных
Регулярные структуры данных представляют собой конструкции, позволяющие объединять набор элементов одинакового типа в структуру. Для организации такой структуры необходимо задать тип элементов, размерность структуры и границы по каждому измерению. Идентификация такой структуры приведет к появлению так называемой полной переменной - переменной не скалярного, а производного типа. Для переменных такого типа, помимо операции присваивания однотипных значений, операции и функции не определены. Действию, обратному организации регулярной структуры, является селектирование, которое состоит в позиционировании на конкретный элемент структуры. Оно состоит в указании индексов элемента и приводит к появлению частичной переменной. Для этой переменной определены операции в соответствии с ее типом. Значения индекса должны образовывать конечное множество упорядоченных значений, поэтому, в качестве индексов могут использоваться все порядковые типы, за исключением длинного целого и поддиапазонов длинного целого. Массив хранится в виде непрерывной последовательности переменных, каждая из которых имеет тип массива. Элементы с наименьшими индексами хранятся в младших адресах памяти. Многомерный массив хранится таким образом, что правый индекс возрастает быстрее.
Векторы
Векторы представляют собой одномерные регулярные структуры.
Типичной задачей является упорядочение - сортировка - элементов вектора. Ниже представлена так называемая обменная сортировка.
...
for Index1:= 1 to HightPoint - 1 do
begin
Minimum:= Vector [ Index1 ];
Location:= Index1;
for Index2:= Index1 + 1 to HightPoint do
begin
if Minimum> Vector [ Index2 ] then
begin
Minimum:= Vector [ Index2 ];
Location:= Index2
end
Vector [ Location ]:= Vector [ Index1 ];
Vector [Index1 ]:= Minimum
end
...
Каждый элемент вектора (и регулярной структуры вообще) имеет два атрибута - значение собственно элемента и индекс элемента.
Часто при организации вычислительного процесса для обработки векторов наиболее подходящими управляющими структурами оказываются циклы с параметром. Это коррелируется со свойствами индекса вектора - его значения образуют упорядоченное конечное множество.
Разберем решение типичной задачи, связанной с обработкой векторов.
Текст задания
Даны следующие описания:
const n= 500;
var x: array [ 1..n ] of Integer;
p: Integer;
k: 0..n;
Элемента массива x упорядочены по возрастанию. Требуется присвоить переменной k номер элемента массива x, равного числу p, или 0, если такого элемента нет. Использовать следующий метод двоичного (бинарного) поиска: сравнить p со средним элементом массива (или элементом около середины); если эти числа равны, поиск завершается, если же p меньше среднего элемента, то p надо искать в левой половине массива, а иначе – в правой; к выбранной половине применяется тот же алгоритм.
Решение
program VectorSample;
const
n= 500;
var
x: array [ 1..n ] of Integer;
p: Integer;
k, t, m, r: 0..n;
begin
writeln('Введите p');
readln(p);
for k:= 1 to n do x[ k ]:= k;
k:= 0;
t:= 1; {левая граница отрезка}
r:= n; {правая граница отрезка}
{поиск p среди x [t..r]}
repeat
m:= (t + r) div 2; {середина отрезка t..r}
if x[ m ]= p then k:= m else
{замена t..r на m + t..r или t..m - 1}
if p > x[ m ] then t:= m + 1 else r:= m - 1
until (k <> 0) or (t > r);
for t:= 1 to n do write(x[ t ]: 5);
writeln;
writeln('Результат - ', k)
end.
Варианты заданий
1. const n = 1000; var s: packed array [1..n] of char; Вывести те элементы массива s, индексы которых являются числами Фибоначчи (1, 2, 3, 5, 8, …).
2. Дан текст из 80 литер. Вывести сначала все цифры, входящие в него, а затем все остальные литеры, сохраняя при этом взаимное расположение литер в каждой из этих двух групп.
3. const n = 100; var x: array [1..n] of real; преобразовать массив x по следующему правилу (x'k- значение k-того элемента массива после преобразования): x'k= max xiпри 1 <= i <= k.
4. const n = 1000; var s: packed array [1..n] of char; Вывести те элементы массива s, индексы которых являются полными квадратами (1, 4, 9, 16, …).
5. const n = 100; var x: array [1..n] of real; преобразовать массив x по следующему правилу (x' k- значение k-того элемента массива после преобразования): элементы массива циклически сдвинуть на одну позицию влево: x'n= x1, x'k= xk+1, при k = 1, 2, …, n-1.
6. var x, y: array [1..70] of real; k: 1..69; Воспользовавшись массивом y как вспомогательным, элементы массива x циклически сдвинуть на k позиций влево.
7. Даны координаты n точек на плоскости: x1, y1, …, xn, yn(n = 20). Найти номера двух точек, расстояние между которыми наибольшее (считать, что такая пара точек единственная).
8. Даны две последовательности по 30 целых чисел в каждой. Найти наименьшее среди тех чисел первой последовательности, которые не входят во вторую последовательность (считая, что хотя бы одно такое число есть).
9. Дана последовательность из 20 целых чисел. Определить количество инверсий в этой последовательности (т.е. Таких пар элементов, в которых большее число находится слева от меньшего: xi> x jпри i < j).
10. Дана непустая последовательность слов из строчных латинских букв; между соседними словами - запятая, за последним словом - точка. Вывести все буквы, которые входят в наибольшее количество слов этой последовательности.
11. Напечатать заданный текст из 100 литер, удалив из него повторные вхождения каждой литеры.
12. Определить, сколько различных литер входит в заданный текст, содержащий более 100 литер и оканчивающийся точкой (сама точка в текст не входит).
13. Дан текст из строчных латинских букв, за которым следует точка. Вывести в алфавитном порядке все буквы, которые входят в этот текст по одному разу.
14. const n = 1000; var s: packed array [1..n] of char; Вывести те элементы массива s, индексы которых являются степенями двойки (1, 2, 4, 8,...).
15. Дан непустой текст из цифр, за которыми следует точка. Напечатать цифру, наиболее часто встречающуюся в этом тексте.
16. Дано 100 вещественных чисел. Распечатать их в обратном порядке по 6 чисел в строке.
17. Дан текст, содержащий от 1 до 70 букв, за которым следует точка. Вывести текст в обратном порядке.
18. const n = 100; var x: array [1..n] of real; элемента массива расположить в обратном порядке.
19. const n = 100; var x: array [1..n] of real; преобразовать массив x по следующему правилу (x'k- значение k-того элемента массива после преобразования): x'1= x 1, x'n= xn, x'k= (xk-1+ xk+ xk+1)/3 при k = 2, 3, … n-1.
20. Дан текст из 80 литер. Определить, симметричен ли он, т.е. читается ли он одинаково слева направо и справа налево.
21. const n = 100; var x: array [1..n] of real; элементы массива циклически сдвинуть на две позиции влево.
22. var x, y: array [1..70] of real; k: 1..69; Воспользовавшись массивом y как вспомогательным, все отрицательные элементы массива x перенести в начало, а все остальные - в конец, сохраняя при этом исходное взаимное расположение, как среди отрицательных, так и среди остальных элементов.
23. Дана последовательность из 100 различных целых чисел. Найти сумму чисел этой последовательности, расположенных между максимальным и минимальным числами (в сумму включить оба этих числа).
24. По заданным коэффициентам многочлена 15-й степени и многочлена 8-й степени определить произведения этих многочленов.
25. По заданным коэффициентам многочлена P(x) 10-й степени и многочлена Q(x) 6-й степени определить коэффициенты многочлена P(Q(x)).
26. const n = 100; var x: array [1..n] of real; Упорядочить массив x по неубыванию (т.е. переставить его элементы так, чтобы выполнялось xk<= xk+1), используя метод сортировки выбором: отыскивается максимальный элемент и переносится в конец массива; затем этот метод применяется ко всем элементам, кроме последнего (он уже находится на своем окончательном месте), и т.д.
27. const n = 100; var x: array [1..n] of real; Упорядочить массив x по неубыванию (т.е. переставить его элементы так, чтобы выполнялось xk<= xk+1), используя метод сортировки обменом: последовательно сравниваются пары соседних элементов xkи xk+1(k= 1, 2, 3, …,n-1) и, если xk> xk+1, то они переставляются; тем самым наибольший элемент окажется на своем месте в конце массива; затем этот метод применяется ко всем элементам, кроме последнего, и т.д.
28. const n = 100; var x: array [1..n] of real; Упорядочить массив x по неубыванию (т.е. переставить его элементы так, чтобы выполнялось xk<= x k+1), используя метод сортировки вставками: пусть первые k элементов массива уже упорядочены по неубыванию; берется (k + 1)-й элемент и размещается среди первых k-элементов так, чтобы упорядоченными оказались уже k+1 первых элементов; этот метод применяется при k от 1 до n – 1.
29. const n= 40; var x: array [1..n] of integer; y, k: integer; t: boolean; Переменной t присвоить значение true, если в массиве x нет нулевых элементов и при этом положительные элементы чередуются с отрицательными, и значение false иначе.
30. const n= 40; var x: array [1..n] of integer; y, k: integer; t: boolean; Переменной k присвоить либо номер первого вхождения y в массив x, либо число n + 1, если y не входит в x.
Матрицы
Матрицы представляют собой двумерные регулярные структуры. Они имеют два измерения, которым могут соответствовать различные типы индексов.
Рассмотрим для примера умножение двух матриц размера nxn
...
for Index1:= 1 to n do
for Index2:= 1 to n do
begin
Result [ Index1, Index2 ]:= 0;
for Index3:= 1 to n do
Result [ Index1, Index2 ]:= Result [ Index1, Index2 ]
+ Matrix [ Index1, Index3 ]
* Matrix [ Index3, Index2 ]
end
...
При задании итеративного процесса обработки регулярной структуры необходимо обращать внимание на счетчик итераций (или параметр для цикла с параметром), с помощью которого происходит позиционирование на очередной элемент массива - необходимо контролировать диапазон его изменения с тем, чтобы его значение не вышло за границы массива.
Разберем решение типичной задачи, связанной с обработкой матриц.
Текст задания
Дана вещественная матрица размером 20 Х 30. Упорядочить ее строки по неубыванию их первых элементов.
Решение
program MatrixSample;
const
n= 20;
m= 30;
type
Row= array [ 1..m ] of Real;
Matrix= array [ 1..n ] of Row;
var
A: Matrix;
x: Row;
i, j, k: Integer;
begin
{ввод A}
for i:= 1 to n do
for j:=1 to m do
read (A[ i, j ]);
{сортировка выбором}
for k:= n downto 2 do
begin {поиск j – номера max A[ 1..k, 1]}
j:= 1;
for i:= 2 to k do
if A[ i, 1 ] > A[ j, 1 ] then j:= i;
{перестановка k-ой и j-ой строк}
x:= A[ k ];
A[ k ]:= A[ j ];
A[ j ]:= x
end;
{вывод A}
for i:= 1 to n do
begin
writeln (i, '-я строка:');
for j:= 1 to m do
write (A[ i, j ]);
writeln
end
end.
Варианты заданий
1. Дана квадратная матрица n- ного порядка (n = 6). Найти матрицу, обратную ей, или установить, что такой не существует. (Замечание: если линейными преобразованиями строк привести заданную матрицу к единичной, то этими же преобразованиями