kays
30/12/2007, 22:27
Büyük fibonacci serilerini hesaplamak için int veya double türü yetmediğinden bunu linked list ile halledebiliyoruz ancak. Aşağıda dilediğiniz uzunluktaki fibonacci serilerini hesaplayabilen C kodu var. Bu kodda fib(n) = fib(n-1) + fib(n-2) uygulanmıştır. ARRAY_SIZE ile hangi uzunlukta fibonacci serisini hesaplamak istediğinizi belirliyorsunuz. Hesaplarken recursive olarak fib(0)=0 ve fib(1) = 1 den hareketle hesaplıyor. İncelemek isteyenler olur diye düşündüm.
/*
Author : Mahmut Gündeş
Description : Calculates the fibonacci series unlimitedly
Date : 01.11.07
License : General Public License(GPL)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/* user defined */
typedef struct tagNode {
int value;
struct tagNode *p_next;
struct tagNode *p_previous;
} NODE, *PNODE;
typedef struct tagList {
PNODE p_head;
PNODE p_tail;
int count;
} LIST, *PLIST;
#define ARRAY_SIZE 1000
#define TRUE 1
#define FALSE 0
/* function protoypes */
void display_usage();
int create_lookup_list_array(PLIST array[], int size);
void destroy_lookup_list_array(PLIST array[], int size);
LIST *create_list(void);
void destroy_list(PLIST p_list);
void clear_list(PLIST p_list);
PNODE create_node(int val);
void set_first_second_series(PLIST array[]);
PNODE add_item_to_head(PLIST p_list, int val);
PNODE add_item_to_tail(PLIST p_list, int val);
int check_lookup_array(PLIST array[], int index);
void display_list(int order, PLIST p_list);
int calculate_fibonacci(PLIST array[], int order);
void add_two_before_series(PLIST array[], int first_before, int second_before, int order);
void write_series_to_file(PLIST array[]);
/* global variables */
int write_to_file_count = 0; //this variable is used as a flag
FILE *file_name = NULL; //file name for writing the results
/* main function */
int main(int argc, char *argv[]) {
char str_exit[5] = "quit";
int order = 0;
int trying_number = 0;
char alphanum[40] = {'\0'}; //for input order, will be checked if it is numeric or not
if (argc != 2) {
printf("USAGE: %s <file_full_path>\n<file_full_path>: The result of fibonacci calculation will be written to the file..\n\n", argv[0]);
return FALSE;
}
PLIST lookup_array[ARRAY_SIZE]; //lookup list array
create_lookup_list_array(lookup_array, ARRAY_SIZE);
set_first_second_series(lookup_array);
do {
printf("Enter an order to calculate fibonacci series corresponding(0 for quit): ");
scanf("%s", &alphanum);
if (is_numeric(alphanum) == 0) {
printf("You must enter a numeric value!\n");
continue;
}
order = atoi(alphanum);
if (order > 1000) {
printf("You must have entered invalid value, value must be smaller then or equal to 1000!\n");
continue;
}
if (order == 0 && trying_number == 0) {
printf("hadn't done any calculation before exiting, so didn't create any output file!\n");
return TRUE;
} else if (order == 0 && trying_number != 0) {
printf("you have wanted to exit;\n");
continue;
}
if (write_to_file_count == 0)
file_name = fopen(argv[1], "wa"); //if the file will be opened first time, creates a new file
else
file_name = fopen(argv[1], "a"); //if file already opened before at least once, we will appened the calculations
if (calculate_fibonacci(lookup_array, order) == 1) {
display_list(order, lookup_array[order-1]); //display the fibonacci serie of given order
}
++trying_number;
} while (order != 0);
fclose(file_name);
destroy_lookup_list_array(lookup_array, ARRAY_SIZE); //free the memory
return TRUE;
}
int create_lookup_list_array(PLIST array[], int size) {
int i;
for (i=0; i<size; i++) {
array[i] = create_list();
}
}
/* allocate memory for LIST structure and then set defaults */
PLIST create_list(void) {
PLIST p_list;
if ((p_list = (PLIST) malloc(sizeof(LIST))) == NULL) {
return NULL;
}
//p_list->p_head = p_list->p_tail = NULL;
p_list->count = 0;
return p_list;
}
void destroy_lookup_list_array(PLIST array[], int size) {
int i;
for (i=0; i<size; i++) {
destroy_list(array[i]);
}
}
/* before freeing linked list, frees the all nodes */
void destroy_list(PLIST p_list) {
clear_list(p_list);
free(p_list);
}
void clear_list(PLIST p_list) {
PNODE p_node, p_temp_node;
p_node = p_list->p_head;
while (p_node) {
p_temp_node = p_node->p_next;
free(p_node);
p_node = p_temp_node;
}
p_list->p_head = p_list->p_tail = NULL;
p_list->count = 0;
}
PNODE create_node(int val) {
PNODE p_node;
if ((p_node = (PNODE) malloc(sizeof(NODE))) == NULL) {
return NULL;
}
p_node->value = val;
p_node->p_next = p_node->p_previous = NULL;
return p_node;
}
/* sets the the first two list's head node with 0 and 1 values */
void set_first_second_series(PLIST array[]) {
add_item_to_head(array[0], 0);
add_item_to_tail(array[1], 1);
}
PNODE add_item_to_head(PLIST p_list, int val) {
PNODE p_new_node = NULL;
if ((p_new_node = create_node(val)) == NULL) {
return NULL;
}
p_new_node->p_next = p_list->p_head;
if (p_list->p_head != NULL) {
p_list->p_head->p_previous = p_new_node; //adding previous pointer
}
p_list->p_head = p_new_node;
if (p_list->p_tail == NULL) {
p_list->p_tail = p_new_node;
}
++p_list->count;
return p_new_node;
}
PNODE add_item_to_tail(PLIST p_list, int val) {
PNODE p_new_node = NULL;
if ((p_new_node = create_node(val)) == NULL) {
return NULL;
}
p_new_node->p_next = NULL;
if (p_list->p_tail == NULL) {
p_list->p_head = p_new_node;
} else {
p_list->p_tail->p_next = p_new_node;
p_new_node->p_previous = p_list->p_tail; //add previous pointer
}
p_list->p_tail = p_new_node;
++p_list->count;
return p_new_node;
}
int check_lookup_array(PLIST array[], int index) {
if (index < 2) {
return FALSE; //dont need to check first and second index
}
PLIST list1 = array[index-1];
PLIST list2 = array[index-2];
if (list1->p_head == NULL || list2->p_head == NULL) {
return FALSE;
}
return TRUE; //already calculated
}
void display_list(int order, PLIST p_list) {
PNODE p_node = p_list->p_tail;
char buffer[1000] = {'\0'};
int i = 0;
if (p_node == NULL) {
printf("count of list is %d, list is empty!\n", p_list->count);
return;
}
printf("Number in List: ");
for (i=0; p_node != NULL; p_node = p_node->p_previous) {
printf("%d", p_node->value);
buffer[i++] = (char) (48+p_node->value);
}
printf("\n");
fprintf(file_name, "Number at %d\t order \t: %s\n", order, buffer);
fflush(file_name);
write_to_file_count++; //incrementin at each result
}
int calculate_fibonacci(PLIST array[], int order) {
if (check_already_calculated(array, order) == 1) {
//printf("%d. serie is already calculated!\n", order);
return TRUE;
} else {
calculate_fibonacci(array, order - 1);
}
add_two_before_series(array, order - 1, order - 2, order);
return TRUE;
}
int check_already_calculated(PLIST array[], int order) {
PLIST p_list = array[order-1];
if (p_list->p_head) //if the head of list is not null, we may say that this order was calculated,
return TRUE; //because all lists's heads are NULL at the begining. Returns TRUE
return FALSE;
}
void add_two_before_series(PLIST array[], int first, int second, int order) {
int remainder = 0;
int addition = 0;
PLIST p_first_list = array[first-1];
PLIST p_second_list = array[second-1];
PNODE first_list_node = p_first_list->p_head;
PNODE second_list_node = p_second_list->p_head;
PLIST p_order_list = array[order-1];
while (first_list_node || second_list_node) { //loop while either one of them is not null
if (first_list_node && second_list_node) {
if ((addition = first_list_node->value + second_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
first_list_node = first_list_node->p_next;
second_list_node = second_list_node->p_next;
continue;
}
else if (first_list_node) {
if ((addition = first_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
first_list_node = first_list_node->p_next;
continue;
}
else if (second_list_node) {
if ((addition = second_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
second_list_node = second_list_node->p_next;
continue;
}
}
if (remainder > 0) {
add_item_to_tail(p_order_list, remainder); //add remainder if any
}
}
int is_numeric(char *alphanumeric) {
int i = 0;
int value = 0;
while((value = alphanumeric[i++]) != '\0') {
if (value < 48 || value > 57)
return FALSE; //if not numeric returns 0
}
return TRUE; //returns 1 if numeric
}
/*
Author : Mahmut Gündeş
Description : Calculates the fibonacci series unlimitedly
Date : 01.11.07
License : General Public License(GPL)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/* user defined */
typedef struct tagNode {
int value;
struct tagNode *p_next;
struct tagNode *p_previous;
} NODE, *PNODE;
typedef struct tagList {
PNODE p_head;
PNODE p_tail;
int count;
} LIST, *PLIST;
#define ARRAY_SIZE 1000
#define TRUE 1
#define FALSE 0
/* function protoypes */
void display_usage();
int create_lookup_list_array(PLIST array[], int size);
void destroy_lookup_list_array(PLIST array[], int size);
LIST *create_list(void);
void destroy_list(PLIST p_list);
void clear_list(PLIST p_list);
PNODE create_node(int val);
void set_first_second_series(PLIST array[]);
PNODE add_item_to_head(PLIST p_list, int val);
PNODE add_item_to_tail(PLIST p_list, int val);
int check_lookup_array(PLIST array[], int index);
void display_list(int order, PLIST p_list);
int calculate_fibonacci(PLIST array[], int order);
void add_two_before_series(PLIST array[], int first_before, int second_before, int order);
void write_series_to_file(PLIST array[]);
/* global variables */
int write_to_file_count = 0; //this variable is used as a flag
FILE *file_name = NULL; //file name for writing the results
/* main function */
int main(int argc, char *argv[]) {
char str_exit[5] = "quit";
int order = 0;
int trying_number = 0;
char alphanum[40] = {'\0'}; //for input order, will be checked if it is numeric or not
if (argc != 2) {
printf("USAGE: %s <file_full_path>\n<file_full_path>: The result of fibonacci calculation will be written to the file..\n\n", argv[0]);
return FALSE;
}
PLIST lookup_array[ARRAY_SIZE]; //lookup list array
create_lookup_list_array(lookup_array, ARRAY_SIZE);
set_first_second_series(lookup_array);
do {
printf("Enter an order to calculate fibonacci series corresponding(0 for quit): ");
scanf("%s", &alphanum);
if (is_numeric(alphanum) == 0) {
printf("You must enter a numeric value!\n");
continue;
}
order = atoi(alphanum);
if (order > 1000) {
printf("You must have entered invalid value, value must be smaller then or equal to 1000!\n");
continue;
}
if (order == 0 && trying_number == 0) {
printf("hadn't done any calculation before exiting, so didn't create any output file!\n");
return TRUE;
} else if (order == 0 && trying_number != 0) {
printf("you have wanted to exit;\n");
continue;
}
if (write_to_file_count == 0)
file_name = fopen(argv[1], "wa"); //if the file will be opened first time, creates a new file
else
file_name = fopen(argv[1], "a"); //if file already opened before at least once, we will appened the calculations
if (calculate_fibonacci(lookup_array, order) == 1) {
display_list(order, lookup_array[order-1]); //display the fibonacci serie of given order
}
++trying_number;
} while (order != 0);
fclose(file_name);
destroy_lookup_list_array(lookup_array, ARRAY_SIZE); //free the memory
return TRUE;
}
int create_lookup_list_array(PLIST array[], int size) {
int i;
for (i=0; i<size; i++) {
array[i] = create_list();
}
}
/* allocate memory for LIST structure and then set defaults */
PLIST create_list(void) {
PLIST p_list;
if ((p_list = (PLIST) malloc(sizeof(LIST))) == NULL) {
return NULL;
}
//p_list->p_head = p_list->p_tail = NULL;
p_list->count = 0;
return p_list;
}
void destroy_lookup_list_array(PLIST array[], int size) {
int i;
for (i=0; i<size; i++) {
destroy_list(array[i]);
}
}
/* before freeing linked list, frees the all nodes */
void destroy_list(PLIST p_list) {
clear_list(p_list);
free(p_list);
}
void clear_list(PLIST p_list) {
PNODE p_node, p_temp_node;
p_node = p_list->p_head;
while (p_node) {
p_temp_node = p_node->p_next;
free(p_node);
p_node = p_temp_node;
}
p_list->p_head = p_list->p_tail = NULL;
p_list->count = 0;
}
PNODE create_node(int val) {
PNODE p_node;
if ((p_node = (PNODE) malloc(sizeof(NODE))) == NULL) {
return NULL;
}
p_node->value = val;
p_node->p_next = p_node->p_previous = NULL;
return p_node;
}
/* sets the the first two list's head node with 0 and 1 values */
void set_first_second_series(PLIST array[]) {
add_item_to_head(array[0], 0);
add_item_to_tail(array[1], 1);
}
PNODE add_item_to_head(PLIST p_list, int val) {
PNODE p_new_node = NULL;
if ((p_new_node = create_node(val)) == NULL) {
return NULL;
}
p_new_node->p_next = p_list->p_head;
if (p_list->p_head != NULL) {
p_list->p_head->p_previous = p_new_node; //adding previous pointer
}
p_list->p_head = p_new_node;
if (p_list->p_tail == NULL) {
p_list->p_tail = p_new_node;
}
++p_list->count;
return p_new_node;
}
PNODE add_item_to_tail(PLIST p_list, int val) {
PNODE p_new_node = NULL;
if ((p_new_node = create_node(val)) == NULL) {
return NULL;
}
p_new_node->p_next = NULL;
if (p_list->p_tail == NULL) {
p_list->p_head = p_new_node;
} else {
p_list->p_tail->p_next = p_new_node;
p_new_node->p_previous = p_list->p_tail; //add previous pointer
}
p_list->p_tail = p_new_node;
++p_list->count;
return p_new_node;
}
int check_lookup_array(PLIST array[], int index) {
if (index < 2) {
return FALSE; //dont need to check first and second index
}
PLIST list1 = array[index-1];
PLIST list2 = array[index-2];
if (list1->p_head == NULL || list2->p_head == NULL) {
return FALSE;
}
return TRUE; //already calculated
}
void display_list(int order, PLIST p_list) {
PNODE p_node = p_list->p_tail;
char buffer[1000] = {'\0'};
int i = 0;
if (p_node == NULL) {
printf("count of list is %d, list is empty!\n", p_list->count);
return;
}
printf("Number in List: ");
for (i=0; p_node != NULL; p_node = p_node->p_previous) {
printf("%d", p_node->value);
buffer[i++] = (char) (48+p_node->value);
}
printf("\n");
fprintf(file_name, "Number at %d\t order \t: %s\n", order, buffer);
fflush(file_name);
write_to_file_count++; //incrementin at each result
}
int calculate_fibonacci(PLIST array[], int order) {
if (check_already_calculated(array, order) == 1) {
//printf("%d. serie is already calculated!\n", order);
return TRUE;
} else {
calculate_fibonacci(array, order - 1);
}
add_two_before_series(array, order - 1, order - 2, order);
return TRUE;
}
int check_already_calculated(PLIST array[], int order) {
PLIST p_list = array[order-1];
if (p_list->p_head) //if the head of list is not null, we may say that this order was calculated,
return TRUE; //because all lists's heads are NULL at the begining. Returns TRUE
return FALSE;
}
void add_two_before_series(PLIST array[], int first, int second, int order) {
int remainder = 0;
int addition = 0;
PLIST p_first_list = array[first-1];
PLIST p_second_list = array[second-1];
PNODE first_list_node = p_first_list->p_head;
PNODE second_list_node = p_second_list->p_head;
PLIST p_order_list = array[order-1];
while (first_list_node || second_list_node) { //loop while either one of them is not null
if (first_list_node && second_list_node) {
if ((addition = first_list_node->value + second_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
first_list_node = first_list_node->p_next;
second_list_node = second_list_node->p_next;
continue;
}
else if (first_list_node) {
if ((addition = first_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
first_list_node = first_list_node->p_next;
continue;
}
else if (second_list_node) {
if ((addition = second_list_node->value + remainder) > 9) {
add_item_to_tail(p_order_list, addition - 10);
remainder = 1;
} else {
add_item_to_tail(p_order_list, addition);
remainder = 0;
}
second_list_node = second_list_node->p_next;
continue;
}
}
if (remainder > 0) {
add_item_to_tail(p_order_list, remainder); //add remainder if any
}
}
int is_numeric(char *alphanumeric) {
int i = 0;
int value = 0;
while((value = alphanumeric[i++]) != '\0') {
if (value < 48 || value > 57)
return FALSE; //if not numeric returns 0
}
return TRUE; //returns 1 if numeric
}