Problem 1: Holey Squares

A holey square is a square matrix each element of which is either a decimal digit or a "hole" (i.e., unoccupied). The digit in the first column of the first row (upper lefthand corner) is called the starting digit. As you scan the rows from top to bottom, each row from left to right, you find that the digits occur in succession (0 is followed by 1, which is followed by 2, ..., which is followed by 9, which is followed by 0). You also find that a hole appears immediately after each occurrence of a particular digit, called the holey digit. To illustrate, here is the holey square of size 5 (i.e., having 5 rows and 5 columns) having 7 as its starting digit and 9 as its holey digit:

7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Develop a program that accepts as input the size, starting digit, and holey digit of a holey square, and that produces as output the corresponding holey square. The program should terminate when the user enters zero as the size.

Sample Program Execution:

Enter size: 9 Enter starting digit: 5 Enter holey digit: 5 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 Enter size: 6 Enter starting digit: 3 Enter holey digit: 8 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 Enter size: 0

Problem 2: Binary to Decimal Translation

In an electronic computer, all data is represented in binary form, i.e., as a sequence of 0's and 1's. In particular, integers are usually represented using the binary number system, as opposed to the decimal number system to which you are accustomed. These two number systems are actually very much alike. Indeed, they are both positional number systems, which means that the "contribution" made by each digit in a number depends not only upon its value but also upon its position within the number.

In the decimal (or base ten) system, we use the ten digits 0, 1, 2, ..., 9. Going from right to left, the positions in a number correspond to units of 1, 10, 100, 1000, etc. (Notice that these are the powers of 10: 10⁰ = 1, 10¹ = 10, 10² = 100, 10³ = 1000, etc.)  The expression 45038 is to be understood to mean

The binary (or base two) number system is just the same, except that we use only the two digits 0 and 1, and the positions in a number correspond to units of 1, 2, 4, 8, 16, etc. (the powers of 2). Thus, for example, 1001101₂ (the subscript indicates that the number is to be interpreted as one written in binary notation) is to be understood to mean

which, in decimal notation, is 77.

Develop a program that, given as input a number expressed in the binary number system, outputs the same number expressed in the decimal number system. The input will have no more than 12 digits. The program should terminate when the user enters 00 as input.

Sample Program Execution:

Enter binary number: 101011 Decimal representation: 43 Enter binary number: 0 Decimal representation: 0 Enter binary number: 10000101 Decimal representation: 133 Enter binary number: 00

Problem 3: Summing Binary Numbers

Develop a program that accepts as input two binary numbers and that calculates and outputs their sum (which is also to be expressed in binary form). Each input will have no more than thirty digits. The program should repeat until both inputs are zero.

As described in the previous problem, the binary number system is completely analogous to the more familiar decimal number system, in terms of how numbers are represented. Hence, it should not be surprising that the procedure for adding two decimal numbers (which you learned in elementary school) applies to binary numbers as well.

Indeed, just as with decimal numbers, we "line up" the two addends (so that digits in corresponding positions appear one above the other) and proceed from the rightmost (i.e., least significant) to the leftmost (i.e., most significant) position. (If one number has more digits than the other, we pad the latter with leading zeros.)

For each position, we add the incoming carry to the sum of the two digits in that position (one for each addend), yielding one of the values zero (00₂), one (01₂), two (10₂), or three (11₂). The digit of lesser significance goes into the corresponding position of the result; the digit of greater significance is carried into the next position.

Sample Program Execution:

1st number: 101101011 2nd number: 101101 Sum: 110011000 1st number: 1111 2nd number: 1010 Sum: 11001 1st number: 0 2nd number: 0

Problem 4: Palindromic Numbers

A palindrome is a string of characters that reads the same forwards as backwards. For example, if we ignore spaces, the phrase "may a moody baby doom a yam" is a palindrome. Here, we consider those palindromes consisting entirely of the digits 0 through 9 and not beginning with 0. Examples are 72427, 5, and 9009. Any number corresponding to such a palindrome is said to be a palindromic number. Note:  By this definition, numbers such as 3300, which could also be written with leading zeros as 003300, do not qualify as being palindromic.

Develop a program that takes as input a positive integer and that reports whether or not that integer is palindromic. The program should repeat until the user enters zero as input.

Sample Program Execution:

Enter number: 81248 NOT PALINDROMIC Enter number: 4 PALINDROMIC Enter number: 30 NOT PALINDROMIC Enter number: 405504 PALINDROMIC Enter number: 0

Problem 5: Rational Arithmetic

A rational number is the ratio of two integers, the second of which is nonzero. We usually express such a number in the form n/d, i.e., as a fraction. We refer to n as the numerator and to d as the denominator. If d>1 and the greatest common divisor of n and d is one, we say that n/d is in simplest form. The simplest form of n/1 is n (with no denominator).

Most programming languages have built-in facilities for representing and manipulating integers so that calculations performed upon them yield exact results. The same is not true of real numbers. Indeed, a "real" number stored in a computer is only an approximation to the number it is intended to represent. This is due to the fact that, in general, to represent a real number exactly requires infinitely many digits, whereas a computer has only a finite memory capacity.

Few programming languages have built-in facilities for dealing with rational numbers. This is not necessarily an oversight: due to the fact that all rational numbers are also real numbers, a programmer may use a language's built-in facilities for real numbers in order to manipulate rationals. Results of calculations will be only approximations, however. This problem challenges you to remedy this situation by developing a program that performs exact arithmetic upon rational numbers!

Write a program that accepts as input a sequence of four nonnegative integers n₁, d₁, n₂, d₂, followed by a symbol op, which must be one of the four basic arithmetic operators (+, -, *, or /). The program should evaluate the expression

and display the result, which must be in simplest form. The required format for input and output is illustrated below. The program should terminate when the user enters 0 for either of the inputs d₁ or d₂

Sample Program Execution:

Enter Expression: 25 45 8 99 + 25/45 + 8/99 = 7/11 Enter Expression: 7 9 18 28 * 7/9 * 18/28 = 1/2 Enter Expression: 12 13 3 26 / 12/13 / 3/26 = 8 Enter Expression: 5 0 2 1 -

 

---

Problem 6: Groceries: To Tax or Not To Tax

Among the items sold at grocery stores, some are taxable and some are not. Thus, when you make a purchase, the final bill is the sum of the prices of the non-taxable items plus the sum of the prices of the taxable items, plus the tax on the taxable items.

Develop a program that calculates a grocery store bill. As input, the user supplies the number of items purchased and, for each item, its price (in dollars) and either Y or N to indicate whether or not, respectively, it is taxable. A tax rate of 6% is to be applied to the sum of the prices of the taxable items. Tax should be rounded to the nearest hundredth of a dollar (i.e., cent). Notice that in the two examples below, 6% of the cost of the taxable items is $0.4506 and $0.4572, respectively, which round to $0.45 and $0.46, respectively. The program should repeat until the user enters zero for the number of items purchased.

Sample Program Execution:

Number of items purchased: 4 Price of item 1: 2.39 Taxable? : N Price of item 2: 3.12 Taxable? : Y Price of item 3: 4.39 Taxable? : Y Price of item 4: 2.09 Taxable? : N Subtotal is 11.99 Tax is 0.45 Grand total is 12.44 Number of items purchased: 3 Price of item 1: 5.61 Taxable? : Y Price of item 2: 2.01 Taxable? : Y Price of item 3: 3.28 Taxable? : N Subtotal is 10.90 Tax is 0.46 Grand total is 11.36 Number of items purchased: 0