Repetition Statements
Take-home Lab #2 (CS1010 AY2011/12 Semester 2)
Date of release: 5 February 2012, Sunday
Submission deadline: 13 February 2012, Monday, 12nn
School of Computing, National University of Singapore

0 Introduction

Please read through lab instructions before attempting this graded lab.

• Remember to spend some time thinking about the algorithm for each exercise before you start typing in your program.
  
  
• Please read instructions of each exercise CAREFULLY and follow them EXACTLY.
  
  
• You should test your program thoroughly with your own test data before submission. Do NOT use CodeCrunch as your testing or debugging tool. As lab progresses, we will reduce the number of submissions allowed.

This lab requires you to do four exercises on repetition control structure, but only the first three will be graded by your discussion leaders/grader. The last exercise is for your own practice only.

1 Exercise 1: The 3x+1 Problem

1.1 Learning objectives

• Using selection and repetition statements
• Writing functions

1.2 Task statement

The 3x+1 problem is also known as the Collatz problem (and a few other names), named after Lothar Collatz who first proposed it in 1937. The Collatz conjecture, still unsolved in mathematics, states the following: Take any natural number n. If n is even, divide it by 2 to get n/2; if n is odd, triple it and add 1 to obtain 3n + 1 (see the mathematical expression below). Repeat the process indefinitely. No matter what number your start with, you will always eventually reach 1.

You are not required to prove the Collatz conjecture, but to write a program collatz.c that reads in a positive integer and determines how many iterations it takes to reach 1.

For example, if the input is 3, then the answer would be 7, as 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

Check sample run for input and output format; submit your program through CodeCrunch.

1.3 Sample runs

Two sample runs are shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

Enter a natural number: 3
Number of iterations = 7

Enter a natural number: 4
Number of iterations = 2

1.4 Important notes

• Write a function count_iterations to compute the number of iterations required for the input value to reach 1.
  
  
• In writing functions, we would like you to include function prototypes before the main function, and the function definitions after the main function.

1.5 Skeleton file and sample test data

• collatz.c
• collatz1.in
• collatz1.out

1.6 Reference solution

Note that the following reference solution is just one way of tackling this exercise. Never take it as a model answer.

• collatz.c (link accessible after deadline)

1.7 Number of submissions

For this exercise, the number of submissions is 10.

1.8 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that some help (or more practice) might be needed.

• Devising and writing the algorithm (pseudo-code): 10 minutes
• Translating pseudo-code into code: 5 minutes
• Typing in the code: 5 minutes
• Testing and debugging: 10 minutes
• Total: 30 minutes

2 Exercise 2: Candles

2.1 Learning objectives

• Using repetition statements
• Writing functions
• Applying neat logic in problem solving

2.2 Task statement

(Past year CS1101 Practical Exam question)

Alexander has n candles. He burns them one at a time and carefully collects all unburnt residual wax. Out of the residual wax of exactly k (where k > 1) candles, he can roll out a new candle.

Write a program candles.c to help Alexandra find out how many candles he can burn in total, given two positive integers n and k.

The output should print the total number of candles he can burn.

The diagram below illustrates the case of n = 5 and k = 3. After burning the first 3 candles, Alexandra has enough residual wax to roll out the 6^th candle. After burning this new candle with candles 4 and 5, he has enough residual wax to roll out the 7^th candle. Burning the 7^th candle would not result in enough residual wax to roll out anymore new candle. Therefore, in total he can burn 7 candles.

Check sample run for input and output format; submit your program through CodeCrunch.

2.3 Sample runs

Two sample runs are shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

Enter number of candles and
number of residuals to make a new candle: 5 3
Total candles burnt = 7

Enter number of candles and
number of residuals to make a new candle: 100 7
Total candles burnt = 116

2.4 Important notes

• Write a function count_candles to compute the total number of candles burnt.
  
  
• In writing functions, we would like you to include function prototypes before the main function, and the function definitions after the main function.
  
  
• This is a problem-solving task where we look for neat logic in your program. Using descriptive variable names, and adding appropriate comments will help the reader (and yourself) understand the logic better.

2.5 Skeleton file and sample test data

• candles.c
• candles1.in
• candles1.out

2.6 Reference solution

Note that the following reference solution is just one way of tackling this exercise. Never take it as a model answer.

• candles.c (link accessible after deadline)

2.7 Number of submissions

For this exercise, the number of submissions is 15.

2.8 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that more practice might be needed.

• Devising and writing the algorithm (pseudo-code): 15 minutes
• Checking/tracing the algorithm: 10 minutes
• Translating pseudo-code into code: 5 minutes
• Typing in the code: 10 minutes
• Testing and debugging: 20 minutes
• Total: 60 minutes

3 Exercise 3: Fortune Cookies

3.1 Learning objectives

• Using nested loops
• Simple algorithm design
• Writing functions

3.2 Task statement

Write a program cookies.c to read in a positive integer and add up its digits repeatedly until the sum is a single digit. For example, if the integer is 12345, then adding its digits (1 + 2 + 3 + 4 + 5) yields 15, and adding its digits again (1 + 5) yields 6. Hence the answer is 6.

Using this single digit result, print out the corresponding Fortune Cookie message according to the table below:

Digit	Fortune Cookie message
1	You will have a fine capacity for the enjoyment of life.
2	Now is the time to try something new.
3	Don't let doubt and suspicion bar your progress.
4	Your principles mean more to you than any money or success.
5	Accept the next proposition you hear.
6	A handful of patience is worth more than a bushel of brains.
7	You have an active mind and a keen imagination.
8	You are talented in many ways.
9	Treat everyone as a friend.

Check sample run for input and output format; submit your program through CodeCrunch.

3.3 Sample runs

Three sample runs are shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

Enter a positive integer: 12345
A handful of patience is worth more than a bushel of brains.

Enter a positive integer: 67890
Don't let doubt and suspicion bar your progress.

Enter a positive integer: 11111111
You are talented in many ways.

3.4 Important notes

• Write a function sum_digits to repeatedly sum the digits until it gets to a single digit answer, and return this answer.
  
  
• Write a function print_cookie to print the corresponding cookie message depending on the digit computed.
  
  
• Although the learning objectives indicate "using nested loops", this problem can be done with a single loop. See if you are able to come out with an algorithm using a single loop. It is okay if you cannot; a doubly nested loop is just as acceptable for this exercise. You may discuss this at your discussion session.
  
  
• In writing functions, we would like you to include function prototypes before the main function, and the function definitions after the main function.
  

3.5 Skeleton file and sample test data

• cookies.c
• cookies1.in
• cookies1.out

3.6 Reference solution

Note that the following reference solution is just one way of tackling this exercise. Never take it as a model answer.

• cookies.c (link accessible after deadline)

3.7 Number of submissions

For this exercise, the number of submissions is 10.

3.8 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that more practice might be needed.

• Devising and writing the algorithm (pseudo-code): 20 minutes
• Translating pseudo-code into code: 10 minutes
• Typing in the code: 10 minutes
• Testing and debugging: 30 minutes
• Total: 70 minutes

4 Exercise 4: Book

4.1 Learning objectives

• Using loops and selections
• Simple algorithm design

4.2 Task statement

This exercise will not be graded.

(Past year CS1101 Sit-in lab question; sit-in lab is a mini-PE)

Write a program Book.c that reads in a positive integer (≤ 5), which indicates the number of books to process. For each book, your program will read in its edition (int type, ≤ 5), publish year and initial price (double type). You are to calculate the final price of each book in 2012 and also count the number of books for each edition.

For each year since its publication, a book's price would depreciate by 10%. For example, if a book was published in 2009 at an initial price of $30, then in 2010 it would cost $27, in 2011 it would cost $24.30, and in 2012 it would cost $21.87. Note the following conditions however:

• There is a limit on how much we allow the price to depreciate. If after deprecation, the book's price falls below $20, then the final price of the book in 2012 will be restored to $20.
• On the other hand, if the book's initial price is already below $20, its final price in 2012 will remain the same as its initial price (i.e., no deprecation).

For each book, you are to display its final price in two decimal places. After all the books' information are processed, your program will count the number of books for each edition and print out the information.

Check sample run for input and output format; submit your program through CodeCrunch.

4.3 Sample runs

Two sample runs are shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

Enter number of books: 3
Book 1
	Edition: 1
	Year of publish: 2005
	Initial price: 49.95
	Final price: 23.89
Book 2
	Edition: 1
	Year of publish: 2006
	Initial price: 49.95
	Final price: 26.55
Book 3
	Edition: 1
	Year of publish: 2009
	Initial price: 49.95
	Final price: 36.41
Number of edition 1 books: 3
Number of edition 2 books: 0
Number of edition 3 books: 0
Number of edition 4 books: 0
Number of edition 5 books: 0

Enter number of books: 4
Book 1
	Edition: 2
	Year of publish: 2002
	Initial price: 50
	Final price: 20.00
Book 2
	Edition: 5
	Year of publish: 2007
	Initial price: 500
	Final price: 295.25
Book 3
	Edition: 4
	Year of publish: 2008
	Initial price: 14.10
	Final price: 14.10
Book 4
	Edition: 5
	Year of publish: 2003
	Initial price: 99
	Final price: 38.35
Number of edition 1 books: 0
Number of edition 2 books: 1
Number of edition 3 books: 0
Number of edition 4 books: 1
Number of edition 5 books: 2

4.4 Important notes

• Take note that the skeleton file use '\t' (tabular) for indentation in outputs.
  
  
• You may either write everything inside the main function or adopt modular programming.
  

4.5 Skeleton file and sample test data

• book.c
• book1.in
• book1.out

4.6 Reference solution

Note that the following reference solution is just one way of tackling this exercise. Never take it as a model answer.

• book.c (link accessible after deadline)

4.7 Number of submissions

For this exercise, the number of submissions is 10.

4.8 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that more practice might be needed.

• Devising and writing the algorithm (pseudo-code): 20 minutes
• Translating pseudo-code into code: 10 minutes
• Typing in the code: 20 minutes
• Testing and debugging: 30 minutes
• Total: 80 minutes

5 Deadline

The deadline for submitting all programs is 13 February 2012, Monday, 12nn. Late submission will NOT be accepted.