Вариант 25 no1 на рисунке — схема дорог, связывающих города а, б, в, г, д, е, ж, з, и, к. по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. сколько суще- ствует различных путей из города а в город к?
Отмечу,что в этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков.
тогда для вершины Б=А=1
Г=А=1
В=А+Б+Г=1+1+1=3
Д=Б+В=1+3=4
Е=В+Г=3+1=4
Ж=В+Д=3+4=7
З=Е+В+Ж=4+3+7=14
И=Ж+Д=7+4=11
К=И+Ж+З=11+7+14=32
Очевидно, что мы могли посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитали индексы всех вершин.
procedure show(x: array100; n: integer); var i:integer; begin writeln(); writeln('Вывод массива[',n,']:'); for i := 1 to n do write(x[i], ' '); writeln(); end;
begin n := 20; max := -200; min := 200;
for i := 1 to n do begin x[i] := random(2*n) - n; end; show(x, n);
for i := 1 to n do begin if (x[i] > 0) and (x[i] mod 2 = 1) then begin if x[i] > max then max := x[i]; if x[i] < min then min := x[i]; end; end; writeln('Max = ', max, ' Min = ', min);
i := 1; while i <= n do begin if x[i] = 0 then begin for j := i + 1 to n do x[j - 1] := x[j]; n := n - 1; end else i := i + 1; end; show(x,n); end.
procedure show(x: array100; n: integer); var i:integer; begin writeln(); writeln('Вывод массива[',n,']:'); for i := 1 to n do write(x[i], ' '); writeln(); end;
begin n := 20; max := -200; min := 200;
for i := 1 to n do begin x[i] := random(2*n) - n; end; show(x, n);
for i := 1 to n do begin if (x[i] > 0) and (x[i] mod 2 = 1) then begin if x[i] > max then max := x[i]; if x[i] < min then min := x[i]; end; end; writeln('Max = ', max, ' Min = ', min);
i := 1; while i <= n do begin if x[i] = 0 then begin for j := i + 1 to n do x[j - 1] := x[j]; n := n - 1; end else i := i + 1; end; show(x,n); end.
32
Пояснение:
дополнительно смотреть изображение
Отмечу,что в этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков.
тогда для вершины Б=А=1
Г=А=1
В=А+Б+Г=1+1+1=3
Д=Б+В=1+3=4
Е=В+Г=3+1=4
Ж=В+Д=3+4=7
З=Е+В+Ж=4+3+7=14
И=Ж+Д=7+4=11
К=И+Ж+З=11+7+14=32
Очевидно, что мы могли посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитали индексы всех вершин.
Индекс вершины К и будет ответом задачи.