How to resolve the algorithm Zeckendorf number representation step by step in the C# programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Zeckendorf number representation step by step in the C# programming language

Table of Contents

Problem Statement

Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series. Recall that the first six distinct Fibonacci numbers are: 1, 2, 3, 5, 8, 13. The decimal number eleven can be written as 013 + 18 + 05 + 13 + 02 + 01 or 010100 in positional notation where the columns represent multiplication by a particular member of the sequence. Leading zeroes are dropped so that 11 decimal becomes 10100. 10100 is not the only way to make 11 from the Fibonacci numbers however; 013 + 18 + 05 + 03 + 12 + 11 or 010011 would also represent decimal 11. For a true Zeckendorf number there is the added restriction that no two consecutive Fibonacci numbers can be used which leads to the former unique solution.

Generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order.
The intention in this task to find the Zeckendorf form of an arbitrary integer. The Zeckendorf form can be iterated by some bit twiddling rather than calculating each value separately but leave that to another separate task.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zeckendorf number representation step by step in the C# programming language

The provided C# code is an implementation of the Zeckendorf representation, which is a way to represent positive integers using a unique sum of Fibonacci numbers. Here's a detailed explanation of the code:

1. Fibonacci Function (Fibonacci):

  • This function uses a recursive approach to calculate the nth Fibonacci number. It starts by handling base cases where n is less than 2 and returns n.
  • For n greater than or equal to 2, it recursively calls Fibonacci(n - 1) and Fibonacci(n - 2), representing the rule that the nth Fibonacci number is the sum of the two preceding Fibonacci numbers.

2. Zeckendorf Function (Zeckendorf):

  • The Zeckendorf function takes a positive integer num and returns its Zeckendorf representation as a string.
  • It starts by initializing an empty list of Fibonacci numbers (fibonacciNumbers) and a variable fibPosition to 2.
  • It then enters a loop to calculate subsequent Fibonacci numbers until the current Fibonacci number (currentFibonaciNum) becomes greater than num.
  • Inside the loop, it adds the current Fibonacci number to the fibonacciNumbers list and increments fibPosition to calculate the next Fibonacci number.

3. Generating Zeckendorf Representation:

  • After the loop finishes, it initializes a temporary variable temp with the value of num.
  • It begins constructing the Zeckendorf representation by iterating through the reversed fibonacciNumbers list.
  • For each Fibonacci number in the list, it checks if it is less than or equal to temp. If so, it appends a "1" to the output string and reduces temp by the Fibonacci number.
  • If not, it appends a "0" to the output string.

4. Main Method:

  • The Main method demonstrates the Zeckendorf representation for numbers from 1 to 20.
  • It uses a for loop to iterate from 1 to 20, calculates each number's Zeckendorf representation using the Zeckendorf function, and prints the number along with its Zeckendorf representation in the following format: "{number} : {Zeckendorf representation}"

Example Output:

1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
6 : 110
7 : 111
8 : 1000
9 : 1001
10 : 1010
11 : 1011
12 : 1100
13 : 1101
14 : 1110
15 : 1111
16 : 10000
17 : 10001
18 : 10010
19 : 10011
20 : 10100

Overall, this code showcases the Zeckendorf representation, a unique way of expressing positive integers using Fibonacci numbers, and provides examples for numbers from 1 to 20.

Source code in the csharp programming language

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Zeckendorf
{
    class Program
    {
        private static uint Fibonacci(uint n)
        {
            if (n < 2)
            {
                return n;
            }
            else
            {
                return Fibonacci(n - 1) + Fibonacci(n - 2);
            }
        }

        private static string Zeckendorf(uint num)
        {
            IList<uint> fibonacciNumbers = new List<uint>();
            uint fibPosition = 2;

            uint currentFibonaciNum = Fibonacci(fibPosition);

            do
            {
                fibonacciNumbers.Add(currentFibonaciNum);
                currentFibonaciNum = Fibonacci(++fibPosition);
            } while (currentFibonaciNum <= num);

            uint temp = num;
            StringBuilder output = new StringBuilder();

            foreach (uint item in fibonacciNumbers.Reverse())
            {
                if (item <= temp)
                {
                    output.Append("1");
                    temp -= item;
                }
                else
                {
                    output.Append("0");
                }
            }

            return output.ToString();
        }

        static void Main(string[] args)
        {
            for (uint i = 1; i <= 20; i++)
            {
                string zeckendorfRepresentation = Zeckendorf(i);
                Console.WriteLine(string.Format("{0} : {1}", i, zeckendorfRepresentation));
            }

            Console.ReadKey();
        }
    }
}


  

You may also check:How to resolve the algorithm Infinity step by step in the Scheme programming language
You may also check:How to resolve the algorithm Parsing/RPN calculator algorithm step by step in the PL/SQL programming language
You may also check:How to resolve the algorithm Bitmap/Midpoint circle algorithm step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Largest proper divisor of n step by step in the Julia programming language
You may also check:How to resolve the algorithm Convert seconds to compound duration step by step in the Forth programming language