diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch6.ipynb')
| -rw-r--r-- | Data_Structures_and_Algorithms_in_Java/ch6.ipynb | 505 |
1 files changed, 470 insertions, 35 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch6.ipynb b/Data_Structures_and_Algorithms_in_Java/ch6.ipynb index 483043b8..c95d1bf1 100644 --- a/Data_Structures_and_Algorithms_in_Java/ch6.ipynb +++ b/Data_Structures_and_Algorithms_in_Java/ch6.ipynb @@ -1,6 +1,7 @@ { "metadata": { - "name": "ch6" + "name": "", + "signature": "sha256:de38e9569976fe6e7666e16fc87eae62ca1e6843703b45eeabd018f73553dc8b" }, "nbformat": 3, "nbformat_minor": 0, @@ -11,36 +12,59 @@ "cell_type": "heading", "level": 1, "metadata": {}, - "source": "Chapter 6 : Recursion" + "source": [ + "Chapter 6 : Recursion" + ] }, { "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.1 Page No : 255" + "source": [ + "Example 6.1 Page No : 255" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nExample 6.1\nevaluates triangular numbers\n'''\n\ndef triangle(n):\n if(n==1):\n return 1\n else:\n return( n + triangle(n-1) )\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\ntheAnswer = triangle(theNumber)\nprint 'Triangle = ' , theAnswer\n", + "input": [ + " \n", + "\n", + "def triangle(n):\n", + " if(n==1):\n", + " return 1\n", + " else:\n", + " return( n + triangle(n-1) )\n", + "\n", + "print 'Enter a number: ' ,\n", + "theNumber = int(raw_input())\n", + "theAnswer = triangle(theNumber)\n", + "print 'Triangle = ' , theAnswer\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": " Enter a number: " + "text": [ + " Enter a number: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "50\n" + "text": [ + "50\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": " Triangle = 1275\n" + "text": [ + " Triangle = 1275\n" + ] } ], "prompt_number": 11 @@ -49,30 +73,88 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.2 Page No : 265" + "source": [ + "Example 6.2 Page No : 265" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 6.2\ncreates anagrams\n'''\narrChar = []\nsize = 0\ncount = 0\ndef doAnagram(newSize):\n if(newSize == 1): # if too small,\n return\n for j in range(newSize): # for each position,\n doAnagram(newSize-1) # anagram remaining\n if(newSize==2): # if innermost,\n displayWord()\n rotate(newSize);\n\ndef rotate(newSize):\n global size\n global arrChar\n position = size - newSize\n temp = arrChar[position]\n for j in range(position+1,size):\n # shift others left\n arrChar[j-1] = arrChar[j]\n arrChar[size-1] = temp;\n\ndef displayWord():\n global count\n global size\n global arrChar\n if(count < 99):\n print ' ' ,\n if(count < 9):\n print ' ' ,\n count += 1\n print count ,\n for j in range(size):\n print arrChar[j] ,\n print '' ,\n if(count%6 == 0):\n print ''\n\nprint 'Enter a word: '\ni = raw_input()\n#global size\nsize = len(i)\nfor j in range(size):\n arrChar.append(i[j])\ndoAnagram(size)\n", + "input": [ + " \n", + "arrChar = []\n", + "size = 0\n", + "count = 0\n", + "def doAnagram(newSize):\n", + " if(newSize == 1): # if too small,\n", + " return\n", + " for j in range(newSize): # for each position,\n", + " doAnagram(newSize-1) # anagram remaining\n", + " if(newSize==2): # if innermost,\n", + " displayWord()\n", + " rotate(newSize);\n", + "\n", + "def rotate(newSize):\n", + " global size\n", + " global arrChar\n", + " position = size - newSize\n", + " temp = arrChar[position]\n", + " for j in range(position+1,size):\n", + " # shift others left\n", + " arrChar[j-1] = arrChar[j]\n", + " arrChar[size-1] = temp;\n", + "\n", + "def displayWord():\n", + " global count\n", + " global size\n", + " global arrChar\n", + " if(count < 99):\n", + " print ' ' ,\n", + " if(count < 9):\n", + " print ' ' ,\n", + " count += 1\n", + " print count ,\n", + " for j in range(size):\n", + " print arrChar[j] ,\n", + " print '' ,\n", + " if(count%6 == 0):\n", + " print ''\n", + "\n", + "print 'Enter a word: '\n", + "i = raw_input()\n", + "#global size\n", + "size = len(i)\n", + "for j in range(size):\n", + " arrChar.append(i[j])\n", + "doAnagram(size)\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Enter a word: \n" + "text": [ + "Enter a word: \n" + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "cats\n" + "text": [ + "cats\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": " 1 c a t s 2 c a s t 3 c t s a 4 c t a s 5 c s a t 6 c s t a \n 7 a t s c 8 a t c s 9 a s c t 10 a s t c 11 a c t s 12 a c s t \n 13 t s c a 14 t s a c 15 t c a s 16 t c s a 17 t a s c 18 t a c s \n 19 s c a t 20 s c t a 21 s a t c 22 s a c t 23 s t c a 24 s t a c \n" + "text": [ + " 1 c a t s 2 c a s t 3 c t s a 4 c t a s 5 c s a t 6 c s t a \n", + " 7 a t s c 8 a t c s 9 a s c t 10 a s t c 11 a c t s 12 a c s t \n", + " 13 t s c a 14 t s a c 15 t c a s 16 t c s a 17 t a s c 18 t a c s \n", + " 19 s c a t 20 s c t a 21 s a t c 22 s a c t 23 s t c a 24 s t a c \n" + ] } ], "prompt_number": 19 @@ -81,19 +163,82 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.3 Page No : 269" + "source": [ + "Example 6.3 Page No : 269" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nLISTING 6.3\ndemonstrates recursive binary search\n'''\nclass ordArray:\n def __init__(self,m): # constructor\n self.a = []\n self.nElems = 0\n def size(self):\n return self.nElems\n\n def find(self,searchKey):\n return self.recFind(searchKey, 0, self.nElems-1)\n\n def recFind(self,searchKey,lowerBound,upperBound):\n curIn = (lowerBound + upperBound ) / 2\n if(self.a[curIn]==searchKey):\n return curIn # found it\n elif(lowerBound > upperBound):\n return self.nElems # cant find it\n else: # divide range\n if(self.a[curIn] < searchKey): # its in upper half\n return self.recFind(searchKey, curIn+1, upperBound)\n else: # its in lower half\n return self.recFind(searchKey, lowerBound, curIn-1)\n\n def insert(self,value): # put element into array\n self.a.append(value)\n self.a.sort()\n self.nElems += 1\n\n def display(self): # displays array contents\n for j in range(self.nElems): # for each element,\n print self.a[j] , \n print ''\n\nmaxSize = 100 # array size\narr = ordArray(maxSize) # create the array\narr.insert(72)\narr.insert(90)\narr.insert(45)\narr.insert(126)\narr.insert(54)\narr.insert(99)\narr.insert(144)\narr.insert(27)\narr.insert(135)\narr.insert(81)\narr.insert(18)\narr.insert(108)\narr.insert(9)\narr.insert(117)\narr.insert(63)\narr.insert(36)\narr.display() # display array\nsearchKey = 27 # search for item\nif( arr.find(searchKey) != arr.size()):\n print 'Found ' , searchKey\nelse:\n print \"Can't find \" , searchKey", + "input": [ + " \n", + "class ordArray:\n", + " def __init__(self,m): # constructor\n", + " self.a = []\n", + " self.nElems = 0\n", + " def size(self):\n", + " return self.nElems\n", + "\n", + " def find(self,searchKey):\n", + " return self.recFind(searchKey, 0, self.nElems-1)\n", + "\n", + " def recFind(self,searchKey,lowerBound,upperBound):\n", + " curIn = (lowerBound + upperBound ) / 2\n", + " if(self.a[curIn]==searchKey):\n", + " return curIn # found it\n", + " elif(lowerBound > upperBound):\n", + " return self.nElems # cant find it\n", + " else: # divide range\n", + " if(self.a[curIn] < searchKey): # its in upper half\n", + " return self.recFind(searchKey, curIn+1, upperBound)\n", + " else: # its in lower half\n", + " return self.recFind(searchKey, lowerBound, curIn-1)\n", + "\n", + " def insert(self,value): # put element into array\n", + " self.a.append(value)\n", + " self.a.sort()\n", + " self.nElems += 1\n", + "\n", + " def display(self): # displays array contents\n", + " for j in range(self.nElems): # for each element,\n", + " print self.a[j] , \n", + " print ''\n", + "\n", + "maxSize = 100 # array size\n", + "arr = ordArray(maxSize) # create the array\n", + "arr.insert(72)\n", + "arr.insert(90)\n", + "arr.insert(45)\n", + "arr.insert(126)\n", + "arr.insert(54)\n", + "arr.insert(99)\n", + "arr.insert(144)\n", + "arr.insert(27)\n", + "arr.insert(135)\n", + "arr.insert(81)\n", + "arr.insert(18)\n", + "arr.insert(108)\n", + "arr.insert(9)\n", + "arr.insert(117)\n", + "arr.insert(63)\n", + "arr.insert(36)\n", + "arr.display() # display array\n", + "searchKey = 27 # search for item\n", + "if( arr.find(searchKey) != arr.size()):\n", + " print 'Found ' , searchKey\n", + "else:\n", + " print \"Can't find \" , searchKey" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 \nFound 27\n" + "text": [ + "9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 \n", + "Found 27\n" + ] } ], "prompt_number": 13 @@ -102,19 +247,42 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.4 Page No : 278" + "source": [ + "Example 6.4 Page No : 278" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 6.4\nsolves the towers of Hanoi puzzle\n'''\ndef doTowers(topN,frm,inter,to):\n if(topN==1):\n print \"Disk 1 from \" , frm , \"to \" , to\n else:\n doTowers(topN-1, frm, to, inter) # from-->inter\n print \"Disk \" , topN ,\" from \" , frm , \" to \" , to\n doTowers(topN-1, inter, frm, to) # inter-->to\n\n\nnDisks = 3\ndoTowers(nDisks, 'A', 'B', 'C')\n", + "input": [ + " \n", + "def doTowers(topN,frm,inter,to):\n", + " if(topN==1):\n", + " print \"Disk 1 from \" , frm , \"to \" , to\n", + " else:\n", + " doTowers(topN-1, frm, to, inter) # from-->inter\n", + " print \"Disk \" , topN ,\" from \" , frm , \" to \" , to\n", + " doTowers(topN-1, inter, frm, to) # inter-->to\n", + "\n", + "\n", + "nDisks = 3\n", + "doTowers(nDisks, 'A', 'B', 'C')\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Disk 1 from A to C\nDisk 2 from A to B\nDisk 1 from C to B\nDisk 3 from A to C\nDisk 1 from B to A\nDisk 2 from B to C\nDisk 1 from A to C\n" + "text": [ + "Disk 1 from A to C\n", + "Disk 2 from A to B\n", + "Disk 1 from C to B\n", + "Disk 3 from A to C\n", + "Disk 1 from B to A\n", + "Disk 2 from B to C\n", + "Disk 1 from A to C\n" + ] } ], "prompt_number": 14 @@ -123,19 +291,59 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.5 Page no : 281" + "source": [ + "Example 6.5 Page no : 281" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 6.5\ndemonstrates merging two arrays into a third\n'''\n# merge A and B into C\ndef merge(arrayA,sizeA,arrayB,sizeB,arrayC ):\n aDex=0\n bDex=0\n cDex=0\n while(aDex < sizeA and bDex < sizeB): # neither array empty\n if( arrayA[aDex] < arrayB[bDex] ):\n arrayC.append(arrayA[aDex])\n cDex += 1\n aDex += 1\n else:\n arrayC.append(arrayB[bDex])\n cDex += 1\n bDex += 1\n while(aDex < sizeA):\n arrayC.append(arrayA[aDex])\n cDex += 1\n aDex += 1\n while(bDex < sizeB):\n arrayC.append(arrayB[bDex]) # but arrayB isnt\n cDex +=1\n bDex += 1\n\ndef display(theArray,size):\n for j in range(size):\n print theArray[j],\n\n\n\narrayA = [23, 47, 81, 95]\narrayB = [7, 14, 39, 55, 62, 74]\narrayC = []\nmerge(arrayA, 4, arrayB, 6, arrayC)\ndisplay(arrayC, 10)\n", + "input": [ + " \n", + "# merge A and B into C\n", + "def merge(arrayA,sizeA,arrayB,sizeB,arrayC ):\n", + " aDex=0\n", + " bDex=0\n", + " cDex=0\n", + " while(aDex < sizeA and bDex < sizeB): # neither array empty\n", + " if( arrayA[aDex] < arrayB[bDex] ):\n", + " arrayC.append(arrayA[aDex])\n", + " cDex += 1\n", + " aDex += 1\n", + " else:\n", + " arrayC.append(arrayB[bDex])\n", + " cDex += 1\n", + " bDex += 1\n", + " while(aDex < sizeA):\n", + " arrayC.append(arrayA[aDex])\n", + " cDex += 1\n", + " aDex += 1\n", + " while(bDex < sizeB):\n", + " arrayC.append(arrayB[bDex]) # but arrayB isnt\n", + " cDex +=1\n", + " bDex += 1\n", + "\n", + "def display(theArray,size):\n", + " for j in range(size):\n", + " print theArray[j],\n", + "\n", + "\n", + "\n", + "arrayA = [23, 47, 81, 95]\n", + "arrayB = [7, 14, 39, 55, 62, 74]\n", + "arrayC = []\n", + "merge(arrayA, 4, arrayB, 6, arrayC)\n", + "display(arrayC, 10)\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "7 14 23 39 47 55 62 74 81 95\n" + "text": [ + "7 14 23 39 47 55 62 74 81 95\n" + ] } ], "prompt_number": 15 @@ -144,19 +352,97 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.6 Page no : 288" + "source": [ + "Example 6.6 Page no : 288" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 6.6\ndemonstrates recursive merge sort\n'''\n\nclass DArray:\n def __init__(self,m):\n self.theArray = []\n self.nElems = 0\n \n def insert(self,value):\n self.theArray.append(value)\n self.nElems += 1\n\n def display(self): # displays array contents\n for j in range(self.nElems):\n print self.theArray[j] ,\n print ''\n\n def mergeSort(self):\n workSpace = []\n for i in range(self.nElems):\n workSpace.append(0)\n self.recMergeSort(workSpace, 0, self.nElems-1)\n\n def recMergeSort(self,workSpace, lowerBound,upperBound):\n if(lowerBound == upperBound): # if range is 1,\n return\n else:\n mid = (lowerBound+upperBound) / 2\n self.recMergeSort(workSpace, lowerBound, mid)\n self.recMergeSort(workSpace, mid+1, upperBound)\n self.merge(workSpace, lowerBound, mid+1, upperBound)\n\n def merge(self,workSpace,lowPtr,highPtr,upperBound):\n j = 0\n lowerBound = lowPtr\n mid = highPtr-1\n n = upperBound-lowerBound+1\n while(lowPtr <= mid and highPtr <= upperBound):\n if( self.theArray[lowPtr] < self.theArray[highPtr] ):\n workSpace[j] = self.theArray[lowPtr]\n j += 1\n lowPtr += 1\n else:\n workSpace[j] = self.theArray[highPtr]\n j += 1\n highPtr += 1\n while(lowPtr <= mid):\n workSpace[j] = self.theArray[lowPtr]\n j += 1\n lowPtr += 1\n while(highPtr <= upperBound):\n workSpace[j] = self.theArray[highPtr]\n j += 1\n highPtr += 1\n for j in range(n):\n self.theArray[lowerBound+j] = workSpace[j]\n\nmaxSize = 100 # array size\narr = DArray(maxSize) # create the array\narr.insert(64) # insert items\narr.insert(21) \narr.insert(33) \narr.insert(70) \narr.insert(12) \narr.insert(85) \narr.insert(44) \narr.insert(3) \narr.insert(99) \narr.insert(0) \narr.insert(108) \narr.insert(36) \narr.display() # display items\narr.mergeSort() # merge sort the array\narr.display() # display items again", + "input": [ + " \n", + "class DArray:\n", + " def __init__(self,m):\n", + " self.theArray = []\n", + " self.nElems = 0\n", + " \n", + " def insert(self,value):\n", + " self.theArray.append(value)\n", + " self.nElems += 1\n", + "\n", + " def display(self): # displays array contents\n", + " for j in range(self.nElems):\n", + " print self.theArray[j] ,\n", + " print ''\n", + "\n", + " def mergeSort(self):\n", + " workSpace = []\n", + " for i in range(self.nElems):\n", + " workSpace.append(0)\n", + " self.recMergeSort(workSpace, 0, self.nElems-1)\n", + "\n", + " def recMergeSort(self,workSpace, lowerBound,upperBound):\n", + " if(lowerBound == upperBound): # if range is 1,\n", + " return\n", + " else:\n", + " mid = (lowerBound+upperBound) / 2\n", + " self.recMergeSort(workSpace, lowerBound, mid)\n", + " self.recMergeSort(workSpace, mid+1, upperBound)\n", + " self.merge(workSpace, lowerBound, mid+1, upperBound)\n", + "\n", + " def merge(self,workSpace,lowPtr,highPtr,upperBound):\n", + " j = 0\n", + " lowerBound = lowPtr\n", + " mid = highPtr-1\n", + " n = upperBound-lowerBound+1\n", + " while(lowPtr <= mid and highPtr <= upperBound):\n", + " if( self.theArray[lowPtr] < self.theArray[highPtr] ):\n", + " workSpace[j] = self.theArray[lowPtr]\n", + " j += 1\n", + " lowPtr += 1\n", + " else:\n", + " workSpace[j] = self.theArray[highPtr]\n", + " j += 1\n", + " highPtr += 1\n", + " while(lowPtr <= mid):\n", + " workSpace[j] = self.theArray[lowPtr]\n", + " j += 1\n", + " lowPtr += 1\n", + " while(highPtr <= upperBound):\n", + " workSpace[j] = self.theArray[highPtr]\n", + " j += 1\n", + " highPtr += 1\n", + " for j in range(n):\n", + " self.theArray[lowerBound+j] = workSpace[j]\n", + "\n", + "maxSize = 100 # array size\n", + "arr = DArray(maxSize) # create the array\n", + "arr.insert(64) # insert items\n", + "arr.insert(21) \n", + "arr.insert(33) \n", + "arr.insert(70) \n", + "arr.insert(12) \n", + "arr.insert(85) \n", + "arr.insert(44) \n", + "arr.insert(3) \n", + "arr.insert(99) \n", + "arr.insert(0) \n", + "arr.insert(108) \n", + "arr.insert(36) \n", + "arr.display() # display items\n", + "arr.mergeSort() # merge sort the array\n", + "arr.display() # display items again" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "64 21 33 70 12 85 44 3 99 0 108 36 \n0 3 12 21 33 36 44 64 70 85 99 108 \n" + "text": [ + "64 21 33 70 12 85 44 3 99 0 108 36 \n", + "0 3 12 21 33 36 44 64 70 85 99 108 \n" + ] } ], "prompt_number": 16 @@ -165,30 +451,120 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.7 Page No :295" + "source": [ + "Example 6.7 Page No :295" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nExample 6.7\nevaluates triangular numbers, stack replaces recursion\n'''\nclass Params: #parameters to save on stack\n def __init__(self,nn, ra):\n self.n=nn\n self.returnAddress=ra\n\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\ntheNumber = 0\ntheAnswer = 0\ntheStack = None\ncodePart = 0\ntheseParams = None\ndef recTriangle():\n global theStack,codePart\n theStack = StackX(10000)\n codePart = 1\n while( step() == False): # call step() until it's true\n pass\n\ndef step():\n global theStack,codePart,theseParams,theAnswer,theNumber\n if codePart==1:\n # initial call\n theseParams = Params(theNumber, 6)\n theStack.push(theseParams);\n codePart = 2\n elif codePart==2:\n # method entry\n theseParams = theStack.peek()\n if(theseParams.n == 1):\n theAnswer = 1\n codePart = 5\n else:\n codePart = 3\n elif codePart==3:\n newParams = Params(theseParams.n - 1, 4)\n theStack.push(newParams)\n codePart = 2 # go enter method\n elif codePart==4:\n theseParams = theStack.peek()\n theAnswer = theAnswer + theseParams.n\n codePart = 5\n elif codePart==5: # method exit\n theseParams = theStack.peek()\n codePart = theseParams.returnAddress # (4 or 6)\n theStack.pop()\n elif codePart==6: # return point\n return True\n else:\n pass\n return False\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\nrecTriangle()\nprint 'Triangle = ' ,theAnswer\n\n", + "input": [ + " \n", + "class Params: #parameters to save on stack\n", + " def __init__(self,nn, ra):\n", + " self.n=nn\n", + " self.returnAddress=ra\n", + "\n", + "class StackX:\n", + " def __init__(self,s):\n", + " self.maxSize = s\n", + " self.stackArray = []\n", + " self.top = -1\n", + "\n", + " def push(self,j):\n", + " self.top += 1\n", + " self.stackArray.append(j)\n", + " \n", + " def pop(self):\n", + " p = self.stackArray[self.top]\n", + " self.top -= 1\n", + " self.stackArray.remove(p)\n", + " return p\n", + " \n", + " def peek(self):\n", + " return self.stackArray[self.top]\n", + "\n", + " def isEmpty(self):\n", + " return (self.top == -1)\n", + "\n", + " def isFull(self):\n", + " return (self.top == self.maxSize-1);\n", + "\n", + "theNumber = 0\n", + "theAnswer = 0\n", + "theStack = None\n", + "codePart = 0\n", + "theseParams = None\n", + "def recTriangle():\n", + " global theStack,codePart\n", + " theStack = StackX(10000)\n", + " codePart = 1\n", + " while( step() == False): # call step() until it's true\n", + " pass\n", + "\n", + "def step():\n", + " global theStack,codePart,theseParams,theAnswer,theNumber\n", + " if codePart==1:\n", + " # initial call\n", + " theseParams = Params(theNumber, 6)\n", + " theStack.push(theseParams);\n", + " codePart = 2\n", + " elif codePart==2:\n", + " # method entry\n", + " theseParams = theStack.peek()\n", + " if(theseParams.n == 1):\n", + " theAnswer = 1\n", + " codePart = 5\n", + " else:\n", + " codePart = 3\n", + " elif codePart==3:\n", + " newParams = Params(theseParams.n - 1, 4)\n", + " theStack.push(newParams)\n", + " codePart = 2 # go enter method\n", + " elif codePart==4:\n", + " theseParams = theStack.peek()\n", + " theAnswer = theAnswer + theseParams.n\n", + " codePart = 5\n", + " elif codePart==5: # method exit\n", + " theseParams = theStack.peek()\n", + " codePart = theseParams.returnAddress # (4 or 6)\n", + " theStack.pop()\n", + " elif codePart==6: # return point\n", + " return True\n", + " else:\n", + " pass\n", + " return False\n", + "\n", + "print 'Enter a number: ' ,\n", + "theNumber = int(raw_input())\n", + "recTriangle()\n", + "print 'Triangle = ' ,theAnswer\n", + "\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Enter a number: " + "text": [ + "Enter a number: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "100\n" + "text": [ + "100\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": " Triangle = 5050\n" + "text": [ + " Triangle = 5050\n" + ] } ], "prompt_number": 17 @@ -197,30 +573,89 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 6.8 Page no : 301" + "source": [ + "Example 6.8 Page no : 301" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nExample 6.8\nevaluates triangular numbers, stack replaces recursion\n'''\n\n\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\ntheNumber = 0\ntheAnswer = 0\ntheStack = None\ntheseParams = None\n\ndef stackTriangle():\n global theNumber,theAnswer,theStack,theNumber\n theStack = StackX(10000)\n theAnswer = 0\n while(theNumber > 0): # until n is 1,\n theStack.push(theNumber) # push value\n theNumber -= 1 # decrement value\n\n while( not theStack.isEmpty() ): # until stack empty,\n newN = theStack.pop() # pop value,\n theAnswer += newN\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\nstackTriangle()\nprint 'Triangle = ' ,theAnswer\n\n\n", + "input": [ + " \n", + "\n", + "\n", + "class StackX:\n", + " def __init__(self,s):\n", + " self.maxSize = s\n", + " self.stackArray = []\n", + " self.top = -1\n", + "\n", + " def push(self,j):\n", + " self.top += 1\n", + " self.stackArray.append(j)\n", + " \n", + " def pop(self):\n", + " p = self.stackArray[self.top]\n", + " self.top -= 1\n", + " self.stackArray.remove(p)\n", + " return p\n", + " \n", + " def peek(self):\n", + " return self.stackArray[self.top]\n", + "\n", + " def isEmpty(self):\n", + " return (self.top == -1)\n", + "\n", + " def isFull(self):\n", + " return (self.top == self.maxSize-1);\n", + "theNumber = 0\n", + "theAnswer = 0\n", + "theStack = None\n", + "theseParams = None\n", + "\n", + "def stackTriangle():\n", + " global theNumber,theAnswer,theStack,theNumber\n", + " theStack = StackX(10000)\n", + " theAnswer = 0\n", + " while(theNumber > 0): # until n is 1,\n", + " theStack.push(theNumber) # push value\n", + " theNumber -= 1 # decrement value\n", + "\n", + " while( not theStack.isEmpty() ): # until stack empty,\n", + " newN = theStack.pop() # pop value,\n", + " theAnswer += newN\n", + "\n", + "print 'Enter a number: ' ,\n", + "theNumber = int(raw_input())\n", + "stackTriangle()\n", + "print 'Triangle = ' ,theAnswer\n", + "\n", + "\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Enter a number: " + "text": [ + "Enter a number: " + ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", - "text": "50\n" + "text": [ + "50\n" + ] }, { "output_type": "stream", "stream": "stdout", - "text": " Triangle = 1275\n" + "text": [ + " Triangle = 1275\n" + ] } ], "prompt_number": 18 @@ -228,7 +663,7 @@ { "cell_type": "code", "collapsed": false, - "input": "", + "input": [], "language": "python", "metadata": {}, "outputs": [] |