Методы программирования. Громов Ю.Ю - 88 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

88
2. Отсортируйте естественным двухпутевым слиянием по алгорит-
му N последовательность из девятнадцати записей: (11 «смотри»), (9 «во-
ду»), (92 «забавой»), (35 «:»), (38 «иначе»), (9 «камешки»), (26 «,»),
(23 «круги»), (31 «образуемые»), (69 «такое»), (4 «в»), (96 «.»),
(29 «ими»), (11 «на»), (1 «Бросая»), (88 «пустою»), (82 «будет»), (71 «бро-
сание»), (10 «,») и установите, сколько при этом будет сделано просмот-
ров (выполнений шага N2).
3. Выполните по алгоритму S сортировку простым двухпутевым
слиянием последовательность из пятнадцати записей: (13 «,»), (43 «свои»),
(26 «прищурь»), (54 «разглядишь»), (7 «на»), (57 «на»), (71 «пятна»),
(97 «.»), (69 «нем»), (43 «и»), (4 «Взирая»), (49 «ты»), (10 «солнце»),
(49 «смело»), (29 «глаза») и установите размещение ключей в двух ис-
пользуемых областях памяти до сортировки, а также по окончании каж-
дого просмотра.
4. Отсортируйте посредством слияния списков по алгоритму L по-
следовательность из пятнадцати записей: (70 «хорошо»), (85 «иногда»),
(66 «иногда»), (43 «белой»), (55 «:»), (67 «напишется»), (0 «Память»),
(93 «.»), (3 «есть»), (83 «а»), (88 «дурно»), (5 «лист»), (2 «человека»),
(74 «,»), (45 «бумаги») и установите распределение связей для двух ли-
нейных списков перед началом сортировки, а также по окончании каждо-
го из просмотров.
15. РАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА
Рассмотрим интересный класс методов сортировки, который, по су-
ществу, прямо противоположен слиянию. Предположим, что нужно от-
сортировать колоду из 52 игральных карт. Для этого введём упорядоче-
ние по старшинству (достоинству) карт в масти
Т < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < В < Д < К,
а также по масти
♣ < ♦ < ♥ < ♠ .
Заметим, что одна какая-нибудь карта предшествует другой, если
она либо младше по масти; либо масти обеих карт одинаковы, но она
младше по достоинству. Таким образом, отсортированная колода карт
должна быть упорядочена следующим образом:
Т ♣ < 2 ♣ < … < К ♣ < Т ♦ < … < Д ♠ < К ♠.
Естественно было бы отсортировать карты сначала по масти, разло-
жив их в четыре стопки, а затем перекладывать карты внутри каждой
стопки до тех пор, пока они не будут упорядочены по достоинству.

Страницы