16.1. type ref = ^integer;
var p,q:ref;
Пусть переменные р и q имеют значения, показанные на рис.8. Ответить на следующие вопросы.
а) Что является значением переменной р: ссылка на объект (переменную) "целого типа или сам этот объект?
Что обозначает переменная р^: ссылку на объект целого типа, сам этот объект или целое 5? Каковы типы переменных р и p^?
б)* Что будет выдано на печать в результате выполнения следующих операторов?
P^:=q^;
if p=q then p:=ni1 else if p^=q^ then q:=p;
if p = q then q^:= 4;
writeln(p^)
16.2 *. type D=record a:boolean; b,c: ^real end;
var r: ^D;
Пусть переменная r имеет значение, показанное на рис.9. Нарисовать структуру значения Переменной r после выполнения следующих операторов:
if r^.b<>nil then r^.c:=r^.b;
r^.b^:=r^.c^—1.4; r^.a:=r^.b=r^.c
16.3* var,q: ^integer; r: ^char;
Какие из следующих операторов неправильные и почему?
a) p:=q; б) q:=r; в) р:=nil;
г) г:=nil; д) q:=p^; e) p^:=nil;
ж) r^:=p^; з) q^:=ord(r^); и) if r<>nil then r^:=nil^;
к) if q>nil then q^:=p^; л) if q=p then write(q);
м) if q<>r then read(r↑)
16.4. Имеется программа
program dynamic (output);
var x: ^boolean; y:boolean;
begin {A} new(x); {B} x^:=true; y:=not x^;
{C} dispose(x); {D} writeln(y)
end.
Ответить на следующие вопросы.
а) Какие переменные существуют в каждой из точек А, В, С и D и каковы их значения в эти моменты?
б) Почему объекты (переменные), создаваемые процедурой new и уничтожаемые процедурой dispose, называют динамическими? Почему им не дают имена?
в) Можно ли переменной х присвоить ссылку на переменную у? Можно ли о помощью процедуры dispose уничтожить переменные х и у?
16.5 *. type A=^char; B=record f1:char; f2:A end;
var p: ^B; q:A;
Нарисовать структуру значений переменных р и q после выполнения следующих операторов:
new(q); q^='7';
new(p); p^.fl:=succ(q^); p^.f2:=q
16.6. type chain — ↑etem;
elem= record data:integer;
link:chain end;
var p,q:chain;
Нарисовать структуру значения переменной р после выполнения следующих операторов:
а) new(p); p^.data:=4; p^.link:=nil;
б) new(p); p^.data:=7; p↑.link:=p;
в) new(q); q^.data:=2; q^.link:=nil;
new(p); p^.data: = l; p^.link:—q;
r)* new(p); p^.data:=5; new(p^.link); p^. link^:=p^
16.7. Найти ошибки в следующей программе:
program errors;
var a,b: ^integer;
begin if a=nil then read(a); a^:=5;
b:=nil; b^:=2;
new(b); read(b^); writeln(b,b^);
new(a); b:=a; dispose(a); b^:=4
end.
16.8 *. Почему недопустимы следующие описания и как их исправить?
type A=^0..9;
B=record p:real; q:C end;
С = ^В;
16.9*. Описать переменную р (и, если надо, вспомогательные переменные) и выписать операторы, присваивающие ей указанные значения (рис. 10).
16.10. type цепочка = ^звено;
звено = record элем:integer;
след:цепочка end;
var р:цепочка;
Выписать операторы, которые преобразуют значение переменной p, показанное на рис. 11,а, к значению, показанному на рис. 1)* 11,б; 2) 11,в; 3) 11,г. (Звенья, ставшие ненужными, уничтожить.)
16.11. Допустимы ли в языке Паскаль конструкцииP^ [2], q^+[2] и r^^? Ответ обосновать.
16.12. type ссылка = lreal;
вектор = аrrау [1..100] of ссылка;
Считая, что все элементы вектора х отличны от nil, описать
а) функцию тах(х) для нахождения наибольшего из чисел, на которые ссылаются элементы вектора х;
б)* функцию neg1(x), значением которой является первый из элементов вектора х, ссылающихся на отрицательные числа, или nil, если таких элементов нет;
в) логическую функцию same(x), которая проверяет, есть ли в векторе х хотя бы две одинаковые ссылки;
г) процедуру unique(x), которая в векторе х все элементы, ссылающиеся на равные числа, заменяет на первый из этих элементов.
16.13. Одно из возможных представлений «длинного» текста —это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки:
const d=…; {длина строки}
n=...; {максим, число строк}
type строка = array [l..d] of char,
ссылка =^строка;
текст = array [l..n] of ссылка;
(Если в тексте менее п строк, то последние элементы массива равны nil; в начале массива ссылок nil не должно быть. Если, в операции над текстом указан номер отсутствующей строки, т. е. элемент массива с этий номером равен nil, то такая операция не выполняется.)
Используя данное представление текста, описать:
а) функцию числострок(Т) для подсчета числа строк в тексте Т;
б) логическую функцию элем(Т,i,j,с), проверяющую, есть ли в тексте Т строка с номером i, и, если есть, присваивающую f-ю литеру этой строки параметру с;
в) процедуру перестановка(T,i, j), меняющую местами i -ю и j -ю строки текста Т;
г) процедуру замена(Т,i,j), заменяющую i -ю строку текста Т на копию j -й строки;
д) процедуру добавить(T,itj), добавляющую после i-й строки текста Т копию j- й строки;
е) процедуру удалиmь(Т ',i). удаляющую i -ю строку из текста Т;
ж) логическую функцию поиск(T,c,i,j), определяющую, входит ли литера с в текст T, и, если входит, присваивающую параметрам i и j «координаты» первого вхождения, этой литеры: i —номер строки, а j —номер позиции в этой строке;
з) процедуру вывод(Т) печатающую построчно текст Т;
и) процедуру ввод(Т), считывающую из входного файла последовательность литер до первой точки и формирующую из них текст Т (последнюю строку, если надо, дополнить пробелами).
В упражнениях 16.14—16.29 использовать (линейные) однонаправленные списки без заглавного эвен (pиc 12,а) или с заглавным звеном (рис. 12,б) при следующем их описании:
type ТЭ =...; {тип элементов списка (уточняемый, если надо, в упражнениях)}
список =^звено;
звено = record элем:ТЭ; след:список end;
При этом параметры L, L1и L2 обозначают списки, а параметры Е, Е1 и Е2 — данные типа ТЭ, к которым применимы операции присваивания и проверки на равенство.
16.14. Описать функцию или процедуру, которая:
а) определяет, является ли список L пустым;
б) находит среднее арифметическое элементов непустого списку L(TЭ=real);
в)*.заменяет в списке L все вхождения Е1 на E2;
г) меняет местами первый и последний элементы непустого списка L;
д)* проверяет, упорядочены ли элементы списка L по алфавиту (TЭ='a'.. 'z');
е) находит сумму последнего и предпоследнего элементов списка L, содержащего не менее двух элементов (TЭ=integer).
16.15. type слово= array [1..10] of char;
ТЭ=слово;
Описать функцию, подсчитывающую количество слов списка L, которые:
а) начинаются и оканчиваются одной и той же литерой;
б) начинаются с той же литеры, что и следующее слово;
в) совпадают с последним словом.
16.16. type файл=file of ТЭ;
массив=аrrау [1..50] of ТЭ;
Описать функцию, значением которой является список, построенный из элементов:
а)* файла f;
б) массива х (список строить от конца).
16.17. Описать процедуру, которая по списку L строит два новых списка: L1 —из положительных элементов и L2—из остальных элементов списка L (ТЭ=rеа1).
16.18. Описать процедуру, которая вставляет:
а) в начало списка L новый элемент E;
б) в конец списка L новый элемент E;
в) новый элемент Е после первого элемента непустого списка L
г) в список L новый элемент Е1 за каждым вхождением элемента E;
д)* в список L новый элемент E1 неред первым вхождением элемента E если Е входит в L;
е) в непустой список L пару новых элементов Е1 и E2 перед его последним элементом;
ж) в непустой список L, элементы которого упорядочены по неубыванию, новый элемент Е так, чтобы сохранилась упорядоченность (ТЭ=real).
16.19. Описать процедуру, которая удаляет:
а) из непустого списка L первый элемент;
б) из списка L второй элемент, если такой есть;
в) из списка L за каждым вхождением элемента Е один элемент, если такой есть и он отличен от Е;
г)* из непустого списка L последний элемент;
д) из списка L первый отрицательный элемент, если такой есть (ТЭ=integer);
е) из списка L все отрицательные элементы (ТЭ=геа1).
16.20 *. Программа. Заданный во входном файле текст (за ним следует точка) распечатать в обратном порядке.
16.21. Программа. Дана непустая последовательность натуральных чисел, за которой следует 0. Напечатать порядковые номера тех чисел последовательности, которые имеют наибольшую величину.
16.22. Программа. Дано целое n>1, за которым следует п вещественных чисел. Напечатать эти числа в порядке их неубывания.
16.23. Описать процедуру или функцию, которая:
а) проверяет на равенство списки L1 и L2;
б) определяет, входит ли список L1 в список L2;
в) проверяет, есть ли в списке L хотя бы два одинаковых элемента;
г) переносит в конец непустого списка L его первый элемент;
д) переносит в начало непустого списка L его последний элемент;
е)* добавляет в конец списка L1 все элементы списка L2;
ж) вставляет в список L за первым вхождением элемента E все элементы списка LI, если Е входит в L;
з) переворачивает список L, т. е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке;
и) в списке L из каждой группы подряд идущих равных элементов оставляет только один;
к) оставляет в списке L только первые вхождения одинаковых элементов.
16.24. Описать рекурсивную функцию или процедуру, которая:
а)* определяет, входит ли элемент Е в список L;
б) подсчитывает число вхождений элемента Е в список L;
в) находит максимальный элемент непустого списка L (ТЭ=rеа1);
г) печатает в обратном порядке элементы списка (ТЭ=char);
д) заменяет в списке L все вхождения Е1 на Е2;
е)* удаляет из списка L первое вхождение элемента E если такое есть;
ж) удаляет из списка L все вхождения элемента Е;
з) строит L1 —копию списка L;
и) удваивает каждое вхождение элемента Е в список L;
к) находит среднее арифметическое всех элементов непустого списка L (ТЭ=real).
16.25. Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые:
а) входят хотя бы в один из списков L1 и L2;
б) входят одновременно в оба списка L1 и L2;
в) входят в список L1, но не входят в список L2;
г) входят в один из списков L1 и L2, но в то же время не входят в другой из них.
16.26. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка L1 и L2 (ТЭ=real) в один упорядоченный по неубыванию список:
а) построив новый список L;
б) меняя соответствующим образом ссылки в L1 и L2 и присвоив полученный список параметру L1.
16.27. Описать процедуру подстановка, (L1,L2), которая в списке L заменяет первое вхождение списка L1 (если такое есть) на список L2.
16.28.
const n=...; {целая константа>1}
type число=расked array [l..n] of 0..9;
ТЭ= число;
Описать процедуру ynop(L), упорядочивающую по неубыванию числа непустого списка L с помощью следующего алгоритма (рис. 13, где n предполагается равным 2).
Создать 10 пустых подсписков (по количеству цифр), а затем, просматривая числа исходного списка, занести в k-й подсписок все числа, оканчивающиеся цифрой k, после чего эти подсписки объединить в один список L,
записав в последнее звено k -го подсписка ссылку на начало (k+l)-гo подсписка. Далее аналогичный метод применяется по отношению к предпоследней цифре чисел (не нарушая при этом упорядоченность по последней цифре), затем—по отношению к третьей от конца цифре и т. д.
16.29. type слово=^цепочка;
цепочка=record буква: ‘a’..’z’;
связь:слово end;
ТЭ=слово;
Описать функцию или процедуру, которая:
а) в списке L переставляет местами первое и последнее непустые слова, если в L есть хотя бы два непустых слова;
б)* печатает текст из первых букв всех непустых слов списка L;
в) удаляет из непустых слов списка L их первые буквы;
г) печатает все непустые слова списка L;
д) определяет количество слов в непустом списке L, отличных от последнего.
16.30. Многочлен
P(x)=anxn+an-1xn-1+... +ахх+а0
с целыми коэффициентами можно представить в виде списка (рис.14, а), причем если аi=0, то соответствующее звено
не включается в список (на рис. 14,6 показано представление многочлена S(x)=52x40—3x8 + x).
Описать на Паскале тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками - многочленами:
а) логическую функцию равно(р,q), проверяющую на равенство многочлены р и q;
б) функцию знач(р1х) вычисляющую значение многочлена р в целочисленной точке х;
в) процедуру диф(p,q) которая строит многочлен р — производную многочлена q;
г) процедуру слож(рм,г), которая строит многочлен р — сумму многочленов q и r;
д) процедуру вывод(р,v), которая печатает многочлен р как многочлен от переменной, однобуквенное имя которой является значением литерного параметра и; например, для указанного выше многочлена S процедура вывод(s,'у') должна напечатать 52у^40—Зу↑8+у;
e) процедуру ввод(р), которая считывает из входного файла безошибочную запись многочлена (за ней—пробел) и формирует соответствующий список-многочлен р.
16.31. Предложить и описать на Паскале представление файлов (из элементов некоторого типа ТЭ) в виде списков и определить функцию eof1(f) и процедуры reset1(f),
Read1(f,x), rewrite1(j) и mite1(j,x), реализующие при таком представлении файлов действия соответствующих стандартных функции и процедур.
16.32. Назовем (иерархическим) «списком» заключенную в круглые скобки последовательность элементов, разделенных запятыми; элементы списка - это атомы или снова СПИСКИ:
<список>::= () | (<элементы>)
<элементы>::=<элемент> |<элемент>,<элементы>
<элемент>::=<атом> | <список>
Под «атомом» понимается последовательность, содержащая от 1 до п букв и цифр, где п —заранее известное натуральное число. Пример подобного списка: (AD75,(3,(),(7H))). Предложить и описать на Паскале представление таких списков и определить следующие рекурсивные функции и процедуры для работы с ними:
а) логическую функцию member (A,L), проверяющую, входит ли атом A в список L;
б) логическую функцию equal(L1,L2), проверяющую на равенство списки L1 и L2;
в) процедуру printat(L), печатающую все атомы, входящие в список L;
г) процедуру printlist(L), печатающую список L в том виде, как он определен указанными выше металингвистическими формулами;
д) процедуру readlist(L), которая считывает из входного файла записанный без ошибок список и строит L — соответствующее представление этого списка.
16.33. Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавным звеном (рис. 15) при следующем описании такого списка;
type ТЭ2=...; {тип элементов списка}
список2=^звено2;
звено2=гecord элем:ТЭ2;
пред,след:список2 end;
и пусть Е обозначает величину типа ТЭ2. Описать функцию или процедуру, которая:
а)* определяет, является ли список L пустым;
б)* печатает в обратном порядке элементы непустого списка L (TЭ2= char);
в) подсчитывает количество элементов списка L, у которых равные «соседи»;
г) определяет, есть ли в списке L хотя бы один элемент, который равен следующему за ним (по кругу) элементу;
д) в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз;
е) удаляет из списка L первый отрицательный элемент, если такой есть;
ж) из списка L, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые «соседи» (первый и последний элементы считать соседями);
з) добавляет в конец списка L новый элемент Е;
и) в списке L, удваивает каждое вхождение элемента Е;
к) строит список L по однонаправленному списку L1
л) в конец непустого списка L добавляет все его элементы, располагая их в обратном порядке (например, по списку из элементов 1, 2, 3 требуется построить список из элементов 1, 2, 3, 3, 2, 1).
16.34. («Считалка».) п ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k -го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга.
Решение этой задачи описать в виде программы (ее исходные данные—натуральные числа п и k), которая должна напечатать номера ребят в том порядке, как они удаляются из круга.
Решения задач 16.35—16.46 описать в виде программ, выбрав для представления данных подходящую списковую структуру.
16.35. Определить, симметричен ли заданный во входном файле текст (за ним следует точка).
16.36. Дана последовательность из не менее чем двух различных натуральных чисел, за которой следует 0. Напечатать в обратном порядке все числа между наибольшим и наименьшим числами этой последовательности.
16.37. Дана непустая последовательность непустых слов из букв; между соседними словами—запятая, за последним словом—точка. Напечатать все слова максимальной длины.
16.38. Дана непустая последовательность слов, в каждом из которых от 1до 12 строчных латинских букв; между словами—пробел, за последним словом—точка. Напечатать эти слова по алфавиту, указав для каждого из них число его вхождений в эту последовательность.
16.39. Решить предыдущую задачу в предположении, что максимальная длина слов заранее не известна.
16.40. Дана непустая последовательность слов, в; каждом из которых от 1 до 8 строчных латинских букв; между словами—пробел, за последним словом—точка. Напечатать эти слова в следующем порядке: сначала—по алфавиту все слова из одной буквы, затем—по алфавиту все двухбуквенные слова и т. д. (одинаковые слова печатат по одному разу).
16.41. Решить предыдущую задачу в предположении, что максимальная длина слов заранее не известна.
16.42. Дан текст, оканчивающийся точкой. Среди литер этого текста особую роль играет знак #, появление которого в тексте означает отмену предыдущей литеры текста; k знаков # подряд отменяют k предыдущих литер (если такие есть). Напечатать данный текст, исправленный с учетом такой роли знака # (например, текст XЭ#E##HELO#LO должен быть напечатан в виде HELLO).
16.43. Дано произвольное натуральное число п. Напечатать все цифры десятичной записи числа п!.
16.44. Дано целое n>2. Напечатать коэффициенты n -го многочлена Чебышева Tn(х), определяемого формулами T0(x)=1; T1(x)=x; Tk(x)=2xTk-1(x)-Tk-1(x) (k=2,3…).
16.45. Дана запись многочлена (от переменной х) произвольной степени с целыми коэффициентами, причем его одночлены могут быть и не упорядочены по степеням х, а одночлены одной и той же степени могут повторяться. Возможный пример:
—8x^4—74x+8x^4+5—x^3.
Требуется привести подобные члены в этом многочлене, после чего распечатать его по убыванию степеней х.
16.45. Промоделировать выполнение любого заданного нормального алгоритма Маркова над любым заданным входным словом (см., например, [9]).