Постановка задачи N – кол-во деревьев в дендропарке, - презентация

1

2 Постановка задачи N – кол-во деревьев в дендропарке, <=100 M i – номера видов деревьев (N штук), <=100 K – кол-во деревьев, встреченных детьми, <=100 L i – номера видов деревьев в том порядке, в котором дети их встречали Известно какие деревья (по номерам) с какими деревьями соединены дорожками.

3 Пример входных данных

4 Идея решения Двумерный массив N на N derevo derevo [i,j] – указывает на связь дорожкой дерева с номером i с деревом с номером j Одномерный массив vid – хранить инф-ию о видах деревьев дерева с номером i. Одномерный массив s – хранить инф-ию о видах деревьев в том порядке, в котором дети их встречали.

5 Пример входных данных vid s derevo

6 Пример входных данных vid s derevo

7 Реализация решения. Ввод данных. BEGIN assign(inp,'input.txt'); reset(inp); readln(inp,n); for i:=1 to n do read(inp, vid[i]); readln(inp); readln(inp,k); for i:=1 to k do read(inp,s[i]); readln(inp); for i:=1 to n do begin while not eoln(inp) do begin read(inp,l); derevo[i,l]:= vid[l]; end; readln(inp); end;

8 Dl:=2; x:=0; for i:=1 to n do if vid[i]=s[1] then poisk(Dl,i); Вывод ответа writeln(x); close(inp); END. Реализация решения. Основная часть. Var n, i, k, Dl, x : byte; vid, s : array[1..100] of byte; derevo : array[1..100,1..100] of byte; input : text;

9 Procedure poisk(var L, r : byte); Var j:byte; Begin if L<>K then begin for j:=1 to n do if derevo[r,j]=s[t] then begin t:=t+1; poisk(t,j); t:=t-1; end; end else for j:=1 to n do if derevo [r,j]=s[t] then x:=x+1; End; Реализация решения. Процедура.

10 НО 1. Что делать, когда …. 2. Что делать, если N будет больше 1000?