Помогите разработать алгоритм для сортировки вагонов.


И надо отсортировать вагоны, склеивая их минимальное количество раз. Количество вагонов первоначально известно.

Это сообщение отредактировал(а) toshun - 18.12.2007, 16:28

Для начала. Если вагоны с номерами Х и Х+1 стоят друг за другом - их всегда следует отправлять на один и тот же путь, вместе. При этом их можно считать одним вагоном.

Следовательно первичный, неоптимизированный, алгоритм, состоит в том, чтобы для каждой пары (возможно, уже составных, т.е. состоящих из нескольких отсортированных) вагонов с номерами Х и Х+1, которые НЕ стоят друг за другом:

1) Если вагон Х стоит в составе раньше - отправить их на один путь.
2) Если нет - отправить вагон Х+1 на другой путь.
3) Склеить составы, начиная с состава, в котором находится вагон 1.

Скажем для «1 3 5 2 4 6 7» это выглядит как? 

Первая перетасовка.
вагон 1 на путь 1
пара 1-2 норм., вагон 2 на путь 1
пара 2-3 ненорм., вагон 3 на путь 2
пара 3-4 норм., вагон 4 на путь 2
пара 4-5 ненорм., вагон 5 на путь 1
пара 5-6 норм., вагон 6 на путь 1
пара 6-7 норм., вагон 7 на путь 1
результат:
путь 1: 15267
путь 2: 34
состав: 1526734

Вторая перетасовка:
вагон 1 на путь 1
пара 1-2 норм., вагон 2 на путь 1
пара 2-3 норм., вагон 3 на путь 1
пара 3-4 норм., вагон 4 на путь 1
пара 4-5 ненорм., вагон 5 на путь 2
пара 5-6 норм., вагон 6 на путь 2
пара 6-7 норм., вагон 7 на путь 2
результат:
путь 1: 1234
путь 2: 567
состав: 1234567

Сортировка завершена.

Спасибо большое!
А можно ли узначть число минимальных склеиваний до самих склеиваний?

Можно. Узнавай.

!  Pakshin A. S.

toshun, кнопка "Сообщить модератору" не предназначена для какого-либо общения с кем-либо - для этого существуют "Личные сообщения"...

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

А запомнить типа не судьба... или религия не позволяет?


Кривой код. Учитесь программировать без ошибок.

а как вы предлагаете запоминать?
там размер меньше или равен  10000. если брать такой двумерный, то стэка не хватит

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