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

Od Petr Zemek, 2008-12-27

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.

Obsah tohoto pole je soukromý a nebude veřejně zobrazen.

Filtrované HTML (využíváno)

  • Povolené HTML značky: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <table>
  • Zvýraznění syntaxe kódu lze povolit přes následující značky: <code>, <blockcode>, <bash>, <c>, <cpp>, <haskell>, <html>, <java>, <javascript>, <latex>, <perl>, <php>, <python>, <ruby>, <rust>, <sql>, <text>, <vim>, <xml>, <yaml>.
  • Řádky a odstavce se zalomí automaticky.
  • Webové a e-mailové adresy jsou automaticky převedeny na odkazy.
CAPTCHA
13 + 1 =
Vyřešte tento jednoduchý matematický příklad a vložte výsledek. Např. pro 1+3 vložte 4.
Nějak se mi tady rozmohl spam, takže poprosím o ověření.

Petr Zemek

15 years 7 months zpět

In reply to by Libor (neověřeno)

Preklep - diky za upozorneni.

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.

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.

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.