Homepage » C cheatsheet

C – cheatsheet

Tento přehled vznikl pro účely výuky programování pro jednu nadšeneckou skupinku. Můj záměr se rozšířil na vytvoření přehledné učebnice, ze které se dokáže naučit programovat inteligentní samouk. Programování se snažím vysvětlovat tak, aby student chápal, co se během tvorby kódu i během výkonu programu odehrává v operačním systému a uvnitř počítače, proto lekcím programování předcházelo několik lekcí obecné informatiky:

Doporučuji tedy se před začátkem čtení případně dovzdělat, pokud vám něco není povědomé. Abyste se mohli podle následujícího textu začít učit, nainstalujte si vim a gcc (v Debianu ze stejnojmenných balíčků).

Úvod: Překlad programu

Kostra programu

Procvičovací úkol

Opište výše uvedený program, přeložte ho za použití chytrých přepínačů a pak ho spusťte.

Proměnné

Procvičovací úkol

Napište program, který nadeklaruje celé číslo s identifikátorem prvocislo s hodnotou 11, reálné číslo s identifikátorem ludolfovo s hodnotou 3.1415926, znak pismenko s hodnotou q, boolean pravda s hodnotou true a textový řetězec pisnicka s hodnotou Jsme silni jak silny je lano co k nebi nas po-ooou-ta. Takový program při spuštění nedává žádný výstup, za úspěch považujte, když se přeloží bez chyb.

Výstup a vstup

Procvičovací úkoly

Minulý program s deklaracemi proměnných doplňte tak, aby takto vypsal identifikátory a hodnoty proměnných: prvocislo je 11, ludolfovo je 3.14159, pismenko je q a pisnicka je Jsme silni jak silny je lano co k nebi nas po-ooou-ta. Potom program doplňte tak, že hodnoty bude zadávat uživatel z klávesnice a tyto se pak vypíšou. Na boolean se vykašlete, ten se jednoduše vypisovat nedá.

Počítání věku na Biblickou stezku: Zobrazit

Do Biblické stezky se přihlašují trojice lidí – hlídky. Součet věků hlídky nemá přesáhnout 42. Věk jednotlivců se určuje pouze podle roku narození. (Takže ikdyby někdo byl narozen 31.12.1994, v roce 2011 by nesměl soutěžit, protože maximální věk je 16.) Vy máte napsat program, co tento součet vypočítá.

Vstup programu (to, co se po spuštění programu zadá z klávesnice):
Jméno1 Příjmení1 RokNarození1
Jméno2 Příjmení2 RokNarození2
Jméno3 Příjmení3 RokNarození3
Výstup programu v roce 2012 (to, co se potom vypíše na obrazovku):
Jméno1, Jméno2 a Jméno3 maji dohromady vek SoučetJejichVěků.
Příklad:
Vstup:
Daniel Friedrich 1999
Michaela Mazna 1999
Tadeas Friedrich 1994
Výstup:
Daniel, Michaela a Tadeas maji dohromady vek 44.

Předpokládejte, že jméno ani příjmení nemá víc, než 31 znaků.

Kdo byste chtěli dál procvičovat, ještě tam můžete třeba na začátku zadávat, co je zrovna za rok, aby se nemusel každý rok zdroják měnit.

Podmínky

Procvičovací úkol

Upravte program pro Biblickou stezku, aby oznámil, zda hlídka smí soupeřit.

Napište program, který zjistí, zda se dá ze tří zadaných čísel sestrojit trojúhelník s těmito délkami stran a pokud ano, tak zda je pravoúhlý.

Intermezzo: přehlednost kódu

Náhodná čísla

Procvičovací úkol

Napište program, který si vymyslí první číslo, operand (+,-,*,/) a druhé číslo a vypíše příklad na obrazovku. Uživatel napíše výsledek. Program mu odpoví spravne nebo spatne a ukončí se. Zkuste pak taky zjistit a vypsat, kolik sekund uživatel příklad počítal. Čísla generujte v rozsahu od 0 do 20. Dejte ale pozor, aby se nedělilo nulou.

Cyklus while

Procvičovací úkol

Napište program, který si vymyslí číslo mezi 0 a 99 a uživatel hádá. Program mu vždy odpoví vic nebo min nebo, když se uživatel trefí, na kolikátý pokus to uhodl a ukončí se.

Motivační úkoly

Napište program, který vypíše 1000 hvězdiček.

Přepište ho na program, který vypíše čísla od 0 do 999.

Přepište ho na program, který vypíše druhé mocniny čísel od 0 do 999.

Cyklus for

Procvičovací úkoly na cykly while a for

Zadá se číslo a program vypíše tolik hvězdiček.

Zadá se číslo a program vypíše prvních jeho 10 násobků.

Zadá se číslo a program vypíše všechny jeho násobky, které jsou menší, než 100.

Zadávají se čísla, dokud se nezadá 0. Pak program vypíše jejich součet.

Zadávají se čísla, dokud se nezadá 0. Pak program vypíše, které bylo největší.

Zadá se textový řetězec, program ho vypíše pozpátku.

Zadá se číslo a program vypíše správně velký trojúhelník z hvězdiček. Příklad:

5
*****
****
***
**
*

Zadá se číslo a program vypíše kruh z písmen (třeba X) o daném poloměru. Příklad:

4
    X    
  XXXXX  
 XXXXXXX 
 XXXXXXX 
XXXXXXXXX
 XXXXXXX 
 XXXXXXX 
  XXXXX  
    X    

Zadá se číslo a program ho vypíše ve dvojkové soustavě. (Pozpátku to je jednodušší.)

Zadá se číslo ve dvojkové soustavě a program ho vypíše v desítkové. (To vstupní si raději načtěte jako string.)

Zadá se číslo a program vypíše všechna prvočísla mezi 0 a tímto číslem.

Pole

Procvičovací úkoly na pole

Zadá se číslo, program vytvoří tak velké pole, naplní ho náhodnými čísly mezi 0 a 100 a pak hodnoty prvků pole vypíše.

Předchozí program se rozšíří tak, že uživatel zadá další číslo a program mu řekne, zda a na jakém indexu je to číslo v poli.

Zadá se číslo a program vytvoří tak velké pole, naplní ho nějakou rostoucí posloupností čísel (větší indexy mají větší hodnoty) a pak hodnoty prvků pole vypíše.

Předchozí program se zase rozšíří tak, že uživatel zadá další číslo a program mu řekne, zda a na jakém indexu je to číslo v poli, a nějak chytře, aby nezkoumal zbytečně moc prvků.

Vezme se program, co vytváří pole naplněné náhodnými čísly a doplní se tak, že je seřadí podle velikosti. Např.:

6
V poli jsou cisla:
52 12 96 3 12 77
Setridene pole:
3 12 12 52 77 96

Složitost algoritmů (ohleduplný úvod)

Motivace

Měli jsme dva programy na vyhledání prvku v poli. Jeden prostě projde celé pole, druhý funguje jen na rostoucích polích, zato se zdá, že rychleji. Je to skutečně tak?

Povídání o složitosti

Úkoly na počítání složitosti

Spočítejte složitost hledání prvku v neuspořádaném poli. (Fáze vytváření pole není součástí algoritmu.)

Spočítejte složitost hledání prvku v uspořádaném poli. (Fáze vytváření pole není součástí algoritmu.)

Spočítejte složitost třídění pole. Najděte rychlejší algoritmus. =:)

Intermezzo: Přesměrování vstupu v shellu

Motivace

Dejme tomu, že dostanete za úkol seřadit 100 jmen, zadávaných z klávesnice, podle abecedy. Při testování takového programu toho napíšete víc při zadávání vstupu, než při psaní kódu.

Shell a standardní vstup/výstup

Procvičovací úkol

V souboru prace.txt plném pracujícího lidu je na každém řádku

Jméno Příjmení Datum ČasPříchodu ČasOdchodu HodinováMzda
např.
Ferdinand Kobliha 29.2. 11:31 23:47 65
, poslední řádek se vyznačuje tím, že je na něm jedna tečka a jinak nic. Vaším úkolem je vypsat jména a celkové mzdy, které máte vyplatit, každé jméno jen jednou. Jméno ani příjmení není delší, než 31 znaků. Různých lidí není víc, než 100. Výsledky vypište do mzdy.txt. Zde najdete vzorový vstup.

Bloky

Pokračování časem. Určitě by měly přibýt ještě následující kapitoly:

Funkce

Motivace

Jak by vypadal program, který by třídil dvě pole? Pět polí? Dvacet polí?

Opakování kódu

Procvičovací úkoly

Napište funkci, která vypíše objem válce, parametry budou poloměr podstavy a výška. Můžou to být i necelá čísla.

Teď ať ta funkce objem vrátí a vypište ho až v pokračování hlavní funkce.

Paměťový zásobník

Ukazatele

Procvičovací úkol

Napište funkci, která dostane dvě čísla a prohodí jejich hodnoty.

Napište funkci, která dostane pole a jeho velikost a setřídí ho.

xkcd

Rekurze

Procvičovací úkol

Spočítejte složitost výpočtu faktoriálu rekurzí a porovnejte to se složitostí výpočtu faktoriálu cyklem for.

Napište za použití rekurze funkci, která počítá Fibonacciho posloupnost. Ta je definována takto:
fi1 = 1; fi2 = 1; pro n > 2 fin = fin-1 + fin-2
Pak tutéž funkci napište bez rekurze.
Pak porovnejte složitosti těchto funkcí. Zjistíte, že zatímco u faktoriálu to vyjde nastejno, v tomto případě rekurze zoufale zaostává, že je v podstatě nepoužitelná. Jak si s tím poradit, o tom zas jindy.

Globální proměnné

Struktury

Zatímco rekurze z hlediska jazyka nebyla nic objevného, zato měla nedozírné důsledky z hlediska uvažování o problémech, se strukturami je to přesně naopak. Problém vám nevyřeší, obejdete se bez nich, ale je to tuze praktická věc.

Dynamické programování

Pokud jste ještě nečetli kapitolu o rekurzi a nepokusili jste se splnit úkoly k ní, nemá moc smysl se pouštět do této.

Procvičovací úkol

Jaká je složitost zrychleného algoritmu na počítání Fibbonaciho posloupnosti?

Máte n záhonků vedle sebe. Na každém můžete zasadit mrkev nebo petržel, nesmí však být dva záhonky petržele hned vedle sebe. Kolika způsoby lze osadit vašich n záhonků?


Časem by měly přibýt ještě tyto kapitoly:

A u těchto to konečně začne být opravdu zábava:

Hlavní programová smyčka

Grafika

Síťování

Tato témata jsou pokročilejší:

Preprocesor

Kód ve více souborech

Automatizovaný překlad

Dynamická alokace paměti

Dynamické datové struktury