Jste zde

Zajímavé úlohy pro programátory v C a C++ #1

Dnešním dnem zahajuji seriál, ve kterém mohou čtenáři řešit zajímavé úlohy z oblasti programovacích jazyků C a C++. Na čtenáři bude najít správné řešení zadané úlohy a podělit se s ním s ostatními do komentáře. Úlohy nebudou nikterak dlouhé ani časově pracné - půjde především o znalost těchto jazyků (a jejich možností), programovacích technik a jazykových idiomů. Pokud se žádnému z čtenářů nepodaří najít správné řešení, tak po určité době zveřejním své (komentované) řešení a rád zodpovím případné dotazy (to se týká i nejasnostech v zadání). Nuže, pojďme se podívat na první úlohu :).

Zadání

Je dán následující zdrojový kód v jazyce C++:

#include <iostream>
 
// Zde doplňte kód
 
int main() {
    int p1[] = {1, 2, 3, 4, 5, 6, 7, 8};
    std::cout << sum(p1) << std::endl; // 36
 
    int p2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << sum(p2) << std::endl; // 45
}

Doplňte do programu definici funkce (lze definovat i jako šablonu funkce, ovšem ne jako makro) sum(), která sečte všechny prvky v předaném (jednorozměrném) poli (délka pole je vždy větší než 0) a vrátí tuto sumu jako výsledek (int).

Omezení

Uvažujte standard C++98. Program musí být přeložitelný podle tohoto standardu a nesmí se spoléhat na nespecifikované či nedefinované chování užitých konstrukcí. Funkce musí být reentrantní (vrátí korektní výsledek, i když je zavolána několikrát "ve stejnou chvíli", např. z několik vláken současně, tj nelze využívat statické proměnné atd.). Mimo vyznačenou část v programu nic neměňte.

Řešení

Zkusíme na to jít postupně. Prvním problémem je, jak do funkce sum() předat velikost předaného pole. Pokud totiž funkci deklarujeme jako

int sum(const int *a);

nebo (ekvivalentně, protože const int a[] se chová úplně stejně jako const int *a, čili a bude pořád ukazatel na konstantní int)

int sum(const int a[]);

tak ztratíme informaci o jeho délce a neexistuje (přenositelný) způsob, jak ji zjistit (pokud za posledním prvkem pole nebude nějaká zarážka, což v našem případě není).

Jednoduché pokusy jako

int sum(const int a[size_t size]);

skončí nezdarem, protože toto není v C++ syntakticky možné.

Tady nastává okamžik pro první "trik", který využívá netypové paramtery šablon. V C++ totiž lze definovat šablonu, jejíž parametr bude hodnota (předat se ale takto (při instanciaci šablony) může pouze konstanta vyčíslitelná v době překladu) a C++ navíc v určitých případech samo dokáže tuto hodnotu vydedukovat při instanciaci šablony (tedy bez explicitního uvedení). S touto znalostí lze zkusit sum() nadelarovat takto:

template <size_t size>
int sum(const int (*a)[size]);

Tato šablona funkce má jako parametr ukazatel na pole o size prvcích a pokud ji zavoláme takto

int p1[] = {1, 2, 3, 4, 5, 6, 7, 8};
sum(&p1);

tak překladač automaticky vydedukuje hodnotu šablonového parametru size jako velikost předávaného pole a to je přesně to, čeho jsme chtěli dosáhnout. Ovšem nyní vyvstal jiný problém, a to, že v zadání se funkce sum() volá bez ampersandu, čili sum(p1);, takže překlad selže...

To je vhodný okamžik na "trik" číslo dvě - každý určitě ví, že pokud se chceme vyhnout předávání prvku explicitně přes ukazatel (tj adresu), tak můžeme argument předávat referencí, čili proč nevyzkoušet referenci na pole :).

template <size_t size>
int sum(const int (&a)[size]);

Samotná definice funkce už je triviální.

Ukázkové řešení je tedy následující:

template <size_t size>
int sum(const int (&a)[size]) {
    int s = 0;
    for (size_t i = 0; i < size; ++i)
        s += a[i];
    return s;
}

Mimochodem, pokud by někoho napadlo deklarovat funkci sum() pouze takto

int sum(const int (&a)[]);

s tím, že si velikost pole zjistí v těle funkce přes operátor sizeof, tak zjistí, že C++ neumožňuje předat referencí pole o neznámé délce.

Komentáře

36+9=42?

Preklep - diky za upozorneni.

hele, jestli se zatim hledaji chyby v zadani, tak by i ta funkce main() mohla vracet nejaky int, ne?

Norma C++98 rika (3.6.1):

If control reaches the end of main without encountering a return statement, the effect is of executing return 0;.

Samozrejme je (z hlediska citelnosti) lepsi ten return uvest explicitne (nez implicitne), ale u takto jednoduchych/ukazkovych prikladu se ten return vetsinou vynechava.

Enjoy:

#include <iostream>
 
#define sum(i) (result(i, sizeof(i)/sizeof(int)))
 
int result(int* array, int n)
{
        int acc = 0;
        for (int i = 0; i < n; ++i)
        {
                acc += array[i];
        }
 
        return acc;
}
 
int main() {
        int p1[] = {1, 2, 3, 4, 5, 6, 7, 8};
        std::cout << sum(p1) << std::endl; // 36
 
        int p2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        std::cout << sum(p2) << std::endl; // 45
}

Zajimave "reseni" :). Bohuzel ale neodpovida zadani, jelikoz se pozadovalo, aby sum byla funkce (ne makro) a aby se do programu doplnila jen definice one funkce a na jinych mistech se zdrojovy kod nemenil.

Zveřejnil jsem ukázkové komentované řešení úkolu.

Zajimave "reseni" :). Bohuzel ale neodpovida zadani, jelikoz se pozadovalo, aby sum byla funkce (ne sablona) a aby se do programu doplnila jen definice one funkce a na jinych mistech se zdrojovy kod nemenil.

Ale jinak diky, ac jsem nepredpokladal, ze by problem slo vyresit bez pouziti bud maker, nebo sablon, tak toto pouziti sablony jsem neznal.

Sablonova funkce je funkce a deklarace sablonovych parametru je soucasti jeji definice, takze to neni v rozporu se zadanim.

A mohl bych se zeptat, na jake adrese ma tato funkce po prelozeni prekladacem podle standardu C++ 98 pri libovolnem spusteni zkompilovaneho programu vstupni bod? ;-)

Na adrese, na kterou ji umisti prekladac, resp. linker/loader :). Jinak, napr. inline funkce je taky funkce a nemusi byt na zadne adrese.

Cili konkretne? ;-) Tvrdit, ze sablona funkce (prosim nepouzivejte oznaceni "sablonova funkce", evokuje to nejake spojeni s navrhovym vzorem "sablonova metoda", mezi temito dvemi vecmi neni zadna souvislost) je funkce, je jako tvrdit, ze forma na babovku je babovka - ano, z dalky to mozna muze oklamat, nicmene podrobnejsi zkoumani odhali duvody, proc by bylo vhodne se konzumaci vyhnout.

Ok, s tou babovkou jsi me dostal :). Opravil jsem zadani, takze uz by to melo byt v poradku i po formalni strance. Pri pristi formulaci zadani se budu muset vic snazit.

Diky, tesim se na dalsi ulohu. :-)

Přidat komentář