sbarichev330
?>

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

Информатика

Ответы

tribunskavictory
1)  количество дорог строго n-1 2)  алгоритм  простой       1. выбираем любую вершину и при волнового алгоритма ищем наиболее удаленную вершину а       2. из вершины а волновым алгоритмом ищем наиболее удаленную вершину б       3. а-б  - максимальный путь 3)  волновой  алгоритм  в  дереве  выполняется  за  o(n),  в нашем случае получаем o(c*n) что равно o(n) саму  программу на python набросаю чуть  позже кстати  alviko  прав,  все  эти  оценки  производительности  в школе не
Salnikov1730
Интересная, исследуем её. понятно, что программ будет 8. но в спрашивается, сколько разных чисел получится из двойки, поэтому нужно исследовать каждую программу 1. +++     +2) +2) +2 = 8 2. ++*       +2) +2) *3 = 18 3. +*+       +2) *3) +2  = 14 4. *++       *3) +2) +2 = 10 5. ***       *3)   *3)   *3 = 54  6. **+       *3)   *3) +2 = 20 7. *+*       *3) +2)   *3 = 24 8. +**       +2) *3)   *3 = 36 вот только теперь можно сказать что из 2 можно получить 8 разных чисел. ps арифметику проверь, писал напрямую в экран, мог допустить неточность.
Zimin1111
1.файл размером 36 мбайт передаётся через некоторое соединение за 3 минуты. определите размер файла (в мбайт), который можно передать через это же соединение за 240 секунд. ответе укажите одно число — размер файла в мбайт.  2.файл размером 9 кбайт передаётся через некоторое соединение за 36 секунд. определите, за сколько секунд можно передать этот же файл через соединение, скорость которого на 1024 бит в секунду больше.  3. файл размером 24 кбайт передаётся через некоторое соединение за 80 секунд. определите размер файла (в кбайтах), который можно передать через это же соединение за 2 минуты. в ответе укажите одно число — размер файла в кбайтах.  4. файл размером 2 мбайта передаётся через некоторое соединение за 16 секунд. определите время в секундах, за которое можно передать через то же самое соединение файл размером 4096 кбайт.  5. файл размером 80 кбайт передаётся через некоторое соединение со скоростью 2048 бит в секунду. определите размер файла (в кбайт), который можно передать за то же время через другое соединение со скоростью 768 бит в секунду.  писать все и дано тоже решите плис

Ответить на вопрос

Поделитесь своими знаниями, ответьте на вопрос:

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

Популярные вопросы в разделе

juliaWinter
Less2014
konnovakat1
Vgubushkin
VladimirovichKazakova1202
oserdyuk41
Natacha3636672
vickuznetsova8677
Vladimirovich-Aleksandrovna96
Gennadevna_Baidalina131
P7Y7V7
АндреевичЮлия
olgaprevisokova302
artmasterstyle
golovins3