Занятие 6. Примеры решения задач с применением динамической структуры кольцо. Творческая работа.

Задание. Рассмотрите приведенные примеры задач, решенные с помощью динамической структуры – кольцо. Наберите их на компьютере, проверьте их действие, вставьте комментарий.

Задача 1. N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая при этом круг. Определить порядок удаления ребят из круга.

Для хранения данных об участниках игры используется список.

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

Program Schitalka;

Type

Children = ^Child;

Child = record

Data : integer;

Next : Children;

end;

Var

Circl, p, Temp : Children;

i, j, NumName : integer;

text : string;

Function NumSlov(Var S : string) : integer;

Var

i, d : integer;

Begin

d := 0;

i := 1;

while i < Length(S) do

begin

while S[i] = ' ' do

Inc(i);

while S[i] <> ' ' do

Inc(i);

d := d+1;

end;

if S[Length(S)] = ''

then

d := d-1;

NumSlov := d;

End;

Procedure AddName(Var Old, Young : Children);

Begin

Young^.Next := Old;

Young^.Prev := Old^.Prev;

Old^.Prev^.Next := Young;

Old^.Prev := Young;

End;

Procedure DeleteName(Var Old : Children);

Begin

Old^.Next^.Prev := Old^.Prev;

Old^.Prev^.Next := Old^.Next;

End;

Begin

new(Circl);

Circl^.Next := Circl;

Circl^.Prev := Circl;

Circl^.Name := '';

writeln('Считалка');

writeln('Введите текст считалки >');

readln(text);

writeln('Сколько человек в кругу? >');

readln(NumName);

if NumName>0

then

begin

write('Введите ',i,'-е имя: ');

new(p);

readln(p^.name);

temp := head^.next;

while temp <> head do

temp := temp^.next;

AddName(temp, p);

end;

for i := 1 to NumName-1 do

begin

temp := head;

for j := 1 to NumSlov(text) do

begin

temp := temp^.next;

if temp^.name = ''

then

temp :=temp^.next;

end;

writeln(temp^.name, '- вышел');

deleteName(temp);

end;

writeln(head^.next^.name, '- остался');

End.

Пример 2. Вывести на экран работающий светофор.

Program GrushinK;

Uses

Crt, Graph;

Type

TypeCircle = ^K;

K = record

Data : char;

Next : TypeCircle;

end;

Const

XX = 80;

R = 50;

Var

Svetofor, x : TypeCircle;

FraphDriver, GraphMode, Y : integer;

Procedure Picture;

Begin

SetViewPort(240, 1, 400, 477, ClipOff);

Line(0, 1, 0, 477);

Line(160, 1, 160, 477);

Line(0, 1, 160, 1);

Line(0, 477, 160, 477);

Line(0, 150, 156, 150);

Line(0, 330, 156, 330);

Line(-240, 480, 0, 100);

Line(400, 480, 160, 100);

Line(380, 460, 160, 460);

Line(160, 440, 368, 440);

Line(368, 440, 380, 460);

Line(-220, 460, -208, 440);

SetFillStyle(1, White);

FloodFill(375, 455, White);

FloodFill(-215, 455, White);

SetFillStyle(7, 6);

FloodFill(-230, 200, White);

SetColor(4);

Line(-240, 150, -120, -1);

Line(400, 150, 240, -1);

SetColor(15);

SetFillStyle(9, 4);

FloodFill(-240, 0, 4);

FloodFill(390, 10, 4);

SetFillStyle(1, 8);

FloodFill(-100, 470, White);

Y := 74;

Circle(XX, Y, R);

Y := 240;

Circle(XX, Y, R);

Y := 405;

Circle(XX, Y, R);

SetFillStyle(9, 6);

FloodFill(5, 5, White);

End;

Procedure Yellow(Y : integer);

Begin

Picture;

Y := 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(850);

ClearViewPort;

End;

Procedure Green(Y : integer);

Begin

Picture;

Y := 405;

SetFillStyle(1, 2);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red Yellow(Y : integer);

Begin

Picture;

Y := 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red(Y : integer);

Begin

Picture;

Y := 74;

SetFillStyle(1, 4);

FloodFill(XX, Y, 15);

Delay(2000);

ClearViewPort;

End;

Procedure Vibor;

Begin

case x^.Data of

'R' : Red(Y);

'2' : Red Yellow(Y);

'G' : Green(Y);

'Y' : Yellow(Y);

End;

Begin

GraphDriver := Detect;

InitGraph(GraphDriver, GraphMode, '..\BGI');

new(x);

u := x;

x^.Data := 'R';

new(x^.Next);

x := x^.Next;

x^.Data := '2';

new(x^.Next);

x := x^.Next;

x^.Data := 'G';

new(x^.Next);

x := x^.Next;

x^.Data := 'Y';

x^.Next := u;

x := u;

while not KeyPressed do

begin

Vibor;

x := x^.Next;

end;

End.

Задание. Придумайте интересную задачу из жизни и решите ее с помощью динамической структуры кольцо.

Список