ВОПРОС. Стр. 75 – 78 (мотивационные задач, матрица смежности) И.В

Стр. 75 – 78 (мотивационные задач, матрица смежности) И.В. Николаева, А.А. Мартынова. « Теория и методика обучения информатике. Содержательная линия «Формализация и моделирование»

Пректные задания

Задание 1.

a. Привести примеры графов, задать графы с использованием диаграмм. Представить заданные графы матрицей смежности, матрицей инцидентности, перечнем рёбер, списком инциденций.

b. Разработать программы ввода графа в память компьютера для каждого способа представления графа. Для контроля коррекции ввода обеспечить вывод каждого описания графа на экран.

c. Разработать процедуры преобразований способов представления графов.

Задание 2.

Составьте компьютерную модель для ответа на вопросы задачи. В некоторой стране n городов, между некоторыми из них летают самолеты. Авиатрассы расположены так, что из любого города можно перелететь в любой другой (возможно с пересадками). Определите можно ли из города i1 добраться в город i2, делая не более 1,2 или 3 пересадок. Выведите на экран все маршруты из города i1 в город i2 и длину каждого из этих маршрутов; каково минимальное число пересадок, определите длину кратчайшего маршрута; отсортируйте длины полученных маршрутов. (Кушниренко, ОИВТ, с. 170 – 171, с. 177, задачи 7,8). При выполнении проекта учащимся предложить выбор способа оформления проекта компьютерной модели, выбор языка для реализации проекта, желательно усложнить содержательную постановку задачи.

Пример 1. Напишите программу нахождения маршрута перелёта пассажира из города i1 в город i2, совершив не более 1 пересадки.

program network;

uses crt;

const n=3;

type tway=array[1..n, 1..n] of 0..1;

tdist= array[1..n, 1..n] of integer;

tname= array[1..n] of string[15];

const

way:tway= ((0,0,1), (0,0,1),(1,1,1));

dist:tdist = ((0,0,33),(0,0,4),(33,4,12));

name: tname = ('Орёл', 'Самара', 'Пенза');

var

i1,i2:string[7];

i,j,t:integer;

p:0..n;

k1,k2:1..n;

k:boolean;

begin

write('введите начальный пункт перелёта ');

readln(i1);

write('введите конечный пункт перелёта ');

readln(i2);

for i:=1 to n do

begin

if i1=name[i] then k1:=i;

if i2=name[i] then k2:=i;

end;

if way [k1,k2] = 1

then writeln (' из города ',i1, ' в город ', i2,' есть прямой рейс')

else

begin

k:= false;

p:=0;

while (p<=n) and (not k) do

begin

p:=p+1;

k:= ((way[k1,p]=1) and (way[p,k2]=1));

end;

if k

then

writeln (' есть маршрут с одной пересадкой в городе ', name[p])

else

writeln (' c одной пересадкой добраться нельзя ');

end

end.

28.ВОПРОС.

СТР. 65 – 71

Стр. 183 – ….Битовые операции. Е. АНДРЕЕВА, СИСТЕМЫ счисления и компьютерная арифметика

Дата добавления: 2015-07-10