Anonymní profil tomas.ch – Programujte.com

Dobrý den,
snažím se vymyslet takové řady, které budou těžko zpracovatelné pro algoritmus quicksort. Vymyslel jsem několik příkladů řad. Prosím podívejte se na ně a napište mi, zda si myslíte, že by s nimi měl quicksort problém. Používám algoritmus A. C. Hoare, takže pivot je vždy ve středu.
řady:
1) 1 000 -> 0 -> 1 000
2) 1 000 -> sudá čísla -> 0 -> lichá čísla -> 1 000
3) 10 -> 0 -> 10 -> 0 ->10-> ............ 10 -> 0 -> 10 -> 0 ->10
napadají vás nějaké další řady čísel, které by mohly podlamovat princi quicksortu? pokud ano tak mi je prosím napište a také prosím ohodnoťte tyto 3 co jsem napsal. Děkuji

A kdybych měl zvolit mezi: 

var B: boolean
    X: byte;
begin
  B:=true;
  while ( X < 10 ) AND B do begin
    if ( cokoliv ) then B:=false;
    else
    inc(X);
  end;
end.

{A nebo}

var X: byte;
begin
  B:=true;
  while ( X < 10 ) do begin
    if ( cokoliv ) then break;
    else
    inc(X);
  end;
end.

Které řešení myslíte, že je lepší?

Dobrý den,

chtěl bych se zeptat ohledně možných nevýhod, nebo možných chyb, které by mohly vyplývat z procedury break;

S pascalem pracuji prozatím krátký čas a nemám s touto procedurou zkušenosti. Učil jsem se programovat na jiném jazyce( C++ ) a od tud mám proceduru break spojenu s řekněme nevhodnými procedurami jako "goto" atd, protože se přece jenom jedná o jakési přeskakování kódu. Na stránkách fpc jsem našel, že v pascau je tato procedura bezproblémová, ale stejně bych se vás chtěl zeptat na vaše zkušenosti.

Jasně, takže if má nějakou časovou složitost X. While má složitost Y. A na konci while, ale stejně oveřuju, zda je podmínka splněna, přičemž tato akce ověření je v podstatě podmínka if. Takže závěrem je, že složitost Y(ať je jakákoli) musí být zákonitě větší, protože na konci while ověřuji ještě podmínku, zda opakovat, či ne o složitosti X. Takže while má složitost při nejmenším Y+X?

Dobrý den,

nedaří se mi nikde vygooglit rozdíl časových složitostí mezi podmínkou a cyklem o jednom průchodu.

if ( X ) then read(Y); 
while ( X ) do read(Y); {Za předpokladu, že cyklus proběhne pouze 1x}

Co proběhne rychleji. Důvod, proč toto řeším nebudu příliš do hloubky rozebírat. Ve zkratce jde o to, zda mám použít podmínku před cyklem, nebo uvnitř cyklu a pokud bude podmínka true, tak cyklus ukončit. Chápu, že se tento důvod může zdát nepochopitelný, ale mám pro to hlubší důvody. Nevíte tedy někdo, jaký bude rozdíl v těchto operacích?  

Ještě pro jistotu bych chtěl zkonzultovat funkci:

  function Empty(var Z: Zasobnik): boolean;
  begin
    Empty:=Z.Zac=nil;
  end;

Tato funkce je využita i v proceduře uvedené výše. Pouze bych si chtěl potvrdit mé tvrzení: "Není nutno kontrolovat, zda i proměnná Kon je rovna nil, protože pokud je proměnná Zac rovna nil není možné, aby proměnná Kon nebyla také nil" je toto tvrzení pravdivé? Já myslím, že je, ale stejně bych to rád slyšel i od někoho zkušenějšího.

děkuji... a co do stability algoritmu...nevidíte v něm něco co by jej mohlo shodit?

#2 JoDiK
využívám pouze zásobníkového vkládání. mazání provádím podle potřeb programu

Dobrý den,

ustavičně uvažuji nad zjednodušením jednoho dílčí procedury, kterou jsem napsal. Už několik hodin hledám způsoby jak více a více zredukovat časovou složitost následujícího kódu, aby se neprováděli žádné akce, které nejsou nezbytné a také se snažím doladit ho do spolehlivé podoby tak, aby nic nemohlo způsobit pád programu. Myslím, že algoritmus už je vcelku obstojný, ale i přes to bych ho chtěl dát i sem, zda vaše zkušenější oko neuvidí nějaké lepší řešení.

Jedná se o algoritmus pro odebrání prvku ze struktury. Tady je zdrojový kód:

type UkPrvek = ^Prvek;
      Prvek = record
        Data: byte;
        Dalsi: UkPrvek;
      end; 
      Zasobnik = record
        Zac, Kon: UkPrvek;
      end;
      
  procedure Odeber(var Z: Zasobnik; D: byte);
  var Poz, Pom: UkPrvek;
      Zarazka : boolean;
  begin
  Zarazka:=false;
    if not Empty(Z) then
      with Z do begin
        Poz:=Zac;
        if ( Poz^.Data = D ) then begin
          Zac:=Zac^.Dalsi;
          dispose(Poz);  
        end else
          while ( Poz^.Dalsi <> nil ) and ( Zarazka = false ) do begin
            if ( Poz^.Dalsi^.Data = D ) then begin
              Pom:=Poz^.Dalsi;
              if ( Pom = Kon ) then begin
                Kon:=Poz;
                Poz^.Dalsi:=nil;
              end else begin
                Poz^.Dalsi:=Pom^.Dalsi;
                Poz:=Poz^.Dalsi;
                Zarazka:=true;
              end;
              dispose(Pom);
            end else Poz:=Poz^.Dalsi; 
          end; 
      end;
  end;

Nejvíce mě na algoritmu trápí to, že jsem použil Zarazka : boolean; a přemýšlím nad tím, jak bez tohoto prvku zajistit to, aby v případě, že prvek naleznu se neprocházel zbytek struktury aniž bych použil break, nebo podobné zlo. 

Ježiš já sem ocas :-D 3 dny nadávám, že něco nefunguje a nakonec je to v takové nepozornosi. Mnohokrát děkuji!

Na úvod uvedu co jsem napsal:

program prog;
var F: text;
    C: char;
    S: string;
    I,X: Byte;
begin
  assign(F, 'txt.txt'); {znak "š" uložený v souboru v utf-8}
  reset(F);
  read(F, C);
  I:=ord(C);
  S:='';
  writeln(I);
  for X:=0 to 8 do begin
    S:=char(ord(odd(I)) + ord('0')) + S;
    I:=I shr 1; 
  end;
  writeln(S);
end.

Tak. Na vstupu mám znak 'š', což je znak s ordinální hodnotou větší než 127. Procedura read() přečte jenom první bit. Jeho ordinální hodnotu zpracuji, ale v prvním bajtu stejně nejsou jedničky (výsledek výše uvedeného kódu je:011000101). Jak je to možné? kde dělám chybu?

stejně to pořád moc nechápu. řekněme že mám X: char; do tohoto charu uložím hodnotu například X:= "s". Potom mám promenou retez: String a já chci udelat proceduru, která mi do promenne retez vlozí hodnotu "01110011" což je binární hodnota znaku "S". Je toto srozumitelnější? 

Dobrý den,

mám za úkol přečíst vstup v kódování UTF-8. Mám ho rozsekat na jednotlivá písmena a binární hodnoty těchto písmen uložit do stringů v nějaké struktuře. Struktury zvládám, ale problém je s prvními dvěma kroky. UTF-8 nejde přečíst pomocí read(), tedy jde, ale v případě, kdy mám například znak "Š" nepřečtu ho celý, protože má dva bity. Druhým problémem je, že nevím jak dostat z charu jeho binární hodnotu. Mohl by mi s tím někdo pomoci?

Je asi tezko to vysvetlit na nejakem abstraktnim prikladu, proto dam konkretni priklad, ktery se snazim zjednodusit sem:

program prog;
type UkSeznam = ^Seznam;
      Seznam = record
        Data: string;
        Dalsi: UkSeznam;
      end;
     
  function Ukol(A: string; B: char): UkSeznam;
  var Pom, Poz: UkSeznam;
  begin
    Ukol:=nil;
    while( POS(B, A) <> 0 ) do begin
      new(Pom);
      Pom^.Data:= COPY(A, 1, POS(B, A));
      Pom^.Dalsi:= nil;   
      if ( Ukol = nil ) then begin Ukol:=Pom; end
      else begin
        Poz:= Ukol;
        while( Poz^.Dalsi <> nil ) do Poz:=Poz^.Dalsi;
        Poz^.Dalsi:=Pom;
      end;
      DELETE(A, 1, POS(B, A));        
    end;
    if not ( POS(B, A) <> 0 ) then begin
      Poz:= Ukol;
      new(Pom);
      Pom^.Data:= A;
      Pom^.Dalsi:= nil;
      while( Poz^.Dalsi <> nil ) do Poz:=Poz^.Dalsi;
      Poz^.Dalsi:=Pom;
    end;   
  end;
 
  procedure Vypis(S: UkSeznam);
  var Pom: UkSeznam;
  begin
    Pom:=S;
    while ( Pom <> nil ) do begin
      Writeln(Pom^.Data);
      Pom:=Pom^.Dalsi; 
    end;
  end;
 
var S: UkSeznam; 
begin

  Vypis(Ukol('Ahoj jak se vede', ' '));

end.

Kod je zbytecne roztahany...to ano...Ale chci se pri jeho optimalizaci zamerovat na dilci casti, tedy momentalne se snazim odstranit zdvojenou podminku ( POS(B, A) <> 0 ) Protože se mi nelíbí, že je tam dvakrát... Ještě dodám zadání dané úlohy: Napište funkci, která dostane v prvním parametru znakový řetězec a v druhém parametru jeden znak, jenž bude chápán jako oddělovač úseků zadaného řetězce. Funkce "rozseká" zadaný řetězec na části podle zadaného oddělovače a nabude hodnoty ukazatele na lineární jednosměrný seznam těchto částí. Je toto už pochopitelnější o co mi jde?

Ano...bohužel se zde jedná o ilustrativní příklad, který se ve skutečnosti týká lineárního dynemického seznamu, pouze jsem sem data prepsal do pole pro zjednodusení...opravdu hledám pouze způsob, jak zjednodusit danou podmínku...tzn, prepsat to nejak tak, aby byla podmínka jenom jedna...

Dobrý den,
mám tu jeden velice základní algoritmus, abych na něm ilustroval jiný problém, který teď řeším. Nejedná se ani tak o problém, protože algoritmus je funkční, ale spíše o to, že bych ho chtěl zjednodušit.
Úkol tohoto algoritmu je následující: V poli jsou uložena čísla. Já chci vlžit na konec pole další číslo, ale pouze za předpokladu, že se v poli
číslo už nevyskytuje.

{I = pomocná proměnná začínající na 1
P = [array of byte]}
while ( I < 100 ) AND ( P[I] <> 10 )  {Procházím pole až dokonce, nebo dokud nnenaleznu prvek s hodnotou 10}
do inc(I);                            {Pořád zvyšuju I, abych se dostal nakonec}
      if( P[I] <> 10 ) then begin     {Pokud je prvek různý od 10ti, znamená to, že jsem na konci pole a mohu tedy prvek přidat}
        P[I+1]:=10;
      end;

na algoritmu se mi nelíbí, že je v něm 2x podmínka ( P[I] <> 10 ). Nenapadá někoho, jak by mohl jít tento už tak velice jednoduchý algoritmus ještě zjednoduši?

Dobrý den,

narazil jsem na problém, který nemohu vyřešit. Jak mohu přečíst char v binární podobě a uložit si jeho podobu do nějakého stringu? Povedlo se mi už do binární podoby převést číselné typy pomocí ord(odd X), ale to to řešení mi pro typ char nefunguje. Poté je tu další problém a to je formát tetu na vztupu (UTF-8), ale s tím už si snad nějak poradím sám. Hlavně bych potřeboval nakopnout správným směrem ve výše uvedeném problému.