CS/COE 0449

Introduction to Systems Software & Programming

Programming Assignment–2

Due:Sunday Feb. 4th by 11:59pm--submitted electronically

Directions: Submit an electronic copy of this assignment to the course ftp-submission site.

 Pack all the assignment files to a FirstName_LastNameAssign2.zip file, using WinZip or a similar application.

 Submit the zipped package by using the computer science department's anonymous FTP server (cs.pitt.edu/incoming/CS449/ or ftp://ftp.cs.pitt.edu/incoming/CS449/). Please make sure submit your project to the proper section (449MWClass or 449THClass) and store it under Assign2 directory.

  • Submission must be before the due date, otherwise, it will be considered late. Once you submit, you can't take the file back! Therefore, please submit your final program and only one time.

Submission Directions

1-Name all the files a unified names: exc1.c, exc2.c... if a question has

several parts: exc5a.c, exc5b.c,...

2- Don't include.exe files because we are compiling under UNIX.

3-The name of the folder is the full name of the student:firstName_LastName

4-Don't include more than one folder...

5-Compile your programs using gcc "because we are using is standard C".

A number of students are submitting files with .cpp files or .c but this runs only using g++.

1. Problem.1:(Towers of Hanoi) Every budding computer scientist must grapple with certain classic problems, and the Towers of Hanoi of Hanoi is one of the most famous of these.

The legend-framework for "the towers of Hanoi" problem supposes there to be three pegs and several disks all of different diameters that can be stacked up on the pegs. The restriction is that any disks stacked on a peg must be arranged so that smaller disks are above larger disks. The problem is how, starting with all the disks stacked on one peg, to move them all to another peg one disk at a time, observing the stacking restriction at each move. The problem is generalized to any number of disks

The initial stack had 64-disks threaded onto one peg and arranged from bottom to top by decreasing size. Moving the stack from this peg to a second peg is done under the constraints that exactly one disk is moved at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding the disks.

Let us attempt to move the disks from peg1 to peg3. We wish to develop an algorithm that will print the precise sequence of disk-to-disk peg transfers. If we were to approach this problem with conventional methods, we would rapidly find ourselves hopelessly knotted up in managing the disks. Instead, if we attack the problem with recursion in mind, it immediately becomes tractable. Moving n disks can be viewed in terms of moving only n-1 disks (and hence the recursion) as follows:

a)Move n-1 disks from peg-1 to peg-2, using peg-3 as a temporary holding area.

b)Move the last disk (the largest) from peg-1 to peg-3.

c)Move n-1 disks from peg-2 to peg-3, using peg-1 as a temporary holding area.

The process ends when the last task involves moving n=1 disks, i.e. the base-case.

This is accomplished by trivially moving the disk without the need for a temporary holding area.

Write a program to solve the Towers of Hanoi problem. Use a recursive function with four parameters:

a)The number of disks to be moved.

b)The peg on which these disks are initially threaded.

c)The peg to which this stack of disks is to be moved.

d)The peg to be used as a temporary holding area.

Your program should print the precise instructions it will take to move the disks from the starting peg to the destination peg. For example, to move a stack of three disks from peg-1 to peg-3, your program should print the following series of moves:

1  3 (this means move one disk from peg-1 to peg-3)

1  2

3  2

1  3

2  1

2  3

1  3

Important Note: any code taken from the Internet will result in a 0-grade and possible further actions.

2. Problem-2:(Airline Reservation System)A small airline has just purchased a computer for its new automated reservation system. The president has asked you to program the new system. You are to write a program to assign seats on each flight of the airline’s only plane (capacity: 10 seats).

Your program should display the following menu of alternatives:

Please type 1 for “first class”

Please type 2 for “economy”

If the person types 1, then your program should assign a seat in the first class section (seats 1-5).

If the person types 2, then your program should assign a seat in the economy section (seats 6-10).

Tour program should then print the boarding pass indicating the person’s seat number and whether it is in the first class or economy section of the plane.

Use a single-subscripted array to represent the seating chart of the plane. Initialize all the elements of the array to 0 to indicate that all seats are empty. As each seat is assigned, set the corresponding element of the array to 1 to indicate that the seat is no longer available.

Your program should, of course, never assign a seat that has already been assigned. When the first class section is full, your program should ask the person if it is acceptable to be placed in the economy section (and vice versa). If yes, then make the appropriate seat assignment. If no, then print he message “Next flight leaves in 3 hours”.

3. Problem-3:(The tortoise and the Hare) In this problem, you will re-create one of the truly great moments in history, namely the classic race of the tortoise and the hare. You will use random number generation to develop a simulation of this memorable event.

Our contenders begin the race at “square 1” of 70-squares. Each square represents a possible position along the race course. The finish line is at square 70. The first contender to reach or pass square 70 is rewarded with a pail of fresh carrots and lettuce. The course weaves its way up the side of a slippery mountain, occasionally the contenders lose ground.

There is a clock that ticks once per second. With each tick of the clock, your program should adjust the position of the animals according to the rules shown below.

Use variables to keep track of the positions of the animals (i.e., position numbers are 1-70).

Start each animal at position 1 (i.e., the “starting gate”). If an animal slips left before square 1, move the animal back to square 1.

Generate the percentages in the table by producing a

random number integer, i, in the range 1 ≤ i ≤ 10.

For the tortoise,

perform a “fast plod” when 1 ≤ i ≤ 5

a “slip” when 6 ≤ i ≤ 7

or a “slow plod” when 8 ≤ i ≤ 10

Use a similar technique to move the hare.

Animal / Move Type / Percentage of the Time / Actual Move
Tortoise / Fast plod / 50% / 3 squares to the right
Slip / 20% / 6 squares to the left
Slow plod / 30% / 1 square to the right
Hare / Sleep / 20% / No moves at all
Big hop / 20% / 9 squares to the right
Big slip / 10% / 12 squares to the left
Small hop / 30% / 1 square to the right
Small slip / 20% / 2 squares to the left

Begin the race by printing:

BANG ! ! ! ! !

AND THEY’RE OF ! ! ! ! !

Then, for each tick of the clock (i.e., each repetition of a loop), print a 70-position line showing the letter T in the position of the tortoise and the letter H in the position of the hare. Occasionally, the contenders will land on the same square. In this case, the tortoise bites the hare and your program should print OUCH!!! (in case if a tie) should be blank.

After each line is printed, test of either animal has reached or passed square 70. If so, then print the winner and terminate the simulation. If the tortoise wins, print TORTOISE WINS!!! YAY!!!

If the hare wins, print Hare wins. Yuch. If both animals win on the same tick of the clock, you may want to favor the turtle (the “underdog”), or you may want to print It’s a tie.

If neither animal wins, perform the loop again to simulate the next tick of the clock. When you are ready to run your program, assemble a group of fans to watch the race. You will be amazed at how involved your audience gets!