diff options
Diffstat (limited to 'Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter5.ipynb')
| -rwxr-xr-x | Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter5.ipynb | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter5.ipynb b/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter5.ipynb new file mode 100755 index 00000000..14960493 --- /dev/null +++ b/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter5.ipynb @@ -0,0 +1,312 @@ +{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 01: Page 346"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "The value of f( 1 ) is 9\n",
+ "The value of f( 2 ) is 21\n",
+ "The value of f( 3 ) is 45\n",
+ "The value of f( 4 ) is 93\n"
+ ]
+ }
+ ],
+ "source": [
+ "#to compute the recursive functions\n",
+ "def f(n):\n",
+ "\n",
+ " if n==0:\n",
+ " return 3\n",
+ " else:\n",
+ " n=n-1\n",
+ " result=2*f(n)+3 #recursive call\n",
+ " return result\n",
+ "for num in range(1,5):\n",
+ " r=f(num)\n",
+ " print \"The value of f(\",num,\") is\",r #Prints the result for individual instance\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 01: Page 361"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter a number whose factorial is to be found4\n",
+ "The factorial of 4 is 24\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute the factorial of a given number using recursion\n",
+ "def factorial(n):\n",
+ " if n==0:\n",
+ " return 1\n",
+ " else:\n",
+ " return n*factorial(n-1) #recursive function call\n",
+ "num=input(\"Enter a number whose factorial is to be found\");\n",
+ "print \"The factorial of\",num,\"is\",factorial(num);\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 02: Page 361"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the number5\n",
+ "Enter the power4\n",
+ "The value of 5 to the power 4 is 625\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute power using recursive algorithm\n",
+ "def power(a,n):\n",
+ " if n==0:\n",
+ " return 1\n",
+ " else:\n",
+ " return a*power(a,n-1) #recursive call algorithm\n",
+ "num=input(\"Enter the number\");\n",
+ "p=input(\"Enter the power\");\n",
+ "print \"The value of\",num,\"to the power\",p,\"is\",power(num,p);\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 03: Page 362"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the first number5\n",
+ "Enter the second number8\n",
+ "The gcd of 5 , 8 is 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute gcd using modular recursion\n",
+ "def gcd(a,b):\n",
+ " if a==0:\n",
+ " return b\n",
+ " else:\n",
+ " return gcd(b%a,a) #recursive call\n",
+ "\n",
+ "num1=input(\"Enter the first number\")\n",
+ "num2=input(\"Enter the second number\")\n",
+ "print \"The gcd of\",num1,\",\",num2,\"is\",gcd(num1,num2)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 04: Page 362"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the number2\n",
+ "Enter the power5\n",
+ "Enter the modulo number3\n",
+ "The answer of mpower( 2 , 5 , 3 ) is 2\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute mpower function using recursion\n",
+ "def mpower(b,n,m):\n",
+ " if n==0:\n",
+ " return 1\n",
+ " else:\n",
+ " if n%2==0:\n",
+ " return ((mpower(b,n/2,m))**2) % m #recursive call\n",
+ " else:\n",
+ " return ((mpower(b,n/2,m)**2)%m*(b%m))%m #recursive call\n",
+ "number=input(\"Enter the number\")\n",
+ "power=input(\"Enter the power\")\n",
+ "modulo=input(\"Enter the modulo number\");\n",
+ "print \"The answer of mpower(\",number,\",\",power,\",\",modulo,\") is\",mpower(number,power,modulo)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 05:INDUCTION AND RECURSION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 09: Page 367"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "enter the numbers to be merge sorted8,2,4,6,9,7,10,1,5,3\n",
+ "Ther Merge sort is ['1', '10', '2', '3', '4', '5', '6', '7', '8', '9']\n"
+ ]
+ }
+ ],
+ "source": [
+ "def msort2(x): #function for merge sort\n",
+ " if len(x) < 2:\n",
+ " return x\n",
+ " result = [] \n",
+ " mid = int(len(x)/2) #divides the elements into halves\n",
+ " y = msort2(x[:mid])\n",
+ " z = msort2(x[mid:])\n",
+ " while (len(y) > 0) and (len(z) > 0):\n",
+ " if y[0] > z[0]:\n",
+ " result.append(z[0]) #merges to append the elements\n",
+ " z.pop(0)\n",
+ " else:\n",
+ " result.append(y[0])\n",
+ " y.pop(0)\n",
+ " result += y\n",
+ " result += z\n",
+ " return result\n",
+ "l=[]\n",
+ "r=[]\n",
+ "l=raw_input(\"enter the numbers to be merge sorted\").split(\",\")\n",
+ "r=msort2(l)\n",
+ "print \"Ther Merge sort is\", r\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 2",
+ "language": "python",
+ "name": "python2"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 2
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython2",
+ "version": "2.7.9"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 0
+}
|