В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
JIucenok
JIucenok
13.09.2020 09:52 •  Информатика

Внекотором государстве есть n городов. между некоторыми парами городов проложены дороги. каждая из дорог имеет длину 100 км. известно, что из любого города можно добраться по последовательности дорог в любой другой, причём единственным а) что можно сказать о числе дорог в таком государстве? б) пусть города занумерованы числами от 1 до n, а каждая дорога задаётся двумя числами – номерами городов, которые она соединяет. напишите на любом известном вам языке программирования программу, которая находит два города, кратчайший путь между которыми имеет наибольшую возможную длину среди всех кратчайших путей в данном государстве. в) оцените время работы вашей программы в зависимости от n. оценку количества действий укажите в комментариях к коду. может ли существовать алгоритм, который решает оптимальнее? если да, то постарайтесь его найти. ответы на вопросы о количестве действий и существовании оптимального алгоритма напишите в комментариях внутри вашей программы.

Показать ответ
Ответ:
зяйка75542
зяйка75542
01.10.2020 22:31
1) количество дорог строго n-1
2) алгоритм простой
    1. Выбираем любую вершину и при волнового алгоритма ищем наиболее удаленную вершину А
    2. Из вершины А волновым алгоритмом ищем наиболее удаленную вершину Б
    3. А-Б - максимальный путь
3) волновой алгоритм в дереве выполняется за O(n), в нашем случае получаем O(C*n) что равно O(n)

саму программу на Python набросаю чуть позже
кстати Alviko прав, все эти оценки производительности в школе не дают
0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота