ALG14

314 Rozdział 14. Zadania różne

element kosztuje nas tylko 2 bajty (jest to zmienna typu int), ale za to z góry musimy przydzielić pamięć na całą tablicę.

Oznaczmy rozmiar tablicy przez N. Wówczas całkowita zajęta przez nią pamięć wynosi 2N~ bajtów. „Magiczną” granicę k, przy której sens stosowania listy jest wątpliwy, można z łatwością obliczyć przy pomocy równości: k*p-2N². Przykładowo dla p=8, N=10, dwudziesty szósty niezerowy element już przebiera miarkę. Praktycznie rzecz ujmując, typowa ilość niezerowych elementów

powinna być znacznie mniejsza od ² '^v - programista musi sam podjąć decy-

P

zję, co do właściwej interpretacji wyrażenia „znacznie”...

Zad. 14-4

Dwie wersje programów rekurencyjnych służących do obliczania xn znajdują się poniżej:

pol.cpp

int potl(int x, int n)

I

if (n==0)

raturn 1; else

return (pot 1(x,n-1)*x';

) int pot2(int x, int n, int temp=l)

(

if (n—0) return temp; elso

return (pot2(x,n-1,temp*x));

)

void main ()

(

cout << "Dwa do potęgi trzeciej: \n"; cout << "Metoda l\t" << potl(2,3!« ”\n"; cout << "Metoda 2\t" << pot2(2,3)<< "\n"; I

Zad. 14-10

Zadanie należy do elementarnych, nie powinno zatem nikomu sprawić trudności dojście do następującego rozwiązania:

palindro.cpp

void palindrom(char *s)