Unformatted text preview:

“Roman Numerals” Case Study© 1996 M. J. Clancy and M. C. LinnBackgroundValues less than 3999 in the Roman numeral system are written using seven “digits” whose decimal equivalents are given in the table below.(There are additional conventions for writing values larger than 3999, which we will not discuss here.) RomandigitdecimalequivalentM 1000D 500C 100L 50X 10V 5I 1Roman numerals are composed using the following rules.Digit order: Roman digits are written in nonascending order, and digit values are added to produce the represented value, except for prefixes as mentioned below.Number of occurrences: No more than three occurrences of M, C, X, or I may appear consecutively, and no more than one D, L, or V may appear at all.Prefixes: The digits C, X, and I can be used as prefixes, and their value is then subtracted from rather than added to the value being accumulated, as follows:• One C may prefix an M or a D to represent 900 or 400; the prefixed M is written after theother M’s, as in MMMCM. The digits following the M or D represent a value no more than 99.• One X may prefix a C or an L to represent 90 or 40; the prefixed C is written after the other C’s. The digits following the C or L represent avalue no more than 9.• One I may prefix an X or a V to represent 9 or 4. The prefixed digit must appear at the end of the numeral.Some examples:“Roman Numerals”, page 54decimal valueRoman numeralrepresentation1987 MCMLXXXVII1999 MCMXCIX339 CCCXXXIXProblemWrite and test a function decimal-value that, given a word representing a legal Roman numeral, returns the corresponding decimal value. The argument will be a word made up of Roman digits, for example, MCMXCIX. Given this word as argument, your decimal-value function should return 1999. ExercisesAnalysis 1. What is the decimal value of each of the following Roman numeral values: MCMLII, MMCDV, CXCIX?Analysis 2. How is each of the following decimal values written using Roman numerals: 1988, 1000, 1349?Analysis 3. For each of the following, determine its value if it’s a legal Roman numeral, or describe which of the rules listed in the problem statement that it violates: XMICVC, XLIX, IIX, XIXIV.Analysis 4. How many Roman digits can the argument contain? (I.e. what’s the longest Roman numeral whose value is 3999 or less?)PreparationThe reader should have already been introduced to recursion using sentences.“Roman Numerals”, page 55Preliminary planningWhat’s a good first step toward a solution?The function to be written for this problem takes Roman numeral (a word) as its argument and returns a number, the value of the corresponding Roman numeral. How are we to dothis?We first note that recursion will be useful. A word of Roman digits must somehow be turned into a number. The number of Roman digits contained in the word isn’t known, so some method for repeating a computation until the end of the word is appropriate. Such repetition in Scheme is done recursively.Recursion involves one or more base cases and one or more recursive calls, so one way to proceed would be to plunge in directly and look for the base cases and recursion. For example, most recursive word processing functions involvethe empty word as a base case.Another approach would be to try to apply solutions we’ve already devised. We haven’t seen anything quite like a Roman numeral translator, so this approach would involve breaking the solution down into smaller pieces and then recognizing one of the pieces as something we’ve seen before. An advantage of this second approach is that it’s likely to waste less time. Recall that in “Difference Between Dates” we encountered a dead end, then were forced to rethink our solution. A dead end is a possibility with any problem. Looking for existing code that that we can modify for a solution thus is a safer approach to design.What programming patterns may be applicable here?The problem statement says that “digit values are added to produce the represented value, except for prefixes”. Adding digits in a word or numbers in a sentence can be done relatively easily:(define (element-sum sent-or-num)(if (empty? sent-or-num) 0(+ (first sent-or-num)(element-sum (first sent-or-num)) ) ) )This is an instance of an accumulating recursion that combines elements of a word or sentence. Similar code that accumulates values of Roman digits will be useful here.“Roman Numerals”, page 56Another component of the solution will be translation. We can’t work with Roman digits directly, at least in a convenient way. In “Difference Between Dates”, we translated dates to numbers in order to subtract them more easily.Here, it makes sense to do something similar: translate Roman digits to numbers in order to add them more easily. What kind of translation provides a good model for translating Roman digits?In “Difference Between Dates”, we translated dates to numbers and month names to numbers.The month-to-number translation seems more relevant here since month names and Roman digits are both words; here it is.(define (month-number month)(cond((equal? month 'january) 1)((equal? month 'february) 2)((equal? month 'march) 3)((equal? month 'april) 4)((equal? month 'may) 5)((equal? month 'june) 6)((equal? month 'july) 7)((equal? month 'august) 8)((equal? month 'september) 9)((equal? month 'october) 10)((equal? month 'november) 11)((equal? month 'december) 12) ) )The code to translate a Roman digit to its corre-sponding decimal value is similar:(define (decimal-digit-value roman-digit)(cond((equal roman-digit 'm) 1000)((equal roman-digit 'd) 500)((equal roman-digit 'c) 100)((equal roman-digit 'l) 50)((equal roman-digit 'x) 10)((equal roman-digit 'v) 5)((equal roman-digit 'i) 1) ) )Ordinarily one might add a cond case to return a value for the default case—here, something that’s not a legal Roman digit—but the problem statement has specified that only legal Roman numerals need be considered.How is the entire sequence of Roman digits translated?Extending the translation to an entire Roman numeral involves including it in code that returnsthe result of applying a function to every elementof a word and returning a sentence* : (define (funct-applied-to-all W)(if (empty? W) '( )“Roman Numerals”, page 57(se(funct (first W))(funct-applied-to-all (bf W)) ) ) )Applying this template produces a function that translates all the Roman digits in a word to their decimal digit values and puts them into


View Full Document

Berkeley COMPSCI 3 - Roman Numerals

Download Roman Numerals
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Roman Numerals and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Roman Numerals 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?