Programowanie obiektowe 1

Zadanie 1

a) Oblicz ilości działań arytmetycznych potrzebnych do obliczenia wartości wielomianu stopnia n różnymi metodami (sumowanie wyrazów z obliczaniem potęg oddzielnie dla każdego wyrazu (przy pomocy oddzielnej funkcji), przy iteracyjnym obliczaniu potęg (równocześnie z obliczaniem sumy), itp. (np. schemat Hornera)). Przedyskutuj wyniki.

b) Oblicz ilość działań arytmetycznych potrzebnych do pomnożenia dwu macierzy n na n metodą "z definicji".

Zadanie 2

Oblicz ile wywołań rekursywnych wykonuje się przy rekursywnym obliczaniu liczb Fibonacciego:

int fib(int n)
{
    if (n < 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

Zadanie 3

Co wypiszą poniższe programy:

#include <iostream>
using namespace std;
void fun(int * a, int * b)
{
        int tmp=*a;
        *a = *b;
        *b = tmp;
}
int main(void)
{
        int a=5, b=2;
        fun(&a, &b);
        cout << a << " " << b << endl;
        return 0;
}

#include <iostream>
using namespace std;
void fun(int * * a, int * * b)
{
        int * tmp=*a;
        *a = *b;
        *b = tmp;
}
int main(void)
{
        int a=5, b=2;
        int * ap = &a, * bp = &b;
        fun(&ap, &bp);
        cout << a << " " << b << endl;
        return 0;
}

Uwaga: Chodzi o to by umieć przewidzieć co zrobi program przed jego wykonaniem.

Zadanie 3

Zapoznaj się z przykładowym programem 'stos.cpp'. Prześledź zawartość stosu dla różnych sekwencji wywołań metod 'umiesc' i 'pobierz'. Używając klasy 'stos' napisz prosty kalkulator RPN, tzn. funkcję która mając dany łańcuch znaków przetworzy znaki tak że cyfry umieszcza na stosie, zaś znaki '+', '-' i '*' powodują pobranie dwu pozycji ze stosu, wykonanie operacji i umieszczenie wyniku na stosie. Wynikiem kalkulatora jest wartość zwracana przez 'pobierz'. Przykladowe dane: "12+" ma dać 3, "123*+" ma dać 6, "123+*" ma dać 5, "12+3*" ma dać 9.

Zadanie 4

Kolejka działa w ten sposób że operacja pobierania zwraca pierwszy element umieszczony w kolejce (w przypadku stosu operacja pobierania zwraca element ktory był ostatnio umieszczony). Można ją zaimplementować podobnie do stosu, ale trzeba pamiętać dwie pozycje: elementu ostatnio umieszczonego (za nim umieszcza się kolejne elementy) i elementu który był umieszczony jako pierwszy (ten będzie zwrócony przez 'pobierz'). Typowo kolejkę w tablicy realizuje się jako tak zwany bufor cykliczny, tzn. po dojściu do końca tablicy elementy umieszcza się od początku (zakładając że jest tam wolne miejsce). Przy takiej implementacji jest problem z odróżnianiem pustej kolejki od kolejki całkowicie zapełnionej, tzn. takiej gdzie wszystkie pozycje w tablicy są używane. Dlatego zwykle nie pozwala się na całkowite zapełnienie tablicy i sygnalizuje się przepełninie już przy próbie użycia ostatniej pozycji. Zaimplementuj kolejkę w tablicy wzorując się na implementacji stosu. Prześledź zawartość dla różnych sekwencji wywołań metod 'umiesc' i 'pobierz'. Dodaj metodę podającą ilość elementów w kolejce.

Zadanie 5

Sortowanie metodą łącznia polega na tym że mając ciąg do posortowania dzielimy go na połowy, sortujemy każdą z nich a następnie łączymy te dwa ciągi w jeden. Aby uniknąć rekursji pożyteczny może być trochę inny punkt widzenia: tablica długości n zawiera n ciągów długości 1. Łącząc ciągi długości 1 uzyskujemy ciągi posortowane długości 2 (na końcu może zostać ciąg długości 1). Następnie łączymy ciągi długości 2 w ciągi długości 4 i tak dalej, aż otrzymamy jeden ciąg posortowany. Napisz funkcję sortująca metodą łączenia. Użyj wariant funkcji 'merge' z listy 1. Uwaga: Przy sortowaniu użyj tablicy pomocniczej o rozmiarze równym wejściowej tablicy.