Oryginalna strona colobot.cba.pl umarła, gdy cba.pl przestało oferować darmowy hosting. To jest statyczny mirror, pobrany w 2018. ~krzys_h
 
Polski Portal COLOBOTa
COLOBOT Polish Portal
C, C#, C++ - Kopiec
Berserker - 24-05-2010, 23:21
Temat postu: Kopiec
Ostatnio bawie sie dziwnymi algorytmami, i zrobilem algorytm do kopca w postaci drzewa binarnego, ktory daje dziwny wynik.
Dla danych wejsciowych:
Kod:
5 4 12 6 7 8

Powinien dawac:
Kod:
12 8 6 7 4

A daje:
Kod:
12 8 7 6 4

Niby kopiec jest poprawny, ale sie zastanawiam, czy dla jakichs podchwytliwych danych wejsciowych nie wywali czegos glupiego.
Dane wejsciowe to liczba oznaczajaca liczbe liczb wejsciowych (...), a pozniej sa liczby do ulozenia w kopiec.
Kod wyglada tak:
Kod:

#include <iostream>
using namespace std;
int size;
int* heap;
void getHeap()
{
       int arr;
       int n;
       int i;
       for(i = 1; i < size; i++)
       {
                n = i;
                while(n > 0 && heap[n] > heap[n/2])
                {
                          arr = heap[n];
                          heap[n] = heap[n/2];
                          heap[n/2] = arr;
                          n /= 2;
              }
      }
}
void coutHeap()
{
       for(int i = 0; i < size; i++)
       {
                  if(i > 0) cout << " ";
                  cout << heap[i];
      }
}
int main(int argc, char *argv[])
{
     cin >> size;
     heap = new int[size];
     int i;
     for(i = 0; i < size; i++)
     {
              cin >> heap[i];
    }
    getHeap();
    coutHeap();
               return 0;
}


Poprzednio nikt nie zajrzal, ciekawe czy ktos teraz zauwazy ten temat ^^
Bartek c++ - 25-05-2010, 06:33
Ja myśle że sknociła to ta dwunastka.
Berserker - 25-05-2010, 15:44
Ja mam takie dziwne wrazenie, ze wina lezy po stronie kodu a nie danych wejsciowych. Co wy myslicie? :>
adiblol - 25-05-2010, 16:28
A nie testowałeś na "znanym i poważanym" programie?
Berserker - 25-05-2010, 16:30
Cytat:
A nie testowałeś na "znanym i poważanym" programie?

Testowalem na windzie, nie chce mi sie sciagac i instalowac linuxa by sprawdzic czy na nim 2 glupie liczby ustawiaja sie inaczej :)
adiblol - 25-05-2010, 16:48
Przecież sam pisałeś ten program, to dlaczego nie sprawdzisz na już istniejącym?
Berserker - 25-05-2010, 17:06
Ehh, proste - nie mam do niego dostepu.
Jak robi sie np na maturze zadanie z matematyki to dostepu do klucza sie nie ma :)

Czy kopiec ma jeszcze jakies specjalne warunki? Bo jesli chodzi o to, ze kazdy potomek ma miec wartosc mniejsza rowna od wezla z ktorego pochodzi to spelnilem, a czy jest cos w stylu "lewy potomek jest wiekszy rowny prawemu potomkowi jesli pochodza od jednego wezla"?
adiblol - 25-05-2010, 17:37
Czy w całym Internecie nie ma innych programów realizujących algorytm kopca?
Berserker - 25-05-2010, 17:46
Sa, m.in moj. Tylko, ze jak znalazlem jakis inny, to najczesciej byl napisany tak zagmatwanie (jak do zapamietywania indexow elementow tablicy mozna uzywac ponad 4 zmiennych pomocniczych? 0.o), ze nie bardzo dalo sie porownac. Z drugiej strony, tu jest cale forum nieaktywnych informatykow, ktorzy tylko narzekaja na systemy operacyjne i spamuja w offtopie - zawsze warto sprobowac przeniesc aktywnosc na inne dzialy :)
adiblol - 25-05-2010, 18:52
Skompiluj ten "zagmatwany" i sprawdź czy daje takie same wyniki.
Bartek c++ - 25-05-2010, 21:15
Na Windowsie własne obliczenia są pogmatwane(niestabilny czasami), lepiej obliczać na UNIX lub Linux.
Berserker - 25-05-2010, 21:45
Kod:
  12
8 6
47

Jakis algorytm z zaimplementowana funkcja wyswietlania tego w kopcu (wow), tylko troche nie dziala dla innej liczby elementow niz 31.
Wnioskuje z tej pseudopiramidki, ze wynik to
Kod:
12 8 6 4 7
Dziwnie poprawny :>

Powered by phpBB modified by Przemo & WRIM © 2003 phpBB Group