• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

[C] Ciąg Fibonacciego rekurencyjnie i iteracyjnie

VPS Starter Arubacloud
0 głosów
18,724 wizyt
pytanie zadane 17 listopada 2017 w C i C++ przez rayman22 Użytkownik (710 p.)

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];
}

 

3 odpowiedzi

0 głosów
odpowiedź 17 listopada 2017 przez Patrycjerz Mędrzec (192,340 p.)

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
0 głosów
odpowiedź 18 listopada 2017 przez mokrowski Mędrzec (155,460 p.)

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 :-)

–2 głosów
odpowiedź 17 listopada 2017 przez Żyrosławw Bywalec (2,300 p.)

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

komentarz 17 listopada 2017 przez Knayder Nałogowiec (37,640 p.)
Plox. Rozróżniaj C i C++

Podobne pytania

0 głosów
1 odpowiedź 1,367 wizyt
pytanie zadane 28 kwietnia 2019 w Systemy operacyjne, programy przez Ewik Nowicjusz (160 p.)
0 głosów
1 odpowiedź 158 wizyt
pytanie zadane 20 maja 2023 w C i C++ przez Igaiga Nowicjusz (120 p.)
+5 głosów
3 odpowiedzi 12,272 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...