5th_Nov_Recursion_Assignment .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "67e590dc",
   "metadata": {},
   "source": [
    "# Recursion Assignment Questions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "296a14ad",
   "metadata": {},
   "source": [
    "# Q.1 Can you explain the logic and working of the Tower of Hanoi algorithm by writing a Python program? How does the recursion work, and how are the movements of disks between rods accomplished?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8275f85",
   "metadata": {},
   "source": [
    "The Tower of Hanoi is a classic problem in computer science and mathematics. The problem consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:\n",
    "\n",
    "1. Only one disk can be moved at a time.\n",
    "2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.\n",
    "3. No disk may be placed on top of a smaller disk.\n",
    "\n",
    "Here's a Python program that solves the Tower of Hanoi problem using recursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "70d50168",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of moves for 3 disks: 7\n"
     ]
    }
   ],
   "source": [
    "def moves(n, s, d, a):\n",
    "    # base condition\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    # move n-1 from s -> a, then move 1 biggest coin s->d and then n-1 coin a->d\n",
    "    return moves(n-1, s, a, d) + 1 + moves(n-1, a, d, s)\n",
    "\n",
    "# Example usage\n",
    "num_disks = 3\n",
    "result = moves(num_disks, 'S', 'D', 'A')\n",
    "print(f\"Number of moves for {num_disks} disks: {result}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5cf20f1a",
   "metadata": {},
   "source": [
    "**Explanation:**\n",
    "\n",
    "1. **Function `moves` Parameters:**\n",
    "   - `n`: The number of disks to be moved.\n",
    "   - `s`: The source rod from which disks are initially placed.\n",
    "   - `d`: The destination rod to which disks need to be moved.\n",
    "   - `a`: The auxiliary (or intermediate) rod used during the process.\n",
    "\n",
    "2. **Base Condition:**\n",
    "   - `if n == 1:`: This is the base case. When there is only one disk (`n == 1`), it directly returns 1, as only one move is needed to transfer the disk from the source rod (`s`) to the destination rod (`d`).\n",
    "\n",
    "3. **Recursive Case:**\n",
    "   - `return moves(n-1, s, a, d) + 1 + moves(n-1, a, d, s)`: This line represents the recursive logic for the Tower of Hanoi problem.\n",
    "     - `moves(n-1, s, a, d)`: Move `n-1` disks from the source rod (`s`) to the auxiliary rod (`a`).\n",
    "     - `1`: Move the largest disk from the source rod (`s`) to the destination rod (`d`).\n",
    "     - `moves(n-1, a, d, s)`: Move the `n-1` disks from the auxiliary rod (`a`) to the destination rod (`d`).\n",
    "\n",
    "4. **Example Usage:**\n",
    "   - `num_disks = 3`: This sets the number of disks for the Tower of Hanoi problem to 3.\n",
    "   - `result = moves(num_disks, 'S', 'D', 'A')`: Calls the `moves` function with the specified parameters and stores the result (total number of moves) in the variable `result`.\n",
    "   - `print(f\"Number of moves for {num_disks} disks: {result}\")`: Prints the result, indicating the number of moves required to solve the Tower of Hanoi problem for 3 disks."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac6b8e49",
   "metadata": {},
   "source": [
    "# Q.2 Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "832d2a5a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The minimum number of operations to convert 'horse' to 'ros': 3\n",
      "The minimum number of operations to convert 'intention' to 'execution': 5\n"
     ]
    }
   ],
   "source": [
    "def min_distance(word1, word2):\n",
    "    m, n = len(word1), len(word2)\n",
    "\n",
    "    # Create a 2D array to store the minimum distances\n",
    "    dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "    # Initialize the first row and column\n",
    "    for i in range(m + 1):\n",
    "        dp[i][0] = i\n",
    "    for j in range(n + 1):\n",
    "        dp[0][j] = j\n",
    "\n",
    "    # Fill the rest of the matrix\n",
    "    for i in range(1, m + 1):\n",
    "        for j in range(1, n + 1):\n",
    "            if word1[i - 1] == word2[j - 1]:\n",
    "                dp[i][j] = dp[i - 1][j - 1]\n",
    "            else:\n",
    "                dp[i][j] = 1 + min(dp[i - 1][j],  # Deletion\n",
    "                                  dp[i][j - 1],  # Insertion\n",
    "                                  dp[i - 1][j - 1])  # Substitution\n",
    "\n",
    "    return dp[m][n]\n",
    "\n",
    "# Example usage 1:\n",
    "word1 = \"horse\"\n",
    "word2 = \"ros\"\n",
    "result = min_distance(word1, word2)\n",
    "print(f\"The minimum number of operations to convert '{word1}' to '{word2}': {result}\")\n",
    "\n",
    "#Example usage 2:\n",
    "word1 = \"intention\"\n",
    "word2 = \"execution\"\n",
    "result = min_distance(word1, word2)\n",
    "print(f\"The minimum number of operations to convert '{word1}' to '{word2}': {result}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f72b494",
   "metadata": {},
   "source": [
    "# Q. 3 Print the max value of the array [ 13, 1, -3, 22, 5]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ac749ea2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum element of the array: [13, 1, -3, 22, 5] is 22\n"
     ]
    }
   ],
   "source": [
    "def find_max(arr):\n",
    "    max_ele = arr[0]\n",
    "    for i in range(1,len(arr)):\n",
    "        if arr[i] > max_ele:\n",
    "            max_ele = arr[i]\n",
    "    return max_ele\n",
    "\n",
    "arr = [13, 1, -3, 22, 5]\n",
    "max_ele = find_max(arr)\n",
    "print(f\"Maximum element of the array: {arr} is {max_ele}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d537d0d5",
   "metadata": {},
   "source": [
    "# Q.4 Find the sum of the values of the array [92, 23, 15, -20, 10]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3bff1e10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sum of values of the array:[92, 23, 15, -20, 10] is 120\n"
     ]
    }
   ],
   "source": [
    "def sum_arr(arr):\n",
    "    val_sum = 0\n",
    "    for i in arr:\n",
    "        val_sum += i\n",
    "    return val_sum\n",
    "\n",
    "arr = [92, 23, 15, -20, 10]\n",
    "val_sum = sum_arr(arr)\n",
    "print(f\"Sum of values of the array:{arr} is {val_sum}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5242d53b",
   "metadata": {},
   "source": [
    "# Q.5 Given a number n. Print if it is an armstrong number or not.An armstrong number is a number if the sum of every digit in that number raised to the power of total digits in that number is equal to the number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "22809cf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "153 is an Armstrong number.\n",
      "157 is not an Armstrong number.\n"
     ]
    }
   ],
   "source": [
    "def check_armstrong(num):\n",
    "    # Save the original number\n",
    "    org = num\n",
    "    # calculate the number of digits of the given number\n",
    "    n = len(str(num))\n",
    "    sum_dig = 0\n",
    "    # loop to iterate through each digit of the number\n",
    "    while org > 0:\n",
    "        #extracting the last digit\n",
    "        d = org % 10\n",
    "        #Add the digit raised to the power of n to the sum\n",
    "        sum_dig += d ** n\n",
    "        # Remove the last digit from the number\n",
    "        org = org//10\n",
    "    \n",
    "    # Check if the sum of digits is equal to the original number\n",
    "    if sum_dig == num:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "# Example usage 1 \n",
    "num = 153\n",
    "result = check_armstrong(num)\n",
    "\n",
    "if result:\n",
    "    print(f\"{num} is an Armstrong number.\")\n",
    "else:\n",
    "    print(f\"{num} is not an Armstrong number.\")\n",
    "\n",
    "        \n",
    "# Example usage 2\n",
    "num = 157\n",
    "result = check_armstrong(num)\n",
    "\n",
    "if result:\n",
    "    print(f\"{num} is an Armstrong number.\")\n",
    "else:\n",
    "    print(f\"{num} is not an Armstrong number.\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}