algoritmus

[Zoltan Balaton]

ano,ja proste potrebujem vediet pravidla..chapte ma,v zivote som to nevidel taketo obrazky,ujo na prednaske mi to nevysvetlil pretoze si myslel ze to mam vediet ..len potrebujem prist na princip..pochopit to od piky..potom to pojde samo..matika nebol nikdy problem

teraz mi skuste vysvetlit ten prvy priklad
v tom prvom to chapem viacmenej,len nechapem napr tomuto
2. deklaracia premennych, inicializacia na nulu (N - nesuhlas, S - suhlas)

a potom co znamenaju sipky v obdlznikovych diagramoch

[faugusztin]

Teraz vazne ? Ide len o rozlozenie problemu do krokov. Ak toto nevies, tak mas problem, pretoze rozkladanie komplexneho algoritmu na dielcie kusky, ktore je uz mozne naprogramovat je prave to, co robi programatora programatorom.

2) Nastavime si pocitadla S (stary) a N (novy) na nulu, kedze chceme pocitat od nuly
3) Nacitame zo vstupu (to je jedno odkial, napriklad z klavesnice) ciselnu hodnotu, ktoru chceme spracovat, teda rok narodenia.
4) pozrieme sa, ci je toto cislo mensie alebo rovne 2000, a podla toho ci je mensie alebo nie ideme do vetvy 5 (ak je rok vacsi ako 2000) alebo 6 (ak je rok mensi alebo rovny 2000). V kazdom opakovani sa vykona vzdy iba jedna z moznosti 5 alebo 6, nakolko cislo nemoze byt mensie aj rovne alebo vacsie ako 2000. Moze byt bud iba mensie a rovne 2000, alebo vacsie ako 2000.
5) v tomto kroku zvysime cislo v pocitadle N o 1, kedze v kroku 4 sme zistili ze nacitana hodnota je vacsia nez 2000.
6) v tomto kroku zvysime cislo v pocitadle S o 1, kedze v kroku 4 sme zistili ze nacitana hodnota je nizsia alebo rovna 2000.
7) Skontrolujeme, ci uzivatel chce zadat dalsie cislo (znova je to napriklad vstup z klavesnice, ked sa ho program opyta na otazky Ano/Nie). Ak uzivatel odpovie ano, tak sa skoci na krok 3 a cely proces sa od toho bodu znova opakuje. Vsimni si, ze sa nejde naspat na bod 2, takze sa vzdy pripocita dalsie cislo bud do N, alebo S. Ak uzivatel odpovie ze nechce pokracovat, tak pokracujeme dalsim krokom (8).
8) Spocitame pocet zadanych cisiel, co je sumar S a N.
9) Vypise celkovy pocet zadanych rokov narodeni, pocet rokov narodeni pred alebo rovne 2000 a pocet rokov narodeni nad 2000.

S<-0 = priradime do S hodnotu 0.
S<-S+1 - priradime do S aktualnu hodnotu S, ku ktorej pripocitame cislo 1. Ak bola hodnota S pred tym krokom 0, tak vysledkom bude S<-0+1, teda nova hodnota S bude 1. Ak mala hodnotu napriklad 195, tak vysledkom bude S=195+1, teda nova hodnota S bude 196.
C<-S+N, priradi do premennej C sumar obcashu premennych S a N.

A tak dalej. Osobne nechapem ako nemozes chapat ten diagram, sice som napriklad ja v zivote podobny diagram nevidel, ale je pochopitelny na prvy pohlad.

[Zoltan Balaton]

dpc..aky mam problem..ved ja to prvy krat vidim..ty si to vedel hned bez toho aby si sa to naucil ?

dik za rady

[faugusztin]

Ano, vedel. Seriozne, pozries sa na to, a musis to tam vidiet aj so sedliackym rozumom.

Sipka od 0 smerom na S. Co to moze asi zmanenat. Asi 0 do S, teda ak vies ze ide o program, tak to musi teda zmanenat priradenie 0 do premennej S.
Sipka od S+1 smerom na S. rovnaka logika - do S priradime aktualnu hodnotu S plus 1.

[M1ch4l]

V tom, ze :
3) priama vymena obsahu premennych nie je mozna.

pretoze:

mas dve premenne, x a y a chces ich vymenit.
ked napises:

Kód: Vybrať všetko

x= y;
y= x;

tak v prvom kroku sa do x dosadi y, teda v oboch premennych mas rovnaku hodnotu a v druhom kroku sa do y dosadi x, ale kedze sa predtym do x dosadilo y, skutocna hodnota y sa nezmeni.
Tymto si stratil hodnotu premennej x.

Ked pouzijes pomocnu premennu:

Kód: Vybrať všetko

z= x;
x= y;
y= z;

tak si najskor hodnotu premennej x odlozis vedla do z (aby si ju nestratil), potom prehodis hodnotu y do x, a posledne prehodis hodnotu z do y, teda v x bude povodna hodnota y, a v y bude povodna hodnota x, premenne su prehodene, vsetci su radi.

Snad sa po niekom neopakujem

skusim ti este nejako polopaticky vysvetlit to s tymi rokmi. Je to velmi, velmi, velmi, velmi....velmi jednoduchy algoritmus. Staci sa nad tym trosku zamysliet, a je to jasne jak facka.

pozor: mam o jedna posunutu hranicu storoci oproti obrazku. Ktore je spravne, si zistis na wiki alebo urob podla obrazku.

Tvojim vstupom je nejaka postupnost kladnych celych cisel. Tie postupne citas.
Budeme pracovat este s tromi premennymi, vsetky budu typu int a nainicializovane na 0, teda:

Kód: Vybrať všetko

int C = 0; //to je to C z obrazka
int N = 0; //toto bude pocet ludi, ktori sa narodili v aktualnom storoci
int S = 0; //toto je pocet ludi, ktori sa narodili pred rokom 2000, teda v starom storoci.

Spravne by sme asi mali aj osetrovat vstupy, ktore by patrili do 19. a 22. storocia, ale to zatial nechame tak.
Najskor sa zameriame len na dva typy: pred rokom 2000 a po roku 2000(vratane).
Vzdy, ked precitas jedno cislo (to je ten rok), tak sa pozries, do ktoreho storocia spada. Kedze mame teraz rok 2011, tak sme v 21. storoci, a to nase storocie je ohranicene rokmi 2000 a 2099. Nas pre jednoduchost zaujima len ta dolna hranica.
Tak urobime to, ze porovname ten precitany rok s 2000 operatorom >= v podmienke. Pozor, zvolil som iny operator ako je v obrazku.
Ak ano, tak zvysime pocet ludi narodenych po 2000 o 1. A ak nie, tak zvysime pocet ludi narodenych pred 2000 o 1.
Teda napiseme:

Kód: Vybrať všetko

if(rok >= 2000) //nasli sme cloveka, co je narodeny po roku 2000 (vratane), huraa, evidujeme. toto je sipka nie v obrazku.
{
     N++; //alebo N = N+1; zalezi na jazyku, v akom to budes pisat
}
else  //podmienka neplati,sme nasli cloveka narodeneho pred 2000, tak ho evidujeme do druhej premennej. toto je sipka ano v obrazku.
{
     S++; 
}

nesmies zabudat, ze toto musis urobit pre kazde cislo, ktore nacitas, takze to musi byt zabalene v nejakom while cykle. Ten while cyklus je dlha sipka smerom hore v obrazku.

ked uz sa dostaneme von z toho while cyklu - neprislo nam ziadne nove cislo, tak este do C dosadime S + N, teda dokopy pocet rokov, ktory sme dostali na vstupe. A samozrejme urobime vystup. To zalezi na jazyku, v akom to budes pisat. Myslim, ze v inej teme si hovoril nieco o C++, tak ti to napisem v C++.

Kód: Vybrať všetko

C = N+S;
std::cout << C << std::endl;
std::cout << S << " ludi pred 2000" << std::endl;
std::cout << N << " ludi po 2000" << std::endl;

Dufam, ze som sa tam nepomylil v tych stringoch a ze sa to vypisuje tak.

Ci sa to da vysvetlit este jednoduchsie, neviem. Snad som pomohol, ale mam pocit, ze uz tu len opakujem, co pisali ludia predo mnou. Ked len okopirujes vsetky tie kusky kodu, co som ti tu dal, tak ti to samozrejme nepojde. Treba to spravne poskladat do jedneho celku. A este samozrejme, ak to pises v C++ alebo C#, tak si musis napisat citanie toho vstupu, co je podla mna narocnejsie ako tento algoritmus. Ak to pises v pascale, tak tam su vstavane citacky aj pre cisla. Teda mozno v C++ nejaka citacka cisel v knizniciach je, neviem.

[materik]

... napisat citanie toho vstupu, co je podla mna narocnejsie ako tento algoritmus

toto si myslel vazne?

[M1ch4l]

tak v takom C# bez nejakych kniznic rozhodne nie je ziadna metoda, co by citala cisla sama. Vie citat len znaky a retazce, cisla si musis vyrabat z toho sam.
v C++ neviem, ci je...
v pascale samozrejme je.

Takze zalezi na jazyku, ako som pisal. A ano, myslim to vazne. Podla mna je zlozitejsie napisat tzv. Hornerovo schema (pri citani po znaku) ako porovnavat cisla s 2000. A manipulacia s retazcami, to ich asi este neucili, ked maju takuto ulohu.

[faugusztin]

V C samozrejme je
http://www.cplusplus.com/reference/clib ... dlib/atoi/

[M1ch4l]

no to je konverzia zo stringu, nie je to tak priamo ako v pascale, teda read(cislo)
mozno lepsie citat po znaku a urobit to tak, kto vie, ako to vyjde casovo...asi zanedbatelny rozdiel
kazdopadne ak sa pocita so zlymi vstupmi, vtedy je lepsie podla mna po znaku citat, osetris si to sam. Neviem ako funguje ta metoda atoi, este nam to nespominali...zatial s C++ len zacinam, no mam za sebou dva semestre programovania (1. sme pouzivali pascal, 2. c#, velmi dobre zvolene poradie podla mna).
vlastne to tam pisu...potom ale neviem, co ro urobi so vstupom napr. "254abcd16", ci to zoberie len tych 254 a 16 sa strati.

[pEpinko]

Prikaz na vymenu "premennych" v principe na x86 existuje (http://en.wikipedia.org/wiki/XOR_swap_a ... nstruction).

V C precitas cislo zo vstupu ako scanf("%d", &premenna), v C++ ako cin >> premenna.

[Mammut]

nepochopil som preco tam je to "z" a preco nemohlo byt bez neho..

Kľudne by to šlo aj bez neho :

1. Začiatok
2. Načítanie x,y
3. x <-- x + y
4. y <-- x - y
5. x <-- x - y
6. Vypíš hodnoty x,y

Prikladám kódovanie v C :


#include <stdio.h>
#include <stdlib.h>

int main(void) {

int x1,y1;
scanf("%d %d",&x1,&y1);
x1=x1+y1;
y1=x1-y1;
x1=x1-y1;
printf("%d %d\n",x1,y1);
return 0;
}

[LordKJ]

ale len v pripade cisel

[M1ch4l]

az na to, ze tie cachre machre s + a - trvaju daleko dlhsie ako ked naozaj napises rovnitka. Udajne dnesne prekladace dokazu optimalizovat vymenu dvoch premennych tak, ze sa v skutocnosti ziadne kopirovanie nedeje, ani sa nealokuje pomocna premenna.
Zatial co u tamtoho sa mozno vola nejaky operator += alebo sa vytvaraju "neviditelne" pomocne premenne na ulozenie medzivysledkov, a to sa potom priradzuje...Velmi pravdepodobne pri takej kombinacii prikazov uz prekladac nepozna, ze chces vymenit hodnotu dvoch prvkov.

Ale mozno nemam pravdu. Kazdopadne ano, je to prijatelny postup, pokial nemozes naalokovat ziadnu pamat naviac, co sa nestava.

[pEpinko]

Aby sme to tu preniesli na trochu rigoroznejsiu uroven, dal som oba sposoby do OllyDbg, nech vidime v com sa taketo vymienanie premennych lisi.

Sposob s + a -:

Kód: Vybrať všetko

CPU Disasm
Address   Hex dump          Command                                
00401329  .  8B55 FC        MOV EDX,DWORD PTR SS:[LOCAL.1]
0040132C  .  8B45 F8        MOV EAX,DWORD PTR SS:[LOCAL.2]
0040132F  .  01D0           ADD EAX,EDX
00401331  .  89C1           MOV ECX,EAX
00401333  .  29D1           SUB ECX,EDX
00401335  .  894D FC        MOV DWORD PTR SS:[LOCAL.1],ECX
00401338  .  29C8           SUB EAX,ECX
0040133A  .  8945 F8        MOV DWORD PTR SS:[LOCAL.2],EAX

Sposob s pomocnou premennou:

Kód: Vybrať všetko

CPU Disasm
Address   Hex dump          Command                              
00401329  .  8B45 F8        MOV EAX,DWORD PTR SS:[LOCAL.2]
0040132C  .  8B55 FC        MOV EDX,DWORD PTR SS:[LOCAL.1]
0040132F  .  894424 08      MOV DWORD PTR SS:[ESP+8],EAX
00401333  .  8955 F8        MOV DWORD PTR SS:[LOCAL.2],EDX
00401336  .  8945 FC        MOV DWORD PTR SS:[LOCAL.1],EAX

Kompilovane bolo pomocou MinGW (gcc) s optimalizaciami -O2. Zdrojovy kod som pouzil od Mammuta.

Co si mozeme hned ako prve vsimnut je, ze pre hardware neexistuje nic ako premenna. Vytvorenie pomocnej "premennej" je vlastne 3 riadok kodu. Ale ako dalej vidime, tato "premenna" sa vlastne nepouzije. Pouziju sa iba registre eax, edx a dve pamatove miesta. Sam sa cudujem naco tento riadok vlastne generator kodu vyrobil.

Sposob s aritmetickymi operaciami nageneruje este nejake add a sub (mimochodom dali by sa zamenit za XOR, ktory je asi trochu rychlejsi). Co je ale dolezite pouzivaju sa tam az tri registre eax, edx, ecx, cize v istom zmysle sa tam tiez pouzivaju tri premenne. Nicmenej nerobi ziadny zbytocny pristup do pamate, co je vzdy velmi draha operacia.

Vymenenie obsahu pomocou trochu premennych bude velmi pravdepodobne rychlejsie hlavne kvoli faktu, ze moderne procesory pouzivaju pipeline na spustanie viacerych operacii naraz. Pri add a sub sa musi cakat na predchadzajuci vysledok, co znemoznuje ich paralelne vykonavanie.