This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
haas:spring2015:cprog:projects:afn0 [2015/02/23 22:15] – created wedge | haas:spring2015:cprog:projects:afn0 [2015/03/20 20:45] (current) – [Prerequisites/Corequisites] wedge | ||
---|---|---|---|
Line 15: | Line 15: | ||
* can perform this trick in your head/by hand (if you can't do it on your own, you have no business trying to tell the computer how to do it) | * can perform this trick in your head/by hand (if you can't do it on your own, you have no business trying to tell the computer how to do it) | ||
- | * understand the pattern/ | + | * understand the pattern/ |
* ability to deploy loops to simplify your process | * ability to deploy loops to simplify your process | ||
* ability to use arrays to facilitate the storage of your processed values | * ability to use arrays to facilitate the storage of your processed values | ||
Line 61: | Line 61: | ||
The answer is: **071426043986547** | The answer is: **071426043986547** | ||
- | ====loops==== | ||
- | A loop is basically instructing the computer to repeat a section, or block, or code a given amount of times (it can be based on a fixed value-- repeat this 4 times, or be based on a conditional value-- keep repeating as long as (or while) this value is not 4). | ||
- | Loops enable us to simplify our code-- allowing us to write a one-size-fits all algorithm (provided the algorithm itself | + | =====Task===== |
+ | The task at hand can benefit from loop and array assistance. | ||
- | Loops can be initially difficult to comprehend because unlike other programmatic actions, they are not single-state | + | For instance, taking the number input and processing it so each digit occupies its own array element would facilate your efforts |
- | With that said, it is important to be able to focus on the process of the individual steps being taken. What is involved in taking a step? What constitutes a basic unit of stairway traversal? If that unit can be easily repeated for the next and the next (and in fact, the rest of the) steps, we've described | + | =====Functions===== |
+ | As indicated, this task shares many attributes with the **mbe1** project; | ||
- | In C and C-derived languages, we typically have 3 loops: | + | Specifically, we will look at modularizing aspects of our solution, using functions, to make for a cleaner, more organized codebase. |
- | | + | We've been using functions all along (everytime you use **fprintf()** or **fscanf()**, for instance), but the value is not just in using pre-existing ones, but also in making our own to use. |
- | | + | |
- | * do-while loop (bottom-driven conditional loop) - similar to the while loop, only we do the check for loop termination at the bottom of the loop, meaning it runs 1 or more times (a do-while loop is guaranteed | + | |
- | ===for loops=== | + | ====Function prototype==== |
- | A for loop is the most syntactically unique of the loops, so care must be taken to use the proper syntax. | + | Like variables, functions need to be declared. |
- | With any loop, we need (at least one) looping variable, which the loop will use to analyze whether or not we've met our looping destination, or to perform another iteration. | + | We can declare them at various scopes (file/ |
- | A for loop typically also has a defined starting point, | + | If a particular function is only to be used by a specific function, and no others, you can opt to declare it local scope (ie within the function that will be calling it). |
- | Here' | + | A function is basically |
- | <code c> | + | Like a program, it takes input, does processing, and provides output. |
- | int i = 0; | + | |
- | for (i = 0; i < 8; i++) | + | Unlike a program, its input may not come from the keyboard, but instead from particular variables, and may not send output to the screen, but instead channel output in a way that it can be stored into a variable. |
- | { | + | |
- | fprintf(stdout, "loop #%d ... %d\n", (i+1), (i*i)); | + | |
- | } | + | |
- | </ | + | |
- | The output of this code, with the help of our loop should | + | This distinctions aside, a function can in many ways be viewed as a micro- or sub-program/ |
- | < | + | Keeping everything in ONE file, ONE big function in that one file, is rather monolithic. In time, with sufficiently large programs, such an arrangement would become a tad unwieldy. So functions help to keep our focus short yet attentive. |
- | loop #1 ... 0 | + | |
- | loop #2 ... 1 | + | |
- | loop #3 ... 4 | + | |
- | loop #4 ... 9 | + | |
- | loop #5 ... 16 | + | |
- | loop #6 ... 25 | + | |
- | loop #7 ... 36 | + | |
- | loop #8 ... 49 | + | |
- | </ | + | |
- | Note how we can use our looping variable | + | To create a function |
- | And again, we shouldn' | + | A function, in many ways, is like a programmable variable |
- | The loop exits once **i** reaches | + | As such, it has a return |
- | The stepping | + | We see this with main()... here are two variations of a **main()** function declaration |
- | **i++** is a shortcut we can use in C; the longhand (and likely more familiar) equivalent is: **i = i + 1** | + | ===Parameterless function=== |
- | + | ||
- | ===while loops=== | + | |
- | A while loop isn't as specific about starting and stepping values, really only caring about what condition needs to be met in order to exit the loop (keep looping while this condition is true). | + | |
- | + | ||
- | In actuality, anything we use a for loop for can be expressed as a while loop-- we merely have to ensure we provide the necessary loop variables and progressions within the loop. | + | |
- | + | ||
- | That same loop above, expressed as a while loop, could look like: | + | |
<code c> | <code c> | ||
- | int i = 0; | + | int main() |
- | + | ||
- | while (i < 8) | + | |
- | { | + | |
- | fprintf(stdout, | + | |
- | i = i + 1; // I could have used " | + | |
- | } | + | |
</ | </ | ||
- | The output of this code should be identical, even though | + | In this example, we see the declaration of main() where it has a return value of **int**, meaning, upon completion, main() will return a value corresponding with an int data type (also in main()' |
- | While loops, like for loops, will run 0 or more times; if the conditions enabling the loop to occur are not initially met, they will not run... if met, they will continue | + | main(), in this case, takes no parameters (just an empty set of parenthesis)... due to this, we refer to this function as a parameterless function. A function without parameters. Without input. |
- | It is possible to introduce | + | Now: this is technically |
- | Another common **logical error** that loops will allow us to encounter will be the "off by one" error-- where the conditions we pose to the loop are incorrect, and the loop runs one more or one less time than we had planned. Again, proper debugging | + | Additionally, with or without parameters, |
- | ===do-while loops=== | + | ===Parametered function=== |
- | The third commonly recognized looping structure in C, the do-while loop is identical to the while (and therefore the for) loop, only it differs in where it checks the looping condition: where **for** and **while** are " | + | |
- | + | ||
- | The placement of this test determines the minimal number of times a loop can run. | + | |
- | + | ||
- | In the case of the for/while loops, because the test is at the top- if the looping conditions are not met, the loop may not run at all. It is for this reason why these loops can run "0 or more times" | + | |
- | + | ||
- | For the do-while loop, because the test occurs at the bottom, the body of the loop (one full iteration) is run before the test is encountered. So even if the conditions for looping are not met, a do-while will run "1 or more times" | + | |
- | + | ||
- | That may seem like a minor, and possibly annoying, difference, but in nuanced algorithm design, such distinctions can drastically change the layout of your code, potentially being the difference between beautifully elegant-looking solutions and slightly more hackish. They can BOTH be used to solve the same problems, it is merely the nature of how we choose express the solution that should make one more preferable over the other in any given moment. | + | |
- | + | ||
- | I encourage you to intentionally try your hand at converting your loops between for/ | + | |
- | + | ||
- | So, expressing that same program in the form of a do-while loop (note the changes from the while): | + | |
<code c> | <code c> | ||
- | int i = 0; | + | int main(int argc, char **argv) |
- | + | ||
- | do { | + | |
- | fprintf(stdout, "loop #%d ... %d\n", (i+1), (i*i)); | + | |
- | i = i + 1; // again, we could just as easily use " | + | |
- | } while(i < 8); | + | |
</ | </ | ||
- | In this case, the 0 or more vs. 1 or more minimal iterations wasn't important; the difference is purely syntactical. | + | In this case, our **main()** function actually takes parameters- two, in fact: |
- | With the do-while loop, we start the loop with a **do** statement (feel free to put the opening brace on the next line as we have all along-- I'm also demonstrating another style of brace placement). | + | |
+ | | ||
- | Also, the do-while is the only one of our loops which NEEDS a terminating semi-colon (**;**).. please take note of this. | + | This function takes two parameters, two pieces of input, available to us in the form of variables, by those names, of those types. We make use of them as we need to in accomplishing the program at hand. |
- | ====arrays==== | + | So, when we wish to create functions |
- | The other important component | + | |
- | An array is basically just a collection of variables. Where before we'd declare a separate variable for each number we'd wish to store, an array lets us have but one variable name, but multiple storage location (like PO Boxes-- they' | + | * the return type |
+ | * the function name | ||
+ | * 0 or more parameters, identifying their order and type | ||
- | An array is what is known as a **homogeneous** composite data type. It technically is a modifier | + | For example, let us make a sum() function. Here would be a likely prototype (we'd place it above main()): |
- | **homogeneous** means all of the same, indicating it can ONLY contain variables of the exact same type (such as only **int**egers, only **short | + | < |
- | + | int sum(int *, int); | |
- | An array has a few other requirements: | + | |
- | + | ||
- | * its size, once declared, remains constant (you cannot say you'd like a 4 element array and then later ask to double or halve it--- there is no such thing as " | + | |
- | * arrays are located by their name (just as any variable is), along with an address/ | + | |
- | * arrays start at an offset of 0. | + | |
- | * arrays can be expressed as a pointer (I tend to treat them as pointers), and there' | + | |
- | * C cannot perform global operations on arrays-- you must transact on an array one element at a time (this is the case with all languages, although some will cheat and do the work behind-the-scenes, | + | |
- | + | ||
- | ===Declaring a 4 element integer array=== | + | |
- | Let us see our array in action: | + | |
- | + | ||
- | <code c> | + | |
- | int numbers[4]; | + | |
</ | </ | ||
- | This code will declare | + | A function prototype (vs. its definition) |
- | To access the first box, we access the **0** offset; the second box is right next to the first, at offset **1** (it is one int away from the first one). Similar with the third and fourth. | + | In our case, our sum() function has the following: |
- | To place a **17** in the first (position **0**) element of our **numbers** array, we'd say the following: | + | * a return type of **int** (particular variable name doesn' |
+ | | ||
+ | | ||
- | <code c> | + | Our sum() function will take an integer array (denoted by the int pointer above), and a size (the second, regular int). |
- | numbers[0] = 17; | + | |
- | </ | + | |
- | To place a **36** in the third (position **2**) element of our **numbers** array, we'd say: | + | Now, parameter order very much matters. In our case, an " |
- | <code c> | + | ====Function definition==== |
- | numbers[2] | + | While a function prototype is technically optional (you can put the definition in place of the prototype-- we just often use prototypes to further allow organization), |
- | </code> | + | |
- | ===Using variables as our array index position=== | + | Our sum() function |
- | Because the array index is a number, and things like **int**s are numbers, we can also specify the array location via a variable. To wit, we will assign a 52 to the fourth array element, but do so via an **index** variable we set up: | + | |
<code c> | <code c> | ||
- | int index = 3; | + | int sum(int |
- | numbers[index] = 52; | + | |
- | </ | + | |
- | + | ||
- | Because | + | |
- | + | ||
- | ===Using variables for array contents=== | + | |
- | As well, because we are putting values in our array elements that conform to particular data types, we can use variables there as well (in this case, put a 96 into the second array element-- using variables to store both the index and the value): | + | |
- | + | ||
- | <code c> | + | |
- | int value = 96; | + | |
- | int index = 1; | + | |
- | + | ||
- | numbers[index] = value; | + | |
- | </ | + | |
- | + | ||
- | Hopefully these examples have proved useful with respect to basic concepts and syntactic usage of arrays. | + | |
- | + | ||
- | We now explore the productive collaboration of arrays and loops: | + | |
- | + | ||
- | ====Using loops and arrays together for universal harmony==== | + | |
- | + | ||
- | To really make the most out of arrays in scaling our algorithms, using them in conjunction with loops gives us the most bang for our buck. The advantage of arrays+loops is that with the ONE consistent variable name, representing many NUMERICALLY-identifiable elements, we can work with ranges of data sets without the need to make tons of exceptions for each possible use case (worst case we just make an array of the maximum expected | + | |
- | + | ||
- | ===42 everywhere=== | + | |
- | + | ||
- | To illustrate, here we will declare an 11 element array (called **data**), and fill each element with the value 42 using a for loop: | + | |
- | + | ||
- | <code c> | + | |
- | int data[11], position = 0; | + | |
- | + | ||
- | for(position = 0; position < 11; position=position+1) // see, using long form, could have done " | + | |
{ | { | ||
- | | + | |
+ | int i = 0; | ||
+ | |||
+ | for (i = 0; i < size; i++) | ||
+ | result = result + array[i]; | ||
+ | |||
+ | return(result); | ||
} | } | ||
</ | </ | ||
- | ===Display array contents=== | + | ====function calling==== |
- | What if we wanted to print the contents of the array? | + | Once we've declared (prototyped) and defined our function, now all we have to do is use it! When you make use of a function, we refer to it as // |
- | Important considerations: | + | Here would be an example of calling |
- | * again, with C, being true to how the computer actually works, we can only access the array one element at a time | + | |
- | | + | |
- | | + | |
- | * each element is located one after the other-- 0 is followed by 1 is followed by 2 etc. | + | |
- | + | ||
- | ... therefore, we have all the ingredients for a **for** loop: | + | |
<code c> | <code c> | ||
- | for (position = 0; position < 11; position++) | + | int scores[4]; |
- | { | + | int tally = 0; |
- | fprintf(stdout, | + | |
- | } | + | |
- | fprintf(stdout, | + | |
- | </ | + | |
- | This should result in the following program output: | + | scores[0] = 88; |
+ | scores[1] = 47; | ||
+ | scores[2] = 96; | ||
+ | scores[3] = 73; | ||
- | < | + | tally = sum(scores, 4); |
- | 42 42 42 42 42 42 42 42 42 42 42 | + | |
- | </ | + | |
- | + | ||
- | ===Backwards? | + | |
- | What if we wanted to display the contents of our array in reverse (from position 10 to position 9, to 8, down to 0)? | + | |
- | + | ||
- | We'd still want to use a loop, but look at how we structure it: | + | |
- | + | ||
- | <code c> | + | |
- | for (position = 10; position >= 0; position--) | + | |
- | { | + | |
- | fprintf(stdout, | + | |
- | } | + | |
- | fprintf(stdout, " | + | |
</ | </ | ||
- | Notice how the loop-terminating relational statements differ (comparing the two-- for forward and backward, does it make sense?), and also how we progress between individual elements (in one we are incrementing, | + | Note, that it is rather important |
- | + | ||
- | That should make sense before you try to proceed. | + | |
- | + | ||
- | ===Thinking with arrays=== | + | |
- | Using arrays in your algorithms represents a potential barrier you have to overcome. Up until this point, we've been getting used to labelling all our variables with unique, individual names. | + | |
- | + | ||
- | Now, with arrays, we have one common name, distinguishable by its element offset. That has been known to cause some conceptual problems due to the mildly abstract nature it creates. It would certainly not hurt to draw some pictures and manually work through some examples, step-by-step... it may be confusing at first, but the more you play with it, ask questions, play, read, etc., the sooner things will start to click. | + | |
- | + | ||
- | As some of you have started to realize with **mbe0**, the actual core work of the project wasn't actually | + | |
- | + | ||
- | + | ||
- | ====Multiplying a number (of varying digits) by 11==== | + | |
- | In **mbe0**, we specifically looked at 3 usage cases for our mental math problem: 1-, 2-, and 3-digit number. I limited it to those because, lacking arrays and loops for that project, | + | |
- | + | ||
- | Now that we have those down, we can now apply arrays and loops to optimize and enhance a solution, and to allow it to scale to a wider range of possibilities (why limit ourselves to just 1-, 2-, and 3-digit values? Once we see the pattern, we can apply this to 4-, 5-, 6-digit numbers and beyond). | + | |
- | + | ||
- | ===3-digits (review)=== | + | |
- | Again, to review, let's look at a 3-digit example. 123 x 11: | + | |
- | + | ||
- | < | + | |
- | 123 x 11 = 1 (1 + 2) (2 + 3) 3 | + | |
- | = (1 + 0) (3 + 0) 5 | + | |
- | = 1 | + | |
- | = 1353 | + | |
- | </ | + | |
- | + | ||
- | And digit-based additions that generate a carry are similarly propagated. | + | |
- | + | ||
- | 567 x 11: | + | |
- | + | ||
- | < | + | |
- | 567 x 11 = 5 (5 + 6) (6 + 7) 7 | + | |
- | = (5)+1 | + | |
- | = 6 | + | |
- | = 6237 | + | |
- | </ | + | |
- | + | ||
- | When doing this, we need to evaluate the number from right to left (just as we would do it if we were to compute it purely mathematically by hand): | + | |
- | + | ||
- | * We know the last digit (1s place) | + | |
- | * The second digit (10s place) is the sum of 6 and 7 (6+7) which is 13 (sum of 3, carry of 1), so: 3 | + | |
- | * The third digit (100s place) is the sum of 5 and 6 plus any carry from the 10s place (which is 1), so (5+6+1) which is 12 (sum of 2, carry of 1), so: 2 | + | |
- | * The fourth digit (1000s place) is the original first value (5 of the 567) plus any carry from the 100s place (which there is, a 1), so (5+1) which yields a sum of 6, carry of 0. | + | |
- | + | ||
- | A dual benefit of this project is that in addition to extending your programming experience / understanding of C, you could develop this as a mental ability (that is where it originated), | + | |
- | + | ||
- | ===4-digits=== | + | |
- | Now let us process a 4-digit example (look for similarities to the 3-digit process, specifically how this is merely an expansion, or an additional step-- due to the additional digit): | + | |
- | + | ||
- | 4567 x 11: | + | |
- | + | ||
- | < | + | |
- | 4567 x 11 = 4 (4 + 5) (5 + 6) (6 + 7) 7 | + | |
- | = (4)+1 | + | |
- | = 5 | + | |
- | = 50237 | + | |
- | </ | + | |
- | + | ||
- | Remember, we are processing this from right to left (so that the carry values can properly propagate). While there is no initial carry coming in, we'll add one anyway (0), so we see 13+0 (which is simply 13)... but because we're interested in place values, this is actually | + | |
- | + | ||
- | Can you see how "the same" this process for 4-digit numbers is when comparing to the process for 3-digit numbers? And how the same comparison can be made for 2-digit, and 5-digit, 6-digit, etc.? Please take some time, working through some examples (by hand) to identify and notice the pattern, or essence, of this process. You need to see how it doesn' | + | |
- | That " | ||
- | (Also, the potential exception here would possibly be 1-digit values... if you cannot easily find a way to make 1-digit numbers work with greater-than-1-digit numbers, that's where an if-statement would come into play-- if 1-digit, do this specific process, else do the regular process). I'm not saying one universal solution isn't possible, but at this stage of your structured programming development, | ||
=====Program===== | =====Program===== | ||
- | It is your task to write an optimized version of your multiply by eleven | + | It is your task to write a program that obtains a long integer value from the user, and processes that single value into separate array elements |
Your program should: | Your program should: | ||
* obtain its input from STDIN. | * obtain its input from STDIN. | ||
- | * input should be in the form of a single integer value | + | * input should be in the form of a single |
* determine the number of digits of the inputted value (store this in a variable) | * determine the number of digits of the inputted value (store this in a variable) | ||
- | * perform the correct algorithm against | + | |
- | * propagate any carries | + | * you may assume a maximum array size of the maximum number of digits you're theoretically able to input that can be stored in a 64-bit value. |
- | * use an array (**digit**) to store individual digits from the number input | + | |
- | * use another | + | * display the problem being solved, along with the answer |
- | * hint: you will want to make the **result** array one element larger. Why is this? | + | * use functions to modularize your code: |
- | * Display output showing aspects of the process | + | * have an **longint2array()** function that takes the long int, and returns an array (the function itself handles the processing |
- | | + | * have a **printarray()** function, whose responsibility it is to display the indicated |
+ | * have a **allfromnine()** function that takes the source array, does the processing, and returns ther result | ||
- | =====Execution===== | + | I might suggest the following function prototypes: |
- | Several operating behaviors are shown as examples. | + | |
- | An eight digit value: | + | <code c> |
+ | unsigned char *longint2array(unsigned long int); | ||
+ | void printarray(unsigned char *, unsigned char); | ||
+ | unsigned char *allfromnine(unsigned char *); | ||
+ | </ | ||
- | < | + | Some questions to contemplate: |
- | lab46:~/ | + | |
- | Enter value: 31415926 | + | |
- | Digits detected: 8 | + | |
- | Obtaining unique digits, storing in array... | + | * Why an array of unsigned chars when we're starting with a long (long) int? |
- | digit[0] = 6 | + | * Why is that the "best fit" size-wise? |
- | digit[1] = 2 | + | * Why will that not result in lost data? |
- | digit[2] = 9 | + | * Why unsigned? |
- | digit[3] = 5 | + | * What impact will that have on our input value' |
- | digit[4] = 1 | + | * Why represent the size of the usable array as an unsigned char? |
- | digit[5] = 4 | + | * Why is this the "best fit" size-wise? |
- | digit[6] | + | =====Execution===== |
- | digit[7] | + | An example |
- | + | ||
- | Applying process... | + | |
- | result[0] | + | |
- | result[1] | + | |
- | result[2] | + | |
- | result[3] | + | |
- | result[4] | + | |
- | result[5] | + | |
- | result[6] | + | |
- | result[7] | + | |
- | result[8] = 3 + 0 + 0 (sum of 3, carry out of 0) | + | |
- | + | ||
- | Displaying result... | + | |
- | 31415926 x 11 = 345575186 | + | |
- | lab46: | + | |
- | </ | + | |
- | + | ||
- | Next, a four digit value: | + | |
<cli> | <cli> | ||
- | lab46: | + | lab46: |
- | Enter value: | + | Enter value: |
- | Digits detected: | + | Digits detected: |
- | Obtaining unique digits, storing in array... | + | |
- | digit[0] = 4 | + | - 31415926535897 |
- | digit[1] = 0 | + | --------------- |
- | digit[2] = 1 | + | |
- | digit[3] = 7 | + | |
- | Applying process... | + | lab46: |
- | result[0] = 4 + 0 + 0 (sum of 4, carry out of 0) | + | |
- | result[1] = 0 + 4 + 0 (sum of 4, carry out of 0) | + | |
- | result[2] = 1 + 0 + 0 (sum of 1, carry out of 0) | + | |
- | result[3] = 7 + 1 + 0 (sum of 8, carry out of 0) | + | |
- | result[4] = 7 + 0 + 0 (sum of 7, carry out of 0) | + | |
- | + | ||
- | Displaying result... | + | |
- | 7104 x 11 = 78144 | + | |
- | lab46: | + | |
</ | </ | ||
- | |||
- | Finally, a five digit value: | ||
- | |||
- | <cli> | ||
- | lab46: | ||
- | Enter value: 56789 | ||
- | Digits detected: 5 | ||
- | |||
- | Obtaining unique digits, storing in array... | ||
- | digit[0] = 9 | ||
- | digit[1] = 8 | ||
- | digit[2] = 7 | ||
- | digit[3] = 6 | ||
- | digit[4] = 5 | ||
- | |||
- | Applying process... | ||
- | result[0] = 9 + 0 + 0 (sum of 9, carry out of 0) | ||
- | result[1] = 8 + 9 + 0 (sum of 7, carry out of 1) | ||
- | result[2] = 7 + 8 + 1 (sum of 6, carry out of 1) | ||
- | result[3] = 6 + 7 + 1 (sum of 4, carry out of 1) | ||
- | result[4] = 5 + 6 + 1 (sum of 2, carry out of 1) | ||
- | result[5] = 5 + 1 + 0 (sum of 6, carry out of 0) | ||
- | |||
- | Displaying result... | ||
- | 56789 x 11 = 624679 | ||
- | lab46: | ||
- | </ | ||
- | |||
- | The execution of the program is short and simple- obtain the input, do the processing, produce the output, and then terminate. | ||
=====Submission===== | =====Submission===== | ||
Line 478: | Line 253: | ||
<cli> | <cli> | ||
- | $ submit cprog mbe1 mbe1.c | + | $ submit cprog afn0 afn0.c |
- | Submitting cprog project "mbe1": | + | Submitting cprog project "afn0": |
- | -> mbe1.c(OK) | + | -> afn0.c(OK) |
SUCCESSFULLY SUBMITTED | SUCCESSFULLY SUBMITTED |