Часто в задачах встречается следующая конструкция — есть дома и дороги, их соединяющие; у каждой дороги есть длина. По другой терминологии такая конструкция называется графом, дома называются «вершинами», дороги — «ребрами» или «дугами», а длина дороги «весом ребра» или «весом дуги».
Таким образом фраза ‘Найти минимальный вес пути между вершинами s и k в графе’ может быть переведена так: ‘Есть дома и дороги их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам’. Пропускная способность дуги (i,j) означает, например, сколько груза может быть перевезено по дороге (по дуге) (i,j) за единицу времени); а поток по дуге (i,j) — это сколько перевозится сейчас на самом деле).
Часто используют следующие обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i; Д(x(i))- множество вершин, из которых есть дуга в вершину i.
Пусть в графе N вершин.
Как правильно описывать задачу на разработку
Длины дуг обычно заносятся в матрицу (назовем ее C) размера N на N, называемой матрицей смежности:
var С: array [1..N,1..N] of integer;
Элемент C[i,j] этой матрицы равен длине дуги (дороги>), соединяющей вершины i и j, и равен (например) 0 или -1, если такой дуги нет. Если дорога двунаправленная (дуга неориентированная), то очевидно, что C[i,j]=C[j,i].
Алгоритм расстановки пометок для задачи о максимальном (от s к t) потоке.
А. Расстановка пометок. Вершина может находиться в одном из трех состояний: вершине приписана пометка и вершина просмотрена ( т.е. она имеет пометку и все смежные с ней вершины «обработаны»), пометка приписана, но вершина не просмотрена ( т.е. она имеет пометку, но не все смежные с ней вершины обработаны), вершина не имеет пометки.
Пометка произвольной вершины x(i) состоит из двух частей и имеет один из двух видов: (+x(j),m) или (-x(j),m). Часть +x(j) пометки первого типа означает, что поток допускает увеличение вдоль дуги (x(j),x(i)). Часть -x(j) пометки другого типа означает, что поток может быть уменьшен вдоль дуги (x(i),x(j)).
В обоих случаях m задает максимальную величину дополнительного потока, который может протекать от s к x(i) вдоль построенной увеличивающей цепи потока. Присвоение пометки вершине x(i) соответствует нахождению увеличивающей цепи потока от s к x(i). Сначала все вершины не имеют пометок.
- Шаг 1. Присвоить вершине s пометку (+s,m(s)=бесконечность). Вершине s присвоена пометка и она просмотрена, все остальные вершины без пометок.
- Шаг 2. Взять некоторую непросмотренную вершину с пометкой; пусть ее пометка будет (+-x(k),m(x(i))) (+- обозначает, что перед x(k) может стоять как плюс, так и минус).
(I) Каждой помеченной вершине x(j), принадлежащей Г(x(i)), для которой c(i,j)
(II) Каждой непомеченной вершине x(j), принадлежащей Д(x), для которой c(i,j)>0, присвоить пометку (-x(i),m(x(j))), где
(Теперь вершина x(i) и помечена, и просмотрена, а вершины x(j), пометки которым присвоены в (I) и (II), являются непросмотренными.) Обозначить каким-либо способом, что вершина x(i) просмотрена.
Краткая запись задачи. Как сделать краткую запись к задаче?
- Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t будет помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока c. Здесь следует отметить, что если X(0)-множество помеченных вершин, а X'(0) — множество не помеченных, то ( X(0) —> X'(0) ) является минимальным разрезом.
Б. Увеличение потока.
- Шаг 4. Положить x=t и перейти к шагу 5.
- Шаг 5. (I) Если пометка в вершине x имеет вид (+z,m(x)), то изменить поток вдоль дуги (z,x) c c(z,x) на c(z,x)+m(t). (II) Если пометка в вершине x имеет вид (-x,z) c c(x,z) на c(x,z)-m(t).
- Шаг 6. Если z=s, то стереть все пометки и вернуться к шагу 1, чтобы начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если z<>s, то взять x=z и вернуть к шагу 5.
Обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i; Д(x(i))- множество вершин, из которых есть дуга в вершину i; c(i,j) — это пропускная способность дуги (т.е., например, сколько груза может быть перевезено по дороге (по дуге) (i,j) за единицу времени); q(i,j) — поток по дуге (i,j) (т.е. сколько перевозится сейчас на самом деле).
Кратчайшее расстояние от вершины нач до остальных вершин.
C[i,j]- длина ребра(i,j), С[i,j]>=0 (если ребра нет, то его длина полагается равной бесконечности).
D[i]- кратчайшее текущее расстояние от вершины нач до вершины i.
флаг[i]- информация о просмотре вершины i: 0 — если вершина не просмотрена, 1 — если просмотрена. Если вершина просмотрена, то для нее D[i] есть наикратчайшее расстояние от вершины нач до вершины i.
предок[i]- информация о номере вершины, предшествующей вершине i в кратчайшем пути от вершины нач.
минрас — это минимальное расстояние.
для i от 1 до N выполнять нц предок[i]:=нач; флаг[i]:=0; D[i]:=C[нач,i] кц флаг[нач]:=1; предок[нач]:=0 для i от 1 до N-1 выполнять нц минрас:=бесконечность; для j от 1 до N выполнять если (флаг[j]=0 и (минрас > D[j]) то минрас:=D[j]; k:=j; все флаг[k]:=1; для j от 1 до N выполнять если флаг[j]=0 и D[j]>D[k]+C[k,j] то D[j]:=D[k]+C[k,j] предок[j]:=k; все кц
Задан набор неповторяющихся пар (A i ,A j ), A i , A j принадлежат множеству А=. Необходимо составить цепочку максимальной длины по правилу
(A i ,A j )+(A j ,Ak)=(A i ,A j ,A k ).
При образовании этой цепочки любая пара может быть использована не более одного раза.
Написать программу, которая:
1) при заданных N,M и сети дорог единичной длины (все имеющиеся A(i,j)=1) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны.
2) Выполнить те же действия, что и в п. 1, но только для различных значений A(i,j).
Примечание: В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.
Требование к вводу-выводу:
1) Все входные данные — целые неотрицательные числа;
2) при задании сети дорог должно быть указано количество дорог — K и пункты их начала и конца в виде пар (i,j).
На плоскости расположено N точек. Имеется робот, который двигается следующим образом. Стартуя с некоторой начальной точки и имея некоторое начальное направление, робот движется до первой встреченной на его пути точки, изменяя в ней свое текущее направление на 90 градусов, т.е. поворачивая налево или направо. После этого он продолжает движение аналогично. Если робот достиг начальной точки, либо не может достичь новой точки (которую он еще не посещал), то он останавливается.
Определить, может ли робот посетить все N точек, если:
- Определены начальные точка и направление робота.
- Определена начальная точка, а направление робота можно выбирать.
- Начальную точку и направление робота можно выбирать.
Координаты точек — целые числа, угол измеряется в радианах относительно оси ОХ.
Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по
Лабиринт задается матрицей смежности N*N, где C(i,j)=1, если узел i связан узлом j посредством дороги. Часть узлов назначается входами, часть — выходами. Входы и выходы задаются последовательностями узлов X(1). X(p) и Y(1). Y(k) соответственно.
Найти максимальное число людей, которых можно провести от
входов до выходов таким образом, чтобы:
а) их пути не пересекались по дорогам, но могут пеpесекаться по узлам;
б) их пути не пересекались по узлам;
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен ( если такой набоp не один, то любой из них ) и количество шестеpен, пpишедших в движение.
На фигуре 1.показана вычислительная система, содержащая достаточное количество процессоров, использующих общую память из 26 числовых переменных A,B,C. Z. Система работает шагами. На каждом шаге, каждый процессор выполняет либо оператор присваивания либо пустой оператор. Оператор присваивания — это конструкция вида
где арифметическое выражение без скобок и содержит не более 2 переменных и арифметические операции. Процессоры вычисляют выражения и присваивают их значения переменным из левых частей операторов, а потом приступают к следующим операторам (при том одновременно). Не допускается одновременное выполнение 2 или больше операторов присваивания с одинаковой левой частью. Пустой оператор обозначаем символом https://algolist.ru/olimp/gra_prb.php» target=»_blank»]algolist.ru[/mask_link]
Программирование ветвящихся алгоритмов
план-конспект урока по информатике и икт (10 класс) на тему
Задание. Для каждой задачи составить программу с ветвящейся структурой, используя условный оператор IF.
- Даны два угла треугольника (в градусах). Определить, существует ли такой треугольник. Если да, то прямоугольный ли он.
writeln(‘введите два угла треугольника’);
if (a+b)>180 then write(‘треугольник не существует’)
begin writeln(‘треугольник существует’);
if (a=90) or (b=90) or (c=90) then
else writeln(‘треугольник не прямоугольный’);
- На плоскости XOY задана своими координатами точка А. Указать, где она расположена: на какой оси или в какой координатной четверти.
writeln(‘введите координаты точки А’);
if (x=0)and (y=0) then write(‘в центре координат’)
else if (y=0) then write(‘на оси x’)
else if (x=0) then write(‘на оси y’)
else if (x>0) then
if y>0 then write(‘в первой четверти’)
else write(‘в четвертой четверти’)
else begin if y>0 then write (‘во второй четверти’)
else write (‘в третьей четверти’);
- Грузовой автомобиль выехал из одного города в другой со скоростью V1 км/ч. Через t ч в этом же направлении выехал легковой автомобиль со скоростью v2 км/ч. Составить программу, определяющую, догонит ли легковой автомобиль грузовой через t ч после своего выезда.
if (v2*t1>=v1*(t+t1)) then write(‘догонит’) else write (‘не догонит’);
- Написать программу нахождения суммы большего и меньшего из 3 чисел.
write (‘введите три числа’);
else if (b>a) and (b>c) then max:=b
- Написать программу, распознающую по длинам сторон среди всех треугольников прямоугольные. Если таковых нет, то вычислить величину угла С.
writeln(‘введите стороны треугольника’);
if (a>b) and(a>c) then f:=(a*a=c*c+b*b)
else if (b>c) and (b>a) then f:=(b*b=a*a+c*c)
if f=true then writeln (‘Треугольник прямоугольный’)
writeln (‘треугольник не прямоугольный’);
writeln(‘Угол С равен: ‘,uc:8:2);
- Составить программу, осуществляющую перевод величин из радианной меры в градусную или наоборот. Программа должна запрашивать, какой перевод нужно осуществить, и выполнять указанное действие.
writeln(‘Перевести в радианы или градусы р/г:’);
if (s=’р’)or (s=’r’)or (s=’R’)or (s=’Р’) then
writeln (‘введите количество градусов’);
write(‘введите количество радиан:’);
По теме: методические разработки, презентации и конспекты
Ветвящиеся алгоритмы. Безусловный переход
Представляю Вашему вниманию конспект урока по теме «Ветвящиеся алгоритмы. Безусловный переход». Материал занятия способствует формированию первоначальных представлений о ветвящихся алгоритмах, реализо.
Лекция «Программирование» Линейные алгоритмы
В данной лекции по дисциплине «Программирование» представлен материал для программирования линейных конструкция в языке С++.
Программирование линейных алгоритмов. Самостоятельная работа по информатике в 9 классе.
Программирование ветвящихся алгоритмов. Самостоятельная работа по информатике в 9 классе.
Язык программирования Паскаль. Алгоритмы и программы.
Представленная разработка составлена в виде контрольно-измерительного материала (каталог задач по ЕГЭ В2) для курса информатики и ИКТ 10 класса по теме «Язык программирования».
Проект «Ветвящийся алгоритм»
Проект направлен на изучение базовой алгоритмической структуры «ветвления», в полной и неполной формах, а также для отработки навыков самостоятельной практической работы описания разветвляю.
Самостоятельная работа по информатике в 9 классе по теме «Программирование ветвящихся алгоритмов»
Самостоятельная работапо информатике в 9 классепо теме «Программирование ветвящихся алгоритмов».
Источник: nsportal.ru
Для каждой задачи составить программу, содержащую ветвления и определяющую принадлежит ли точка с координатами (X, Y) заштрихованной области
#include typedef long double ld;using namespace std;int main() < ld x, y; cin >> x >> y; if (x*x + y*y >= 9 x*x + y*y = 0) cout
Программа выводит YES, если точка принадлежит закрашенной области, иначе NO.
Язык программирования C++.
Оцени ответ
Не нашёл ответ?
Если тебя не устраивает ответ или его нет, то попробуй воспользоваться поиском на сайте и найти похожие ответы по предмету Информатика.
Источник: domashechka.ru