代写Stacks、代写Towers of Hanoi、代写python Stacks程序

日期：2018-07-12 03:20

Lab 2: Towers of Hanoi, Stacks and Callable Objects 10 points

ECEC-301 Summer 2018

1. Stacks: Python does not have its own Stack module, because it is easy to simulate a stack

using lists and the pop() command for lists. First thing you must do is learn about stacks, one of

the classic data structures in computer science.

Viewing Assignment: Watch this video.

https://www.youtube.com/watch?v=FNZ5o9S9prU

Reading Assignment 1: Carefully read the description of stacks here and study Table 1. Similar

examples may appear on a quiz.

http://interactivepython.org/runestone/static/pythonds/BasicDS/TheStackAbstractDataType.html

Reading Assignment 2: Carefully read the info on stacks here. The pictures are very helpful.

http://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

Reading Assignment 3: Using lists as stacks.

https://docs.python.org/3/tutorial/datastructures.html

Keywords to master: stack, LIFO, pop(), push(), peek(), isFull() (for bounded stacks only),

isEmpty(), top, size().

Open and run the file named Stack.py

Study how it works. Notice the pointer always indicates the top of the stack. Run the file and

explore the first demo. Also notice how the argument to the constructor is optional because it

was given a default value.

def __init__(self, initial_list=[]): # example of an optional argument

self.items = initial_list # the list of items in the Stack

a. Study the first demo1.

b. Create a second demo to test if a string is a palindrome. Complete these steps.

i. In the Stack class, complete the magic method __eq__ so that two stacks are equal iff and

only if their stack_list attributes are equal.

ii. In the body of demo2(), use a for loop to grab each character (ch) in the test_phrase, and if it is

an alphabetical character [Use: isalpha()] push it onto both the Stacks named stack1 and temp.

Temp is a temporary stack that will shortly be consumed.

iii. Create a reversed copy in stack2, by popping every item from temp and pushing it onto

stack2. A while loop and not isEmpty() should help.

iv. Test if stack1 and stack2 are equal using ==, and print an appropriate message using an if/else

structure.

Sample Output: Yes, TACOCAT is a palindrome!

2

Have fun! Test some of these other palindromes:

A nut for a jar of tuna.

A Toyota’s a Toyota.

Aerate pet area.

Dammit, I’m mad!

Do geese see God?

Drab as a fool, aloof as a bard.

Evil, a sin, is alive.

Flee to me, remote elf.

Goldenrod-adorned log.

Hey, Roy! Am I mayor? Yeh!

I’m a fool; aloof am I.

Lepers repel.

2. Some Magic Methods for Lists: You can see the magic methods for lists by typing

help(list) in the Python Console (or running that command in a script). All the magic methods

begin with double underscore __ and end with double underscore. That’s why magic methods are

also called dunder methods (rhymes with under).

>>> help(list)

The file dunder_methods_for_lists.py contains ten examples of magic methods. Redo each

example using the appropriate dunder method instead. Examples 1 to 5 are done for you. Complete

the remaining 5 parts using the parallel dunder method. Your TA will randomly pick two parts

from 6 to 10 to grade this question.

Exercise 3. Callable objects in Python: callable() and the magic method __call__

More info about magic methods can be found in the second lecture from Dr. Shackleford inside the

Lectures folder. Especially, magic methods.

Definition: A function is a callable object in Python. That means it can be called using the call

operator: __call__ More generally, a callable is an object that allows you to use round

parenthesis ( ) and eventually pass some parameters, just like functions. If f is a callable for which

10 is a valid argument, then f(10) is equivalent to f.__call__(10)

Open the file callable_examples.py. Carefully explore the examples in this file.

3

Examples 1-4 illustrate that int, max, string.upper and math.sin are all callable. Each example

verifies callable(object) returns True, then gets the same result using the call operator:

object.__call__(arguments)

An object or method m is callable if and only if this command returns True. >>> callable(m)

A callable method with arguments such as max(1,2,3)

is equivalent to: max.__call__(1, 2, 3)

Example 5 illustrates that strings are not callable and uses exception handling to not crash the program.

Example 6 illustrates that you can create your own callables using the magic method __call__().

Example 7 illustrates your own function definitions produce callables.

Review all these examples carefully to prepare for the Midterm.

Now to earn some points.

a. Complete example 8: Is callable callable?

i. Test if callable is callable without using __call__.

ii. Test if callable is callable using exactly one __call__.

iii. Test if callable is callable using __call__ exactly twice. There are two ways.

b. Complete example 9: For each object below, print out whether or not it is callable. Fully

document each example using print statements. If it is callable, demonstrate that using the

__call__ operator.

i. 3, ii. math, iii. math.sqrt, iv. math.pi, v. range

Grader: One point if example 8 is complete and correct. One more point for example 9.

Note the dot!

4

Exercise 4. HanoiStacks

Note: You must complete __call__ before running this code.

The goal in the Tower of Hanoi puzzle is to move all the disks or rings from stack A to the stack

C. In general, we can start with any number N of rings on Stack A.

Key Rule: You are never allowed to cover a smaller disk with a larger disk.

To solve the problem, we will first define a subclass HanoiStack of the Stack class and then solve

the game in a third class TowerOfHanoi which aggregates the three HanoiStacks. That is, each

object in this class has attributes including three HanoiStacks named A, B and C, and also two

integers numberOfRings and numberOfMoves (to keep track of progress).

Objects in the subclass HanoiStack of Stack will be quite “clever”, so that the Tower of Hanoi

game can practically solve itself.

Problem Insights: Let’s look at a few simple cases to gain insight into the problem.

Case N = 1: If there is just one ring, we can solve the puzzle in a single move. 2" − 1 = 1

Stack

HanoiStack TowerOfHanoi

aggregation

subclass

superclass

inheritance

A B C

N=7

Rings

A B C

Solve in 1 move:

Pop Stack A and push the

ring onto stack C. Stack B

is inactive.

Inactive Stack: Move:

1. B A(C)

5

Case N = 2: If there are just two rings, we can solve the puzzle in 3 moves: 2" − 1 = 3

Add the midway (+1) point, we are half-way there. Just pop the small ring from B onto C to finish.

At the midway point, the largest ring is now on C and the rest of the rings are on B.

Case N = 3: If there are three rings, we can solve the puzzle in seven moves: 2( − 1 = 7

A B C

Solve in 3 moves:

1.Pop Stack A and push the small ring onto stack B.

2.Pop Stack A and push the big ring onto stack C.

3.Pop Stack B and push the small ring onto stack C.

A B C

A B C

Inactive Stack: Move:

1. C A(B)

2. B A(C)

3. A B(C)

6

Here’s the half-way point after 4 moves. Again, we see the biggest ring is on C and the rest are in

the middle on B.

First Move: The first move is always to pop the small ring off Stack A, and place it on either B

or C. If N is odd, we place the small ring on C. If N is even, we place the small ring on B.

Solution: After each move, update the inactive stack. If N is odd, the new inactive stack is obtained

by adding one. If N is even, the new inactive stack is obtained by subtracting one. The next move

is always the same. The two active stacks call each other. Repeat until the problem is solved!

OK, time to earn some points!

a. Open the file HanoiStack.py and locate the incomplete __call__ method. Complete this

method by coding the following parts.

i. The two stacks are called self and other. If both stacks are empty, just return. Do nothing.

In the header of the required if statement, you can use isEmpty() twice, since this in

inherited from the super class named Stack.

ii. If the calling stack named self is empty, pop other and push that onto self, then return.

Both pop and push are available from the superclass by inheritance.

iii. If the called stack named other is empty, pop self and push that onto other, then return.

iv. The general case, where neither stack is empty is done for you using peek.

b. When you have completed the code above, you should be able to run the main method.

At the beginning, we made B initially inactive, since N=3 is odd. Five of the seven steps are given.

Complete the last two steps to solve the Tower of Hanoi with N=3.

A B C

Half-Way Point:

1.Pop Stack A and push the small ring onto stack C.

2.Pop Stack A and push the middle ring onto stack B.

3.Pop Stack C and push the small ring onto stack B.

4.Pop Stack A and push the big ring onto stack C.

Inactive Stack: Move:

1. B A(C)

2. C A(B)

3. A B(C)

4. B A(C) ß Pattern repeats

7

Exercise 5. Tower of Hanoi with N Rings

Note: You must complete HanoiStack.py before attempting this problem.

Complete the file Tower_of_hanoi.py to solve the problem with any number of rings.

The two active stacks call each other, and the inactive stack is reset each turn. With these

definitions, the solution becomes simply:

That is, just keep calling tower.solve() until the problem is solved! Wow! How simple is that!

a. Add the above code to at the bottom of the main method, and verify the Tower is solved.

b. Add a print statement to show the number of moves it took to solve the puzzle.

Does it agree with our formula 2* − 1?

c. Test by changing the number of rings to 5. Does it still agree with our formula 2* − 1?

d. Pause at the half-way point. We saw earlier that the half-way point is after 2*+, moves.

This corresponds to the biggest ring on tower C and all the rest [n-1, n-2, … , 1] in a stack on

another ring. This could be the basis for an inductive solution, but we don't need that, because

our Towers are SMART and can solve the problem with no help.

Add a pause of 10 seconds to display the half-way point. Just add an if

statement inside the while loop for the solution.

while not tower.isDone():

tower.solve()