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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #21  
Старый 13.04.2011, 15:15
queit

 
Сообщений: n/a

Итоговый результат
#include <iostream>
#include <conio>
#include <stdlib.h>
#include <stdio.h>
#include <math>
#include <string.h>
#include <stdlib.h>
#include <vector>

using namespace std;
//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

int N;
vector <int> arrB, arrC, arrA;
int infinity;
//---------------------------------------------------------------------------

#pragma argsused

void CreateTree(void)
{
int i,j,L,H,minA,v;

//Установка размера выходного массива
arrB.resize(N);

//Заполнение вспомагательного вектора
arrC = arrA;

L = log(N)/log(2); //Определяем кол-во уровней
for (j = 0; j < L; j++){
//На последнем этапе итерации просто устанавливаем в корень
//минимальный элемент на прошлом этапе
if (j==(L-1)){
arrB[1] = min(arrB[2],arrB[3]);
return;
}
//Определение размера вспомогательного массива
H = arrC.size();
i = 1;
while(i < H){
//Итератор для результирующего массива
//int v = 0;
if (i==1){
v = pow(2, L-j)/2;
}
else v+=1;

//Определение минимального элемента из пары i и i+1
if (arrC[i-1] < arrC[i]){
minA = arrC[i-1];
}
else{
minA = arrC[i];
}

//Установка мин.значения в результирующий массив
arrB[v] = minA;
//Добавим во вспомогательный массив мин. элемент
arrC.push_back(minA);

i=i+2;
}
//Изменаем размер вспомагательного массива
vector<int>::iterator p = arrC.begin();
arrC.erase(p - 1, p - 1 + H);
}
}
//---------------------------------------------------------------------------

void DefineInfinity(void){
int MaxA;
MaxA = arrA[0];
for (int i=0; i<N; i++){
if (arrA[i]>MaxA) MaxA = arrA[i];
}

infinity = MaxA + 1;
}
//---------------------------------------------------------------------------

void TreeSort(void){

int k = 0;
int i, minA;
//int j = 0;

while (k < N){
i = 1;
if (arrB[i] == infinity) break;

//Текущий элемент является минимальным
minA = arrB[i];
//Обнуляем текущий элемент
arrB[i] = infinity;

//Спуск по дереву
while (i < 2*N){
if (2*i+1 > 2*N-1){
arrA[k] = minA;
arrB[i] = infinity;
break;
}

if (arrB[2*i] == minA){
arrB[i] = infinity;
i = 2*i;
}
else if (arrB[2*i+1] == minA){
arrB[i] = infinity;
i = 2*i + 1;
}
}

//Подъем по дереву
while(i > 1){
//Определить четность i-го элемента
if (i%2 == 1){//Нечетный элемент
if (arrB[i] > arrB[i-1]) arrB[(i-1)/2] = arrB[i-1];
else arrB[(i-1)/2] = arrB[i];
}
else{//Четный элемент
if (arrB[i] > arrB[i+1]) arrB[i/2] = arrB[i+1];
else arrB[i/2] = arrB[i];
};

//Обнуляем текущий элемент
//arrB[i] = infinity;

i=i/2;
}

k+=1;
//if (k > (N-1)) break;
}

}
//---------------------------------------------------------------------------


void main(void)
{

//Заполнение исходного вектора
arrA.push_back(1);
arrA.push_back(3);
arrA.push_back(4);
arrA.push_back(5);
arrA.push_back(1);
arrA.push_back(7);
arrA.push_back(4);
arrA.push_back(3);

/*arrA.push_back(1);
arrA.push_back(2);
arrA.push_back(3);
arrA.push_back(4);
arrA.push_back(5);
arrA.push_back(6);
arrA.push_back(7);
arrA.push_back(8);
arrA.push_back(9);
arrA.push_back(10);
arrA.push_back(11);
arrA.push_back(12);
arrA.push_back(13);
arrA.push_back(14);
arrA.push_back(15);
arrA.push_back(16);*/

N = arrA.size();

for (int i=0; i<N-1; i++){
cout << arrA[i] << " | ";
}
cout << endl;
cout << endl;


CreateTree();

//Дописываем в конец результирующего массива исходный (нижний уровень в дереве)
for (int i=0; i<N; i++) arrB.push_back(arrA[i]);

cout << "| ";
for (int i=0; i<2*N-1; i++){
cout << arrB[i] << " | ";
}
cout << endl;

cout << "| ";
for (int i=0; i<2*N-1; i++){
if (i>9) cout << i << "| ";
else cout << i << " | ";
}
cout << endl;

cout << endl;
DefineInfinity();
cout << "Infinity = " << infinity << endl;
cout << endl;
cout << endl;

/*int k = 0;
for (int i = 1; i < 2*N - 1; i++){
if (TreeSort(i,k)) k+=1;
}*/


TreeSort();


for (int i=0; i<N; i++){
cout << arrA[i] << " | ";
}
cout << endl;

getch();
}
//---------------------------------------------------------------------------
  #22  
Старый 13.04.2011, 15:19
queit

 
Сообщений: n/a

Возможно есть более изящная реализация. Моя не претендует на оптимальность и совершенство, я просто реализовал алгоритм.
Еще один момент хочу отметить: алгоритм применим в основном для массивов размерность которых кратна степени 2, т.е. 2^1=2, 2^2=4, 2^3=8, 2^4=16 и т.д.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм наилучшего взаимного выбора Detech Математические алгоритмы (другое) 6 17.11.2010 04:52
Вопрос по правильности выбора обучения Serg555 Искусственный интеллект, нейронные сети 1 16.03.2010 20:03
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Алгоритм, который определяет, является ли граф деревом trans-tech Сортировка и поиск 1 26.11.2008 15:55
Метод квадратичного выбора ToR Сортировка и поиск 12 05.11.2008 23:02