Funkcia v C - faktorial

[Josef Pavlik]

nevěř prezkovi. Jestli už pár let programuje a nepochopil, jak funguje hello world, tak ti nemá co říct. Kromě toho, debugger je sice krásná věc, ale v praxi je poměrně málo použitelný. Krokovat se dá tak leda právě ten hello world, ale na složitější programy se mi osvědčily debugovací hlášky. Prostě si do programu dám pár fprintf(stderr, "cyklus, i=5%", i); a pak se podívám co to při běhu vyhlašuje. Osvědčilo se mi to podstatně víc než krokování programu debugerem. Vyplatí se ti nechat většinu debugovacích hlášek i v produkční verzi programu a v případě potřeby je přesměrovat do file. Pak, když se klientovi někde něco podělá, tak se mrkneš kudy ten program chodil a kde byla chyba.
Ale hlavně, při programování (nejenom) v C bys měl vědět jak program funguje. Pokud to nevíš, tak těžko napíšeš program, který dělá víc než hello world a podobně.

příklad faktoriálu s rekurzí (bez kontroly počtu parametrů a rozsahu):

Kód: [Vybrat]

#include "stdio.h"
void print_fact(int n)
{
  if (n>1) { print_fact(n-1); printf("x"); }
  printf("%d", n);
}
main(int argc, char **argv)
{
  int n=atoi(argv[1]); // fixme - kontrolovat pocet parametru
  // fixme - kontrolovat rozsah hodnot
  printf("%d!=", n); print_fact(n); printf("\n");
}

Samozřejmě to bude žrát spoustu stacku, ale zato je to krátké.
Rekurze je krásná věc, ale v praxi je ve většině případů lepší použít cyklus. Ale zkuste třeba někdo napsat quicksort bez rekurze :-)

[Reklama]

[ApoC]

tak to si naprogramuj funkci na serazeni posloupnosti celych cisel.
Pouzij algoritmus binarniho puleni a mas to procviceny

Binarni puleni se pouziva pro vyhledavani ne pro razeni.

[ApoC]

Krokovat se dá tak leda právě ten hello world, ale na složitější programy se mi osvědčily debugovací hlášky. Prostě si do programu dám pár fprintf(stderr, "cyklus, i=5%", i); a pak se podívám co to při běhu vyhlašuje.

Umet pracovat s debuggerem je stene dulezite jako ovladat samotny programovaci jazyk. Pokud clovek vyviji nejaky slozitejsi kod, ktery se preklada radove treba 30 minut, tak pridani jakekoliv debug hlasky do implementace v header filu muzu zpusobit, ze budete debuggovat cely den a stejne prijdete na prd, protoze mate kod zaneradeny tolika vypisy, ze se v tom proste nevyznate a uz po destate prekladate binarku co se kompiluje 30 minut .

[Kolemjdoucí]

Binarni puleni se pouziva pro vyhledavani ne pro razeni.

Quicksort je založen na binárním půlení.

[Kolemjdoucí]

Kód: [Vybrat]

Ale zkuste třeba někdo napsat quicksort bez rekurze :-)
[/quote]

Levou zadní. V prostředích kde je málo paměti pro stack je dokonce nerekurzivní implementace quicksortu nutnost.

[Reklama]

[and]

Pokud clovek vyviji nejaky slozitejsi kod, ktery se preklada radove treba 30 minut, tak pridani jakekoliv debug hlasky do implementace v header filu muzu zpusobit, ze budete debuggovat cely den a stejne prijdete na prd, protoze mate kod zaneradeny tolika vypisy, ze se v tom proste nevyznate a uz po destate prekladate binarku co se kompiluje 30 minut .

Mohl by jsi uvest priklad takto sloziteho projektu? I kernel se zvladne rychleji...

Ja rozhodne podporuji debug vypisy. Spusteny debuger jsem naposledy videl jen u embedded desek...

[gamer]

Ja rozhodne podporuji debug vypisy. Spusteny debuger jsem naposledy videl jen u embedded desek...

Debug výpisem nenastavíš memory breakpoint, breakpoint při vyhození výjimky a podobné věci. Jinak bych ale používání debuggeru nepřeceňoval, moje zkušenost je taková, že projekty, u kterých bylo nutné často používat debugger, nekončily dobře.

[iwtu]

Mily Vilem.
Super, ze si programujem len tak pre radost, z hanby ci nasrania. Rozdeluj a panuj neries, zvlast, pokial mas problemy s takymi ulohami ako tu pises.  Jednak ta tema nie je trivialna, druhak pri faktorialy je to ale uplne zbytocne, tretiak v praxi to cloveku treba malokedy. Aspon pre mna tak 10 rokov dozadu ta tema fakt nebola trivialna. Vybral si si C, lebo Ti viac sedelo, ok. No mozno by bolo lepsie sa odhladnut po nejakej inej ucebnici Pythonu. Ale ak sa Ti C paci a vyhovuje Ti v nom robit, tak potom asi uvazujes priamociaro a s C by si nemal mat problemy. Sice, nebudes mysliet na take veci ako spominal gamer, napriklad ta implicitna konverzia, ale to nevadi. Tym sa fakt teraz netrap. C je jednoduchy jazyk, ak clovek uvazuje priamociaro, lebo tam nie je skoro ziadna magia. Aj tie pointre su v principe jednoduche a vo svojich malych programikoch by si s nimi nemal mat problem. Teda bez do C. Velmi Ti moze pomoct Ucebnica jazyka C od Herouta. Sice jeden znamy guru vravel, ze Herout tomu C az tak nerozumie, ale to su uz ludia uplne niekde a inde a ja v C nie som doma. Jo, a este jedna vec. Keby bol ucitel a moji studetni by vedeli nieco, co ja nie, tak by som mal z toho velku radost

Ak chces riesit C, do toho ale rozdeluj a panuj teraz este neries. Najprv zvladni ako tak C :-)

Drz sa.

[prezek]

Josef Pavlik: Dokážeš mi pospat, jak se Hello World tahá do paměti? Která knihovna, či jaká část kernelu a jak se stará o to, aby printf začernil/zabělil/vystínoval určitý pixel? Jak se přepíná kontext mezi současně běžícími aplikacemi? Jak se předávají vstupní parametry a návratové hodnoty? U mikrokontrolerů bez operačního systému jakž-takž chápu, jak Hello World funguje, ale jak to probíhá na čemkoliv s operačním systémem, to je mi záhadou.

[Josef Pavlik]

jak se hello world taha do pameti, to zalezi na operacnim systemu a/nebo loaderu. Napriklad v CP/M nebo v MSDOS (v pripade programu.com) se napred program natahne do pameti od adresy 0x100 a pak se spusti od te same adresy. Na ni vetsinou byva skok na zacatek inicializacnich rutin programu.

V linuxu je to zajimavejsi. program se napred spusti a teprve potom se natahne :-). Zjednodusene receno se program namapuje do urciteho mista pameti (coz je prakticky zavolani jednoho syscallu, ktery zinicializuje swapovaci tabulky). Pak se skoci na zacatek tohoto bloku. Pokus o cteni nebo vykonani kodu ve frame pameti, kde neni namapovana zadna fyzicka stranka vede k vyjimce (interrupt), ktera je obsouzena kernelem. Ten do prislusneho frame namapuje fyzickou stranku pameti (kde ji vezme je namet na dalsi kapitolu). Pokud se ukaze, ze tento frame je namapovany na urcity file (text programu), jednoduse se tato cast programu precte z disku a zapise do pameti. Pokud naopak tato adresa mela obsahovat globalni promenne, tato stranka se vynuluje, pripadne zinicializuje.
 
Jak printf zacerni/zabeli/vystinuje urcity pixel? Jednoduse nijak. Printf tady neni proto, aby se staral o takovehle veci. O tohle se stara VGA v pripade textoveho rezimu, pripadne X server v pripade grafickeho rezimu (embeded graficke programy ted nechame stranou). Printf je funkce libc. Prevezme parametry, na jejich zaklade vygeneruje output string a s nim zavola funkci puts nebo fwrite. Tyto dve posledni funkce vedou na zavolani syscallu kernelu, ktery uz to posle na VGA nebo pres nejake presmerovani do X nebo jineho grafickeho serveru.

Jak se prepina kontext mezi soucasne bezicimi aplikacemi? To je zalezitost kernelu, to muzes maximalne lehce ovlivnit, ale tezko se do toho hrabe.

Jak se predavaji parametry a navratove hodnoty (predpokladam, ze mas na mysli parametry funkci) - vetsinou na stacku, navratova hodnota se pravdepodobne predava v registru (pokud se nejedna o strukturu). Je to zajimava otazka, tohle je jedna z veci, ke kterym je debuger uzitecny. Tady bude taky dost zalezet na parametrech kompilatoru.

Ja samozrejme nerikam, ze debuger neni vubec k nicemu, obcas pouzivam ddd, ale pouzivam ho tak jednou za rok.


Pokud chces vedet ktere knihovny se tahaji z urcitemu programu, tak na to je ldd. Tohle je napriklad ten programek na faktorial, ale stejne to bude pro jakykoliv C program, kde nepotrebujes jine knihovny nez libc.
root@moonlight:/tmp# ldd ./f
        linux-gate.so.1 =>  (0xb7738000)
        libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb756e000)
        /lib/ld-linux.so.2 (0xb7739000)
co je to linux-gate.so.1 nemam tuseni, pravdepodobne je to interface na volani kernelu. ld-linux.so.2 je loader a libc.so.6 obsahuje vsechny standardni C funkce jako printf, qsort a podobne.

[ogar]

Pokud by jsi to chtel s rekurzi, ktera faktorial vypocita a pritom jenom tak nahodou pri navratu z rekurze zobrazi i tu posloupnost:

Kód: [Vybrat]

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

static
int fakt(int x){
int Result;

if (x<=1){
Result=1;
printf("1");
}
else{
Result=x*fakt(x-1);
printf("*%d",x);
}

return Result;
}

int main(int argc,char *argv[]){
int Result,x;

printf("Enter number:");
Result=scanf ("%d", &x);
printf("\n");

if (Result==1){ // something acceptable
printf("%d!=",x);
Result=fakt(x);
printf("=%d\n",Result);
}

return 0;
}

Ale jak uz tady nekolikrat zaznelo: dulezite je vedet co chces dosahnout (co ma program delat), pak si poradne promyslet, jak to efektivne udelat a pak uz je jedno, v jakem jazyce to naprogramujes :-)

Ono pri tom reseni je dobre si problem rozlozit na vice mensich, ktere se daji resit vicemene samostatne a paralelne.
Ale pak je duelzite vybalancovat pomer mezi mnozstvim jednotlivych kousku/komponent a jejich rozhrannim:
Na jedne strave je klasicky spagheti kod, a nad druhe treba java, kdy na kazdy 'prd' sa dela specialni trida s 'kosatym interface' (milion funkci a frameworku), a pak sa vyslednem kodu a factory constructor factory maker .... (nejenom) clovek ztrati :-)

[ogar]

Pokud by jsi to chtel s rekurzi, ktera faktorial vypocita a pritom jenom tak nahodou pri navratu z rekurze zobrazi i tu posloupnost:

Kód: [Vybrat]

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

static
int fakt(int x){
int Result;

if (x<=1){
Result=1;
printf("1");
}
else{
Result=x*fakt(x-1);
printf("*%d",x);
}

return Result;
}

int main(int argc,char *argv[]){
int Result,x;

printf("Enter number:");
Result=scanf ("%d", &x);
printf("\n");

if (Result==1){ // something acceptable
printf("%d!=",x);
Result=fakt(x);
printf("=%d\n",Result);
}

return 0;
}

Ale jak uz tady nekolikrat zaznelo: dulezite je vedet co chces dosahnout (co ma program delat), pak si poradne promyslet, jak to efektivne udelat a pak uz je jedno, v jakem jazyce to naprogramujes :-)

Ono pri tom reseni je dobre si problem rozlozit na vice mensich, ktere se daji resit vicemene samostatne a paralelne.
Ale pak je duelzite vybalancovat pomer mezi mnozstvim jednotlivych kousku/komponent a jejich rozhrannim:
Na jedne strave je klasicky spagheti kod, a nad druhe treba java, kdy na kazdy 'prd' sa dela specialni trida s 'kosatym interface' (milion funkci a frameworku), a pak sa vyslednem kodu a factory constructor factory maker .... (nejenom) clovek strati :-)