Scribd
Upload
13 views3 pages

AS_fibonacci

The document outlines a problem involving Fibonacci coding, which encodes positive integers into binary words ending in '11'. It describes a recursive function to generate Fibonacci numbers and provides a step-by-step process for encoding integers and decoding hexadecimal representations of Fibonacci codes. Sample inputs and outputs are included to illustrate the encoding and decoding process.

Uploaded by

CK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
13 views3 pages

AS_fibonacci

The document outlines a problem involving Fibonacci coding, which encodes positive integers into binary words ending in '11'. It describes a recursive function to generate Fibonacci numbers and provides a step-by-step process for encoding integers and decoding hexadecimal representations of Fibonacci codes. Sample inputs and outputs are included to illustrate the encoding and decoding process.

Uploaded by

CK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 3

ACSL

ALL-STAR American Computer Science League Program #3


Fibonacci Code

PROBLEM: By Wikipedia definition “Fibonacci coding is a universal code that


encodes positive integers into binary words. All words end in 11.”

This recursive function generates, where n is the term number, the Fibonacci number
sequence needed to encode positive integers into Fibonacci code. Note that the first two
terms of the sequence are both 1’s and that only one 1 is used in the encoding process.
The first few terms of the unique sequence are:

Position number 1 2 3 4 5
Fibonacci value 1 2 3 5 8

The process to encode a number X is as follows:

1. Find the largest Fibonacci number less than or equal to X; subtract this number
from X; save the difference.
2. If the number subtracted was the Nth unique Fibonacci number, put a 1 in the Nth
position of the output.
3. Repeat the process above, substituting the saved difference for X, until the
difference is 0.
4. All of the output positions less than the Nth position that do not contain a 1 are
filled in with 0’s.
5. Place a 1 in the (N + 1)th position.

As an example the integer 117converts to 010 1001 0011. Note that 89, the 10th
Fibonacci value in the unique sequence, is the largest Fibonacci value less than or equal
to 117. The other 1’s are found by repeating the process. Starting on the right and
grouping the digits in 4’s as shown, the Fibonacci code converts to 293 in hexadecimal.
If the hexadecimal 293 needed to be converted back to an integer a problem arises in
converting the 2 to 0010 binary since the leading zero would change the value of the
conversion. The length of the code is needed. Given that the length is 11, the leading
zero must be deleted to convert it correctly.

INPUT: There will be 10 inputs. The first 5 will be positive integers. The largest integer
will be less than 106. The last 5 inputs will be binary words in Fibonacci code that have
been converted to hexadecamal. Since this code is place value dependent and the leading
zeros are significant, the length of the code will also be given.

OUTPUT: For each positive integer input, print the Fibonacci code for that positive
integer converted to hexadecimal and the length of the code. For each hexadecimal
conversion of the Fibonacci code and its corresponding length, print its positive integer
value.
SAMPLE INPUT SAMPLE OUTPUT

1. 1 1. 3, 2
2. 45 2. 053, 9
3. 100 3. 143, 11
4. 4 4. B,4
5. 164 5. 543, 12
6. 3, 2 6. 1
7. 3, 3 7. 2
8. 3, 4 8. 3
9. B, 4 9. 4
10. 543, 12 10. 164
ACSL
ALL-STAR American Computer Science League Program #3
Fibonacci Code

TEST DATA

TEST INPUT TEST OUTPUT

1. 43 1. 113, 9
2. 692 2. 4943, 15
3. 1269 3. 4513, 16
4. 11201 4. 104203, 21
5. 22578 5. 00A113, 22
6. 113, 9 6. 43
7. 4943, 15 7. 692
8. 4513, 16 8. 1269
9. 104203, 21 9. 11201
10. 00A113, 22 10. 22578

You might also like