This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
haas:spring2015:cprog:projects:afn0 [2015/02/25 13:46] – [loops] 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 62: | Line 62: | ||
- | ====arrays==== | + | =====Task===== |
- | The other important component of our **mbe1** project will involve the effective use of arrays to further aid us in having an efficient (and very importantly: | + | The task at hand can benefit from loop and array assistance. |
- | 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' | + | For instance, taking the number input and processing it so each digit occupies its own array element would facilate your efforts in the overall task-- a process strongly resembling some of the work you had to do in the **mbe1** project to get your input ready for the multiply by 11 activity. |
- | An array is what is known as a **homogeneous** composite data type. It technically is a modifier (or adjective, if you will) of any valid variable data type. We basically use it to say " | + | =====Functions===== |
+ | As indicated, this task shares many attributes with the **mbe1** project; in fact, the mental math process itself may be slightly simpler. That affords us the opportunity | ||
- | **homogeneous** means all of the same, indicating it can ONLY contain variables | + | Specifically, we will look at modularizing aspects |
- | An array has a few other requirements: | + | We've been using functions all along (everytime you use **fprintf()** or **fscanf()**, |
- | * 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 " | + | ====Function prototype==== |
- | * arrays are located by their name (just as any variable is), along with an address/ | + | Like variables, functions need to be declared. |
- | * 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 | + | We can declare them at various scopes (file/ |
- | Let us see our array in action: | + | |
- | <code c> | + | 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). |
- | int numbers[4]; | + | |
- | </ | + | |
- | This code will declare | + | A function is basically |
- | 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. | + | Like a program, it takes input, does processing, |
- | To place a **17** in the first (position **0**) element of our **numbers** array, we'd say the following: | + | Unlike |
- | <code c> | + | This distinctions aside, a function can in many ways be viewed as a micro- or sub-program/routine. We use functions to assist us in making our code more readable/ |
- | numbers[0] = 17; | + | |
- | </code> | + | |
- | To place a **36** | + | Keeping everything |
- | <code c> | + | To create a function we must first declare (or prototype) it. This needs to happen BEFORE said function is ever used (just as with variables- you must declare a variable before it is first used, otherwise the compiler yells). |
- | numbers[2] = 36; | + | |
- | </ | + | |
- | ===Using variables as our array index position=== | + | A function, in many ways, is like a programmable |
- | Because the array index is a number, and things | + | |
- | <code c> | + | As such, it has a return value of a type (the function' |
- | int index = 3; | + | |
- | numbers[index] = 52; | + | |
- | </ | + | |
- | Because | + | We see this with main()... here are two variations of a **main()** function declaration (technically also the start of the definition as well, in the case of **main()**): |
- | ===Using variables for array contents=== | + | ===Parameterless function=== |
- | 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> | <code c> | ||
- | int value = 96; | + | int main() |
- | int index = 1; | + | |
- | + | ||
- | numbers[index] = value; | + | |
</ | </ | ||
- | Hopefully these examples have proved useful | + | 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 |
- | We now explore the productive collaboration | + | 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. |
- | ====Using loops and arrays together | + | Now: this is technically a different form of input and output than you are used to. Input doesn' |
- | To really make the most out of arrays in scaling our algorithms, using them in conjunction | + | Additionally, with or without parameters, we can always perform additional input (and output) within a given function, through |
- | ===42 everywhere=== | + | ===Parametered function=== |
- | + | ||
- | 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> | <code c> | ||
- | int data[11], position = 0; | + | int main(int argc, char **argv) |
- | + | ||
- | for(position = 0; position < 11; position=position+1) // see, using long form, could have done " | + | |
- | { | + | |
- | data[position] = 42; | + | |
- | } | + | |
</ | </ | ||
- | ===Display array contents=== | + | In this case, our **main()** function actually takes parameters- two, in fact: |
- | What if we wanted to print the contents of the array? Once again, we use a loop, and print out each value, one at a time. | + | |
- | Important considerations: | + | - an integer, we are calling **argc** |
- | * again, with C, being true to how the computer actually works, we can only access the array one element at a time | + | |
- | | + | |
- | * because we know how big our array is (11 elements, from previous example), we know how many elements to go for | + | |
- | | + | |
- | ... therefore, we have all the ingredients for a **for** loop: | + | 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 |
- | <code c> | + | So, when we wish to create functions of our own, we need: |
- | for (position = 0; position < 11; position++) | + | |
- | { | + | |
- | fprintf(stdout, "%d ", data[position]); | + | |
- | } | + | |
- | fprintf(stdout, | + | |
- | </ | + | |
- | This should result in the following program output: | + | * the return type |
+ | * the function name | ||
+ | * 0 or more parameters, identifying their order and type | ||
- | < | + | For example, let us make a sum() function. Here would be a likely prototype (we'd place it above main()): |
- | 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)? | + | int sum(int *, int); |
- | + | ||
- | We'd still want to use a loop, but look at how we structure it: | + | |
- | + | ||
- | < | + | |
- | for (position = 10; position >= 0; position--) | + | |
- | { | + | |
- | fprintf(stdout, | + | |
- | } | + | |
- | fprintf(stdout, " | + | |
</ | </ | ||
- | Notice how the loop-terminating | + | A function prototype (vs. its definition) will have a terminating |
- | That should make sense before you try to proceed. | + | In our case, our sum() function has the following: |
- | ===Thinking with arrays=== | + | * a return type of **int** (particular variable name doesn' |
- | Using arrays in your algorithms represents | + | * the function's name (sum) |
+ | * a comma-separated list of types corresponding | ||
- | Now, with arrays, we have one common name, distinguishable | + | Our sum() function will take an integer array (denoted |
- | As some of you have started to realize with **mbe0**, the actual core work of the project wasn't actually that hard, once you saw through the illusion of complexity we had placed in front of it. By using arrays, we can make our solutions even easier (and code even simpler)... but, we will initially have to eliminate self-imposed mental obstacles making | + | Now, parameter order very much matters. In our case, an "int *" came first, followed by an " |
+ | ====Function definition==== | ||
+ | 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), | ||
- | ====Multiplying a number | + | Our sum() function will be defined (below |
- | 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 | + | <code c> |
- | + | int sum(int *array, int size) | |
- | ===3-digits | + | { |
- | Again, to review, let's look at a 3-digit example. 123 x 11: | + | int result |
- | + | int i = 0; | |
- | <code> | + | |
- | 123 x 11 = 1 | + | for (i = 0; i < size; i++) |
- | | + | |
- | = 1 | + | |
- | = 1353 | + | return(result); |
+ | } | ||
</ | </ | ||
- | And digit-based additions that generate | + | ====function calling==== |
+ | 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 // | ||
- | 567 x 11: | + | Here would be an example of calling the above-mentioned **sum()** function: |
- | < | + | < |
- | 567 x 11 = 5 (5 + 6) (6 + 7) 7 | + | int scores[4]; |
- | | + | int tally = 0; |
- | = 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): | + | scores[0] = 88; |
+ | scores[1] = 47; | ||
+ | scores[2] = 96; | ||
+ | scores[3] = 73; | ||
- | * We know the last digit (1s place) of 567 x 11 right off the bat: 7 | + | tally = sum(scores, 4); |
- | * 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 a sum of 3, carry of 1... and that one gets sent over to the next place (which has an 11)... so 11+1 will be 12, or sum of 2, carry 1... that carry will propagate | + | Note, that it is rather important |
- | 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 368: | 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 |