[C] Ciąg Fibonacciego rekurencyjnie i iteracyjnie

Question

Witam. Napisałem poniższy kod. Prosiłbym o sprawdzenie, czy wszystko jest w porządku.

Dodatkowo mam za zadanie sprawdzić czas wykonywania obu funkcji dla odpowiednio dużego n (n jako numer wyrazu ciągu Fibonaciego. Mógłbyś prosić o wskazówki, w jaki sposób mógłbym to zrobić? Dziękuję!

long int fib(int n) /* rekurencyjna */
{
    if (n==1 || n==2)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

long int fib2(int n) /* iteracyjna */
{
    int i, tab[n];
    tab[0]=0;
    tab[1]=1;

    for (i=2;i<n;i++)
        tab[i]=tab[i-1]+tab[i-2];

    return tab[n-1];
}

 

Answer 1

Kody są poprawne. Jedyne, do czego bym się przyczepił, to niestandardowa deklaracja tablicy korzystająca ze zmiennej zamiast stałej jako wyznacznika rozmiaru. Taka komenda nie pójdzie we wszystkich środowiskach, ale dla uproszczenia może być.

Ten czas ma być sumą obu, czy pokazany oddzielnie dla każdej funkcji? Tak czy inaczej, wykorzystaj funkcję clock i makro CLOCKS_PER_SEC. Najprawdopodobniej precyzja w twoich pomiarach ma być rzędu milisekund, więc licz czas za pomocą takiego wyrażenia:

float czas = clock() / (float)CLOCKS_PER_SEC * 1000;

Funkcja clock zwraca jednostki czasu procesora wykorzystane do danej chwili przez program. Aby więc obliczyć dany przedział, potrzebujesz wyznaczyć różnicę czasu późniejszego i czasu wcześniejszego:

czas_późniejszy - czas_wcześniejszy

Answer 2

Zdecyduj czy Twój ciąg rozpoczyna się od (0, 1, ....) czy od (1, 1,...). W obu funkcjach masz różnie. Najczęściej wybierana jest wersja z (0, 1, ...).

fib2(..) można bez problemu napisać bez użycia jakiejkolwiek tablicy. Spada wtedy zużycie pamięci. Jeśli chodzi o fib(...), poprawiłem go dla ciągu (0, 1, ...).

#include <stdio.h>
#include <time.h>

long int fib(int n) /* rekurencyjna */
{
    return n < 2 ? n: fib(n - 1) + fib(n - 2);
}

long int fib2(int n) /* iteracyjna */
{
    int x0 = 0;
    int x1 = 1;

    for(int i = 0; i < n; ++i) {
        int temp = x0 + x1;
        x0 = x1;
        x1 = temp;
    }

    return x0;
}

void checkTime(long int (*func)(int), int arg) {
    clock_t startTime = clock();
    func(arg);
    clock_t stopTime = clock();
    printf("Czas wykonania funkcji to %.2f ms.\n",
        1000.0 * (stopTime - startTime) / CLOCKS_PER_SEC);
}

int main(void) {
    puts("Dla wersji rekurencyjnej:");
    checkTime(fib, 45);
    puts("Dla wersji iteracyjnej:");
    checkTime(fib2, 45);

    return 0;
}

Oczywiście pomiar tylko jednego wykonania nie jest miarodajny. Ale do celów ćwiczebnych i przy takich różnicach czasów akceptowalny :-)

Answer 3

Liczenie czasu możesz zrobić używając biblioteki chrono. Sprawdzić czas tuż przed wywołaniem funkcji, tuż po i obliczyć różnicę. Nic trudnego.

 

dokumentacja chrono

Comments

Plox. Rozróżniaj C i C++