Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по информатике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 293 RSS
←   Октябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/228
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

293 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Информатика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

_Ayl_
Статус: Студент
Рейтинг: 1366
∙ повысить рейтинг » 		Яна
Статус: Бакалавр
Рейтинг: 1068
∙ повысить рейтинг » 		Jimhucksly
Статус: 5-й класс
Рейтинг: 796
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Информатика

Номер выпуска:169
Дата выхода:11.10.2009, 15:00
Администратор рассылки:Калашников О.А., Руководитель
Подписчиков / экспертов:209 / 134
Вопросов / ответов:1 / 1

Вопрос № 172975: Здравствуйте, уважаемые эксперты. Помогите построить пирамиду пирамидальным методом , используя в качестве набора букв ЗОРИНСЕРГЕ. Я как не пытался понять принцип построения пирамиды, но так и не смог. Мне необходимо показать пошаговое создание пирам...

Вопрос № 172975:

Здравствуйте, уважаемые эксперты. Помогите построить пирамиду пирамидальным методом , используя в качестве набора букв ЗОРИНСЕРГЕ. Я как не пытался понять принцип построения пирамиды, но так и не смог. Мне необходимо показать пошаговое создание пирамиды, чтобы я мог понять как происходит сортировка этим методом.

Отправлен: 06.10.2009, 14:36
Вопрос задал: Hellphoenix, Посетитель
Всего ответов: 1
Страница вопроса »

Отвечает Владимир Лазурко, Профессионал :
Здравствуйте, Hellphoenix.

Алгоритм пирамиды еще по-другому называется "Метод сортировки Уильямса-Флойда".

Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм не требует дополнительной памяти. Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.

Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды". На втором этапе осуществляется сортировка "пирамиды".

Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:

X[1]
X[2] X[3]
X[4] X[5] X[6 ] X[7]
X[8] X[9] ................................


Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося "пирамидой", обладают дополнительными свойствами:

1. Любой элемент пирамиды X[i] не меньше, чем его элементы-потомки X[2i] и X[2i+1] (соответственно первый элемент обладает максимальным значением):

X[i] >= X[2i],
X[i] >= X[2i+1]

2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2], ... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.

В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвост а". Наибольший элемент массива окажется последним. "Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом.

В Приложении текст Pascal-процедуры, реализующей один из возможных вариантов описанного алгоритма.

Источник, более подробно и с картинками здесь.
Форма поиска.

Успехов!
С уважением, Владимир.

Приложение:

Ответ отправил: Владимир Лазурко, Профессионал
Ответ отправлен: 06.10.2009, 17:42

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 255087 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.9 от 25.09.2009
    В избранное