1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <time.h>
using namespace std;

int num_of_ways(int);

double timeStart,timeEnd;
timespec time1, time2;

timespec diff(timespec start, timespec end)
{
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return temp;
}

int main(){

int n,r;
cout<<"Please enter n: "; cin>>n;
timeStart = clock();
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1);
r = num_of_ways(n);
timeEnd = clock();
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2);
cout<<"number of ways = "<<r<<endl;
cout<<"total time (clock) = "<<(timeEnd - timeStart)/CLOCKS_PER_SEC <<" s"<<endl;
cout<<"total time (clock_gettime) = "<<diff(time1,time2).tv_sec<<":"<<diff(time1,time2).tv_nsec<<endl;
return 0;

}

int num_of_ways(int n){

if( n==3 )
return 4;
else if( n==2 )
return 2;
else if( n==1 )
return 1;
else
return(num_of_ways(n-1)+num_of_ways(n-2)+num_of_ways(n-3));
}