Tuesday, March 21, 2023

Fibonacci Numbers & Tower of Hanoi

 

📌 Fibonacci Numbers & Tower of Hanoi


1️⃣ Fibonacci Numbers

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones:

🔹 Formula:

F(n)=F(n1)+F(n2)F(n) = F(n-1) + F(n-2)

🔹 Base Cases:

F(0)=0,F(1)=1F(0) = 0, \quad F(1) = 1

🔹 Example Sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

(a) Recursive Fibonacci (Simple but Inefficient)


#include <stdio.h> int fibonacciRecursive(int n) { if (n <= 1) return n; // Base Case return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); } int main() { int n = 10; printf("Fibonacci(%d) = %d\n", n, fibonacciRecursive(n)); return 0; }

🔹 Time Complexity: O(2^n) (Exponential, slow)
🔹 Space Complexity: O(n) (Recursive stack)


(b) Optimized Fibonacci (Using Iteration)


#include <stdio.h> int fibonacciIterative(int n) { if (n <= 1) return n; int a = 0, b = 1, temp; for (int i = 2; i <= n; i++) { temp = a + b; a = b; b = temp; } return b; } int main() { int n = 10; printf("Fibonacci(%d) = %d\n", n, fibonacciIterative(n)); return 0; }

🔹 Time Complexity: O(n) (Linear)
🔹 Space Complexity: O(1) (Constant, no extra memory used)


(c) Fibonacci Using Dynamic Programming (Memoization)


#include <stdio.h> #define MAX 100 int fibCache[MAX]; int fibonacciMemo(int n) { if (n <= 1) return n; if (fibCache[n] != -1) return fibCache[n]; // Use cached result return fibCache[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2); } int main() { for (int i = 0; i < MAX; i++) fibCache[i] = -1; int n = 10; printf("Fibonacci(%d) = %d\n", n, fibonacciMemo(n)); return 0; }

🔹 Time Complexity: O(n) (Faster than recursion)
🔹 Space Complexity: O(n) (For memoization table)


2️⃣ Tower of Hanoi

The Tower of Hanoi is a mathematical puzzle where three pegs (A, B, C) and n disks must be moved while following these rules:

🔹 Rules:
1️⃣ Only one disk can be moved at a time.
2️⃣ A larger disk cannot be placed on a smaller disk.
3️⃣ The goal is to move all disks from peg A to peg C using peg B as an auxiliary.

🔹 Steps for n Disks:

  1. Move n-1 disks from A → B (using C).
  2. Move the largest disk from A → C.
  3. Move n-1 disks from B → C (using A).

🔹 Minimum Moves Required:

M(n)=2n1M(n) = 2^n - 1

🔹 Example for n = 3 (Moves = 7):


Move Disk 1 from A to C Move Disk 2 from A to B Move Disk 1 from C to B Move Disk 3 from A to C Move Disk 1 from B to A Move Disk 2 from B to C Move Disk 1 from A to C

Recursive Solution for Tower of Hanoi


#include <stdio.h> void towerOfHanoi(int n, char from, char to, char aux) { if (n == 1) { printf("Move Disk 1 from %c to %c\n", from, to); return; } towerOfHanoi(n - 1, from, aux, to); // Move n-1 disks from A to B printf("Move Disk %d from %c to %c\n", n, from, to); towerOfHanoi(n - 1, aux, to, from); // Move n-1 disks from B to C } int main() { int n = 3; // Number of disks towerOfHanoi(n, 'A', 'C', 'B'); return 0; }

🔹 Time Complexity: O(2^n) (Exponential)
🔹 Space Complexity: O(n) (Recursive calls)


🚀 Summary Table: Fibonacci vs Tower of Hanoi

ProblemApproachTime ComplexityBest Optimization
FibonacciRecursionO(2^n) (Exponential)Memoization (O(n))
FibonacciIterationO(n)Best for large n
Tower of HanoiRecursionO(2^n)No major optimizations
Tower of HanoiIterationDifficult to implementMostly solved using recursion

No comments:

Post a Comment

Complete Binary Tree in Data Structures

  Complete Binary Tree in Data Structures 🌳 A Complete Binary Tree (CBT) is a type of Binary Tree where: ✔ All levels except possibly t...