Задача 1
Разработать программу вычисления расписания сети сортировки
Дано:
n1, n2 – либо количества элементов в двух упорядоченных группа
(при n1>=1, n2>=1), либо количество неупорядоченных элементов в первой группе
(при n1>=1, n2=0).
n1 и n2 передаются через параметры командной строки
bsort n1 [n2]
Требуется: Вывести в файл стандартного вывода расписание в следующем формате:
n1 n2 i0
c0u c0d
c1u c1d
c2u c2d
c3u c3d
.
c..u c..d
n_comp
n_tact
где:
i0 – номер первой строки. Строки нумеруются следующим образом:
[i0,...,i0+n1-1] и, если n2=0, то [i0+n1,...,i0+n1+n2-1]
c..u c..d – номера строк, соединяемых компаратором сравнения перестановки.
Рекомендуется обеспечить возможность вычисления сети для числа элементов из
диапазона [1…10000], то есть, для 1<=n1+n2<=10000.
Рекомендуется предусмотреть проверку правильности сети хотя бы для небольших
значений числа сортируемых элементов.
Рекомендуется представить краткий отчет с пояснением условия, метода решения и
метода проверки.
Пример 1.
bsort 4 0
4 0 0
0 1
2 3
0 2
1 3
1 2
5
3
0 │ ┐ │ ┐ │
1 │ ┘ │ │┐ │ ┐
2 │ ┐ │ ┘│ │ ┘
3 │ ┘ │ ┘ │
│ 1 │ 2 │ 3
3 1 2 4 ┃ 3 1 2 4
└─┘ └─┘ ┃ 1 3 2 4
└───┘ ┃ 1 3 2 4
└───┘ ┃ 1 3 2 4
└─┘ ┃ 1 2 3 4
4 1 3 2 ┃ 4 1 3 2
└─┘ └─┘ ┃ 1 4 2 3
└───┘ ┃ 1 3 2 4
└───┘ ┃ 1 3 2 4
└─┘ ┃ 1 2 3 4
Пример 2.
bsort 2 2
2 2 0
0 2
1 3
1 2
3
2
0 │ ┐ │
1 │ │┐ │ ┐
2 │ ┘│ │ ┘
3 │ ┘ │
│ 1 │ 2
1 3 │ 2 4 ┃ * * * *
└─────┘ ┃ 1 * * *
└─────┘ ┃ 1 * * 4
└───┘ ┃ 1 2 3 4