UMBC CMSC 201
CSEE | 201 | 201 F'07 | lectures | news | help
Out: Monday 11/12/07
The design document for this project, design4.txt, is due: Before Midnight, Sunday 11/18/07
The purpose of this assignment is to give you practice with recursion, using command line arguments, changing numbers to strings, writing error messages to stderr and to do some more file handling and dynamic memory allocation. As always, you should continue to practice using top-down design and good implementation techniques.
A palindromic number is an integer whose digits are the same whether read forward or backward. Its first digit and last digit are the same, and if long enough, its second and next-to-last digits are the same, etc. Here are some examples of palindromic numbers: 121, 93439, 6, 22, 887020788
It is interesting that if an integer is not a palindromic number, if its
digits are reversed and then that new number is added to the original number,
a palindromic number is often produced,
i.e. 123 + 321 = 444
If that sum is not a palindromic number reversing its digits and adding that to the sum will often produce a palindromic number,
i.e. 964 + 469 = 1433 1433 + 3341 = 4774
Although most numbers produce a palindromic number with just one or two reverse and add iterations, some take longer. The number 89 takes 24 iterations of the reverse and add algorithm before a palindromic number is produced.
Some numbers are being tested that appear to never form a palindromic number regardless of the number of reverse and add iterations that have been performed. The definition of a lychrel (pronounced la-shrel) is a number that has been proven to never form a palindrome even after repeated reversal and addition. Wade VanLandingham is credited for the term lychrel.
Although proof has been found that some numbers in other bases are lychrels, proof has not been found that any number in base 10 is a lychrel. So numbers in base 10 that appear to be lychrels can technically only be called candidate lychrels. Several candidate lychrels are known. The first candidate lychrel is 196. It hasn't yet produced a palindrome even after over a million iterations of reverse and add. The first million non-palindromic digits were discovered by John Walker.
If you're interested, here's more information about lychrels.
Since we don't want your project to run infinitely, you'll need to check to see if the random number generated is a candidate lychrel first. If it is, don't attempt to do the reversal and adds, just print a message and get another random number to test. See the sample output.
If the number is not a candidate lychrel, you should check to see if it is a palindrome. If it's not a palindrome, perform as many reverse and adds as necessary in a recursive function until a palindrome is formed, printing the numbers used and the sum at each step. After the palindrome has been formed you must state the number of reverse and adds that were necessary.
Your program is to use command line arguments to accept a seed for the random number generator, the number of random numbers to check, and the name of the data file containing a list of candidate lychrels.
Since one of the objectives of this project is to give you practice working with characters, in this case the characters that represent digits, you will be working not only with numbers, but also digit characters that are stored in strings.
Here is a link to the sample output of this program.
Please note that the sample output only shows what is expected from your program if the user is actually entering everything as instructed. This is not a test of the program at all, but just a sample for your clarification.
Since we are all using the same random number generator, for the same exact command line arguments, your output should match mine precisely.
To submit your program, type the following command at the Unix prompt
submit cs201 Proj4 followed by all of your .c and .h files necessary for
DO NOT submit the stringtoll.o and stringtoll.h files that I provided.
We'll be using my copies of those files during grading.
To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.
submitls cs201 Proj4
Tuesday, 13-Nov-2007 16:25:57 EST