Hi Evribodri!

Koszonet mindenkinek, aki 'antirendezes', azaz
tomb elemeinek osszecserelese temaban segitett.

Osszefoglalva:

a legegyszerubb (es leggyorsabb) megoldasok:

1.) 2 veletlenszeruen kivalasztott elem csereje
    x-szer (minel nagyobb x, annal rendezetlenebb a tomb)
    Ennel a modszernel a rendezetlenseg tehat 'beallithato'.

2.) Amire igazabol nekem is szuksegem volt
   (abszolut osszevisszasag elerese):
    Adott X elemu tomb;
    A tomb elemeit sorban (1-tol n-ig) vegigcserelni
    egy veletlenszeruen kivalsztott masik elemmel.
    Igy minden elemnek 'lehetosege van' kicserelodni.

Udvozlettel: meri

 Laszlo MERENYI
 meri / wrkplc
 

Hali!

Most csak a globalis valtozokhoz akarok halkan annyit megjegyezni, hogy
nemely esetben
bizony szukseg van rajuk...En POS-terminalokat prgzek melohelyen.
Ne tudd meg!  egycsipes 8086! 5 Mhz orajel! !!!!!!!!!512 byte
stack!!!!!!!!!!!!!
Azota sok minden van globalis valtozoban....
hat ha az osszes miskulanciat Te be tudod gyomoszolni 512 byte
stackteruletre, kiraly vagy! :-))))
Ja! alloc() es tarsai nincsenek!minek ide memoriat foglalni....

Mindenesetre nem art modulnevet is tartalmazo nevet adni a globalis
valtozonak. Erre mostanaban jottem ra.
Sok modul, sok modulonkent egyezo nevu globalis valtozo(biztos kicsi a
fantaziam), mindegyik static persze.
Most megszunt a lehetoseg a staticra...mivel az ugye kinullazza a dolgokat,
es mostantol az eloredefinialt erteku
valtozok konstansokka minosulnek compileriro kollegaim szerint
ugyebar......arrol mar nem beszelve, hogy
adatszegmensbe kellene kerulniuk, de hat kodba rakja az allatja, mivel a
kodot tartalmazo szegmens ellenorzo
osszeggel van vedve megvaltozas ellen...utobbi esetben "No application
loaded"...ezek miatt mar ossze sem lehet linkelni.
erre mar csak erdekesseg, hogy long szamon nem lehet switch() mert az
general ilyen valtozot forditaskor....de minek?!

Bocs a kifakadasert. :-))

Hali!
Steve

Hi !

A keveres nem tunik tul bonyolult feladatnak,
de latszik, hogy megis sokan bele esnek az
egyszerunek tuno feladatok csapdajaba.

  irta :

> Egy eleg gyors es hatekony algoritmus a kovetkezo:
>
> tomb[N]
>
> Eljaras Osszekavar
> ciklus i = 1 to N
>   seged=tomb[i]
>   y=Veletlenszam(N)
>   tomb[i]=tomb[y]
>   tomb[y]=seged
> Ciklus vege
> Eljaras vege

Sajnos az adott megoldas tenyleg gyors es hatekony csak
hibas !
Ugyanis ( itt egy kicsit matematikaibb erveles kovetkezik
a tevedes bemutatasara : )
pl. induljunk ki 3 szam keveresebol :
Ha kiindulo esetben minden szam a neki megfelelo 
sorszamu helyen van, azaz a sorrend 1, 2, 3.
Es jeloljuk matrixokkal annak a valoszinuseget, hogy egy 
adott elem egy adott pozicioban van.
A matrixban levo i-edik sorban levo j-edik elem jelolje
annak a valoszinuseget, hogy az i-edik szam eppen a j-edik 
helyen van.
Azaz kiindulasnal :

  1 0 0
  0 1 0
  0 0 1

Mert minden elem helye keveres elott ismert.
Ezutan harom lepes kovetkezik ami kozben a valoszinusegek 
megvaltoznak.
Az elso elemre vonatkozo csere utan :
 
  1/3  1/3  1/3

  1/3  2/3   0 

  1/3   0   2/3

A masodik elemre vonatkozo csere utan ;

  1/3  1/3  1/3

  4/9  1/3  2/9

  2/9  1/3  4/9

A harmadik elemre vonatkozo csere utan :

   1/3    1/3   1/3

  10/27   8/27  1/3

   8/27  10/27  1/3

Azaz lathato, hogy a kapott eredmeny nem veletlenszeru.
A kapott eredmeny szimulacioval is konnyen ellenorizheto,
azaz ezzel a rendezessel a 2-es szam 10/27 valoszinuseggel
lesz az 1-es helyen es 8/27-eddel a helyen marad!
( 2 elemu tombre a modszer viszont meg helyes).
A modszeren lathato, hogy mindig egy adott oszlopot tesz
veletlenszeruve ( 1/3-as ertek) de kozben az elozoleg
veletlenszeruve tett oszlopertekeket elrontja.
A hiba nem tul nagy, de hiba!

    irta:
> Talan a legegyszerubb az lenne ha venned a tombodet feltoltve,
> majd randommal generalnal szamparokat, majd a paroknak megfelelo
> indexu parokat felcserelned.

Sajnos csak ugy spontan ez a modszer sem jo mert, hany szampart
generaljon ( nincs eles hatar ahonnan a modszer mar pont jo).

Viszont az elso algoritmus javitasa mar jo. A modszer
kizarja, hogy a matrix mar 'veletlenszerusitett' oszlopai
elromoljanak.
A javitott algoritmus:

tomb[N] { N > 1}

Eljaras Osszekavar
ciklus i = N downto 2
  seged=tomb[i]
  y=Veletlenszam(i)
  tomb[i]=tomb[y]
  tomb[y]=seged
Ciklus vege
Eljaras vege

Az elobbi matrixokkal :
Kiindulas:  
  1 0 0      
  0 1 0
  0 0 1

i = 3 utan :

  2/3   0   1/3
   
   0   2/3  1/3
 
  1/3  1/3  1/3

i = 2 utan :

  1/3  1/3  1/3

  1/3  1/3  1/3

  1/3  1/3  1/3
   
Udv!                         Csaba

Sziasztok!

Nem tud valaki veletlenul egy hasznalhato awk leirast magyarul?
Link is johet. Elore is koszonom!

Balage