Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Часть ответов к билетам
10 ВЫРАЖЕНИЯ
Выражение может быть арифметическим, логическим или литерным. Важно, чтобы тип величины был согласован с видом выражения.
Арифметические выражения должны быть записаны в так называемой линейной записи согласно следующим правилам:
• выражение должно быть записано в виде линейной цепочки символов;
• используемые операции приведены в таблице:
|
НАЗВАНИЕ ОПЕРАЦИИ |
ФОРМА ЗАПИСИ |
|
сложение |
x + y |
|
вычитание |
x - y |
|
умножение |
x * y |
|
деление |
x / y |
• нельзя опускать знаки операций, например писать 5b. Для записи произведения чисел 5 и b надо писать 5*b;
• аргументы функций (sin, cos и др.) как и аргументы вспомогательных алгоритмов, записываются в круглых скобках, например sin(x), cos(4*x).
Порядок выполнения операций при вычислении арифметических выражений можно регулировать при помощи скобок по обычным правилам. Там, где скобки отсутствуют, ЭВМ выполняет операции в следующем порядке:
• вычисляет значение всех алгоритмов-функций и стандартных функций;
• выполняет справа налево все операции возведения в степень;
• выполняет слева направо все операции умножения и деления;
• выполняет слева направо все операции сложения и вычитания.
В нашем случае сначала переменной number1 присваивается значение равное 3 и переменной number2 присваивается значение равное 4, затем вычисляется значение выражения (number1 + number2) и оно присваивается переменной rezult.
Сумма чисел посчитана.
Теперь надо вывести ее значение на экран. Для этого используют оператор Write – записать (вывести) на экран значение переменной, записанной в скобках. В нашем случае значение переменной number1, затем символ + , далее значение переменной number2, символ = и, наконец, значение результата rezult.
И, наконец, в конце раздела операторов стоит служебное слово End, после которого стоит точка.
15 ОПЕРАТОРНЫЕ СКОБКИ
Операторные скобки
В Паскале под «операторными скобками» понимают два служебных слова: Begin (открывающаяся скобка) и End (закрывающаяся скобка).
13. ВВОД/ВЫВОД ДАННЫХ В ЯЗЫКЕ PASCAL
Решим задачу, прокомментировав каждое свое действие в фигурных скобках. Напомним, что комментарий не воспринимается компьютером, а нам он нужен для того, чтобы лучше понять как работает программа.
Задача. Напишите программу, которая бы очищала экран и вычисляла произведение двух чисел, вводимых пользователем.
Program Proizv2;
Uses
Crt;{Подключаем модуль Crt}
Var
number1, {переменная, в которой будет содержаться первое число}
number2, {переменная, в которой будет содержаться второе число}
rezult {переменная, в которой будет содержаться результат}
: integer;
Begin
ClrScr;{Используем процедуру очистки экрана из модуля Crt}
Write ('Введите первое число ');
{Выводим на экран символы, записанные между апострофами}
Readln (number1);
{Введенное пользователем число считываем в переменную number1}
Write ('Введите второе число ');
{Выводим на экран символы, записанные между апострофами}
Readln (number2);
{Введенное пользователем число считываем в переменную number2}
rezult := number1 * number2;
{Находим произведение введенных чисел и присваиваем переменной rezult}
Write ('Произведение чисел ', number1, ' и ', number2, ' равно ', rezult);
{Выводим на экран строчку, содержащую ответ задачи}
Readln;{Процедура задержки экрана}
End.
Чтобы лучше понять действие программы, наберите ее на компьютере и проверьте ее действие. Ответьте на вопросы:
• почему программу назвали Proizv2?
• зачем в раздел Uses поместили модуль Crt?
• какое назначение переменных number1, number2, rezult?
• какой тип у этих переменных? что это значит?
• если присвоить переменным number1 и number2 соответственно значение 5 и 7, то какую строчку выдаст компьютер при исполнении последней процедуры Write? Запишите ее в тетрадь.
• в каких строчках у пользователя запрашиваются значения переменных?
• в какой строчке происходит умножение чисел?
• что делает оператор присваивания в этой программе?
Задание. Измените программу так, чтобы она запрашивала у пользователя еще одну переменную и выводила результат произведения трех чисел.
Мы уже использовали операторы Write и WriteLn, но нам необходимо подробнее остановиться на правилах применения этих операторов.
Write (англ. писать) – оператор, который используется для вывода информации на экран. Оператор WriteLn выполняет то же самое действие, но так как у него есть еще окончание Ln (line - англ. линия, строка), то после вывода на экран нужного сообщения, он дополнительно переводит курсор на следующую строчку.
Общий вид:
Write (список выражений)
WriteLn (список выражений)
Процедуры Write и WriteLn используются не только для вывода результата, но и для вывода различных сообщений или запросов. Это позволяет вести диалог с пользователем, сообщать ему, когда ему нужно ввести значения , когда он получает результат, когда он ошибся и др.
Например, при выполнении процедуры WriteLn(‘Найденное число ‘,а), будет напечатана строчка, заключенная в апострофы, а затем выведено значение переменной а.
Оператор WriteLn можно применить и без параметров. В этом случае напечатается строка, состоящая из пробелов, и курсор будет переведен на другую строку. Это иногда нам нужно для лучшего восприятия ввода данных.
Вспомним, что основное назначение ЭВМ – сэкономить человеческий труд. Поэтому необходимо обеспечить возможность, однажды написав программу, многократно ее использовать, вводя каждый раз другие данные. Такая гибкость в языке обеспечивается операторами Read и ReadLn. Этими операторами вводится информация с клавиатуры.
Общий вид:
Read(переменная, переменная...)
ReadLn(переменная, переменная...)
При выполнении процедуры Read ожидается ввод перечисленных в скобках значений. Вводимые данные нужно отделить друг от друга пробелами. Присваивание значений идет по очереди.
Например, если вводятся значения 53 и Х, то при выполнении оператора Read(a,b) переменной а будет присвоено число 53, а переменной Х – буква Х. Причем, отметим, чтобы не было аварийной ситуации, нужно правильно определить тип данных в разделе Var; в нашем случае а:integer, а b:char.
Особых различий при чтении и записи в использовании операторов Read и ReadLn нет. Часто процедуру ReadLn без параметров применяют в конце программы для задержки: до нажатия на клавишу <Enter> результат выполнения программы остается на экране. Это очень полезно делать для анализа результатов.
Примечание. Когда Вы ставите задержку экрана, обратите внимание на предыдущий ввод. Если данные запрашивались процедурой Read задержки не будет.
Решим задачу, в которой рассмотрим все возможные употребления этих процедур.
Задача. Найти среднее значение трех чисел.
Примечание. Чтобы найти среднее значение нескольких чисел, нужно сложить эти числа и сумму разделить на количество этих чисел.
Program Srednee;
Uses
Crt;
Var
First, Second, Third : integer;
Sum : real;
Begin
ClrScr;
Write (‘Введите первое число ‘);
ReadLn(First);
Write (‘Введите второе и третье числа через пробел ‘);
ReadLn(Second, Third);
Sum := First + Second + Third;
Sum := Sum/3;
Write (‘Среднее значение ‘, First, ‘, ‘,Second, ‘ и ‘, Third, ‘ равно ‘, Sum:5:2);
ReadLn;
End.
Наберите текст задачи и внимательно рассмотрите каждую строчку. Имя программы Srednee отражает содержание задачи. Кстати, договоримся о том, чтобы имя программы и имя файла, который содержит эту программу, совпадали. Далее идет подключение модуля Crt. В разделе Var описаны First, Second, Third как переменные целого типа, а Sum – действительного типа. Раздел операторов начинается со стандартной процедуры очистки экрана ClrScr (Clear Screen), которая находится в модуле Crt. Далее оператором Write мы выводим на экран сообщение ‘Введите первое число ‘, получив которое пользователь должен ввести число. Теперь компьютер должен считать введенные символы и занести их в переменную First, это произойдет при выполнении следующего оператора ReadLn(First). Затем с помощью оператора Write запрашиваем значения еще двух чисел и считываем их в переменные Second и Third. Затем вычисляем их сумму и присваиваем полученное число переменной Sum. Чтобы найти среднее, нужно теперь полученное число разделить на 3 и сохранить результат в какой-либо переменной. Совсем не обязательно описывать еще одну переменную для сохранения результата. Можно, как в нашей программе, значение переменной Sum разделить на 3 и результат опять присвоить той же переменной Sum. Теперь можно вывести результат вычислений на экран с помощью процедуры Write. И, наконец, последняя процедура ReadLn задержит наш вывод на экране до нажатия на клавишу.
Нажмите клавиши <Ctrl>+<F9>. Введите значения переменных 5, 7 и 12, на экране увидите следующее:
Среднее значение 5, 7 и 12 равно 8.00
Просмотрите внимательно эту строчку и сравните со строчкой вывода результата в нашей программе. Протестируйте программу еще несколько раз для других значений переменных.
Выберите с учителем задачи для решения из следующего перечня:
1. Ввести два числа a и b. С помощью оператора присваивания обменять их значения:
а) с использованием промежуточной переменной (x:=a; a:=b; b:=x);
b) без использования промежуточной переменной (a:=a-b; b:=a+b; a:=b-a).
2. Составить программу, которая запрашивает у пользователя целое число, действительное число, произвольный символ и строку, а затем все выводит в одной строчке.
3. Выведите на экран свою фамилию, имя и отчество, а через две строки – дату своего рождения.
4. Написать программу для печати звездочками одной из фигур:
а) елочки (нескольких елочек);
б) снежинки (нескольких снежинок);
в) домика.
Например,
*
* *
* *
**********
* *
* *
* *
* *
**********
5. Составить свою визитную карточку.
*******************************
* Иванов Сергей *
* Пролетарская 74 кв. 55 *
* Телефон 45-72-88 *
*******************************
6. Составьте диалог пользователя с компьютером на произвольную тему.
Например, машина задает два вопроса “Как тебя зовут?” и “Сколько тебе лет?”; после введения имени (Антон) и числа (15) выводит на экран “Да... Через 50 лет тебе уже будет 65 лет, а звать тебя будут не Антон, а дед Антон”
7. Запросить у пользователя два числа и вывести на экран результат суммы, разности, произведения и частного этих чисел полным ответом.
8. Запросить у пользователя два числа и вывести на экран результат целочисленного деления и остаток от целочисленного деления в виде таблицы. Например, при вводе чисел 5 и 3 на экране должна быть такая таблица:
**************************
* X * Y * div * mod *
**************************
* 5 * 3 * 1 * 2 *
**************************
9. Написать программу, которая запрашивает название животного и число, а затем выводит на экран фразу типа "Белка съест 10 грибов" (при вводе слова "белка" и числа 10).
10. Организуйте диалог продавца (компьютер) и покупателя (пользователь) при покупке какого-либо товара по следующей схеме: предложение товара по определенной цене, запрашивание количества покупаемого товара, определение и вывод на экран денежной суммы, которую должен заплатить покупатель за покупку.
16 ЦИКЛ С ПРЕДУСЛОВИЕМ, С ПОСТУСЛОВИЕМ
Очень многие алгоритмы, выполнение которых поручается компьютеру, по своей природе являются циклическими. И это не случайно, потому что человек обычно поручает машине рутинную работу, где нужно много считать, и счет производится по некоторым одинаковым правилам.
Определение. Цикл – это последовательность операторов, которая может выполняться более одного раза.
Определение. Циклический алгоритм – это алгоритм, содержащий один или несколько циклов.
Возьмем для примера задачу: найти сумму некоторого количества чисел, задаваемых пользователем.
Исходными данными в этом случае являются переменная N - количество чисел и сами эти числа. Значение очередного числа обозначим переменной Х. Результатом работы алгоритма станет сумма этих чисел, которую обозначим переменной S.
S=x1+x2+x3+...+xn
Допустимые значения переменной N должны удовлетворять условию n>0, так как количество слагаемых не может быть числом отрицательным.
Как же мы должны решать эту задачу? Сначала нужно запросить, сколько чисел нужно будет сложить и считать это число в переменную N. Затем нужно так организовать операторы, чтобы программа запрашивала очередное число и каждый раз складывала его с предыдущими; и повторяла эту группу операторов N раз.
На предыдущих занятиях при изучении оператора безусловного перехода мы знакомились с решением подобных задач. Но в языке Паскаль существуют более удобные конструкции для организации циклов:
• цикл с предусловием;
• цикл с постусловием;
• цикл со счетчиком.
Познакомимся с первым из них – оператором цикла с предусловием while.
Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла.
При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно. Если условие сразу ложно, то оператор не выполнится ни разу.
Общая форма записи следующая
while <булево выражение> do
begin
группа операторов
end;
На русском языке это звучит примерно так:
пока выполняется это условие делай
от начала
группа операторов
до конца;
Вполне понятно, что операторные скобки ставят, чтобы отделить от остальной программы ту группу операторов, которую нужно повторить в цикле. Если в цикле нужно выполнить только один оператор, то операторные скобки не ставят.
При использовании цикла с предусловием надо помнить следующее:
1) значение условия выполнения цикла должно быть определено до начала цикла;
2) если значение условия истинно, то выполняется тело цикла, после чего повторяется проверка условия. Если условие ложно, то происходит выход из цикла;
3) хотя бы один из операторов, входящих в тело цикла, должен влиять на значение условия выполнения цикла, иначе цикл будет повторяться бесконечное число раз.
Вернемся к нашей задаче вычисления суммы чисел. При вычислении суммы используем следующий прием: вначале, когда еще не задано ни одно слагаемое, сумму полагают равной нулю (S:=0), а затем, получая очередное слагаемое, прибавляют его к сумме (S:=S+x) (см. программу ниже).
Очень важное значение в операторе цикла имеет так называемая переменная цикла. В нашей программе она называется i. С ее помощью мы обращаемся к пользователю за очередным числом (write (‘Введите ‘,i,’-ое число ’)) и считаем количество уже введенных чисел (i:=i+1), чтобы не запросить лишнее. Одновременно переменная цикла участвует в булевом выражении (i<=N).
Рассмотрите внимательно программу, решающую нашу задачу.
Program Summa;
Uses
Crt;
Var
i,
N : integer;
x, S : real;
Begin
ClrScr;
write (‘Сколько чисел для сложения? ‘);
readln (N);
S:=0;
i:=1;
while i<=N do
begin
write (‘Введите ‘,i,’-е число ’);
readln (x);
S:=S+x;
i:=i+1;
end;
write (‘Сумма введенных чисел равна ‘,s:5:2);
readln;
End.
Хотелось бы, чтобы Вы смогли представить работу этой программы. Давайте попробуем вместе.
Пусть нам требуется сложить следующие числа: 5, 7, -4, 0, 8, 20. Посчитаем, сколько их всего – шесть. Это число мы введем, когда программа задаст вопрос: Сколько чисел для сложения? Теперь наша программа запросит ввести 1-ое число, т. к. на первом шаге переменная i равна 1. Мы введем число 5. Программа считает его в переменную х. Теперь число 5 сложим с числом 0 и результат присвоим переменной S (оператор S:=S+x). В этот момент S становится равной 5. Чтобы перейти к следующему числу, увеличим значение переменной i на 1 (оператор i:=i+1). Выполнение операторов тела цикла закончено. Теперь программа переходит опять к анализу условия вхождения в цикл (i<=N). Переменная цикла i=2, переменная N=6, поэтому значение логического условия 2<=6 равно True. Значит снова выполняется тело цикла:
while i<=N do {2<=6}
begin
write (‘Введите ‘,i,’-ое число ’); {Введите 2-е число}
readln (x); {Считали число 7}
S:=S+x; {S:=5+7}
i:=i+1; {i:=2+1}
end;
Итак, мы сложили два числа и переходим опять к проверке условия. Ответим на вопрос: 3<=6? Да. Поэтому снова начинаю работать операторы тела цикла и мы переходим к третьему числу:
while i<=N do {3<=6}
begin
write (‘Введите ‘,i,’-ое число ’); {Введите 3-е число}
readln (x); {Считали число -4}
S:=S+x; {S:=12 + (-4)}
i:=i+1; {i:=3+1}
end;
Аналогично, мы сложим и остальные числа. Но когда же операторы цикла выполнятся последний раз и остановится работа цикла? Когда сложим последнее число. Проверим это.
while i<=N do {6<=6}
begin
write (‘Введите ‘,i,’-ое число ’); {Введите 6-е число}
readln (x); {Считали число 20}
S:=S+x; {S:=16+20}
i:=i+1; {i:=6+1}
end;
Проверяется опять условие 7<=6. Значение этого условия равно False, а значит тело цикла выполняться не будет. Цикл закончил свою работу. А мы получили результат: посчитали сумму всех шести чисел S=32.
В этом примере известно заранее количество повторений - N раз. Но чаще всего этот вид цикла используется тогда, когда количество повторений заранее не известно и зависит от выполнения какого-либо условия. Рассмотрим еще один пример.
Отвлечемся от цифр и вспомним окружающую жизнь. Сколько циклических алгоритмов можно увидеть вокруг, если внимательно посмотреть на события: чередование времен года, посещения магазинов, школы или секции, получение за контрольные оценок и др. Попробуем записать их.
Например, рассмотрите следующие циклические алгоритмы
а) Пока не сдал выпускные экзамены делай
начало
готовь уроки;
посещай школу;
конец;
б) Пока есть желание, возможность и здоровье делай
посещай занятия спортом
Продолжим изучение цикла с предусловием на примере решения следующей задачи.
Задача. Найти сумму чисел в непустой последовательности.
Рассмотрим алгоритм решения. Пусть нам дана такая последовательность чисел:
3, -4, 0, 5, 19, -20, 6, 2
Для работы нам нужно организовать обращение к каждому элементу последовательности. Нетрудно догадаться, что это будет происходить через порядковый номер каждого члена последовательности. Пронумеруем эти числа:
1 2 3 4 5 6 7 8
3, -4, 0, 5, 19, -20, 6, 2
Получилось, что всего у нас чисел восемь, на первом месте стоит число 3, на втором - число (-4), на третьем - число 0 и т.д. Тогда переменная цикла i будет пробегать числа от 1 до 8, становясь на каждом шаге больше на 1 и запрашивая каждый раз очередное число. Поэтому общая схема цикла будет выглядеть так:
i:=1;
while i<=N do
begin
write (‘Введите ‘,i,’-ое число’);
readln (x);
. . .
i:=i+1;
end;
Здесь N - количество чисел последовательности (в нашем случае 8), х - член последовательности, i - порядковый номер очередного члена последовательности. Просмотрим, как будет работать этот цикл.
1 шаг
i:=1;
while i<=N do {Проверяется условие 1<=8? Да. Значит выполняем тело цикла}
begin
write (‘Введите ‘,i,’-ое число’);{Вывод на экран “Введите 1-ое число”}
readln (x); {Считываем число 3 в переменную х}
. . .
i:=i+1; {Переходим к следующему по порядку числу: i=2}
end;
2 шаг
i:=1;
while i<=N do {Проверяется условие 2<=8? Да. Значит выполняем тело цикла}
begin
write (‘Введите ‘,i,’-ое число’);{Вывод на экран “Введите 2-ое число”}
readln (x); {Считываем число (-4) в переменную х}
. . .
i:=i+1; {Переходим к следующему по порядку числу: i=3}
end;
3 шаг
i:=1;
while i<=N do {Проверяется условие 3<=8? Да. Значит выполняем тело цикла}
begin
write (‘Введите ‘,i,’-ое число’);{Вывод на экран “Введите 3-ое число”}
readln (x); {Считываем число 0 в переменную х}
. . .
i:=i+1; {Переходим к следующему по порядку числу: i=4}
end;
и т. д.
8 шаг
i:=1;
while i<=N do {Проверяется условие 8<=8? Да. Значит выполняем тело цикла}
begin
write (‘Введите ‘,i,’-ое число’);{Вывод на экран “Введите 8-ое число”}
readln (x); {Считываем число 2 в переменную х}
. . .
i:=i+1; {Переходим к следующему по порядку числу: i=9}
end;
9 шаг
i:=1;
while i<=N do {Проверяется условие 9<=8? Нет. Значит цикл закончил свою работу и компьютер переходит к обработке следующего за end оператора}
Итак, у нас уже организован цикл считывания чисел. Осталось только вписать в тело цикла оператор, который бы суммировал все эти числа. Для этого опишем переменную Summa в разделе описания переменных и присвоим ей нулевое значение перед выполнением цикла. Тогда при каждом шаге нашего цикла значение этой переменной должно быть изменено на х. Это произойдет при выполнении оператора
Summa:=Summa+x;
Если Вам не совсем понятно, что происходит при выполнении этого оператора, Вам нужно вспомнить, как происходит присваивание значение переменной: сначала вычисляется значение выражения в правой части (в нашем случае Summa+x, т.е, значение переменной Summa увеличиваем на х), а затем присваиваем это значение переменной с именем, записанным в левой части (Summa). Таким образом, в переменной Summa собирается сумма всех считанных чисел.
16. ЦИКЛ С ПРЕДУСЛОВИЕМ И С ПОСТУСЛОВИЕМ
20 МАССИВЫ
22 СПОСОБЫ СОРТИРОВКИ
Все методы сортировки можно разделить на две большие группы:
- прямые методы сортировки;
- улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
1) сортировка вставкой (включением);
2) сортировка выбором (выделением);
3) сортировка обменом (так называемая "пузырьковая" сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса
23 СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА
Сортировка методом простого обмена.
Принцип метода:
Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.
Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
Procedure Obmen(Var a : Array1);
Var
i,j,f,g:integer;
Begin
for i:=n downto 2 do
for j:=1 to i-1 do
if a[j]>a[j+1]
then
begin
f:=a[j];
a[j]:=a[j+1];
a[j+1]:=f;
end;
End;
Алгоритм решения задачи:
Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм и особенности этой сортировки таковы:
24 МЕТОД ВЫБОРА
Сортировка выбором
Принцип метода:
Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.
Рассмотрите схему алгоритма прямого выбора.
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
Procedure Vibor(Var a: Array1);
Var
i, j, Min, MinI : integer;
Begin
for i:=1 to c do
begin
Min:=a[i];
MinI:=i;
for j:=i+1 to c do
if a[j]<min
then
begin
Min:=a[j];
MinI:=j;
end;
a[MinI]:=a[i];
a[i]:=Min;
end;
End;
26 МЕТОД ВСТАВКИ
сортировку методом вставки.
Принцип метода заключается в следующем:
Массив разделяется на две части: отсортированную и не отсортированную. элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной – все остальные элементы.
Таким образом, алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:
• взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;
• поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
• сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
• вставка взятого элемента в найденную i-ю позицию.
Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличаться способом поиска позиции вставки.
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
Procedure Vstavka(Var a : Array1);
Var
i, j,e,g:integer;
Begin
for i:=2 to c do
begin
e:=A[i];
j:=1;
while (e>a[j]) do
Inc(j);
for g:=i-1 downto j do
a[g+1]:=a[g];
a[j]:=e;
end;
End;
Задание. Составьте программу сортировки одномерного массива рассмотренным методом.
35 ОРГАНИЗАЦИЯ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ
Динамические структуры данных
Объект данных обладает динамической структурой, если его размер изменяется в процессе выполнения программы или он потенциально бесконечен.
Классификация структур данных
Используемые в программировании данные можно разделить на две большие группы:
Данные статической структуры – это данные, взаиморасположение и взаимосвязи элементов которых всегда остаются постоянными.
Данные динамической структуры – это данные, внутреннее строение которых формируется по какому-либо закону, но количество элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы, согласно закону формирования.
Данные динамической структуры:
К данным динамической структуры относят файлы, несвязанные и связанные динамические данные.
Заметим, что файлы в данной классификации отнесены к динамическим структурам данных. Это сделано исходя из вышеприведенного определения. Хотя удаление и вставка элементов в середину файла не допускается, зато длина файла в процессе работы программы может изменяться – увеличиваться или уменьшаться до нуля. А это уже динамическое свойство файла как структуры данных.
Для работы с динамическими переменными в программе должны быть выполнены следующие действия:
Программист должен сам резервировать место, определять значение указателей, освобождать ДП.
Вместо любой статической переменной можно использовать динамическую, но без реальной необходимости этого делать не стоит.
Присваивание значений динамическим переменным
После того, как динамическая переменная объявлена, ей можно присваивать значения, изменять их, использовать в выражениях и т.д. Для этого используют следующее обращение: переменная_указатель^. Такое обращение называется операция разадресации (разыменования). Таким образом происходит обращение к значению, на которое указывает указатель, т.е. к данным. Если же за переменной_указателем значок ^ не стоит, то имеется в виду адрес, по которому расположены данные.
Динамически размещенные данные можно использовать в любом месте программы, где допустимо использование выражений соответствующего типа.
Например:
R^:= sqr( R^) + I^ -17;
q^:= 2; inc(q^); writeln(q^)
Недопустимо использовать выражения, подобные следующим:
Адрес --->R:= sqr( R^) + I^ -17 <---вещественное выражение.
Вещественная переменная --->R^:= sqr( R) <---аргумент – адрес.
Рассмотрим пример работы с указателями:
36 СПИСКИ
Линейные списки (однонаправленные цепочки).
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.
Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.
Описание списка
Пример описания списка
Type ukazat= ^ S;
S= record
Inf: integer;
Next: ukazat;
End;
В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.
Формирование списка
Чтобы список существовал, надо определить указатель на его начало.
Пример описания списка
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
End;
Создадим первый элемент списка:
New (u); {выделяем место в памяти}
u^. Next:= nil; {указатель пуст}
u^. Inf:=3;
Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.
А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:
New(x);
Readln(x^.Inf);
x^. Next:= u;
u:= x;
Б)Добавление элемента в конец списка. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).
x:= hv;
New( x^. next); {выделяем память для следующего элемента}
x:= x^.next;
x^.next:= nil;
x^. inf:= 5;
hv:=x;
Просмотр списка
While u<> nil do
Begin
Writeln (u^.inf);
u:= u^.next;>
end;
Удаление элемента из списка
А)Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.
x:= u;
u:= u^.next;
dispose(x);
Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.
x:= u;
while ( x<> nil) and ( x^. inf<> digit) do
begin
dx:= x;
x:= x^.next;
end;
dx:= x^.next:
dispose(x);
В)Удаление из конца списка. Для этого нужно найти предпоследний элемент.
x:= u; dx:= u;
while x^.next<> nil do
begin
dx:= x; x:= x^.next;
end;
dx^.next:= nil;
dispose(x);
Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.
summa:= 0;
x:= u;
while x<> nil do
begin
summa:= summa+ x^.inf;
x:= x^.next;
end;
Динамические объекты сложной структуры
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.
37 КОЛЬЦА (двунаправленный списк)
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
Pred: ukazat;
End;
Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:
Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:
Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
Существуют различные методы использования динамических списков:
38 СТЕК
особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
Начнем с рассмотрения примера. Пусть в трубку с запаянным концом закатываются шарики. Извлекать их можно только в обратном порядке: тот шарик, что закатился последним, будет извлечен первым.
Подобным образом можно организовать и данные. Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.
Пример. Рассмотрим последовательные этапы засылки с стек чисел 1, 2, 3.
На этапе б) обращение к процедуре извлечения из стека дает число 2, на этапе в) – число 3.
Опишем стек, в который можно помещать цепочку динамических переменных:
type
stackp = ^stackcomp;
stackcomp = record
I: integer;
P: stackp
end;
var
S: stackp;
Если помещать в этот стек последовательность 1, 2, 3, то получится следующий вид:
Поместить в такой стек компоненту можно, например, процедурой SN:
S := nil;
…
procedure SN(k: integer);
var
inew: stackp;
begin
{резервируется память под новую компоненту,
в inew засылается адрес этой компоненты}
new(inew);
with inew do begin
I := k;
P := S
end;
S := inew;
end;
Если со стеком вида как на рисунке выше обратиться к процедуре SN для засылки числа 4, то получим стек вида:
Процедура извлечения компоненты из такого стека может иметь следующий вид:
procedure OUT(var k: integer);
var
iold: stackp;
begin
iold := S;
{значение последней компоненты}
k := iold^.I;
{извлекается и засылается в S значение
соответствующего указателя на 3}
S := iold^.P;
dispose(iold);
end;
После обращения к процедуре OUT стек вернется к первоначальному виду (1, 2, 3).
Пустым стеком называется стек, не содержащий компонент. Такой стек можно получить, присвоив значение Nil соответствующей ссылочной переменной (в нашем случае S := nil;).
Если к пустому стеку применить несколько раз процедуру SN, а затем столько же раз процедуру OUT, то получим снова пустой стек.
Замечание. Нельзя применять процедуру OUT к пустому стеку.
Стеки позволяют гибко и экономно использовать память, т.к. в каждый момент в стеке могут находиться только те переменные, которые нужны для дальнейшей работы программы. (В то время как под массивы, например, мы зачастую вынуждены резервировать и держать избыточную память.)
39 ОЧЕРЕДЬ–
это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.
40 ОПЕРАЦИИ НАД ДИНАМИЕСКИМИ СТРУКТУРАМИ ДАННЫХ
Добавление элемента в стек
Пусть указатель a содержит адрес вершины стека, b - другой объявленный указатель.
Извлечение элемента из стека
a - указатель на вершину, b - другой указатель
Проверка, пуст ли стек;
Просмотр элемента в вершине стека без удаления;
Очистка стека.
типовые операции над списками:
47 СОЗДАНИЕ ДИНАМИЧЕСКИХ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ
Действия с рисунком
n:= LoadPicture (name) – загружает рисунок из файла с именем name в оперативную память и возвращает описатель рисунка в целую переменную n.
Если файл не найден, то возникает ошибка времени выполнения.
Загружать можно рисунки в формате .bmp, .jpg или .gif.
DrawPicture (n, x, y) - выводит рисунок с описателем n в позицию (x,y) графического окна.
DrawPicture (n, x, y, w, h) – устанавливает ширину (w) и высоту (h) рисунка
SetPictureTransparent(n, true) - устанавливает (b = True) или отключает (b = False) режим прозрачности при рисовании рисунка с описателем n. Если b = True, то при его рисовании фон не отображается. Фоновым считается цвет левого нижнего пиксела рисунка.
Sleep(ms) - осуществляет паузу в выполнении программы на ms миллисекунд
Использование процедуры перерисовки Redraw позволяет избежать моргания экрана.
Практическая работа
Пусть автомобиль перемещается на фоне здания и деревьев слева направо на расстояние 400 пикселей.
Загрузим изображения фона и автомобиля из файлов gorod.gif и avto.jpg, поместив их описатели в переменные fon и avto. Установим прозрачность фона для изображения автомобиля SetPictureTransparent(avto,true). Зададим начальные координаты (х, у), ширину w и высоту h изображения автомобиля. Все переменные имеют тип integer.
Процедуры рисования и стирания будем повторять в цикле с предусловием While до тех пор, пока автомобиль не переместится на 400 пикселей. На каждом шаге цикла координату х левого верхнего угла изображения увеличиваем на 10. Ширину уменьшаем на 2, а высоту на 1 пиксель для уменьшения изображения при удалении.
program Avto1;
uses GraphABC;
var fon, avto, x,y, w,h: integer;
begin
SetWindowSize (600, 300);
fon:= LoadPicture ('город.gif');
avto:= LoadPicture ('автомобиль.jpg');
SetPictureTransparent (avto, true);
x:= 10; y:= 170; w:= 240; h:= 100;
while x < 400 do
begin
ClearWindow;
DrawPicture (fon, 0, 0);
DrawPicture (avto, x, y, w ,h);
x:= x + 10; w:= w - 2; h:= h - 1;
sleep (20); Redraw;
end;
end.
program babochka;
uses Graphabc;
var f, b, x, y : integer;
begin
setwindowsize (450, 550);
b:= LoadPicture ('цветы.jpg');
f:= LoadPicture ('бабочка.gif');
x:= 10; y:= 350;
while x<= 200 do
begin
DrawPicture (b, 0, 0);
Setpicturetransparent (f, true);
DrawPicture (f, x, y);
x:= x + 7;
y:= y- 4;
sleep (200);
end;
end.
Загрузим изображение циферблата из файла таймер.jpg, поместив описатель в переменную fori. Зададим координаты центра вращения стрелок (хО.уО) и начальные значения секунд sec:=0 и минут min:=0.
На каждом шаге цикла с постусловием repeat...until будем увеличивать значение секунд на 1 до тех пор. пока время не превысит 60 мин. или не нажата любая клавиша (keyPressed). Значения минут вычислим целочисленным делением секунд на 60: min:= secdiv60.
Секундную стрелку будем рисовать линией длиной 120 и толщиной 3 пикселя, а минутную - 100 и 7 пикселей. Радианная мера угла поворота секундной стрелки равна Pi*sec/30. а минутной Pi"min/30. Координаты концов стрелок (х,у) вычисляем по формулам тригонометрии и округляем до целых Например, для секундной стрелки x:=x0+Round<120"sin(Pi'sec/30))i y:=yO-Round(120'cos(Pi'sec/30)).
Program Timer;
uses crt, GraphABC;
var fon, x0, y0, x, y, R, min, sec: integer;
begin
SetWindowSize (360, 480); HideCursor;
x0 := 173; y0 := 300; min : =0; sec := 0;
fon := LoadPicture ('таймер.jpg');
repeat
DrawPicture (fon, 0, 0);
sec := sec + 1; min := sec div 60;
x := x0 + Round (120 * sin (Pi * sec / 30));
y := y0 – Round (120 * cos (Pi * sec / 30));
SetPenWidth (3);
Line (x0, y0, x, y);
x := x0 + Round (100 * sin (Pi * min / 30));
y := y0 – Round (100 * cos (Pi * min / 30));
SetPenWidth (7);
Line (x0, y0, x, y);
sleep (1000);
until (min >= 60) or keyPressed;
end.