1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
Как пересечь мост по-быстрее?

2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.

Здравствуйте, sugarde, Вы писали:

S>1. Как пересечь мост по-быстрее?
Вроде, быстрее чем за 17 минут не получится.

Над доказательством (не переборным ) и вторым вопросом пока думаю.

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?
Мои перешли за 17 мин. Хочется увидеть другие решения, пока свое придержу...

S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Ой лениво... Но NP полноты не будет.

P.S. Задачка эта мне уже встречалась, только там была река, лодка и братья

Здравствуйте, samius, Вы писали:

S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
S>Ой лениво... Но NP полноты не будет.
С одной стороны, чувтвуется, что есть какое-то дин.прог решение, с другой подозрительная задачка.
Тоже думаю.

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?

S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.


Сначала идут номера
1,2 — проходят за 2 минуты
потом
5,10 проходят за 10 минут

итого 12 минут.

Здравствуйте, codelord, Вы писали:

C>Здравствуйте, sugarde, Вы писали:

S>>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>>Как пересечь мост по-быстрее?

S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.


C>Сначала идут номера
C>1,2 — проходят за 2 минуты
C>потом
C>5,10 проходят за 10 минут

C>итого 12 минут.

или я не понял условие или для любого количества решением будет:
сортировка по времени и выход по парам начиная с конца сортированного списка т/е
имеем время проходов
20 60 80 1 2 555 30 21
сначала сортируем
1 2 20 21 30 60 80 555
и выпускаем
80 — 555
30 — 60
20 — 21
1 — 2
если остается последний ( нечетный список значит идет последним один )
получаем минимальное время прохода пар

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?

S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.

Ну я так и думал, видимо лампу надо вернуть и она у них одна,
Но про это никто не сказал

т/е решения выше не подходят

Здравствуйте, samius, Вы писали:


S>Мои перешли за 17 мин.

Согласен

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?

Самый быстрый бегает по мосту взад-вперед и переводит всех.

S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.

Здравствуйте, Socrat, Вы писали:

S>Самый быстрый бегает по мосту взад-вперед и переводит всех.
Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).

Здравствуйте, Socrat, Вы писали:
S>Самый быстрый бегает по мосту взад-вперед и переводит всех.

Это наверное решение допустим имеем

1 5 30 60 120
тогда по вашему решению
результат будет
5 + 30 + 60 + 120 + 1 + 1 + 1 + 1 + 1 + 1 + 1
итого : 222

а более быстрым будет вариант
1 5 ( -> 1 ) та сторона ( 5 ) (эта сторона 1 30 60 120 )
60 120 ( -> 5 ) ( 60 120 ) ( 1 5 30 )
30 5 ( -> 5 ) ( 60 120 30 ) ( 1 5 )
1 5 ( 60 120 30 1 5 ) ( )
итого времени:
5 + 1 + 120 + 5 + 30 + 5 + 5
результат : 171

Здравствуйте, sugarde, Вы писали:

Первая задачка — по легенде задавалась в майкрософте на собеседовании

Здравствуйте, RomikT, Вы писали:


S>>Самый быстрый бегает по мосту взад-вперед и переводит всех.
RT>Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).

Действительно, погорячился. Надо двух самых быстрых использовать, чтобы лампу относить назад, а самых медленных группировать парами...

Здравствуйте, Socrat, Вы писали:

S>Здравствуйте, RomikT, Вы писали:


S>>>Самый быстрый бегает по мосту взад-вперед и переводит всех.
RT>>Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).

S>Действительно, погорячился. Надо двух самых быстрых использовать, чтобы лампу относить назад, а самых медленных группировать парами...

верной дорогой идете товарищь

Здравствуйте, sugarde, Вы писали:

S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.

S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
S>Как пересечь мост по-быстрее?

17 минут (задача от MS):

-> — туда
<- — назад

->1+2 (2)
<-2 (2)
->10+5 (10)
<-1 (1)
->1+2 (2)


S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.

Здравствуйте, samius, Вы писали:

S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
S>Ой лениво... Но NP полноты не будет.

Обобщить как раз довольно таки просто...

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

Алгоритм перевозки такой.
0. i=0.
1. Перевозчики переходят мост.
2. Самый быстрый из перевозчиков идет обратно.
3. Мост переходит пара N-2i, N-(2i+1).
4. Оставшийся перевозчик идет обратно с лампой.
5. i=i+1.
6. Если остались пары не перевозчиков, идем на шаг 1.
7. Если осталася непарный "тормоз". Самый быстрый из перевозчиков переходит с ним мост и возвращается обратно.
8. Пара перевозчиков переходит мост. Конец.

NP полноты действительно нет.

---
С уважением, Сиваков Константин.

Здравствуйте, sugarde, Вы писали:

[..]

S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.

ИМХО всё сводится к тому как лучше перевести двух самых медленных из оставшихся. Есть 2 разумных подхода:

1) Самый быстрый последовательно переводит обоих самых медленных и возвращается назад с лампой.
2) Двое самых быстрых переходят с лампой, потом один возвращает лампу назад, с этой лампой переходят двое самых медленных после чего второй быстрый возвращает лампу назад.

На каждом шаге определяется, какой из вариантов эффективнее.

Здравствуйте, gbear, Вы писали:

G>Алгоритм перевозки такой...
Алгоритм, видимо, неправильный, так как не работает для [102, 104, 105, 108]

Здравствуйте, RomikT, Вы писали:

RT>Здравствуйте, gbear, Вы писали:

G>>Алгоритм перевозки такой...
RT>Алгоритм, видимо, неправильный, так как не работает для [102, 104, 105, 108]

1. 102 и 104 переходять мост.
2. 102 возращается.
3. 105 и 108 переходят мост.
4. 104 возвращается.
5. 102 и 104 переходят мост.

И того:

104
102
108
104
104

Есть способ быстрее?

--
С уважением, Сиваков Константин.