Programování v C++ — zápočet LS 2007

Viz také Zkouška LS 2007

29. 5. 2007 nevimkvkolik: Osobně jsem u toho nebyl, ale jako zadání bylo toto: [soubor zadani0531.gif se zřejmě někam ztratil:/]

Tak dnes 30. 5. 2007 o 10:00 sme dostali takéto zadanie: naprogramujte sčítanie, násobenie a odčítanie dlhých čísel. Myslím, že túto úlohu by som zaradil medzi tie ľahšie, aj keď dá zabrať... Roman

30. 5. 2007 14:00: No nevím, když jsme přišli, tak ještě vyháněl lidi, co tam od těch desíti byli – takže někomu to skutečně dá zabrat. My měli tuto úlohu (řešení jsem připsal do zdrojáku: file:adamuvzapocet200705301400.c. Jde vlastně o další variaci na statistiku slov v souboru. První lidé odcházeli po hodině, hodině a půl, předpokládám ale, že někteří tam byli i o dost déle, jako na jiných termínech. Tak hodně štěstí, ať se to nestane vám. — Adam

4. 6. 2007 10:00 No...dostali jsme dnes takovouto úlohu...program dostane jako prametry m a n což jsou rozměry šachovnice a dále ještě dvojice čísel, což jsou souřadnice speciálních polí, k nimž se dostanu za chvíli. Korektní parametry vypadají třeba takto 8 6 2 3 4 5 1 2 (to jest šachovnice o rozměrech 8 x 6 a speciální pole [2,3], [4,5], [1,2]. Můžeme předpokládat, že parametry jsou zadány korektně. A teď to podstatné – máme koně stojícího na souřadnicích [0,0] a máme zjistit počet polí, na které se můžeme dostat, s tím, že na pole, na které jsme již skočili, se nesmíme vracet (tj. již na něj nesmíme skočit znovu). Význam speciálních polí – pokud kůň dupne na pole [1,1], tak se tato pole ivertují – tzn, že pokud ho máme označené, že už jsme na něm v minulosti byli a teď na něj nemůžeme skočit, tak nyní můžeme a opačně. Kůň se nesmí zacyklit a na pole [1,1] smí skočit i vícekrát. Výstup je počet POLí na kterých jsme byli, ne počet tahů. Pokud jsme na invertovaném poli byli vícekrát, počítáme ho samozřejmě jen jednou. Na první pohled vypadá jednoduše, většina lidí to měla jakžtakž, ale třeba pro jeden vstup nefungovalo....celkem nas tam bylo kolem 20, dalo to asi 5 lidi (já bohužel ne, odcházel jsem něco před druhou a myslím, že ostatní už taky vyhazoval). Tak hodně štěstí...:) — Karel Jakubec

5. 6. 2007 dopoledne file:statistika.zip <— je to nafoceny na webkameru, ale mozna to bude i k precteni. tk

5.6.2007 14.00 Hra 7-UP. Dostaneme obdélníkovou hrací plochu, která se skládá z volných políček "." a zdí "#". Jsou dva hráči a ti mají hrací kameny. Do jednoho rohu postavíme kámen jednoho hráče “O” a do protilehlého rohu kámen toho druhého “X”. Hra probíhá následovně: Hrači se střídají v tazích. Hráč v každém tahu vybere náhodně nějaké volné pole ".", v přímém okolí svých kamenů (ale jen ve svislém a vodorovném směru, ne diagonálně) a zabere všechny soupeřovy kameny v okolí vybraného pole (=přemění jejich barvu na svou). Pokud hráč nemá, jak táhnout (je zablokovaný, nebo už je celá plocha plná), hra končí. Vyhrává ten, kdo má vlastní kamenů. Cílem není vymyslet AI, ale jen hru odsimulovat. Program vypíše počáteční a koncový stav a taky, kdo vyhrál. Program může brát vstup ze souboru (zadaného argumentem), jinak ze stdinu. Hrací plocha může mít rozměry větší než jakákoliv konstanta (=NE staticky alokované pole). Argument -v zapne verbose mód, tj. po každém tahu se pole vykreslí. JAK NA TO? Existuje asi více možností, já si vybral tuto (jistě není nejefektivnější ani nejelegantnější): Hrací plochu mám uloženou jako pole znaků + rozměry. Načtení probíhá asi takto: nejdřív zjistím šířku hrací plochy: dokud nenarazím na konec řádky, zvětšuji si buffer, do kterého postupně načítám. Pak už alokuji po celých řádcích. (takže samý realloc). Pak vložím startovní kameny a spustím vlastní herní smyčku, která vlastně je popsána už v pravidlech hry (=očuchám okolní pole a ukradnu soupeřovy kameny). Jedinou otázkou je, jak vybírat další pole. Já jsem to moc náhodně nedělal, protože jsem zápasil s poťochlými bugami v načítání, ale i tak to bylo uznáno. Pozorování: chtělo to asi nějak jinak vyřešit přístup k položkám, protože to, co jsem tam bastlil byla docela prasárna. Poznámka: Nejvíc jsem se obával Visual Studia a toho, že tam není žádný Vim a gdb, ale nakonec to v tom taky šlo napsat... Bohouš

6.6.2007 14.00 Začíná jít do tuhého... Pamatujete na vyhodnocování výrazů? +,-,*,/, unární prasárny typu +~~±±+~~-1, závorky... Zadání je takové, že program dostane na vstupu (nekonečně) dlouhý výraz. Jediné, co můžeme předpokládat, je, že se čísla vejdou do intu, a že je výraz správně uzávorkován. Naprogramujte funkci, která jej vyhodnotí a vrátí výsledek. Funkce musí ošetřovat přetékání intů a musí jej být schopná obejít(je-li to možné) – reprezentace čísel je udělána pomocí zlomků. Nekorektní znaky ve vstupu musejí způsobit chybu. Toť vše. Oproti předchozím zadáním se docela přitvrdilo...

7.6.2007 10:00 Zadání bylo následující: Program obdrží jako parametry z příkazové řádky (absolutní či relativní) cesty ke vstupním a výstupním souborům (pokud výstupní nejsou, nebo je jich málo, bere se stdout). Projde vstupní soubory a nahradí všechny direktivy "#include <cesta_k_souboru>" obsahem souboru, na který ukazuje parametr <cesta_k_souboru>. Direktiva #include je case insensitive (tedy #In Cl U De? je platné...). Parametr cesta_k_souboru začíná za jednou či více mezerami po slově include a končí znakem nového řádku. Soubory, na které ukazuje direktiva #include mohou obsahovat další #include a tyto je třeba ošetřit podle pravidel tohoto zadání. Množství takto vzniklých zanoření není omezeno. Je třeba ošetřit: 1. Cyklické includy – aby se soubory korektně naincludovaly, ale nebyl includovan žádný soubor, který už includován byl, pokud by takto mohl vzniknout cyklus. 2. špatná cesta k souboru – program ukončí činnost s výpisem chyby obsahujícím problematický soubor, řádek a odkazovaný soubor, který neexistuje. 3. Korektnost vstupních parametrů (existence vstupních souborů). Omezující podmínky – soubory větší, než maximální velikost paměti, kterou dokážete naalokovat.

8.6.2007 10:00 Zadání bylo zhruba: Na standardním vstupu dostaneme text. Program ma text projít a zaznamenat všechny výskyty všech identifikátorů (posloupnost znaků začínající písmenem nebo podtržítkem, dále může obsahovat i číslice). Na standardní výstup vypíše všechny identifikátory setříděné podle počtu výskytů a u každého identifikátoru všechny řádky, na kterých se vyskytoval. Počet řádek, počet výskytů a délka identifikátorů může být libovolná (tj. nelze omezit konstantou). STL bylo povolená, což náramně usnadnilo práci. – Zdeněk

Ještě jak jsem to vyřešil:
#include <string> #include <map> #include <vector> #include <iostream> #include <cctype> int main() { std::map<std::string, std::vector<unsigned> > stat; std::map<std::string, std::vector<unsigned> >::iterator iStat, jStat; std::vector<unsigned> tmp; char c = 0; std::string word; unsigned lineNumber = 1; // pocitadlo radek int i; while (c != EOF) { c = std::cin.get(); if (c == '\n') lineNumber++; // NACITANI SLOVA word.clear(); // vyprazdneni stringu if (isalpha(c) || c == '_') while (isalpha(c) || isdigit(c) || c == '_') { word = word + c; c = std::cin.get(); } if (word.empty()) // aby se nepridavala prazdna slova continue; // ZPRACOVANI SLOVA iStat = stat.find(word.c_str()); // najde slovo v mape if (iStat == stat.end()) { // slovo v mape jeste neni tmp.push_back(lineNumber); // prida radku vyskytu stat.insert(make_pair(word, tmp)); // prida slovo do mapy tmp.pop_back(); } else if (iStat->second[iStat->second.size() - 1] != lineNumber) iStat->second.push_back(lineNumber); // pridani vyskytu if (c == '\n') lineNumber++; } // VYPIS SLOV OD NEJVETSIHO POCTU VYSKYTU while (! stat.empty()) { jStat = stat.begin(); iStat = stat.begin(); while (iStat != stat.end()) { // vybere slovo s nejvetsim poctem vyskytu if (jStat->second.size() < iStat->second.size()) jStat = iStat; iStat++; } std::cout << jStat->first << ": "; // vypise slovo for (i = 0; i < jStat->second.size(); i++) std::cout << jStat->second.at(i) << " "; // vypise vyskyt std::cout << std::endl; stat.erase(jStat); // vymaze slovo z mapy } }
– Zdeněk

* 25. 6. 2007 10:00 Druhy pokus, nastesti tentokrat uspesny. Zadani – program dostane jako parametry vyraz, kde jsou cisla zapsana v tomto formatu – xxxxxx(y), kde y predstavuje soustavu, ve ktere je cislo zapsano (y <= 35). Jako operatory se vyskytuji pouze ± a unarni minus. Kazde cislo vc. vysledku se vejde po prevedeni do desitkove soustavy do unsigned long long. U soustav s vyssim zakladem nez 10 pouzijte jako cisla pismena anglicke abecedy (v abecednim poradi a = 10, b = 11 ... az do z). Ukolem je vypsat vysledek v desitkove soustave. STL bylo povoleno, pred testem jsme si mohli stahnout slajdy. Byl to asi jeden z nejlehcich testu, co jsme mohli dostat, stacilo si prevest cisla do 10 soustavy, a nekde uchovavat, jetli je zaporne a pak uz jen obycejne secist/odecist. Kdyz jsem po 2.5 hodinach odchazel (STL jsem se ucil 3 dny pred tim, tak jsem se trochu zamotal v iteratorech), sedelo v ucebne uz ne vic jak 5 lidi (celkove asi z 20).-- Karel Jakubec

Protože se nudim a nedal jsem ani jeden z termínů, tak sem občas dopíšu, jak by mohl vypadat zdroják
#include "stdio.h" #define TYP unsigned long TYP NactiCislo(char * retezec, int * znamenkocisla){ TYP i=0; TYP zaklad=0; TYP vysledek=0; TYP nasobek=1; TYP cislo; char * konec=NULL; if(retezec[i]=='-'){*znamenkocisla=-1;retezec=&(*(retezec+1));}else{*znamenkocisla=1;}; while ( retezec[i] && (( retezec[i] >= '0' && retezec[i] <= '9') || ( retezec[i] >= 'a' && retezec[i] <= 'z' ) ) ) { i++; }; // nacteni pred zavorku konec=&(retezec[i]); i++; // preskoceni zavorky while ( retezec[i] && ( retezec[i] >= '0' && retezec[i] <= '9') ){ zaklad = zaklad*10 + retezec[i] - 48; i++; }; // nyni je treba vratit cislo v 10kove soustave while (konec!=retezec){ // podle Hornerova schematu nacitam cislo odzadu a nasobim mocninou zakladu konec=&(*(konec-1)); cislo=*konec; if(cislo>'9' /*pokud neni cislo*/){ cislo=cislo-97+10; }else{ cislo=cislo-48; }; vysledek = vysledek + nasobek*cislo; nasobek*=zaklad; }; return vysledek; }; int NactiOperator(const char * retezec){ switch (retezec[0]){ case '+': return 1; case '-': return -1; default : return 0; } }; int Secti ( TYP vysledek, int * vznamenko, int operace, TYP cislo, int cznamenko ){ if ( operace == -1 ) cznamenko*=-1; if ( vysledek >= cislo ){ // vysledek cislo neovlivni if ( *vznamenko == 1 ) return vysledek + cznamenko*cislo; if ( *vznamenko == -1 ) return vysledek - cznamenko*cislo; }else{ if ( cznamenko*(*vznamenko) == 1 ) return cislo + vysledek; if ( cznamenko*(*vznamenko) == -1 ){ *vznamenko=cznamenko; return cislo - vysledek; }; }; return 0; } int main ( unsigned int argc, char ** argv ){ TYP i=1; TYP cislo, vysledek; int vznamenko = 1; int cznamenko = 1; int operace; vysledek=NactiCislo(argv[i],&vznamenko); if(vznamenko==1){ printf(" ( "); }else{ printf(" (-"); }; printf(" %d ) ",vysledek); ++i; while ( i<argc ){ operace=NactiOperator(argv[i]); printf(" %s ",argv[i]); ++i; if(i<argc)cislo=NactiCislo(argv[i], &cznamenko); if(cznamenko==1){ printf(" ( "); }else{ printf(" (-"); }; printf(" %d ) ",cislo); ++i; vysledek=Secti ( vysledek, &vznamenko, operace, cislo, cznamenko ); }; if(vznamenko==1){ printf(" = ( "); }else{ printf(" = (-"); }; printf("%d )", vysledek); getchar(); return 0; }
Př. program.exe -12(10) + -15(12) + -ff(16)
Karel V.

* 26. 6. 2007 14:00 Nactete z stdin rovnici, a upravte ho tak aby vlevo zůstalo jenom x:
(x*5)/a=5-g -> x=((5-g)*a)/5
(samozrejme to melo resit i mnohem slozitejsi)