Zadanie domowe z odcinka o rekurencjach

Question

Witam!

Zrobiłem zadanie domowe z odcinka rekurencjach (porównanie czasu rekurencji i iteracji liczenia silnii). Wydaje mi się, że zrobiłem wszystko poprawnie, ale kiedy włączam program to oba czasy są równe zero. Czy zrobiłem coś źle?

 

#include <iostream>
#include <time.h>
#include <cstdlib>

using namespace std;

clock_t start, stop;
double czas;
int ile;
long int wynikit=1;

long int silnia(int n)
{
    if (n==0) return 1;
    else return n*silnia(n-1);
}

int main()
{
    cin>>ile;
    start=clock();
    silnia(ile);
    stop=clock();
    czas=(double)(stop - start) / CLOCKS_PER_SEC;
    cout<<"Ile czasu (rekurencja): "<<czas<<" s"<<endl;

     start=clock();
    for(int i=1;i<=ile;i++)
    {
        wynikit=(wynikit)*i;
    }
    stop=clock();
    czas=(double)(stop - start) / CLOCKS_PER_SEC;
    cout<<"Ile czasu (iteracja): "<<czas<<" s"<<endl;


    return 0;
}

 

Answer 1

clock() podaje czas w milisekundach. Dzisiejsze komputery są na tyle szybkie, że te twoje funkcje wykonują w czasie paru nanosekund. Wykonaj je milion razy w pętli, aby otrzymać jakiś znaczący/widoczny wynik.

Comments

Tylko, że nie mogę podać więcej niż 60000 (wtedy pokazuje czas 0.0001 i 0), bo wtedy mi się program kraszuje.

---

No z powodu iż jest to funkcja rekurencyjna - istnieje szansa na stack overflow. Chociaż powinno się to dziać przy dużej ilości odwołań rekurencji, a nie ilości wywołań podstawowej funkcji. Tak czy inaczej różnica między tymi funkcjami jest naprawdę niewielka. I taka dygresja. Rozmiar long int na większości obecnych kompilatorów równa się int. Jeśli chcesz większe liczby to użyj 64-bitowego long long.

Answer 2

Może program tak szybko liczy, że czas jest bardzo bliski zeru i dlatego go nie wyświetla.

Comments

Nie, zmienna oznaczająca czas jest typu double przez co nawet bardzo małe liczby są wyświetlane(ale w notacji wykładniczej). Mi wyświetla wszystko normalnie

Answer 3

Zrób to tak:

#include <iostream>
#include <time.h>
#include <cstdlib>

#define L_POWT 1000000
 
using namespace std;
 
clock_t start, stop;
double czas;
int ile;
long int wynikit=1;
 
long int silnia(int n)
{
    if (n==0) return 1;
    else return n*silnia(n-1);
}
 
int main()
{
	cout<<"Podaj liczbę, której silnia ma być obliczona:";
    cin>>ile;
    start=clock();
    for(int i=1; i <= L_POWT; i++){
    	silnia(ile);
    }
    stop=clock();
    czas=stop - start;
    cout<<"Ile czasu (rekurencja): "<<czas / CLOCKS_PER_SEC<<" s"<<endl;
 
    start=clock();
    for(int i=1;i<=L_POWT;i++)
    {
        for(int i=1;i<=ile;i++)
	    {
	        wynikit=wynikit*i;
	    }
    }
    stop=clock();
    czas=stop - start;
    cout<<"Ile czasu (iteracja): "<<czas / CLOCKS_PER_SEC<<" s"<<endl;
 
    return 0;
}

Mi wyszło dla 10! metodą rekurencyjną 0,062 s, a interacyjną 0,047 s

Comments

Czemu używasz preprocesora do tworzenia stałych. Piszesz w C++ więc używaj const

---

Wolę wstawić literał w miejscu jego użycia niż skakać w pamięci do stałej zadeklarowanej gdzieś w pamięci.

---

http://blog.malcom.pl/2009/naduzywanie-preprocesora-w-cpp.html

Answer 4

Pozwolę znowu sobie zacytować fragment tekstu z serwisu warsztat.gd:

2. "Co tu jest źle?"

: Pokaże wam swój kod. Ściągnijcie go i zobaczcie, dlaczego to nie działa? Nie wiem, gdzie tu jest błąd.

Każdy z nas ma swój kod i swoje błędy. W twoim kodzie błędy możesz znaleźć tylko ty sam - zrobisz to najszybciej i najlepiej, bo już go znasz. Nikt nie będzie analizował dziesiątek czy setek linii twojego kodu albo całego projektu.