Duebelstäresystem Sich - eng vun den einfachsten Weeër en Element an engem vill ze fannen

Ganz oft, Programméierer, och Ufänger, mat der Tatsaach konfrontéiert, datt et eng Rei vun Zuelen, déi eng spezifesch Zuel fannen muss. Et ass dës Kollektioun ass eng vill genannt. An ze fannen Elementer an et, et sinn enger ganzer vun Manéieren. Mä déi einfach vun hinnen kann en Duebelstäresystem Sich iwwert déi riets Säit considéréiert ginn. Wat ass dës Method ass? A wéi Duebelstären Sich ze realiséieren? Pascal ass am einfachsten Ëmwelt fir d'Organisatioun vun esou engem Programm, also mir wäert et benotzen ze studéieren.

Éischt, analyséieren, wat d'Virdeeler vun dëser Method sinn, et ass esou kënne mir verstoen, Wat ass de Punkt an der Etude vun der Sujet. Also mer elo mat enger Dimensioun vun op d'mannst 100000000 Elementer eng Partie Problemer hunn, déi e puer ze fannen braucht. Natierlech, kann dëse Problem einfach duerch eng einfach linear Sich geléist ginn, an deem mer den Zyklus gi benotzt gëtt déi néideg Element mat all deenen, déi an der vill sinn vergläichen. De Problem ass, dass d'Ëmsetzung vun där Iddi gëtt ze vill Zäit huelen. An engem einfachen Pascal Programm an puer Behandlungen, an dräi Linnen vun der Haaptrei Text, Dir wäert et net virdrun, mee wann mir zu engem méi oder manner grouss Projete mat enger grousser Zuel vu Secteuren a gutt Funktionalitéit kommen, wäert de Programm prett sinn fir ze laang iwwerlaascht gin. Virun allem wann de Computer ass eng schwaach Leeschtung. Dofir, et ass en Duebelstäresystem Sich, déi op d'mannst zweemol Sich Zäit reduzéiert.

Also, wat ass de schaffen Prinzip vun dëser Method? Direkt sollen et soen dass Duebelstäresystem Sich Wierker ass net an all vill, mä nëmmen op engem zortéiert Formatioun vun Zuelen. Bei all Schrëtt Mëtt Element vun der vill geholl (Bedeitung d'Zuel vun de Element). Wann déi néideg Zuel méi grouss wéi ass d'Moyenne, dann all déi lénks ass, dass manner wéi d'Moyenne Zell ass, kann discarded ginn an net do am Wanterschlof war. Ëmgedréit, wann manner wéi d'Moyenne - ënnert deenen Zuelen un d'Recht, kënnt Dir net Sich. Dann wielt en neie Sich Géigend, wou déi éischt Element gëtt d'Mëtt Element vum ganze vill ginn, an de leschten an de leschten gëtt. Der Moyenne Zuel vun neien Terrain wäert ¼ vun all Segment ginn, dass, (déi lescht Element + d'Mëtt Element vum ganze vill) ass / 2. Kéier, ass déi selwecht Operatioun - e Verglach mat der Moyenne Nummer vun der Partie. Wann der Zil- Wäert ass manner wéi d'Moyenne, refuséieren mer der rietser Säit, an och nächste ze maachen, bis elo dëst Mëtt Element net Wonsch géif.

Natierlech, ass et am beschten op e Beispill vun Wanterschlof wéi Duebelstären Sich ze schreiwen. Pascal hei wäert jiddereen Kostüm - Versioun net wichteg ass. Loosst d'engem einfachen Programm schreiwen.

Et ass eng vill vun 1 bis h ënnert dem Numm "massiv", eng Variabel déi ënnescht Grenz vun der Sich besot, genannt "niz", der ieweschter Limite, genannt "verh", der Moyenne Sich Begrëff - "sredn"; an déi néideg Zuel - "isk".

Also éischte mir der ieweschter a manner Limite vun der Gamme Sich uginn:

niz: = 1;
verh: = h + 1;

Dann organiséieren den Zyklus "bis ënnen ass manner wéi d'Uewergrenz":

Iwwerdeems niz fänken

Bei all Schrëtt, Gruef mir de Segment 2:

sredn: = (niz + verh) Divisiounen 2; {Benotzt der Funktioun Divisiounen, well de Gruef ouni Rescht}

All Zäit vun iwwerpréiwen. Well de Punkt schonn fonnt gouf, ob déi mëttel- Wënsch ass, di Zyklus:

іf sredn = isk dann Stand;

Wann d'Mëtt Element vun der vill méi wéi Wënsch, déi lénks Säit verännert, dat ass, z'iwwerwaachen an der ieweschter Grenz vun der Moyenne Element:

wann massiv [sredn]> isk dann verh: = sredn;

A wann op der Géigendeel, mécht et der manner Grenz:

aneren niz: = sredn;
Enn;

Dat ass all dass am Programm ginn.

Loosst eis betruecht, wéi et der Duebelstäresystem Method an der Praxis kucken gëtt. Betruecht dëser vill: 1, 3, 5, 7, 10, 12, 18 an et gëtt der Zuel 12 sichen.

Am Ganzen hu mir 7 Elementer, sou wäert d'véiert mëttelfristeg, de Wäert 7.

Zënter méi wéi 12, 7, 1,3 an 5 Elementer, kënne mir déi verännert. Dunn hu mir d'Nummer 4, 4/2 kee schwätze komm ass ass 2. Also eng nei Element eng Moyenne vun 10 ginn.

Zanter 12 méi wéi 10 ass, verännert mir 7. nëmmen 10, 12 an 18 bleift.

Hei, d'Mëtt Element ass schonn 12, ass et déi néideg Zuel. Dës Aufgab ass ofgeschloss - Nummer 12 fonnt.