Lab 4 Identifying and Exploiting Repeating Patterns Introduction ============ In lab 3, we explored how to make decisions. Decision making allows us to write much more interesting programs because we have programs with multiple paths of execution. This week we will be looking at loops and patterns. Looping is the control structure which allows us to write programs which are far more useful. Unfortunately, loop behavior can be a bit difficult to comprehend. In this lab, we will explore using loops to create repeating patterns. In both the guided and self labs, we will explore problems which have non-obvious solutions, and they will seem a little complicated. The key to solving these problems will be in spotting the underlying pattern in them. Part I (Guided) - Fun With Etruscan Sheep ========================================= In the land of Tuscany, before the birth of Romulus and Remus, there lived two shepherds named Reg and Stan. One morning, Reg noticed that something was amiss. "Stan, does it seem like we have fewer sheep today than we did yesterday?", he asked. Stan replied, "I don't know. Tell you what. Let's take this bone and cut a notch into it for each sheep, then we can recount it in the morning and see if there may be a wolf in our midst." That day, they set out doing just that. They took a lamb bone and carved notches: |||| The next day, they repeated the same task: ||| "Aha!", exclaimed Reg, "We are down by one. Let's stay up tonight and see what's happening to the sheep." That night they found a wolf prowling their fields. They killed the wolf by pelting it with rocks, thus preserving the number of their flock. Now, Reg and Stan became the most successful shepherds in all of Tuscany, and they had also made one of the first steps for building a mechanical computer. Their success, however, turned to dismay after a particularly successful lambing season. Reg returned with the following notches: ||||||||||||||||||||| Stan took one look and said "I just can't handle that many notches! It's hard to read at a glance. We'll spend all our time counting notches!" Reg thought it over and then said, "What if we change every 5th mark?" He then carved a new bone: ||||/\||||/\||||/\||||/\| Stan took one look and said, "Ah! So every fifth mark is /\. Now we can count by fives. What if we extend it further, and made every tenth mark be overlapping 5's like this." Stan took the bone and carved: ||||/\||||X||||/\||||X| Reg took one look and liked what he saw. "Now we can see at a glance, that we have 2 10's and 1 left over notch. That's bloody brilliant!" (All 7th century BC Etruscans used British slang. Just roll with it!). They then decided to expand this just a little further. They made a symbol for every 5th X and for every 2nd 50. Thus the Etruscan counting bone system was: Number Symbol ------ ------ 1 | 5 /\ 10 X /|\ 50 | 100 >|< They didn't go above 100, because that was more sheep than they had ever seen in their lives. It's easy to see that this is a method that can be used for counting large numbers efficiently. Thus the Etruscan counting bone became one of the world's first manual computers! In time, Reg and Stan decided they wanted to chart their business over long periods of time. Now that they had over 50 sheep, they were going through a lot of bones. One day as Stan was recording a year's worth of sheep he started to get tired. He had carved: /|\ ||||/\||||X||||/\||||X||||/\||||X||||/\||||/\||||X||||/\||||| As Stan was massaging his swollen wrist it hit him. "Oy! These notches are brilliant for adding, but they are rubbish for recording data." After a little thinking he said, "I have it! We can just take everything prior to the largest symbol as read, so I could just carve: /|\ | "and we'll know that those exhausting marks came before it. I could also just do groups of those, for instance, I could do XX for 20 sheep." Reg liked the idea, but there was just one small problem. "What about when you have one less than the big one?" "Oh yeah..." Almost at the same instant, a bolt of genius hit them. "What if we put the notch just before the big group. Like |X would mean 9 and we'd just understand that the 3 others are there. You know, they'd have to build up to it anyway." So they practiced and found that this worked well. |X for 9, |/\ for 4... and all was well. Then came the rise of Populous Romanus. They liked Reg and Stan's counting method. They especially liked how it work for both counting and recording, but they thought the symbols looked like something that a shepherd would come up with. So, they decided to use letters. | became I, /\ became V, and so on. This made it easy for Roman stone carvers to carve numbers into Roman walls. They also extended the system a bit, so the total table of symbols became: Decimal Symbol ------- ------ 1 I 5 V 10 X 50 L 100 C 500 D 1000 M They also decided to call these things "Roman Numerals." Our Etruscan friends were none too pleased by this. "Bloody Romans!" they muttered, "What have they ever done for us?" Problem ------- We want to create a program which will convert any decimal number to Roman Numerals. At first glance, this seems like a monumental task. Up to 10 is easy, but I want to be able to do the following: 1024 - MXXIV 3900 - MMMCM 249 - CCXLIX A sample run of the program which you are going to write is: -- Begin Sample Run -- Enter Number: 597 DXCVII -- End Sample Run -- Developing a Solution --------------------- In order to solve this problem, we need to identify a repeating pattern. Using the standard set of Roman numerals would allow us to count to 3,999 before the pattern will break. A later addition used the drawing of bars over the letters to multiply them by 1000. So _ M Would become 1,000,000. This is a bit too much for us to handle at the present state of our knowledge of C++, however, so we are going to make 3,999 our maximum number. You could solve every single Roman numeral and then have a 4,000 element switch statement, but that would be very tiring. Instead, we want to work smarter, not harder! Take a look at the story above, especially the tables and the notches. Can you see a pattern to what they are doing? Ponder it a bit before you read the next paragraph. They are using an ordinal counting system, where the total value of the numbers accumulate from left to right. The largest amount of the values is always at the left. For instance, X would be preceded by 9 marks prior to the X. That's how they came up with the short form |X (or IX for the Romans). So if we want to convert numbers to Roman numerals, we are going to start by subtracting out the larger parts and record their symbols. For instance, let's say we look at 2013. We can see that the highest part of the number is in the thousands. So we record as many thousands as we can: MM This leaves us with 13. 13 is less than 500, 100, and 50. Now we record as many 10's as we can: MMX this leaves us with 3. There can be no 5's, but there can be ones. We record the remaining 1's. MMXIII So pseudocode at the first attempt at this would work as follows: For each letter in {M, D, C, L, X, V, I} if num >= value of letter print num / value of that letter num = num % value (the remainder) end if end for There is, of course one problem with this. Can you see what it is? Try a hand trace of the above for the number 40. You'll end up with "XXXX" which is invalid. So we have to think about this some more. We know that the base symbols are {M, D, C, L, X, V, and I}. Just like Reg and Stan, we are faced with the problem of boundaries between these symbols. So we could augment the above algorithm with these boundaries: For each letter in {M, D, CD, C, XC, L, XL, X, IX, V, IV, I} if num >= value of letter print num / value of that letter num = num % value (the remainder) end if end for This algorithm will work. But how can we implement it? After all, how will the computer know the value of the numbers? In order to implement this, we are going to use an iterative design and implementation process. This is a technique which allows us to go back and forth between pseudocode and C++ code in an effort to develop the program over time. The first detail we will look at is the issue of the values of these separations. Observe the following table of symbols (including the boundaries): Decimal Symbol ------- ------ 1000 M 900 CM 500 D 400 CD 100 C 90 XC 50 L 40 XL 10 X 9 IX 5 V 4 IV 1 I Now, if we look closely at this, we can see an underlying pattern. Notice how we keep repeating 9,5,4,1? We do this once at each multiple of 10. That is, we have 900, 500, 400, 100; and we also have 90, 50, 40, 10. So we could iterate over these values by keeping track of where we are in the sequence. We will need a counter for each of the positions. There are 4 states in the sequence: for counter=3 to 0 case 3 value = 9 case 2 value = 5 case 1 value = 4 case 0 value = 1 print value end for This will, of course, handle our sequence 9,5,4,1 but not the full counting that we want. The full counting needs to loop through each decade, starting at 1000 and decreasing to 1. We will stay in each decade for a count of 4. We can combine all this into one large loop by observing that we decrease the decade only once the counter reaches 0. The pseudocode for all this is: counter=0 decade=1000 while decade > 0 switch(counter) case 3 value = 9 * decade case 2 value = 5 * decade case 1 value = 4 * decade case 0 value = decade decade = decade / 10 counter = 4 end switch counter = counter - 1 display the value end while As you can see, we are getting close to C++ code, so let's go ahead and write some C++. Create a file called "roman.cpp" and enter the following code: -- Begin roman.cpp -- /* * File: roman.cpp * Purpose: A little program to compute the roman numeral sequence. */ #include using namespace std; int main(void) { int counter=0; int decade=1000; int val=1000; // run through all decades while(decade) { //update the value switch(counter) { case 3: val = 9 * decade; break; case 2: val = 5 * decade; break; case 1: val = 4 * decade; break; case 0: val = decade; decade /= 10; //new decade! counter=4; break; } //update the counter counter --; //output the value cout << val << endl; } return 0; } -- End roman.cpp -- Run this code and verify that it prints: 1000 900 500 400 100 90 50 40 10 9 5 4 1 Now we can iterate over the correct values, we want to add to it iteration over the correct symbols. Of course, this is pretty simple in that we can just add in the following switch statement. Instead of //output the value cout << val << endl; What we really want is: //output the correct symbol switch(val) { case 1000: cout << "M" << endl; break; case 900: cout << "CM" << endl; break; case 500: cout << "D" << endl; break; case 400: cout << "CD" << endl; break; case 100: cout << "C" << endl; break; case 90: cout << "XC" << endl; break; case 50: cout << "L" << endl; break; case 40: cout << "XL" << endl; break; case 10: cout << "X" << endl; break; case 9: cout << "IX" << endl; break; case 5: cout << "V" << endl; break; case 4: cout << "IV" << endl; break; case 1: cout << "I" << endl; break; } Make that change and run the program. Verify that it runs through the correct symbols. Now we can implement the technique for conversion we discussed above. First, we need to make new variables for the number we want to convert, and also counters for the number of each symbol. Let's create the variables first. Add the following to the appropriate place in code: int i, n, num; Before we enter the loop, we want to get the number we are going to convert. Add the following before the loop: //get the number cout << "Number: "; cin >> num; Now we want to surround the printing of symbols in the following around the switch case which prints out the letters n=num / val; for(i=0; i