fib.c (1390B)
1 #include <limits.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 6 #include "tree.h" 7 8 typedef struct Fnode Node; 9 10 11 inline Node * 12 finit(void) 13 { 14 Node *root = emalloc(sizeof(Node)); 15 16 root->left = NULL; 17 root->right = NULL; 18 19 return root; 20 } 21 22 Node * 23 create(unsigned int depth) 24 { 25 switch (depth) { 26 case 0: 27 return NULL; 28 case 1: 29 case 2: 30 return finit(); 31 default: 32 Node *root = finit(); 33 root->left = create(depth - 1); 34 root->right = finit(); 35 root->right->right = create(depth-2); 36 return root; 37 } 38 } 39 40 unsigned long int 41 count(Node *root) 42 { 43 if (!root) 44 return 0; 45 if (root->left == NULL && root->right == NULL) 46 return 1; 47 48 return count(root->left)+count(root->right); 49 } 50 51 static inline void 52 usage(void) 53 { 54 eprintf("usage: %s [-c] [-s] [depth]\n", argv0); 55 } 56 57 int 58 main(int argc, char *argv[]) 59 { 60 int cflag = 0, sflag = 0; 61 62 ARGBEGIN { 63 case 'c': 64 cflag = 1; 65 break; 66 case 's': 67 sflag = 1; 68 break; 69 default: 70 usage(); 71 } ARGEND 72 if (argc != 1 && (cflag + sflag) < 1) 73 usage(); 74 75 76 clock_t start_time, elapsed = 0; 77 if (cflag) 78 start_time = clock(); 79 Node *root = create(estrtonum(argv[0], 0, UINT_MAX)); 80 if (cflag) 81 elapsed += clock() - start_time; 82 83 volatile unsigned long int fib = 0; /* to avoid optimization */ 84 if (sflag) { 85 start_time = clock(); 86 fib = count(root); 87 elapsed += clock() - start_time; 88 } 89 90 printf("%f\n", (double)elapsed/CLOCKS_PER_SEC); 91 }