Matematické Fórum

VojtechSejkora · 13. 11. 2010 15:00

Code:

type Pole = array[1..MAXN] of Integer;
 
procedure HeapSort(var A: Pole);
var i, x: integer;
   procedure bublej(m, i: integer); { "zabublání" prvku }
   { m je velikost haldy, i je index zabublávaného prvku }
   var j, x: integer;
   begin
      while 2*i<=m do begin
         j:=2*i;
         if (j<m) and (A[j+1]>A[j]) then j:=j+1;
         if A[i]>=A[j] then break;
         x:=A[i]; A[i]:=A[j]; A[j]:=x;
         i:=j;
      end;
   end;
begin    
   for i:=N div 2 downto 1 do bublej(N,i); { bublej }
   for i:=N downto 2 do begin { vybírej maximum }
      x:=A[1]; A[1]:=A[i]; A[i]:=x;
      bublej(i-1, 1);
   end;
end;

vážně nevím jak toto mám přepsat do céčka:(
jelikož vůbec nevím co to je ta proměnná A a jak je možné že jsou dvě procerudy v sobě, to taky nevím jak bych měl přepsat do céčka:(

pizet · 13. 11. 2010 15:13

↑ VojtechSejkora:

Ono je to celkom jednoduché. Ak by si na to do večera neprišiel, tak ti to do tohoto príspevku dám, ok? Sorry ale teraz nemám čas.

A prečo chceš akurát heapsort?

VojtechSejkora · 13. 11. 2010 15:25

↑ pizet:
no protože haldu jsem si už dokázal udělat.... tak mi stačí už jen z té haldy vyzískat jednotlivé prvky že?

takže asi proto...

takj á to zkouším už nějakou tu hodinu, ale nějak na to nemohu stále přijít co se v tom kódu vlastně děje:( a to se pak těžko přepisuje:(

jarrro · 13. 11. 2010 15:42

Heapsort(int pole[]) nie?

VojtechSejkora · 13. 11. 2010 15:48

↑ jarrro:
ano to jo, ale nevím jaký pole typu int se tam má dávat... jestli ta halda, která má vrchol nejvyšší číslo a nebo něco jiného:(

VojtechSejkora · 13. 11. 2010 16:43

Code:

 
 mojeRazeni(){   
int vrchol=halda[0];
                      smaz_nejmensi();                                                   
              
  return vrchol;
 }
 
 smaz_nejmensi(){              
int i, j, x;

  halda[0]=halda[N];
  N=N-1; i=0;
  while (2*i<=N){
    j=i;
    if (halda[j]>halda[2*i]) j=2*i;
    if ((2*i+1<=N) && (halda[j]>halda[2*i+1])) j=2*i+1;
    if (i==j) break;
    
    x=halda[i]; halda[i]=halda[j]; halda[j]=x;
    i=j;
  }

tak takto jsem to nakonec přepsal já... asi to není nejlepší, ale mě to jinak nenapadlo, ale funguje to...

VojtechSejkora · 13. 11. 2010 18:18

dá se nějak rychle odebrat 1 prvek a místo něj tam dát jiný aby stále platilo to, že je to halda?

VojtechSejkora · 13. 11. 2010 19:42

↑ pizet:
mohl by jsi mi to tedy přepsat? díky moc

pizet · 13. 11. 2010 20:41 — Editoval pizet (13. 11. 2010 20:42)

Sorry ale asi ťa ešte nehám trocha sa hrať (nestíham už nič, naozaj).

Našiel som toto:

Code:

program heap;
uses crt;

const N = 10;

type pole = array [1..N] of integer;
     Halda = record
        data: pole;
        pocet: 0..N;
        end;

var P: pole;
    i: integer;

procedure heapsort (var M: pole);
    var H: Halda;
        i,j,d,p: integer;
        pokracovat: boolean;
    begin
        with H do
        for i:=1 to N do {usporiada prvky do haldy}
            if pocet <> N then begin
                pocet := pocet+1;
                data[pocet] := M[i];
                j := pocet;
                pokracovat := j > 1;
                while pokracovat do begin
                    p := j div 2;
                    if data[j] < data[p] then begin
                        d := data[j];
                        data[j] := data[p];
                        data[p] := d;
                        j := p;
                        pokracovat := j > 1;
                        end
                    else
                        pokracovat := false;
                end
            end;

        with H do
        for i:=1 to N do begin{postupne vybratie vsetkych minim}
            M[i] := data[1];
            data[1] := data[pocet];
            pocet := pocet-1;
            j := 1;
            pokracovat := pocet >= 2;
            while pokracovat do begin
                p := 2*j;
                if p < pocet then
                    if data[p+1] < data[p] then p:=p+1;
                if data[j] > data[p] then begin
                    d := data[j];
                    data[j] := data[p];
                    data[p] := d;
                    j := p;
                    pokracovat := pocet >= j*2;
                    end
                else
                    pokracovat := false;
            end
        end
    end;

begin
    writeln ('Zadaj prvky pola:');
    for i:=1 to N do
        read (P[i]);

    heapsort (P);

    for i:=1 to N do
        write (P[i], ' ');


repeat
until keypressed;
end.

Robil som to ja kedysi v packale. Implementácia, je podľa mňa zrozumiteľnejšia o niečo, i keď zdĺhavejšia. Ak s dačím budeš potrebovať poradiť, tak mi kľudne napíš, môžem ti dať môj mail. Môžem sa podeliť s tebou o tú trošičku čo zatiaľ viem.

VojtechSejkora · 13. 11. 2010 20:47

↑ pizet:
to jsi mě dostal teď tedy.... se s tím morduju už asi 6 hodin néli déle... a stále jsme na to nepřišel a mám ještě déle přemýšlet? hmm...pěkné:(

pizet · 13. 11. 2010 21:05 — Editoval pizet (13. 11. 2010 21:06)

No veď si vravel, že haldu vybudovať si už zvládol. Tak sa potom pozri na tú prvú časť.

Prvá časť je len ako akoby N-krát volaná procedúra Pridaj do haldy. s tým, že namiesto N-krát volanej procedúry je to v cykle, s tým, že sa vyberajú prvky postupne z pola M.

Druhá časť je ako keby N-krát volaná procedúra Vyber. Priradím minimum do pola M na prvú pozíciu a potom preusporiadam haldu.

Písal si, že si už haldu spraviť zvládol. Potom nechápem celkom s čím máš ten problém. Heapsort podla mňa kľudne môžeš spraviť aj tak, že N-krat zavoláš funkciu vlož a vyber a pri tom vyber budeš automatiky prvky ukladať do poľa. Tie funkcie sú tu. A to si teda povedal, že si zvládol.

Lumikodlak

Narychlo jsem bezmyslenkovite prepsal ten puvodni kod v Pascalu do C. Jde to zkompilovat, ale netestoval jsem to zatim. Nevim presne, jestli je to to, co potrebujes: (kdyztak to jeste zEdituju)

Code:

int Pole[MAXN];
void bublej(int m, int i, int A[]){ //  "zabublání" prvku
  int j, x; // m je velikost haldy, i je index zabublávaného prvku
  while (2 * i <= m){
    j = 2 * i;
    if (j < m && A[j+1] > A[j]) j ++;
    if (A[i] >= A[j]) break;
    x = A[i];
    A[i] = A[j];
    A[j] = x;
    i = j;
  }
}
void HeapSort(int A[]){
  int i, x;
  for (i = N / 2 -1; i > 0; i--) bublej (N, i, A);
  for (i = N - 1; i > 1; i --){
    x = A[0];
    A[0] = A[i];
    A[i] = x;
    bublej (i - 1, 0, A);
  }
}

(Tak jsem to testoval a nefunguje to (netridi to), tak se jeste na to podivam.)
(Tak ted uz to funguje - obratil jsem tam 'i' a 'm v te procedure bublej)

pizet · 17. 11. 2010 10:22

↑ Lumikodlak:
Rozhodol som sa to naprogramovať. A keď tak pozerám na tvoje, tak neviem prečo ti to funguje. Ja tam mám menšie ale podstatné rozdiely rozdiely (Vyznačil som ich komentárom do tvojho kódu.).

Code:

void bublej(int m, int i, int A[]){
  int j, x;
  while (2 * i <= m){ // TU while (2*i+1 <= m)
    j = 2 * i; // TU j = 2*i+1
    if (j < m && A[j+1] > A[j]) j ++;
    if (A[i] >= A[j]) break;
    x = A[i];
    A[i] = A[j];
    A[j] = x;
    i = j;
  }
}
void HeapSort(int A[]){
  int i, x;
  for (i = N / 2 -1; i > 0; i--) bublej (N, i, A); // TU i >= 0
  for (i = N - 1; i > 1; i --){ // A TU i >= 1
    x = A[0];
    A[0] = A[i];
    A[i] = x;
    bublej (i - 1, 0, A);
  }
}

VojtechSejkora · 17. 11. 2010 13:12

↑ pizet:
no tak hladu jsme dokázal sice udělat, ale nevěděl jsem jak ji po vyndání jednoho prvku zas zahaldovat....

ale díky za pomoc

Matematické Fórum

#1 13. 11. 2010 15:00

Přepsání pascal do céčka

Code:

#2 13. 11. 2010 15:13

Re: Přepsání pascal do céčka

#3 13. 11. 2010 15:25

Re: Přepsání pascal do céčka

#4 13. 11. 2010 15:42

Re: Přepsání pascal do céčka

#5 13. 11. 2010 15:48

Re: Přepsání pascal do céčka

#6 13. 11. 2010 16:43

Re: Přepsání pascal do céčka

Code:

#7 13. 11. 2010 18:18

Re: Přepsání pascal do céčka

#8 13. 11. 2010 19:42

Re: Přepsání pascal do céčka

#9 13. 11. 2010 20:41 — Editoval pizet (13. 11. 2010 20:42)

Re: Přepsání pascal do céčka

Code:

#10 13. 11. 2010 20:47

Re: Přepsání pascal do céčka

#11 13. 11. 2010 21:05 — Editoval pizet (13. 11. 2010 21:06)

Re: Přepsání pascal do céčka

#12 13. 11. 2010 21:06 — Editoval Lumikodlak (13. 11. 2010 21:13)

Re: Přepsání pascal do céčka

Code:

#13 17. 11. 2010 10:22

Re: Přepsání pascal do céčka

Code:

#14 17. 11. 2010 13:12

Re: Přepsání pascal do céčka

Zápatí