piątek, 27 czerwca 2014

Kod C++ - rekurencja

#include <iostream>
#include <ctime>
#include <cstdlib>

int exponentiation_recursion(int base, int index);
int exponentiation_iteration(int base, int index);
int fibonacci_recursion(int number);
int fibonacci_iteration(int number);
int factorial_recursion(int number);
int factorial_iteration(int number);
double execution_time(int (* pointer)(int), int argument, int & result); // Funkcja obliczająca czas wykonania danej funkcji.
double execution_time(int (* pointer)(int, int), int first_argument, int second_argument, int & result); // Funkcja obliczająca czas wykonania danej funkcji (przeładowanie).

int main() {
    int result;
    double recursion_time, iteration_time;

    recursion_time = execution_time(fibonacci_recursion, 30, result);

    iteration_time = execution_time(fibonacci_iteration, 30, result);

    std::cout << "Funkcja obliczajaca rekurencyjnie ciag Fibonacciego dla liczby 30 wykonala sie w czasie " << recursion_time << " sekund.\n";

    std::cout << "Funkcja obliczajaca iteracyjnie ciag Fibonacciego dla liczby 30 wykonala sie w czasie " << iteration_time << " sekund.\n";

    recursion_time = execution_time(exponentiation_recursion, 2, 30, result);

    iteration_time = execution_time(exponentiation_iteration, 2, 30, result);

    std::cout << "Funkcja obliczajaca rekurencyjnie 2 do potegi 30 wykonala sie w czasie " << recursion_time << " sekund.\n";

    std::cout << "Funkcja obliczajaca iteracyjnie 2 do potegi 30 wykonala sie w czasie " << iteration_time << " sekund.\n";
}

int exponentiation_recursion(int base, int index) {
    if (index == 0) // Przypadek elementarny.
        return 1;
    else
        return (base * exponentiation_recursion(base, (index - 1)));
}

int exponentiation_iteration(int base, int index) {
    if (index == 0)
        return 1;
    else if (index == 1)
        return base;
    else {
        int result = base;

        for (int iterator = 2; iterator <= index; iterator++)
            result *= base;

        return result;
    }
}

int fibonacci_recursion(int number) {
    if ((number == 1) || (number == 2)) // Przypadek elementarny.
        return 1;
    else
        return (fibonacci_recursion(number - 1) + fibonacci_recursion(number - 2));
}

int fibonacci_iteration(int number) {
    if ((number == 1) || (number == 2))
        return 1;
    else {
        int result;
        int before = 1, after = 1;

        for (int iterator = 3; iterator <= number; iterator++) {
            result = (before + after);

            before = after;

            after = result;
        }

        return result;
    }
}

int factorial_recursion(int number) {
    if (number == 0) // Przypadek elementarny.
        return 1;
    else
        return (number * factorial_recursion(number - 1));
}

int factorial_iteration(int number) {
    if (number == 0)
        return 1;
    else {
        int result = 1;

        for (int iterator = 1; iterator <= number; iterator++)
            result *= iterator;

        return result;
    }
}

double execution_time(int (* pointer)(int), int argument, int & result) {
    clock_t start, stop;
    double time;

    start = clock();

    result = pointer(argument);

    stop = clock();

    time = static_cast<double>(stop - start); // Wynikiem jest liczba cykli procesora.

    time /= CLOCKS_PER_SEC; // Wynik w sekundach.

    return time;
}

double execution_time(int (* pointer)(int, int), int first_argument, int second_argument, int & result) {
    clock_t start, stop;
    double time;

    start = clock();

    result = pointer(first_argument, second_argument);

    stop = clock();

    time = static_cast<double>(stop - start); // Wynikiem jest liczba cykli procesora.

    time /= CLOCKS_PER_SEC; // Wynik w sekundach.

    return time;
}