I was practicing question 1a of the British Informatics Olympiad 2023 past paper.
In the Fibonacci sequence each number is generated by adding the previous two numbers in the sequence. We will start with the numbers 1 and 2, so the sequence is 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … The Zeckendorf representation of the number n consists of the distinct numbers from the Fibonacci sequence which sum to n, where no two adjacent numbers from the Fibonacci sequence are used. There is always a unique representation.
For example:The Zeckendorf representation for n always includes the largest number from the Fibonacci sequence that is no greater than n.
- 21 is represented by the single number 21;
- 21 is not represented by 8 13, even though they sum to 21, as those numbers are adjacent in the Fibonacci sequence;
- 100 is represented by 3 8 89
Write a program that reads in a number (between 1 and 1,000,000 inclusive) and outputs the numbers (in any order) in the corresponding Zeckendorf representation.
I wrote this code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;
int find_largest_le_fib_n(int n) {
if (n == 0 || n == 1) {
return n;
}
int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
Node* find_zeckendorf(int n) {
Node *last;
Node *first;
Node *penultimate = NULL;
int largest_le_fib;
while (n > 0) {
largest_le_fib = find_largest_le_fib_n(n);
last = malloc(sizeof(Node));
last->data = largest_le_fib;
last->next = NULL;
if (first == NULL) {
first = last;
}
if (penultimate != NULL) {
penultimate->next = last;
}
penultimate = last;
n -= largest_le_fib;
}
return first;
}
int main() {
int n = 0;
printf("Enter number: ");
scanf("%d", &n);
Node *zeckendorf_list = find_zeckendorf(n);
while (zeckendorf_list != NULL) {
printf("%d ", zeckendorf_list->data);
Node *temp = zeckendorf_list;
zeckendorf_list = zeckendorf_list->next;
free(temp);
}
printf("\n");
}
Example run:
Enter number: 100
89 8 3
(More test cases can be found in the mark scheme)
I would be grateful to hear about any improvements that could be made to this code.
last = malloc(sizeof(Node));
orlast = malloc(sizeof *last);
? \$\endgroup\$