сервис вопросов и ответовВ некотором государстве есть n городов. Между некоторыми парами городов проложены дороги. Каждая из дорог имеет длину 100 км. Известно, что из любого
5-9 класс|
|
города можно добраться по последовательности дорог в любой другой, причём единственным способом.
а) Что можно сказать о числе дорог в таком государстве?
б) Пусть города занумерованы числами от 1 до n, а каждая дорога задаётся двумя числами – номерами городов, которые она соединяет. Напишите на любом известном вам языке программирования программу, которая находит два города, кратчайший путь между которыми имеет наибольшую возможную длину среди всех кратчайших путей в данном государстве.
в) Оцените время работы вашей программы в зависимости от n. Оценку количества действий укажите в комментариях к коду. Может ли существовать алгоритм, который решает задачу оптимальнее? Если да, то постарайтесь его найти.
Ответы на вопросы о количестве действий и существовании оптимального алгоритма напишите в комментариях внутри вашей программы.
нюша2605
08 февр. 2017 г., 23:40:10 (7 лет назад)
Korolb
09 февр. 2017 г., 1:26:10 (7 лет назад)
1) количество дорог строго n-1
2) алгоритм простой
1. Выбираем любую вершину и при помощи волнового алгоритма ищем наиболее удаленную вершину А
2. Из вершины А волновым алгоритмом ищем наиболее удаленную вершину Б
3. А-Б - максимальный путь
3) волновой алгоритм в дереве выполняется за O(n), в нашем случае получаем O(C*n) что равно O(n)
саму программу на Python набросаю чуть позже
кстати Alviko прав, все эти оценки производительности в школе не дают
ZdankinMihail
09 февр. 2017 г., 2:51:04 (7 лет назад)
Комментарий удален
12vovchik071997v12
09 февр. 2017 г., 3:22:26 (7 лет назад)
Комментарий удален
Garikrudov
09 февр. 2017 г., 6:04:31 (7 лет назад)
Комментарий удален
Ivanovaanisia
09 февр. 2017 г., 8:10:47 (7 лет назад)
Комментарий удален
Ответить
Другие вопросы из категории
3.Укажите, в какой из групп устройств перечислены устройства вывода информации 1.Принтер, винчестер,
мышь.
2.Винчестер, лазерный диск, модем.
3.Монитор, принтер, плоттер, звуковые колонки.
Читайте также
В бутылке,стакане,кувшине и банке находится молоко,лимонад,квас и вода.Известно,что вода и молоко не в бутылке,сосуд с лимонадом стоит между кувшином и
сосудом с квасом,в банке не лимонад и не вода стакан стоит между банкой и сосудом с молоком.В каком сосуде находится каждя из жидкости?
В Бутылке,стакане,кувшине и банке находятся молоко,лимонад,квас и вода.известно,что вода и молоко не в бутылке,сосуд с лимонадом стоит между кувшином и
сосудом с квасом,в банке не лимонад и не вода,стакан стоит между банкой и сосудом с молоком. В каком сосуде находится каждая из жидкостей?
У Пети дома есть несколько компьютеров, каждый из которых имеет в своем составе системный блок, монитор и клавиатуру. Если все системные блоки,
мониторы и клавиатуру собрать вместе, то все элементы, кроме двух, будут системными блоками, все элементы, кроме двух - клавиатурами, все элементы, кроме двух, будут мониторами
Сколько компьютеров у Пети дома? Помогите, пожалуйста, решить эту задачу.
РЕШИТЕ КТО, ЧТО МОЖЕТ!!!!! 1.В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12
букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер - одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 32 автомобильных номеров.
2.Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-». Сколько различных сообщений можно закодировать, используя в каждом из них не менее 3-х и не более 7 знаков?
3.В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?
4. Перевести 38(10) в (7)...
5. Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении - 3 или 4, между сообщениями - паузы. Сколько различных сообщений могут передавать мальчики?
6. Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?
7. Для кодирования секретного сообщения используются 12 специальных значков-символов. При этом символы кодируются одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения длиной в 256 символов?
8. Объем сообщения равен 11 Кбайт. Сообщение содержит 11264 символа. Какова мощность алфавита?
9. В некоторой стране автомобильный номер состоит из 8 символов. Первый символ - одна из 26 латинских букв, остальные семь - десятичные цифры. Пример номера - A1234567. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер - одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 30 автомобильных номеров.
1) Скорость передачи данных по некоторому каналу связи равна 512 Кбит/с. Передача файла по этому каналу связи заняла 4 мин. Определите размер файла в
мегабайтах.
2) Скорость передачи данных по некоторому каналу связи равна 32 Кбит/с. Передача текстового файла по этому каналу связи заняла 15 с. Определите, сколько страниц содержал переданный текст, если известно, что иформационный вес одного символа равек 8 битам, а на одной странице 48 символов.
3) Скорость передачи данных по некоторому каналу равна 64000 бит/с. Передача файла по этому каналу связи заняла 16 с. Определите размер файла в килобайтах.
хотя бы первую решите....
С пояснениями пожалуйта .. Буду очень признательна
Вы находитесь на странице вопроса "В некотором государстве есть n городов. Между некоторыми парами городов проложены дороги. Каждая из дорог имеет длину 100 км. Известно, что из любого", категории "информатика". Данный вопрос относится к разделу "5-9" классов. Здесь вы сможете получить ответ, а также обсудить вопрос с посетителями сайта. Автоматический умный поиск поможет найти похожие вопросы в категории "информатика". Если ваш вопрос отличается или ответы не подходят, вы можете задать новый вопрос, воспользовавшись кнопкой в верхней части сайта.