|
0 / 0 / 0
Регистрация: 13.09.2011
Сообщений: 39
|
|
Найти минимальную суммарную длину n отрезков28.12.2011, 16:36. Показов 5115. Ответов 11
Метки нет (Все метки)
Всем привет. Пытаюсь решить задачу и ничего не выходит. Помогите решить.
Условие: Пусть n красных и n синих точек на плоскости заданы своими координатами. Построить n отрезков с разноцветными концами, суммарная длина, которых минимальна (каждая точка является концом только одного отрезка). Плоскость я под себя определил такую: int a[10][10]={{0,0,0...}...}; 3 красные точки red1[2][2],red2[2][9],red3[8][7] 3 синие точки blue1[8][1],blue2[4][4],blue3[10][8] Пытался сложить индексы, но числа получал астрономические, не получается у меня. По условию, я нужно соединить отрезки, найти самый минимальный отрезок из 3-х возможных комбинаций, и так для каждого, затем сложить значения этих трех отрезков и вывести в консоли.
0
|
|
| 28.12.2011, 16:36 | |
|
Ответы с готовыми решениями:
11
Найти минимальную длину пути
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 28.12.2011, 16:44 | |
|
Расскажу только теорию.
Создаем массив a[][] размером n*n. Заполняем его значениями. Элемент [i][j] равен расстоянию от i красной точки до j синей точки. Затем рекурсия, перебор: перебираем все варианты когда выбрано n значений из массива a[][] - в каждой строке и каждом столбце ровно один выбранный элемент. Считаем суммы выбранных элементов. Минимальная сумма и есть ответ.
0
|
|
|
0 / 0 / 0
Регистрация: 13.09.2011
Сообщений: 39
|
|
| 28.12.2011, 16:49 [ТС] | |
|
Я не знаю как это реализовать, эти рекурсии, переборы, вообще тьма, помоги пожалуйста.
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||
| 28.12.2011, 16:57 | ||
|
Кстати если будете обращаться по поводу решения сразу напишите: Как вводятся данные (из файла, вручную). Максимальное n. Какой тип числа координат (вещественный, целый), в каком допустимом диапазоне лежат координаты. В каком порядке вводятся указанные данные. Что нужно вывести: только минимальную динну, или еще какие красные вершины с какими синими соеденены. Куда нужно вывести - в файл, или на экран.
0
|
||
|
0 / 0 / 0
Регистрация: 13.09.2011
Сообщений: 39
|
|
| 28.12.2011, 17:02 [ТС] | |
|
Жаль, что сегодня не успеешь, мне завтра уже сдавать
![]() По делу: данные не вводятся, все сразу в коде, максимальное n пусть будет 3 для точек и 10 для двумерного массива, тип integer. Нужно вывести только значение минимальной длины в сумме всех 3 отрезков.
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||||||
| 29.12.2011, 08:04 | |||||||
0
|
|||||||
|
0 / 0 / 0
Регистрация: 11.04.2012
Сообщений: 3
|
|
| 11.04.2012, 15:30 | |
|
поставили такую же задачу, но данные забиваются вручную, а n произвольно, хоть до 10000, основную идею понял, а вот как реализовать с рекрсией нет, можете обьяснить?
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||
| 11.04.2012, 19:11 | ||
|
0
|
||
|
0 / 0 / 0
Регистрация: 11.04.2012
Сообщений: 3
|
||
| 11.04.2012, 19:22 | ||
|
0
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 11.04.2012, 20:37 | ||||||
0
|
||||||
|
347 / 292 / 37
Регистрация: 23.03.2012
Сообщений: 838
|
|
| 11.04.2012, 20:42 | |
|
По-моему, надо построить матрицу расстояний, а потом решить задачу о назначении.
1
|
|
|
0 / 0 / 0
Регистрация: 11.04.2012
Сообщений: 3
|
||
| 11.04.2012, 22:51 | ||
|
0
|
||
| 11.04.2012, 22:51 | |
|
Помогаю со студенческими работами здесь
12
Даны четыре точки на числовой оси A, B, C И D. найти длину пересечения отрезков AB И CD
Написать процедуру, которая находит минимальную суммарную длину Найти минимальную и максимальную возможную суммарную стоимость всех заготовок в ящике Найти минимальную сумму отрезков последовательности чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|