Динамические структуры данных
4.3.1. Основные сведения о ссылочном типе данных (указателях)
Различные типы данных используют статическое распределение памяти, т. е. распределение памяти на стадии компиляции. Перераспределение памяти на стадии выполнения программы не допускается. Поэтому для массива иногда приходится резервировать в задаче максимально возможный размер. Но существует возможность динамического управления памятью — выделение памяти во время выполнения программы.
Это возможно при использовании нового типа данных, который называются указатель. Указатель — это переменная, которая в качестве своего значения содержит адрес первого байта памяти, начиная с которого записаны данные.
Переменной, на которую указывает указатель, не обязательно присваивать какое-либо имя. К ней можно обращаться через имя указателя, потому она называется ссылочной переменной. Все ссылочные переменные имеют одинаковый размер, равный 4 байтам. Для хранения динамических переменных выделяется специальная область памяти, называемая кучей (хипом). Работая с указателями, мы работаем с адресами величин, а не с их именами. Место для данных в куче отводится и освобождается только во время работы программ, и потому мы говорим о динамических данных.
Для объявления переменных ссылочного типа используется специальный символ «^», после которого записывается базовый тип динамической переменной.
|
|
|
Туре <имя_типа>= ^<базовый тип>;
Var <имя_переменной>:<имя_типа>;
или Var <имя_переменной>: ^ <базовый тип>;
Например:
Type ss = ^Integer;
Var x, у: ss; {Указатели на переменные целого типа.}
а: ^Real; {Указатель на переменную вещественного типа. }
Среди возможных указателей в Паскале выделяется один специальный указатель, который «никуда не указывает». Для его обозначения используется зарезервированное слово Nil. Указатель Nil считается константой, совместимой с любым ссылочным типом.
Основной операцией при работе со ссылочными переменными является операция разыменования — переход от ссылочной переменной к значению, на которое она указывает.
Например: х^:= 15 означает, что по адресу, который является значением указателя х, записывается значение 15.
Размещение динамических переменных выполняется с помощью процедуры New(x), которая отводит место для хранения динамической переменной х^ и присваивает ее адрес ссылке х.
Процедура Dispose(x) освобождает память, занимаемую динамической переменной. После выполнения процедуры значение указателя х становится неопределенным.
4.3.2. Виды динамических структур
Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями. Динамическая структура, в отличие от массива или записи, может занимать несмежные участки оперативной памяти.
|
|
|
Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Например, если в процессе выполнения программы требуется многократно упорядочивать большой массив данных, имеет смысл организовать его в виде линейного списка. При решении задач поиска элемента в тех случаях, когда важна скорость, данные лучше всего представить в виде бинарного дерева.
4.3.3. Линейные списки
Списком называется структура данных, каждый элемент которой связывается со следующим элементом посредством указателя. Из определения следует, что каждый элемент списка содержит как минимум одно поле данных которое может иметь сложную структуру, и поле ссылки на следующий элемент. Поле ссылки последнего элемента списка имеет значение Nil. Указатель на начало списка (первый элемент) является значением отдельной переменной.
|
|
|
Пример описания списка:
Type pt=^elem;{Указатель на элемент списка.}
elem=Record
data:Integer;{ Поле данных .}
next:pt {Указатель на следующий элемент списка.}
End;
Var first:pt;{Указатель на первый элемент списка.}
Основные операции с элементами списка:
· просмотр элементов списка;
· вставка элемента в список;
· удаление элемента из списка.
Процедура, осуществляющая просмотр элементов списка:
Procedure Print(z:pt);
Begin
While z<>Nil Do
Begin
Write(z^.data,' ');
z:=z^.next
End
End;
Ее рекурсивная реализация:
Procedure Print (z:pt);
Begin
If z<>Nil Then Begin
Write(z^.data,' ');
Print(z^.next)
End
End;
Вставить элемент в список можно в его начало, конец и средину. Разберем эти случаи.
1. Вставка элемента в начало списка.
Procedure Ins_begin(Var first:pt; el:Integer);
Var new_first:pt;
Begin
New(new_first);
new_first^.next:=first;
new_first^.data:=el;
first:=new_first;
End;
2. Вставка в конец списка
Procedure Ins_end(Var last:pt; el:Integer);
Begin
New(last^.next);
last:=last^.next;
last^.data:=el;
last^.next:=Nil
End;
3. Вставка в середину списка
Очевидно, что для вставки элемента в список необходимо знать, как минимум, адрес предшествующего элемента списка, т. е. элемента, после которого осуществляется вставка. Мы считаем, что этот элемент не последний. При вставке разрывается существующая связь и появляются две новые связи.
|
|
|
Пусть мы создаем упорядоченный по неубыванию список элементов (информационная часть любого элемента списка меньше информационных частей следующих за ним элементов списка или равна им). Для того, чтобы найти место для вставки очередного элемента, следует просматривать элементы списка до тех пор, пока вставляемый элемент больше информационной части текущего элемента.
Procedure Ins_med(Var first:pt; el:Integer);
Var t,new_m:pt;
Begin
New(new_m);
t:=first;
While el>t^.next^.data Do t:=t^.next;
new_m^.next:=t^.next;
new_m^.data:=e;
t^.next:=new_m End;
И наконец, общий алгоритм вставки элемента в упорядоченный список.
Создаваемый список отличается от декларированного вначале тем, что он описывается двумя указателями: на первый и последний элементы списка.
Procedure Ins(Var first,last:pt; el:Integer);
Begin
If el<first^.data Then Ins_begin(first,el)
Else If el>last^.data Then Ins_end(last,el)
Else Ins_med(first,el);
End;
Ввод исходных данных при создании упорядоченного списка осуществляется с клавиатуры. Напомним, что признак конца файла (Eof = True) в этом случае вырабатывается при нажатии клавиш Ctrl + Z (если стандартной переменной CheckEof модуля Crt присвоено значение True). Все действия по организации ввода представлены в процедуре Solve.
Procedure Solve(Var first,last:pt);
Var el:Integer;
Begin
Write('First element: ');
Read(el);
If Not Eof Then Begin
first:=Nil; Ins_begin(first, el); last:=first
End
Else Begin first :=Nil; last :=Nil End;
While Not Eof Do
Begin
Write('Next: '); Read(el);
If Not Eof Then Ins(first,last,el)
End;
End;
Действия при удалении элемента из списка различны в зависимости от места удаляемого элемента: первый он или нет. Для сохранения структуры списка необходимо помнить адрес элемента списка, предшествующего удаляемому элементу (dx), а также запоминать адрес удаляемого элемента для корректного использования процедуры Dispose.
Приведем процедуру удаления всех элементов списка, информационная часть которых равна заданному числу el.
Procedure Del_el(Var first:pt; el:Integer);
Var t,x,dx:pt;
Begin
t:=first;{Переменная цикла.}
While toNil Do{покa список не просмотрен.}
If t^.data=el Т hen{Есть совпадение.}
If t=first Then
Begin
x:=first; {Удаляем первый элемент списка.}
First:=first^.next; {3апоминаем, ибо “кучу” засорять не следует.}
Dispose(x); {Изменяем значение указателя на первый элемент списка.}
t:=first; {Освобождаем место в “куче".}
{Переменная цикла изменила свое значение.}
End
Else Begin
x:=t;{3апоминаем адрес удаляемого элемента.}
t:=t^.next;
dx^.next:=t;{Удаление элемента не должно нарушать структуру списка, ключевой оператор процедуры} Dispose(x);
End
Else
Begin
dx:=t; t:=t^.next;
End;{Переход к следующему элементу списка. Адрес текущего запоминается в переменной dx.}
End;
4.3.4. Стеки
Стек является простейшей динамической структурой. Добавление элементов в стек и выборка из него выполняются из одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека.
Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым обслужен). Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.
Для работы со стеком используются две статические переменные: указатель на вершину стека и вспомогательный указатель.
var top, p : pnode;
Тип указателей должен соответствовать типу элементов стека.
Пример 1. Приведена программа, которая формирует стек из пяти целых чисел и их текстового представления и выводит его на экран. Функция занесения в стек по традиции называется push, а функция выборки — pop.
program Example_1;
const n = 5;
type pnode = ^node;
node = record { элемент стека }
d : word;
s : string;
p : pnode;
end;
var top : pnode; { указатель на вершину стека }
i : word;
s : string;
const text : array [1 .. n] of string = ('one', 'two', 'three', 'four', 'five');
{занесение в стек}
function push(top : pnode; d : word; const s : string) : pnode;
var p : pnode;
Begin
new(p);
p^.d := d; p^.s := s; p^.p := top;
push := p;
end;
{ ------ выборка из стека ----}
function pop(top : pnode; var d : word; var s : string) : pnode;
var p : pnode;
Begin
d := top^.d; s := top^.s;
pop := top^.p;
dispose(top);
end;
{ --- главная программа ---- }
Begin
top := nil;
for i := 1 to n do top := push(top, i, text[i]);
{ занесение в стек: }
while top <> nil do begin { выборка из стека: }
top := pop(top, i, s); writeln(i:2, s);
end;
end.
4.3.5. Очереди
Очередь — это динамическая структура данных, добавление элементов в которую выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым обслужен). В программировании очереди применяются очень широко — например, при моделировании, буферизованном вводе-выводе или диспетчеризации задач в операционной системе.
Для работы с очередью используются указатели на ее начало и конец, а также вспомогательный указатель:
var beg, fin, p : pnode;
Тип указателей должен соответствовать типу элементов, из которых состоит очередь.
Пример 2. Программа, которая формирует очередь из пяти целых чисел и их текстового представления и выводит еe на экран. Для разнообразия операции с очередью оформлены в виде процедур. Процедура начального формирования называется first, помещения в конец очереди — add, а выборки — get.
program Example_2;
const n = 5;
type pnode = ^node;
node = record { элемент очереди }
d : word;
s : string;
p : pnode;
end;
var beg, fin : pnode; { указатели на начало и конец очереди }
i:word;
s:string;
const text : array [1 .. n] of string = ('one', 'two', 'three', 'four', 'five');
{ начальное формирование очереди }
procedure first(var beg, fin : pnode; d : word; const s : string);
Begin
new(beg);
beg^.d := d; beg^.s := s; beg^.p := nil;
fin := beg;
end;
{ добавление элемента в конец }
procedure add(var fin : pnode; d : word; const s : string);
var p : pnode;
Begin
new(p);
p^.d := d; p^.s := s; p^.p := nil;
fin^.p := p;
fin := p;
end;
{ выборка элемента из начала }
procedure get(var beg : pnode; var d : word; var s : string);
var p : pnode;
Begin
d := beg^.d; s := beg^.s;
p := beg; beg := beg^.p;
dispose(p);
end;
{ главная программа }
Begin
{ занесение в очередь: }
first(beg, fin, 1, text[1]);
for i := 2 to 5 do add(fin, i, text[i]);
{ выборка из очереди: }
while beg <> nil do begin
get(beg, i, s);
writeln(i:2, s);
end;
end.
4.3.6. Деревья
Для того чтобы разобраться с динамической структурой «дерево» нужно вспомнить некоторые базовые понятия теории графов.
Граф — это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.
Если на каждом ребре задать направление, то граф будет ориентированный.
Рис. 35. Ориентированной граф
Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем. Замкнутый путь, состоящий из различных ребер, называется циклом.
Граф называется связным, если любые две его вершины соединены путем. Связный граф без циклов называется деревом.
На рис. 35 изображено дерево, в узлах которого располагаются символы. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.
Рис. 36. Пример структуры данных - дерево
Для дальнейшей работы с деревьями необходимо определить ряд понятий.
Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.
Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.
Количество непосредственных потомков внутренней вершины называется ее степенью.
Степенью дерева называется максимальная степень всех вершин.
Например:
· вершины F, D, Е являются непосредственными потомками вершины В;
· вершины F, D, E являются листьями;
· вершины С, G, Н — внутренние;
· степень вершины В — 3, а вершины Н — 1;
· степень дерева равна 3.
Двоичное дерево — это дерево, в котором из каждой вершины исходит, не более двух ребер.
Описание деревьев
Дерево — это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.
Для описания требуются ссылки. Опишем, как переменные с фиксированной структурой — сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве два поддерева - левое и правое.
Type TreeLink = ^Т r ее;
Tree—Record
Data: <mun данных >;
Left , Right : TreeLink ;
End;
Корень дерева опишем в разделе описания переменных:
Var kd: TreeLink;
Основные операции над деревом
К основным операциям над деревьями относятся:
· занесение элемента в дерево;
· обход дерева;
· удаление элемента из дерева.
Пример 1
Создать и вывести на экран дерево, элементы которого вводятся с клавиатуры и имеют целый тип. Причем для каждой вершины дерева во всех левых вершинах должны находиться числа меньшие, а в правой большие, чем числа, хранящиеся в этой вершине. Такое дерево называется деревом поиска.
Опишем процедуру вставки в дерево новой вершины. При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая, и правая связи новой вершины должны быть равны Nil. Когда дерево пусто, значение передаваемой в виде параметра ссылки равно Nil. В этом случае нужно изменить ее так, чтобы она указывала на новую вершину, которая была вставлена как корневая. При вставке второго элемента переданный из основной программы параметр t уже не будет равен Nil, и надо принимать решение о том, в какое поддерево необходимо вставить новую вершину.
Procedure InsTree(n:Integer; Var t:treelink);
Begin
If t=NIL Then Begin new(t);
With t^ Do Begin
Left:=NIL; right:=NIL; data:=n
End;
End
Else If n<=t^.data Then InsTree(n,t^.left)
Else InsTree(n,t^.right); End;
Опишем процедуру вывода значений элементов двоичного дерева на экран. Для этого необходимо выполнить полный обход дерева. При обходе дерева его отдельные вершины посещаются в определенном порядке. Вывод двоичного дерева можно производить рекурсивно, выполняя для каждой вершины три действия:
· вывод числа, хранящегося в узле;
· обход левого поддерева;
· обход правого поддерева.
Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:
· прямой вывод (сверху вниз);
· обратный вывод (слева направо);
· концевой вывод (снизу вверх).
Процедура обратного вывода дерева имеет следующий вид:
Procedure PrintTree(t:treelink);
Begin
If t <> NIL Then
Begin
PrintTree(t^.left);Write(t^.data:3);PrintTree(t^.right)
End; End;
Пример 2. Процедуры прямого и концевого вывода значений элементов дерева.
Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа treelink — значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.
Begin {основная программа}
Writeln('окончание ввода — э0');
kd:=NIL; Read(Digit); While Digit <>0 Do Begin
InsTree(Digit, kd);
Writeln('введите очередное число'); Read(Digit); End;
PrintTree(kd); End.
В дереве поиска можно найти место каждого элемента, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значений встречающихся данных.
Использование деревьев поиска значительно сокращает время решения задачи. В среднем для нахождения элемента в списке нужно просмотреть половину списка, то есть если в списке N элементов, то надо выполнить N\2 сравнений. Для поиска же заданного элемента в дереве при его правильной организации может потребоваться не более logN сравнений.
Правильно организованным деревом считается идеально сбалансированное дерево, то есть для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.
Пример 3. Формирование идеально сбалансированного дерево, элементами которого являются N чисел, вводимых с клавиатуры.
Поскольку требуется построить идеально сбалансированное дерево, то его узлы в процессе построения должны распределяться равномерно. Сформулируем правило равномерного распределения узлов при известном их числе:
1. Взять один узел в качестве корня.
2. Построить левое поддерево с числом узлов n1=Ndiv2 тем же способом.
3. Построить правое поддерево с числом узлов n2=N – n1 - 1 тем же способом.
Program Example_3;
Uses Crt;
Type Pt=^Node;
Node=Record
Data:Integer;
Left, Right: Pt; End;
Var n:integer
kd:Pt; f:text;
Function Tree(n:Integer):pt;
Var newnode:pt;
x, n1, n2:integer;
Begin
If n=0 Then Tree:=nil Else begin
N1:=n Div 2; n2:=n – n1 - 1;
Read(f, x); New(newnode);
With newnode^ Do Begin
Data:=x; Left:=Tree(n1); Right:=Tree(n2); End;
Tree: =newnode; End; End;
Procedure PrintTree(t:pt; h:Integer);
Var r.Integer;
Begin
If t<> Nil Then With t^ Do Begin
PrintTree(left, h+l);
For i:= 1 To h Do Write(' ');
Writeln(Data:6);
PrintTree(Right,h+l);
End; End;
Begin
Assign(f, 'Ex.pas'); Reset(f); Write('n='); Readln(n);
kd:=tree(n); printtree(kd, 0); End
Удаление из дерева
Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной или из нее выходит только одно ребро. Для этого нужно изменить соответствующую ссылку у предшествующей вершины. Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины. Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая:
· удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка);
· удаляемая вершина имеет не более одного поддерева (0 или 1);
· удаляемой вершины в дереве нет.
Попробуйте самостоятельно написать рекурсивные процедуры удаления вершин дерева.
4.3.7. Динамические массивы
При работе с обычными массивами очень часто возникает проблема указания точного количества элементов в нем. Решение этой проблемы – динамические массивы.
Динамическим называется массив, размер которого может меняться во время исполнения программы. Переменная типа динамический массив представляет собой ссылку. Поэтому динамический массив нуждается в инициализации (выделении памяти под элементы).
Описание
array of тип элементов (одномерный массив)
array [,] of тип элементов (двумерный массив)
Выделение памяти
1 способ
var
a: array of integer;
b: array [,] of real;
begin
a := new integer[5];
b := new real[4,3];
end.
a := new integer[3](1,2,3);
b := new real[4,3] ((1,2,3),(4,5,6),(7,8,9),(0,1,2));
2 способ
SetLength(a,10);
SetLength(b,5,3);
При повторном вызове старое содержимое массива сохраняется: var с: array of array of integer;
Инициализация:
SetLength( с ,5);
for i := 0 to 4 do
SetLength(c[i],3);
Например,
type IntArray = array of integer;
var с: array of IntArray;
...
c := new IntArray[5];
for i := 0 to 4 do
c[i] := new integer[3];
Длина массива (количество элементов в нем) возвращается стандартной функцией Length или свойством Length:
l := Length(a);
l := a.Length;
Для многомерных массивов длина по каждой размерности возвращается стандартной функцией Length с двумя параметрами или методом GetLength(i):
l := Length(a,0);
l := a.GetLength(0).
Контрольные вопросы
1. Какие типы относятся к порядковым?
2. Что такое массив? Опишите способы его описания.
3. Как правильно организовать ввод и вывод элементов двумерного массива?
4. Чем строки (string) отличаются от массивов? Чем они схожи?
5. При решении каких задач удобно использовать записи (record)?
6. Зачем использовать оператор присоединения?
7. Как описать и организовать ввод-вывод элементов множества?
8. Опишите этапы организации работы с файлами в программе на Паскале. Приведите операторы.
9. Для чего используют подпрограммы?
10. Чем процедура отличается от функции?
11. Чем удобны модули? Опишите структуру модуля на Паскале.
12. Что такое рекурсивный алгоритм? Можно ли его организовать без использования подпрограмм?
13. Что такое указатель? Что в нем хранится?
14. Опишите и дайте сравнительную характеристику динамических структур данных.
Задачи и упражнения
1. Дана целочисленная прямоугольная матрица. Определить количество столбцов, не содержащих ни одного нулевого элемента (оформить в виде функции).
2. Характеристикой строки целочисленной матрицы назовем сумму ее положительных четных элементов. Переставляя строки заданной матрицы, расположить их в соответствии с ростом характеристик (оформить в виде процедуры).
3. Разработать функцию, вычисляющую длину стороны по координатам двух точек. Разработать процедуру, вычисляющую площадь треугольника, заданного координатами вершин. Написать программу определения площади выпуклого многоугольника, заданного координатами вершин.
4. В файле 1 записаны нечетные страницы книги. В файле 2 — четные страницы. Собрать все страницы по порядку в одном файле. Количество строк во всех страницах одинаково и равно s.
5. В файле содержатся данные о фамилиях людей и годах их жизни. Разбить файл на несколько файлов, содержащих данные об определенном веке. Переписать в нужный файл фамилии людей, годы жизни которых приходились на соответствующий век. Если человек родился в одном, а жил в другом веке, то его фамилия должна попасть в два файла.
6. Список авторов, список литературных героев и список соответствия номера автора номерам героев представлены строками. Один автор может иметь несколько героев в списке. Сформировать одномерный массив, в котором герои и их авторы будут чередоваться. Например, Пушкин, Салтан, Пушкин, Онегин, Грибоедов, Чацкий и т.д.
7. Дано многозначное число. Определить множество цифр, которые встречаются в записи этого числа более одного раза.
8. Известны данные о 16-ти сотрудниках фирмы: фамилия и отношение в воинской службе (военнообязанный или нет). Напечатать фамилии всех военнообязанных сотрудников.
9. Известна информация о 30-ти клиентах пункта проката: фамилия, имя, отчество, адрес и домашний телефон. Известно также название предмета, взятого каждым из них напрокат (в виде: т – телевизор, х – холодильник и т. п.). Вывести на экран фамилию, имя и адрес клиентов, взявших напрокат телевизор.
10. Написать программу которая удалить из текста хранящегося в текстовом файле все дублирующие пробелы (т.е. между словами должно быть ровно по одному пробелу).
11. Написать и оттранслировать модуль для работы с симметричными относительно главной диагонали матрицами, представленными верхней треугольной матрицей. Должны быть предусмотрены операции: сложения, вычитания, умножения на число, произведения матриц, ввода и вывода матриц в полном и треугольном видах. Разработать документацию на него с описанием его назначения, формы, представления информации, включенных процедур, функций и алгоритмов работы.
12. Задан список слов. Написать программу, удаляющую из списка элементы с заданным слогом.
13. Написать программу для решения задачи коммивояжера. Коммивояжер должен выехать из первого города, посетить по раз в произвольном порядке города 2,3, …, n и вернуться в первый город. Расстояния между всеми городами известны. Требуется установить порядок обхода городов, чтобы путь коммивояжера был кратчайшим. Выбрать подходящую динамическую структуру для решения задачи. Обосновать выбор.
14. В текстовом файле находится текст, состоящий из слов. Написать программу, создающую список, содержащий частоту упоминания в тексте каждого слова.
15. Решить задачу используя рекурсию. Крестьянин пришел к царю и попросил: «Царь, позволь мне взять одно яблоко из твоего сада». Царь разрешил. Пошел крестьянин к саду и видит: весь сад огорожен тройным забором, в каждом заборе только одни ворота и около каждых ворот стоит сторож.
«Царь разрешил мне взять одно яблоко из сада», - сказал крестьянин сторожу у первых ворот.
«Возьми, но при выходе отдашь мне половину тех яблок, которые у тебя будут, и еще одно», — ответил сторож. То же сказали и другие сторожа, охранявшие ворота.
Сколько яблок должен взять крестьянин, чтобы, отдав положенные части трем сторожам, унести домой одно яблоко? Обобщить решение задачи на случай n заборов и m яблок. Упражнения для выполнения без компьютера
Упражнения для выполнения без компьютера
16. Определить, какая задача решается в предложенном. фрагменте программы. Назвать все операторы и типы данных, использованные в нем, рассказать, как они работают:
const n=10;
var u, v: array [1..n] of integer;
w: array [0..n] of integer;
j, k, t: integer;
begin k: =0;
for j:=n downto 1 do
begin t:=u[j]+v[j]+ k;
w[j]:=t mod 10;
k:=t div 10;
end;
w[0]:=k;
end.
17. Если массив описан так:
type mas=array[1..3] of array [1..5] of integer;
var a,b,c:mas;,
то возможны ли присваивания а[2]:=b[1]; a[i][j]:=c[i,j];.
18. Какую задачу решают предложенные фрагменты программ? Указать возможные ошибки при их исполнении.
1) for i:=1 to length (s) div 2 do
If not odd(i) then delete (s, i, 1) ;
2) i:=2;
While i<=length(s) div 2 do
Begin delete(s,i,1);
i:=i+2;
End;
3) i:= length(s) div 2;
While i>1 do
Begin delete (s,i,1);
i:=i-2;
19. Дано описание функции:
Function f(x,y:real):real;
Begin if x>=y
Then f:=(x+y)|2
Else f:=f(f(x+2,y-1), f(x+1, y-2));
End.
Определить f(1, 10). Каким более простым способом можно представить и вычислить f(a,b)?
20. Исправить ошибки в программе:
Type katja=record s:real;
n:integer;
i:integer;
a:array[1..100] of real
end;
var a:katja;
i:integer;
begin
write('Сколько элементов массива примут учасnbt в вычислениях (<100)');
readln(a.n);
for i:=l to a.n do
with a do readln(a[i]);
a.s:=0;
for i:=l to a.n do a.s:=a.s+a.a[i];
write(a.s:7:3);
end.
Дата добавления: 2018-09-22; просмотров: 299; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!