Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 129 lines (122 sloc) 5.603 kb
f8c38d6 @cooljeanius Initial Commit
authored
1 /* Eric Gallager
2 * In-Class Assignment #3
3 *
4 * Problem:
5 * For this assignment, I would like you to write a program that will print a level of Pascal's Triangle specified by the user.
6 *
7 * You might recall Pascal's triangle from a previous class. If you don't you may always visit Wikipedia and look up Pascal's triangle.
8 * Consider the first few rows of Pascal's triangle, numbered starting at zero.
9 *
10 * 0: 1
11 * 1: 1 1
12 * 2: 1 2 1
13 * 3: 1 3 3 1
14 * 4: 1 4 6 4 1
15 *
16 * What we can see here is that the zeroth level is 1, then subsequent levels are made by placing 1's at the edges and summing values 'above' the numbers we wish to create for a row.
17 * However, there is a short cut for our assignment which is for the user to input a row at zero or more* and then for the program to print the row labeled with that number.
18 * We can use Combinations. You might have also heard of combinations, but if you haven't you can also go to Wikipedia.
19 *
20 * The Formula for a Combination is:
21 *
22 * C(n,r) = n! /(r! * (n-r)!)
23 *
24 * What the combination formula is used to do is find out the number of ways to choose items without regard for the order those items are picked in.
25 * When used in this fashion;
26 * n = the number of items in your collection.
27 * r = the number of items that you choose from the collection.
28 *
29 * Consider then a group of 4 markers which are red, black, green, and blue.
30 * There is 1 way to choose 0 markers from the set of 4 markers, you just choose no markers.
31 * There are 4 ways to choose 1 markers from the set of 4 markers. You can choose a red one, a green one, a blue one, or a black one.
32 * There are 6 ways to choose 2 markers from the set of 4 markers. You can choose (1) red and black, (2) red and green, (3) red and blue, (4) black and green, (5) black and blue, or (6) green and blue.
33 * Now consider the formula, choosing 2 markers from a set of 4 markers is called 4 choose 2; which is
34 * C(4,2) =
35 * 4! / (2! * (4-2)!) =
36 * 4! / (2! * 2!) =
37 * (4*3*2!)/(2!*2!) =
38 * (4*3)/2! =
39 * 12/2 =
40 * 6
41 *
42 * There are also 4 ways to choose 3 markers and 1 way to choose all 4 markers.
43 * We can relate this math to Pascal's triangle because the numbers that you get for a row are the same numbers you get when you do the combinations by setting r to the numbers between 0 and n. To take a closer look at the forth row 4: C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4) =1.
44 * This sort of logic can be done for any other row.
45 *
46 * So, now what do you need to do this assignment.
47 * You need to write a function for Factorial which you can do easily
48 * You need to write a function for Combination, which you can do after you have a function for Factorial.
49 * Then you need to use the Combination function to create a row of Pascal's triangle by using the Combination function in a loop from 0 to the user's selected n.
50 *
51 * ---
52 *
53 * Algorithm for the factorial function:
54 *
55 * 1. Get a number as input
56 * 2. Find all numbers from that number down to 1 (use a for-loop, subtracting 1 each time) (actually never mind, maybe try recursion instead)
57 * 3. Multiply all those numbers
58 *
59 * Actually never mind all that, there's a perfectly good one in the textbook
60 *
61 */
62
63 #include <math.h>
64 #include <stdio.h>
65
66 /*
67 * Factorial function: computes n! for n greater than or equal to zero.
68 */
e8b904e @cooljeanius make separate library for factorial function
authored
69 int factorial(int n); // Prototype
f8c38d6 @cooljeanius Initial Commit
authored
70 int
71 factorial(int n)
72 {
73 int i, /* local variables */
74 product = 1;
75
76 /* Computes the product n x (n-1) x (n-2) x ... x 2 x 1 */
77 for (i = n; i > 1; --i) {
78 product *= i;
79 }
80
81 /* Returns function result */
82 return (product);
83 /* printf("\n %d \n", product); // statement for debugging */
84 }
85
86 /*
87 * Combination function: computes the number of combinations of n items taken r at a time
88 */
e8b904e @cooljeanius make separate library for factorial function
authored
89 int combination(int n, int r); // Prototype
f8c38d6 @cooljeanius Initial Commit
authored
90 int
91 combination(int n, int r)
92 {
93 int c = factorial(n) / (factorial(r) * factorial(n-r));
94 return (c);
95 /* printf("\n c is %d \n", c); // statement for debugging */
96 }
97
98 /*
99 * Main function: does what the program was overall designed for
100 */
101 int main (int row_number) {
102 int i = 1;
103 int answer = 1;
104 printf("\n Enter the row of Pascal's Triangle you would like to find \n (the first row is row 0) \n (also be nice to your computer and keep your row number reasonably low) \n > "); // prompt // ("reasonably low" currently means below 13 to get correct results, and below 34 to *not* get a floating point exception.)
105 scanf("%d", &row_number); // get input
106 /* printf("\n Row number is %d. \n", row_number); // statement for debugging */
107 printf("\n The contents of row %d are: \n", row_number);
108 /* int fact = factorial(row_number);
109 printf("\n Factorial of the row number is %d ", fact); // testing factorial function */
110 /*
111 * WARNING!
112 * In some circumstionces, the following will make the program fail to compile unless you pass -fnested-functions to the compiler, so be sure to enable that flag
113 */
114 if (row_number == 0) { // the first few rows are odd, hard-coding them just in case
115 printf("\n 1 \n");
116 } else if (row_number == 1) {
117 printf("\n 1 1 \n");
118 } else if (row_number > 1) { // here's the actual programmatic part
119 printf("\n 1 "); // this needs to be hard-coded
120 for (i = 1; i <= row_number; i++) { // incrementing is done with the normal i++, *not* the combination function (duh)
121 answer = combination(row_number, i); // the combination part goes here, not in the incrementing step for the for-loop
122 printf(" %d ", answer);
123 }
124 printf(" \n ");
125 } else
126 printf("\n This is not supposed to happen. \n"); // just in case
127 return 0;
128 }
Something went wrong with that request. Please try again.