Помогите пожалуйста решить задачу о деревянной рейке и связанных гвоздях

[BDA]

Вадим Мошев, координаты тоже одномерные и они нужны, так как гвозди можно вбивать через разное расстояние друг от друга.

[Serge_Bliznykov]

Сообщение от BDA

Вадим Мошев, координаты тоже одномерные и они нужны, так как гвозди можно вбивать через разное расстояние друг от друга.

я бы сказал, что гвозди ОБЯЗАТЕЛЬНО вбиты на разном расстоянии друг от друга, иначе задача вырождается в элементарнейшую (о чём, собственно, нам Вадим Мошев и написал )

[Вадим Мошев]

Сообщение от Serge_Bliznykov

я бы сказал, что гвозди ОБЯЗАТЕЛЬНО вбиты на разном расстоянии друг от друга, иначе задача вырождается в элементарнейшую

Может, я что-то не понимаю, но прошу объяснить мне, что это меняет?
Ведь решение то же, что и я написал ранее?

Предположим, что у нас три гвоздя. Расстояние между первым и вторым равно 1 километру. Между вторым и третьим составляет 1000 километров. Соединяем первый гвоздь ниткой со вторым. Второй связываем с третьим. Несмотря на то, что общая протяжённость нитки громадная, она является минимальной из возможных. Я прав?

Та как вам моё вариант решения поставленной задачи?
То есть, нам просто надо просуммировать получившиеся расстояния для получения выходного результата, хотя в коде этого я не наблюдал. Может, я чего-то не понимаю?

ЗЫ. Конечно, если гвозди расположены на одном и том расстоянии друг от друга, то можно не суммировать расстояния, а вообще умножить количество соединённых пар на расстояние между гвоздями.

[BDA]

Хорошо, а такой пример:
* 4 * 1 * 2 * 3 *
(* - гвоздь)
Соединили по-Вашему:
* 4 * 1 * 2 * 3 * = 4 + 2 + 3
Минимум:
* 4 * 1 * 2 * 3 * = 4 + 1 + 3

[Serge_Bliznykov]

Сообщение от Вадим Мошев

Предположим, что у нас три гвоздя.

бессмыслено. Вы ещё два гвоздя рассмотрите.
Три гвоздя связываются друг с другом при любом расстоянии по условиям задачи.

Вот, посмотрите пример BDA, он наглядно показал, в чём Вы ошибаетесь.

[Вадим Мошев]

Сообщение от BDA

Хорошо, а такой пример:
* 4 * 1 * 2 * 3 *
(* - гвоздь)
Соединили по-Вашему:
* 4 * 1 * 2 * 3 * = 4 + 2 + 3
Минимум:
* 4 * 1 * 2 * 3 * = 4 + 1 + 3

Я пока что не могу понять, какой гвоздь с каким соединяется в вашем примере. Единственное, что я понял - это то, что цифры обозначают расстояния между гвоздями

[Smitt&Wesson]

Ребята, вы о чём? Задача легко решается методом Коммивояжёра.
Находим минимальную длину общего пути, затем удаляем пути через один, начиная с самого длинного. Получаем пары с самыми короткими путями.

[BDA]

Красным выделены соединения.
В Вашем случае 1 и 2, 3 и 4, 4 и 5.
Минимум - 1 и 2, 2 и 3, 4 и 5.