Форум программистов, компьютерный форум CyberForum.ru

Пирамида не строится до конца (пирамидальная сортировка) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Удаление узла из бинарного дерева http://www.cyberforum.ru/cpp-beginners/thread1071999.html
Здравствуйте, не могу понять алгоритм замены в данной задаче: Напишите алгоритм и программу для удаления узла из бинарного дерева, которые будет заменять этот узел на его предка в симметричном порядке, а не на его преемника в симметричном порядке. Вот для примера дерево, допустим удаляется 5-узел, судя по всему его надо заменить на 2-й, но как это сделать, не могу разобраться, поясните...
C++ Ошибка в выделении памяти проблема с выделением памяти. ошибку никак найти не могу, поможет кто исправить? #include <iostream> #include <stdlib.h> using namespace std; template <class T> class Queue { public: http://www.cyberforum.ru/cpp-beginners/thread1071990.html
C++ Файловый ввод
Помогите пожалуйста решить задачу. Ввод из текстового файла "file1"(нужно самому создать этот файл) 1. -количество строк матрицы -количество столбцов матрицы -значения элементов матрицы(int) 2. определить номер столбцов матрицы,содержащие отрицательные элементы. 3. вывод результатов выполнения пункта 2 на экран 4. вывод результата выполнения пункта 2 в текстовый файл "file4" (его...
Прочитать данные из файла C++
Доброго времени суток! Помогите написать программку для чтения данных из файла, а то никак не получается. Есть файл, в первой строке которого я знаю, что написано. В матлабе всё отлично считывается, а повторить на С++ не получается. В первой строке подряд записаны следующие переменные: char long long char long long. Результат должен быть следующий: GIDR 2 344 test ta 10 2 Файл прилагаю. ...
C++ Классы, бинарное дерево, конструкторы. Исправить код http://www.cyberforum.ru/cpp-beginners/thread1071928.html
Здравствуйте! Не знаю, как исправить последнюю возникшую ошибку и заставить программу работать. А уже скоро сдавать и преподавателя доставать вопросами возможности нет... :( Помогите, пожалуйста, понять, что же тут не так, и заставить эту прогу работать, уже месяц противиться... 3 раз переделываю... // class3.cpp: определяет точку входа для консольного приложения. //
C++ предложите свой алгоритм решения Множество попарно различных плоскостей в трехмерном пространстве задано перечислением троек точек, через которые проходит каждая из плоскостей. Вы брать максимальное подмножество попарно непараллельных плоскостей. Во первых фишка в том, что нельзя использовать структуры, объекты и всякие плюшки из STL итп. Решать через массивы. Во вторых не совсем понимаю что тут написано ... если у нас... подробнее

Показать сообщение отдельно
Ульяниус
 Аватар для Ульяниус
1 / 1 / 0
Регистрация: 15.08.2013
Сообщений: 132
15.01.2014, 12:54     Пирамида не строится до конца (пирамидальная сортировка)
Строю пирамиду на основе задачи, взятой из инета, выполняется 5 шагов, как и в примере,
а дальше цикл заканчивается, а надо еще проверить правильно ли размещены дети для новых вершин,
подскажите, в чем косяк?
Ниже привожу код программы, а затем ход решения так как должно работать, но
не работает .

Пример: Построим пирамиду для последовательности x = [22, 100, 44, 15, 2, 36, 53, 23, 82, 5].
Делим пополам: 22, 100, 44, 15, 2 | 36, 53, 23, 82, 5. То что справа уже пирамида, слева - то, что будет просеиваться через нее.
C++
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include  <stdio.h>
#include  <conio.h>
#include <time.h>
#include  <stdlib.h>
#include <math.h>
 
 
int swap (int *x, int i, int j) //обмен
 {
  int t; int M;
  if (x[i]==x[j]) return 0;
  t=x[i];
  x[i]=x[j];
  x[j]=t;
  M=1;
  return M;
 }
 
void Pyramid (int *x,int L, int R, unsigned long C, unsigned long M)
 {
  int i,j,t,S;
  //просеивание нового элемента
  if (R!=0)
  {
   t=x[L];
   i=L;
   while (i<=L) //пока у х[i] есть дети
   {
    j=2*i+1;
    while ((j<R)&&(x[j]<x[j+1]))//выбираем большего сына*
      {
       j++;
       C++;
      }
    if (t>=x[j])
     break;
    C++;
    x[i]=x[j];//переносим сына наверх пирамиды
    i=j;
   }
    x[i]=t;
   M++;
  }
 }
 
void main ()
 {
  int i,j,L,R,x[10],k;unsigned long C=0, M=0;
  div_t Div;
k=10;
  Div=div(k,2);
  R=k-1;
  x[0]=22;x[1]=100;x[2]=44;x[3]=15;x[4]=2;x[5]=36;x[6]=53;x[7]=23;x[8]=82;x[9]=5;
  for(L=Div.quot-1;L>=0;--L)      
  {
   Pyramid (x,L,R,C,M);
  }
  for(R=k-1;R>0;--R)
  {
   M+=swap (x,0,R); //М-подсчет количества перестановок
   Pyramid (x,0,R-1,C,M);
 }
 }
Шаг1. Просеиваем x[4] = 2 через пирамиду [36, 53, 23, 82, 5]
Дети этого элемента, вернее только один: x[9] = 5. 5>2 => меняем местами x[4], x[9].
Далее дети x[9] - нет уже => итерация завершена, новая пирамида: [5, 36, 53, 23, 82, 2]

Шаг2. Просеиваем x[3]=15 через [5, 36, 53, 23, 82, 2].
Дети: x[7]=23, x[8]=82. x[8] - наибольший. Т.к. x[8]=82 > x[3]=15 => Обмениваем x[3],x[8].
У x[8] - детей уже нет => итерация завершена, новая пирамида: [82, 5, 36, 53, 23, 15, 2]

Шаг3. Просеиваем x[2]=44 через [82, 5, 36, 53, 23, 15, 2].
Здесь, аналогично, получаем: обмен x[2],x[6], новая пирамида [53, 82, 5, 36, 44, 23, 15, 2]

Шаг4. Просеиваем x[1]=100 через [53, 82, 5, 36, 44, 23, 15, 2].
x[1] больше максимального(x[3]=82) своего ребенка. Итерация завершается без обменов.
Новая пирамида: [100, 53, 82, 5, 36, 44, 23, 15, 2]

Шаг5. Просеиваем x[0]=22 через [100, 53, 82, 5, 36, 44, 23, 15, 2].
Наибольший ребенок x[1]=100 > x[0] => обмениваем x[0],x[1].
Получаем [100, 22, 53, 82, 5, 36, 44, 23, 15, 2]:

(далее у меня прога выходит из цикла и начинает сортировку, хотя пирамида еще не отбаллансирована)

Далее согласно алгоритму, смотрим детей уже для нового x[1] = 22: x[3]=82,x[4]=5.
Максимальный x[3]=82 > x[1]=22 => меням x[1],x[3].
Получили [100, 82, 53, 22, 5, 36, 44, 23, 15, 2]:


Опять смотрим детей уже для нового x[3]=22: x[7]=23, x[8]=15.
Максимальный x[7]>x[3] => обмен x[7],x[3].
Получили [100, 82, 53, 23, 5, 36, 44, 22, 15, 2]:

У x[7] - детей уже нет => итерация завершена.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 09:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru