В некотором государстве есть n городов. Между некоторыми парами городов проложены дороги. Каждая из дорог имеет длину 100 км. Известно, что из любого города можно добраться по последовательности дорог в любой другой, причём единственным способом. а) Что можно сказать о числе дорог в таком государстве? б) Пусть города занумерованы числами от 1 до n, а каждая дорога задаётся двумя числами – номерами городов, которые она соединяет. Напишите на любом известном вам языке программирования программу, которая находит два города, кратчайший путь между которыми имеет наибольшую возможную длину среди всех кратчайших путей в данном государстве. в) Оцените время работы вашей программы в зависимости от n. Оценку количества действий укажите в комментариях к коду. Может ли существовать алгоритм, который решает задачу оптимальнее? Если да, то постарайтесь его найти. Ответы на вопросы о количестве действий и существовании оптимального алгоритма напишите в комментариях внутри вашей программы.
1) количество дорог строго n-12) алгоритм простой 1. Выбираем любую вершину и при помощи волнового алгоритма ищем наиболее удаленную вершину А 2. Из вершины А волновым алгоритмом ищем наиболее удаленную вершину Б 3. А-Б - максимальный путь3) волновой алгоритм в дереве выполняется за O(n), в нашем случае получаем O(C*n) что равно O(n)саму программу на Python набросаю чуть позжекстати Alviko прав, все эти оценки производительности в школе не дают
⭐⭐⭐⭐⭐ Лучший ответ на вопрос «В некотором государстве есть n городов. Между некоторыми парами городов проложены дороги. Каждая из дорог имеет длину 100 км. Известно, что из любого города можно добраться по последовательности дорог в любой другой, причём единственным способом. а) Что можно сказать о числе дорог в таком государстве? б) Пусть города занумерованы числами от 1 до n, а каждая дорога задаётся двумя числами – номерами городов, которые она соединяет. Напишите на любом известном вам языке программирования программу, которая находит два города, кратчайший путь между которыми имеет наибольшую возможную длину среди всех кратчайших путей в данном государстве. в) Оцените время работы вашей программы в зависимости от n. Оценку количества действий укажите в комментариях к коду. Может ли существовать алгоритм, который решает задачу оптимальнее? Если да, то постарайтесь его найти. Ответы на вопросы о количестве действий и существовании оптимального алгоритма напишите в комментариях внутри вашей программы.» от пользователя Оксана Стрельникова в разделе Экономика. Задавайте вопросы и делитесь своими знаниями.
Открой этот вопрос на телефоне - включи камеру и наведи на QR-код!