Category Archives: C/C++

Code I’ve written in C or C++ (or some other derivative of C).

Fun With Permutations

Posted on May 1, 2012 by Jonathan Landrum
Reply

A friend of mine was complaining at work the other day about a programming assignment he had, frustrated that he couldn’t think of the answer. I asked him if he’d email me the basic premise of the assignment so I could tackle it myself after finals were over, and he agreed. Here’s what he sent me:

Write a program that returns the number of permutations of the set {A, B, C, D, E, F} where A appears before D.

The reason most people in that class had a problem with this assignment is because they hadn’t yet had Probability and Statistics. What you have to throw away is the concept of the letters “A” and “D” and where they appear in the list. You only need to concern yourself with the blanks they occupy and how many ways these blanks can be arranged. A Permutation is an arrangement of items in a set where order matters, and where there’s no replacement of items. This value is generalized by n! where n is the size of the set.

At first glance, this task seems daunting, since we’re not dealing with numbers. Sure, I can factorial an integer, but how do you factorial D? As I alluded before, you don’t have to. The easiest way to think about this — and make no mistake, this is primarily a cognitive assignment — is to imagine all the permutations of the set where “A” is first. Since “D” will always fall after “A” in this case, all we have to calculate now is how many permutations of the subset from “B” to “F” there are. That is as simple as calculating 5! using the factorial() method we’ve come to know and love.

That’s our first number, now we need to find our second one, where “A” is second in the list. This will be the same factorial(5) call as before, but we have to subtract from this total the number of times “D” appears before “A”. That set looks like “{D, A, X, X, X, X}” where the X’s are the other letters. And again, notice it doesn’t matter what those letters are, just that there are four blanks we’re swapping around. So “A” appears in the second slot 5! times, and “D” appears before “A” a subset of those times, which is the number of ways the remaining four letters can be arranged. The final calculation for the second number is factorial(5) - factorial(4).

And this pattern repeats itself for each successive number, up to the calculation where “A” appears sixth in the set. That calculation looks like this:

factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4) - factorial(4)

That is one factorial(5) for our “A” position, and one factorial(4) for each possible position of “D”. Since there are five blanks before “A” this time, that’s five factorial(4) calculations. If you are very familiar with factorials, you will notice that 5 × 4! = 5!. So what we really have here is 5! – 5!, which is obviously 0. And that makes sense, because when “A” is last in the list, there are no permutations where “A” appears before “D”.

Once you see the pattern, the program practically writes itself. Now add up the six numbers, and you have your total. You want to know what’s really interesting? It’s the same number, no matter which two letters you pick. Remember: what’s in the blanks doesn’t matter. I hope I didn’t math you out too much this time.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

/*********************************
 Programmer:      Jonathan Landrum
 Program:         permutations.cpp
 Date:            1 May 2012
 ---------------------------------
 Assumptions:     None.
 Dependencies:    None.
 *********************************/
 
 
#include <iostream>
using namespace std;
long int factorial (long int in);
 
 
// --------------------------------------------------
// main():
//
// Calls the factorial function, and returns results.
// --------------------------------------------------
int main() {
    int first, second, third, fourth, fifth, sixth;
 
    cout << "/====================================\\" << endl;
    cout << "|                                    |" << endl;
    cout << "|          C++ Permutations          |" << endl;
    cout << "|                                    |" << endl;
    cout << "\\====================================/" << endl;
    cout << endl;
    cout << "This program returns the number of" << endl;
    cout << "permutations there are of the letters" << endl;
    cout << "from A to F where A appears before D." << endl;
    cout << endl;
    cout << "--------------------------------------" << endl;
    cout << "Processing..." << endl;
    cout << endl;
 
    /****************************
     Each factorial(5) is where
     A appears in the set, and
     each factorial(4) is an
     exception where D appears
     before A. Notice that when A
     is first, it doesn't matter
     where D appears.
 
     We could have more easily
     multiplied our factorial
     calculations and gained some
     speed, but I wanted to show
     WHY these numbers are right.
     ****************************/
    first  = factorial(5);
                        // {D,A,X,X,X,X}
    second = factorial(5) - factorial(4);
                        // {D,X,A,X,X,X} & {X,D,A,X,X,X}
    third  = factorial(5) - factorial(4) - factorial(4);
                        // {D,X,X,A,X,X} & {X,D,X,A,X,X} & {X,X,D,A,X,X}
    fourth = factorial(5) - factorial(4) - factorial(4) - factorial(4);
                        // {D,X,X,X,A,X} & {X,D,X,X,A,X} & {X,X,D,X,A,X} & {X,X,X,D,A,X}
    fifth  = factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4);
 
    /****************************
     Notice that factorial(4) x 5
     is equal to factorial(5). So
     this is a wasted calculation
     for the sake of example.
     ****************************/
                        // {D,X,X,X,X,A} & {X,D,X,X,X,A} & {X,X,D,X,X,A} & {X,X,X,D,X,A} & {X,X,X,X,D,A}
    sixth  = factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4) - factorial(4);
 
    cout << " " << first << " <- All where A is 1st" << endl;
    cout << "  " << second << " <- All where A is 2nd" << endl;
    cout << "  " << third  << " <- All where A is 3rd" << endl;
    cout << "  " << fourth << " <- All where A is 4th" << endl;
    cout << "  " << fifth << " <- All where A is 5th" << endl;
    cout << "+  " << sixth << " <- All where A is 6th" << endl;
    cout << "----" << endl;
    cout << " " << first + second + third + fourth + fifth + sixth << endl;
    cout << endl;
    cout << "Process complete." << endl;
    cout << "--------------------------------------" << endl;
    cout << "\\\\//_ Live long and prosper." << endl;
}
 
 
// --------------------------------------------------
// factorial():
//
// Recursive function.
// Returns long int, accepts (long int in).
//
// Calculates the factorial of the given number.
// --------------------------------------------------
long int factorial (long int in) {
    long int result = 0;
 
    if (in == 0)
        result = 1;
    else
        result = in * factorial(in - 1);
 
    return result;
} // End factorial

Translating Programs Between Languages

Posted on April 29, 2012 by Jonathan Landrum
Reply

I’ve written on this site so far in a few of the languages I know, and today I want to demonstrate that any language you like is usually a perfectly valid language to use. Each has their own niche that sets them apart, but generally they all do the same thing.

I was recently given an assignment to write a program that prints an hourglass shape using asterisks, and the user input should specify how many rows of asterisks there are on each end of the figure. For instance, a user input of 3 should output the following figure:

*****
 ***
  *
 ***
*****

Three rows on top, and three on bottom (counting the center asterisk as one each time.) I wrote the assignment in C++, since that’s what the assignment specifically called for. But I have also translated the program into Java and Fortran to demonstrate my point.

Java is only a slight change from C++, so it’s obvious. But Fortran is absolutely foreign in comparison; can an algorithm from C++ really be translated to Fortran? If you keep the basic premise of your algorithm’s logic intact, then yes, it can easily be done. You just have to be familiar with the differences in each language’s logical structures. Let’s start with the original C++ code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;
 
int main () {
    int input = 0;
 
    cout << "Enter the size of your hourglass: ";
    cin  >> input;
 
    for (int c = input - 1; c > 0; --c) {
        for (int i = 0; i < (input - c) - 1; ++i)
            cout << " ";
        for (int i = (2 * c + 1); i > 0; --i)
            cout << "*";
        cout << endl;
    } // End top for loop
    for (int c = 0; c < input; ++c) {
        for (int i = 0; i < (input - c) - 1; ++i)
            cout << " ";
        for (int i = (2 * c + 1); i > 0; --i)
            cout << "*";
        cout << endl;
    } // End bottom for loop
} // End main

Two for loops with diligent attention given to the counter variables and the conditions that make the loops exit, and you’re done. Simple, right? Converting this to Java is just as simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.Scanner;
 
public class hourglass {
	public static void main (String[] args) {
		int input = 0;
		Scanner scan = new Scanner(System.in);
 
		System.out.print ("Enter the size of your hourglass: ");
		input = scan.nextInt();
 
		for (int c = input - 1; c > 0; --c) {
			for (int i = 0; i < (input - c) - 1; ++i)
				System.out.print (" ");
			for (int i = (2 * c + 1); i > 0; --i)
				System.out.print ("*");
			System.out.println ();
		} // End top for loop
		for (int c = 0; c < input; ++c) {
			for (int i = 0; i < (input - c) - 1; ++i)
				System.out.print (" ");
			for (int i = (2 * c + 1); i > 0; --i)
				System.out.print ("*");
			System.out.println ();
		} // End bottom for loop
	}
}

So we’ve got our program working in two different languages now (which wasn’t all that difficult, really.) Now let’s give Fortran a try. This one is going to be a bit tricky; we can’t just copy-and-paste the code and change the differences. Fortran is altogether different. But the principles of making this function work are identical. Watch:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

PROGRAM hourglass
	IMPLICIT NONE
 
	INTEGER :: input = 0
	INTEGER :: c
	INTEGER :: i
 
	WRITE (*,'(a)',advance='no') 'Enter the size of your hourglass: '
	READ  (*,*) input
 
	c = input - 1
	DO WHILE (c > 0)
		i = 0
		DO WHILE (i < (input - c) - 1)
			WRITE (*,'(a)',advance='no') ' '
			i = i + 1
		END DO
		i = (2 * c + 1)
		DO WHILE (i > 0)
			WRITE (*,'(a)',advance='no') '*'
			i = i - 1
		END DO
		c = c - 1
		WRITE (*,*)
	END DO
	c = 0
	DO WHILE (c < input)
		i = 0
		DO WHILE (i < (input - c) - 1)
			WRITE (*,'(a)',advance='no') ' '
			i = i + 1
		END DO
		i = (2 * c + 1)
		DO WHILE (i > 0)
			WRITE (*,'(a)',advance='no') '*'
			i = i - 1
		END DO
		c = c + 1
		WRITE (*,*)
	END DO
END PROGRAM hourglass

It’s longer than the other two; nearly twice as long. And there’s a lot of line return control going on. But it can be done, and without any hacks or Fortran-fu. It’s a simple translation of the exact for loop structure from before into a Fortran DO WHILE structure. And that, my friend, is how you translate code from one language to another. Know both languages first, know how to work logical constructs in both, and you’ll do fine. Happy coding.

~Jonathan

Inductive Reasoning with Recursion

Posted on April 16, 2012 by Jonathan Landrum
Reply

This afternoon I found some programming assignments posted on a university website by a professor for his Discrete Structures course, and I decided to tackle these assignments one at a time. This is the first of those assignments, written in C++.

This program makes use of Inductive Reasoning to prove the fundamental theorem of arithmetic:

The fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers.

This program makes use of two recursive functions: the prime() function, which you’ve seen here many times before (just search for “prime”), and the induce() function. The former is an exact duplicate of that used in Computing the nth Prime and Adding the Prime Numbers Less Than 2,000,000. The latter function had to be written from scratch. Fortunately, it’s a trivial function. To decide how to go about writing that function, let’s look at the assignment:

Given a particular n > 1, your job is to generate a direct proof that n can be written as a product of primes. For example, if given n = 5, your program should generate output similar to the following:

5 is prime, so it is a product of a single prime.

On the other hand, given n = 60, your program should output:

In order to prove that 60 is a product of primes
	we prove that 6 and 10 are products of primes.
In order to prove that 6 is a product of primes
	we prove that 2 and 3 are products of primes.
2 is prime, so it is a product of a single prime.
3 is prime, so it is a product of a single prime.
Having proven that 2 and 3 are products of primes,
	we conclude that 6 = 2 * 3
	is a product of primes.
In order to prove that 10 is a product of primes
	we prove that 2 and 5 are products of primes.
2 is prime, so it is a product of a single prime.
5 is prime, so it is a product of a single prime.
Having proven that 2 and 5 are products of primes,
	we conclude that 10 = 2 * 5
	is a product of primes.
Having proven that 6 and 10 are products of primes,
	we conclude that 60 = 6 * 10
	is a product of primes.

The generated proof breaks 60 into 6 and 10, proves that 6 and 10 can each be written as a product of primes, and concludes as a result that 60 = 6 × 10 can also be written as a product of primes.

This program works according to the directions, with the simple deviation that my induce() method checks for divisibility by a short list of primes rather than the two factors nearest to √n. I have tested it to the maximum size of an int in C, and it works flawlessly.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

// ==================================================
// Programmer:  Jonathan Landrum
// Date:        16 April 2012
// ==================================================
// Program:     induce.cpp
// Purpose:     Uses inductive reasoning to show that
//		a number input by the user is a
//		product of primes.
// Assumptions: 1.) The number input is a natural
//		    number.
//		2.) The number input is > 1.
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// Function prototypes
// --------------------------------------------------
void induce(int);
bool prime(int);
 
 
// --------------------------------------------------
// main():
// Calls the induce() function
// --------------------------------------------------
int main () {
 
	// Variables
	int  input = 0;
 
	// Introduce the program
	cout << endl;
	cout << "--------------------------------" << endl;
	cout << "-      Inductive Reasoning     -" << endl;
	cout << "--------------------------------" << endl;
	cout << endl;
	cout << "This program uses recursion to" << endl;
	cout << "show that any natural number > 1" << endl;
	cout << "is a product of primes.";
	cout << endl << endl;
 
	// Get user input
	while (input < 2) {
		cout << "Enter an integer to test: ";
		cin  >> input;
	}
 
	cout << endl;
 
	// Return the results
	induce(input);
	cout << endl;
	cout << "--------------------------------" << endl;
	cout << "\\\\//_ Live long and prosper." << endl;
	return (0);
} // End main
 
 
// --------------------------------------------------
// induce():
// Prints out the results of proving the number input
// is a product of primes.
// --------------------------------------------------
void induce (int n) {
	if (prime(n)) {
		cout << n << " is prime, so it is a product of a single prime." << endl;
	} else {
		cout << "In order to prove that " << n << " is a product of primes" << endl;
		if (n % 13 == 0) {
			cout << "\twe prove that " << n / 13 << " and 13 are products of primes." << endl;
			induce(n/13);
			induce(13);
			cout << "Having proven that " << n / 13 << " and 13 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 13 << " * " << 13 << endl;
		} else if (n % 11 == 0) {
			cout << "\twe prove that " << n / 11 << " and 11 are products of primes." << endl;
			induce(n/11);
			induce(11);
			cout << "Having proven that " << n / 11 << " and 11 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 11 << " * " << 11 << endl;
		} else if (n % 7 == 0) {
			cout << "\twe prove that " << n / 7 << " and 7 are products of primes." << endl;
			induce(n/7);
			induce(7);
			cout << "Having proven that " << n / 7 << " and 7 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 7 << " * " << 7 << endl;
		} else if (n % 5 == 0) {
			cout << "\twe prove that " << n / 5 << " and 5 are products of primes." << endl;
			induce(n/5);
			induce(5);
			cout << "Having proven that " << n / 5 << " and 5 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 5 << " * " << 5 << endl;
		} else if (n % 3 == 0) {
			cout << "\twe prove that " << n / 3 << " and 3 are products of primes." << endl;
			induce(n/3);
			induce(3);
			cout << "Having proven that " << n / 3 << " and 3 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 3 << " * " << 3 << endl;
		} else if (n % 2 == 0) {
			cout << "\twe prove that " << n / 2 << " and 2 are products of primes." << endl;
			induce(n/2);
			induce(2);
			cout << "Having proven that " << n / 2 << " and 2 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 2 << " * " << 2 << endl;
		}
		cout << "\tis a product of primes." << endl;
	}
}
 
 
// --------------------------------------------------
// prime():
// Determines if a number is prime
// --------------------------------------------------
bool prime (int n) {
	// Variables
	bool result;
	int  i;
 
	// Do work
	if (n <= 1) {
		result = false; // 1 is not prime
 
	} else if ((n == 2) || (n == 3)) {
		result = true; // Hard code 2 and 3
 
	} else if (n % 2 == 0) {
		result = false; // Get rid of evens
 
		/* All other cases are out, so now we check
		 to see if n is divisible by the odd
		 numbers from 3 on. */
	} else {
		i = 3;
		result = true; // Assume it's prime, then prove
 
		while (true) {
			/* If i^2 is not a root of n, or if
			 n % i == 0. (Won't be larger than
			 the square.) */
			if ((i * i > n) || (n % i == 0))
				break;
			i += 2; // Iterate by 2 to get odds
		} // End while
 
		// Record the answer
		if (i * i > n)
			result = true;
		else
			result = false;
	} // End if
 
 
	// Return the answer
	return result;
}

Making a Queue From a Stack

Posted on April 10, 2012 by Jonathan Landrum
Reply

We’ve used stacks twice now (Writing a Drop-Out Stack and Using a Stack to Make a Checkbook Ledger), and they have already proved quite useful. Since a stack is so similar to a queue, let’s explore turning our stack into one.

The first thing we need to change is our header file. I’ve renamed it queue.h, since that’s all it defines this time. There is really quite little to change in the header beyond changing the names of the methods. I have also changed the data type to be int, just because. As before, a more useful queue would be one that could handle generic objects, but that is beyond the scope of this activity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <cstdlib>
#include <iostream>
#include <string>
 
#define SIZE 10
 
using namespace std;
 
class queue {
private:
	/* Instance Variables */
	int  count;
	int  front;
	int  rear;
public:
	/* Constructor */
	queue();
 
	/* Instance Methods */
	bool isEmpty();
	void enqueue(const int item);
	int  dequeue();
	int  first();
	int  size();
};

You’ll notice a couple of new variables, front and rear. These keep up with which cell of the array is the front of the queue and which is the rear. In implementing this queue, I have chosen a circular array queue as the structure. This structure made the most sense to me when studying data structures last semester. The only difference, really, is in how the enqueue and dequeue methods determine which cell of the array to use as their next location.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include "queue.h"
 
 
int data[SIZE];
 
queue::queue() {
	count  = 0;
	front  = 0;
	rear   = 0;
 
	for (int i = 0; i < SIZE; ++i)
		data[i] = 0.0;
}
 
bool queue::isEmpty() {
	bool result;
 
	if (count == 0)
		result = true;
	else
		result = false;
 
	return result;
}
 
void queue::enqueue(const int item) {
	if (count < SIZE) {
		data[rear] = item;
		rear = (rear + 1) % SIZE;
		++count;
	} else
		std::cerr << "Error: Attempt to enqueue to full queue\n";
 
}
 
int queue::dequeue() {
	int result = 0;
 
	if (!isEmpty()) {
		result = data[front];
		data[front] = NULL;
		front = (front + 1) % SIZE;
		--count;
	} else
		std::cerr << "Error: Attempt to dequeue from an empty queue\n";
 
	return result;
}
 
int queue::first() {
	return data[front];
}
 
int queue::size() {
	return count;
}

Beyond the few changes I have already mentioned, you can plainly see that a stack and a queue are quite similar. This is because they are practically the same structure. A stack can be thought of as a stack of plates, the top of the stack being both where you add new plates and where you retrieve a plate to use. A queue is like a line in a grocery store, the one who has been in line longest being the next one served.

But the two structures are arranged in the same order. The single difference is from where in the list you remove items. That is why it is so very easy to convert a stack into a queue and vice versa. Putting it to use is similarly simple, with our main method being almost identical to that from our stack program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include "queue.h"
 
 
int main() {
	int   count;
	int   item;
	queue myQueue;
 
	cout << "--------------------------------------------------------\n\n";
	cout << "               Programming a Queue in C++\n\n";
	cout << "--------------------------------------------------------\n\n";
 
	cout << "This program simulates a waiting line -- also called a\n";
	cout << "queue -- using a queue data structure.\n\n";
	cout << "This program only handles integers at the moment; other\n";
	cout << "data types would be trivial to implement.";
 
	for (count = 0; count < SIZE; ++count) {
		cout << "Entry " << count + 1 << ": ";
		cin  >> item;
		myQueue.enqueue(item);
		cout << "Items in the list: " << myQueue.size() << endl;
	}
 
	cout << "\nNow to dequeue those items:\n" << endl;
 
	for (count = 0; count < SIZE; ++count) {
		cout << "Entry " << count + 1 << ": " << myQueue.dequeue() << endl;
	}
 
	return (0);
}

As before, since we have three files to deal with, a makefile simplifies the process. And also as with the other files of this program, the makefile is nothing more than a search-and-replace change from the old program name to the new one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#
# Makefile for queue
#
 
CC=g++
CFLAGS=-g -Wall
 
queue: main.o queue.o
	$(CC) $(CFLAGS) -o queue main.o queue.o
main.o: main.cpp queue.h
	$(CC) $(CFLAGS) -c main.cpp
queue.o: queue.cpp queue.h
	$(CC) $(CFLAGS) -c queue.cpp
 
clean:
	rm -f queue *.o
 
# End of makefile

Having done all of my data structure programming in Java, I am pleased to begin creating these same structures in C. This program worked flawlessly as designed, and can be expanded to be quite a useful addition to a larger application.

~Jonathan

Using a Stack to Make a Checkbook Ledger

Posted on April 9, 2012 by Jonathan Landrum
1

The other day I wrote you about using a stack to make an undo button, and now I want to show you how you can use a stack to keep up with a running total in a ledger. This program still makes use of a stack data structure to organize the data, but there are a couple of new methods added:

1
2
3
4
5
6
7
8

void stack::addItem(const float item) {
	push(item);
	total += item;
}
 
float stack::returnTotal() {
	return total;
}

The first method, addItem(), extends the push() method by adding a running total to the items pushed. The second method, returnTotal(), simply gives the current total added. This is all there is to it. Everything else is a standard stack.

I’ve also split this program up into a main.cpp file — which contains the main method, a checkbook.cpp file — which defines the methods of the stack, and a checkbook.h file — which declares the methods and variables used by the stack. I have also created a makefile to make compiling easier. I’ll include it last. But first, here’s checkbook.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdlib>
#include <iostream>
#include <string>
 
#define SIZE 10
 
using namespace std;
 
class stack {
private:
	/* Instance Variables */
	int   count;
	float total;
public:
	/* Constructor */
	stack();
 
	/* Instance Methods */
	bool  isEmpty();
	void  push(const float item);
	float pop();
	void  addItem(const float item);
	float returnTotal();
};

All of the headers go in this .h file, and this one header will be included in the other two files. Essentially, this code will be pasted into the head of each of those two files, so whatever is here will be repeated in both places at compile time.

This file won’t actually be compiled; it’s just used for definitions. As such, anything that has to be allocated cannot be included here or you’ll get strange errors. There is an array used for the stack, but it has to be declared in checkbook.cpp in order for the program to compile and link correctly. That file is the extension of this header, defining the bodies of the methods declared in this header file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include "checkbook.h"
 
 
float data[SIZE];
 
stack::stack() {
	count = 0;
	total = 0.0;
 
	for (int i = 0; i < SIZE; ++i)
		data[i] = 0.0;
}
 
bool stack::isEmpty() {
	bool result;
 
	if (count == 0)
		result = true;
	else
		result = false;
 
	return result;
}
 
void stack::push(const float item) {
	if (count < SIZE) {
		data[count] = item;
		++count;
	} else
		std::cerr << "Error: Attempt to push to full stack\n";
 
}
 
float stack::pop() {
	float result = -1;
 
	if (!isEmpty()) {
		--count;
		result = data[count];
	} else
		std::cerr << "Error: Attempt to pop from an empty stack\n";
 
	return result;
}
 
void stack::addItem(const float item) {
	push(item);
	total += item;
}
 
float stack::returnTotal() {
	return total;
}

Now that our stack is declared and defined, we can use it in our main program.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include "checkbook.h"
 
 
int main() {
	int   count;
	float item;
	stack myStack;
 
	cout << "---------------------------------------------------------\n\n";
	cout << "                      C++ Checkbook\n\n";
	cout << "---------------------------------------------------------\n\n";
 
	cout << "This program simulates a checkbook program. Enter values\n";
	cout << "for each checkbook entry as floating point numbers.\n\n";
 
	for (count = 0; count < SIZE; ++count) {
		cout << "Entry " << count + 1 << ": ";
		cin  >> item;
		myStack.addItem(item);
		cout << "Running total: " << myStack.returnTotal() << "\n\n";
	}
 
	cout << "\nTOTAL: " << myStack.returnTotal() << endl;
 
	return (0);
}

This program initializes a stack and then uses the methods of this stack to add numbers together. A stack isn’t totally necessary for this application, but this program could be extended to do further computations beyond simply adding numbers together. And since the structure is in place, it will be trivial to extend it in the future.

Now to compile it all. You can compile each file separately and then link them, or you can use a makefile to do all that for you. Additionally, defining a proper makefile has the added benefit of the make clean command, which removes all object code and executables created in the compilation process (useful while writing the program.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#
# Makefile for checkbook
#
 
CC=g++
CFLAGS=-g -Wall
 
checkbook: main.o checkbook.o
	$(CC) $(CFLAGS) -o checkbook main.o checkbook.o
main.o: main.cpp checkbook.h
	$(CC) $(CFLAGS) -c main.cpp
checkbook.o: checkbook.cpp checkbook.h
	$(CC) $(CFLAGS) -c checkbook.cpp
 
clean:
	rm -f checkbook *.o
 
# End of makefile

This program is a good platform for building stack-based applications that span multiple headers and files, and it was good practice in writing classes. I’m quite happy with the outcome.

~Jonathan

Writing a Drop-Out Stack

Posted on April 5, 2012 by Jonathan Landrum
2

Last year in Data Structures we had to write what is known as a drop-out stack, which is exactly like a regular stack, only with one modification: when the contents of the stack reaches its maximum, the oldest item on the stack (the one at the bottom) “drops off” and is replaced by the next oldest item.

These types of stacks are frequently used in cases such as an undo button. You have, for instance, a ten-step history you can go back to. But when you make the eleventh change, the first one drops out and you can no longer go back that far. The reason many programs do not have infinite undo’s is because it eats up a lot of memory. So in the interest of being efficient, they limit how many steps you can recall.

I wrote this undo stack last night in about ten minutes using C++. The stack_dropOut() method only does two things: first, it counts through the stack from 0 to SIZE (defined as the maximum size of the stack), shuffling to the current position the next highest item. Then it decrements the item count by one. So if your limit is 10, it overwrites from the bottom — the first item — beginning with item 2, and goes all the way to item 9, and then it decrements the count. When the next item is pushed to the stack, it goes in position 10 (since the count is set to that position.)

I put all the contents of the stack into a separate header file in order to keep main() cleaner. So let’s go ahead and write that, and then worry about writing the stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include "stack.h"
 
int main() {
	stack myStack;
	stack_init(myStack);
	int item;
 
	// Demonstrate the dropout
	for (int c = 0; c < 15; ++c) {
		cout << "Enter a number to the stack: ";
		cin  >> item;
		stack_push(myStack, item);
		stack_toString(myStack);
	}
 
	cout << endl;
 
	// Demonstrate an empty collection exception
	for (int c = 0; c < 11; ++c) {
		stack_pop(myStack);
		stack_toString(myStack);
	}
 
	return (0);
}

I kept main() incredibly brief, because I really just wanted a quick example program that demonstrated the two things I wanted to show: first, of course, the stack_dropOut() method when stack_push() is called too many times, and then I wanted to demonstrate what happens when the stack_pop() method is called when the stack is empty. A proper stack should throw an empty collection exception, but this works in a pinch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#define SIZE 10
using namespace std;
 
 
struct stack {
	int count;
	int data[SIZE];
};
 
inline void stack_init(struct stack & the_stack) {
	the_stack.count = 0;
}
 
inline void stack_dropOut(struct stack & the_stack) {
	for (int c = 0; c < SIZE; ++c)
		the_stack.data[c] = the_stack.data[c + 1];
 
	--the_stack.count;
}
 
inline bool stack_isEmpty(struct stack & the_stack) {
	return (the_stack.count == 0);
}
 
inline void stack_push(struct stack & the_stack, const int item) {
	if (the_stack.count == SIZE)
		stack_dropOut(the_stack);
 
	the_stack.data[the_stack.count] = item;
	++the_stack.count;
}
 
inline int stack_pop(struct stack & the_stack) {
	if (stack_isEmpty(the_stack)) {
		cout << "Error: Empty Collection Exception" << endl;
		return(-1);
	}
 
	--the_stack.count;
	return (the_stack.data[the_stack.count]);
}
 
inline int stack_peek(struct stack & the_stack) {
	return (the_stack.data[the_stack.count]);
}
 
inline bool stack_size(struct stack & the_stack) {
	return (the_stack.count);
}
 
inline void stack_toString(struct stack & the_stack) {
	for (int c = 0; c < the_stack.count; ++c)
		cout << "Item " << c + 1 << ": " << the_stack.data[c] << endl;
}

I’m really glad to get this one written in C++. The last one I wrote was in Java, and it used generics in order to accept anything to the stack. As such, it was quite a few files in length. This stack only accepts integers at the moment, but it can be extended to be generic later on, and it’s just a driver and a single header.

~Jonathan

Perfecting Combinatorics

Posted on April 2, 2012 by Jonathan Landrum
Reply

I’ve written you now three times on this subject, first in printing Pascal’s Triangle, then using that to find binomial combinations in the triangle, and finally I wrote you about making the combinatorics algorithm more efficient. Today I want to present the final step in the efficiency process: getting rid of recursive functions altogether.

Throughout my mathematics and computer science courses, extensive use has been made of factorial functions, particularly in probability and statistics. As such, it’s interesting to find an algorithm that cuts right to the chase and foregoes the long, arduous factorial calculations. Even doing these on a computer will severely slow your program down, as we have seen over the past week. What we need is an equation that will give us the answer straightaway, or at least give it to us after an iteration. And that’s just what we’ve got.

Perfecting binomial calculations

This is an algorithm similar to sigma notation, only in this case we multiply in each cycle of the loop rather than add. By placing this set of instructions in a for loop we will produce our answer almost immediately. And this method will allow much larger combinations, as the number is simply multiplied up to a point, rather than being calculated as a factorial first. Another benefit: our code is now 73 lines shorter.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

// ==================================================
// Programmer:  Jonathan Landrum
// Date:        29 March 2012
// ==================================================
// Program:     combinations.cpp
// Purpose:     Calculates the number of combinations
//		that can be made with given input of
//		discrete items.
// Assumptions: - Input is an integer. Real input
//		  will be cast to the next lowest
//		  integer.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
 
// --------------------------------------------------
// main():
// Calls factorial() and returns results.
// --------------------------------------------------
int main () {
 
	// Variables
	float n, r;
	int   group, choose;
	long int result = 1;
 
	// Introduce the program
	cout << endl;
	cout << "------------------------------------" << endl;
	cout << "-     Combinatorics Calculator     -" << endl;
	cout << "------------------------------------" << endl;
	cout << endl;
	cout << "              /n\\      n!" << endl;
	cout << "        nCr = | | = --------" << endl;
	cout << "              \\r/   r!(n-r)!" << endl;
	cout << endl;
	cout << "This program calculates how many" << endl;
	cout << "combinations can be made of a given" << endl;
	cout << "number of choices, and a given sized" << endl;
	cout << "group from which to choose." << endl;
 
	// Get user input
	try {
		do {
			cout << endl;
 
			cout << "Size of the group (n): ";
 
			cin  >> n;
		} while (n < 0);
 
		do {
			cout << endl;
 
			cout << "Number of choices (r): ";
 
			cin  >> r;
		} while (r < 0);
 
		cout << endl;
 
		group  = (int)n;
		choose = (int)r;
	}
	catch (...) {
		cout << "Error: << Unexpected Input >>" << endl;
		return (-1);
	}
 
	if (choose > group) {
		cout << 0 << endl << endl;
		return (0);
	}
 
	for (int i = 1; i <= choose; ++i)
		result *= ((float)(group - choose + i)/i);
 
	cout << result << endl << endl;
 
	return (0);
} // End main

Revisiting Combinatorics

Posted on by Jonathan Landrum
1

I’ve written twice this week about creating Pascal’s Triangle and using it to find binomial combinations. I now want to present the first of two more-efficient algorithms, given me by my instructor, Dr. Glenn Wiggins.

I’ve mentioned before that iterative and recursive solutions are fine, but if you can find an algorithmic solution you’ll be much better off. This solution still makes use of the factorial() function from before, but its use is much more limited.

The calculation is taken from a method for finding Binomial coefficients:

Calculation for finding Binomial Coefficients

With this algorithm and our factorial() function, returning our answer is a much faster affair. You will also notice that with successive improvements, larger numbers can be handled. That is because the less you use a recursive function, the more efficient your program will be as a whole. But there is actually an even better method, and I’ll show you that one next.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

// ==================================================
// Programmer:  Jonathan Landrum
// Date:        29 March 2012
// ==================================================
// Program:     combinations.cpp
// Purpose:     Calculates the number of combinations
//		that can be made with given input of
//		discrete items.
// Assumptions: - Input is an integer. Real input
//		  will be cast to the next lowest
//		  integer.
// Issues:      - The function factorial() slows down
//		  significantly for input greater
//		  than 23 due to the fact that they
//		  use recursion to calculate their
//		  results.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
 
// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
long int factorial (long int in);
 
 
// --------------------------------------------------
// main():
// Calls factorial() and returns results.
// --------------------------------------------------
int main () {
 
	// Variables
	float n, r;
	int   group, choose;
	long int result = 1;
 
	// Introduce the program
	cout << endl;
	cout << "------------------------------------" << endl;
	cout << "-     Combinatorics Calculator     -" << endl;
	cout << "------------------------------------" << endl;
	cout << endl;
	cout << "              /n\\      n!" << endl;
	cout << "        nCr = | | = --------" << endl;
	cout << "              \\r/   r!(n-r)!" << endl;
	cout << endl;
	cout << "This program calculates how many" << endl;
	cout << "combinations can be made of a given" << endl;
	cout << "number of choices, and a given sized" << endl;
	cout << "group from which to choose." << endl;
 
	// Get user input
	try {
		do {
			cout << endl;
 
			cout << "Size of the group (n): ";
 
			cin  >> n;
		} while (n < 0);
 
		do {
			cout << endl;
 
			cout << "Number of choices (r): ";
 
			cin  >> r;
		} while (r < 0);
 
		cout << endl;
 
		group  = (int)n;
		choose = (int)r;
	}
	catch (...) {
		cout << "Error: << Unexpected Input >>" << endl;
		return (-1);
	}
 
	if (choose > group) {
		cout << 0 << endl << endl;
		return (0);
	}
 
	result = group;
 
	for (int i = 1; i <= choose - 1; ++i)
		result *= (group - i);
 
	cout << (result/factorial(choose)) << endl << endl;
 
	return (0);
} // End main
 
 
// --------------------------------------------------
// factorial():
//
// Recursive function.
// Returns int, accepts (int in).
// 
// Calculates the factorial of the given number.
// --------------------------------------------------
long int factorial (long int in) {
	long int result = 0;
 
	if (in == 0)
		result = 1;
	else
		result = in * factorial(in - 1);
 
	return result;
} // End factorial

Using Pascal’s Triangle to Find Binomial Combinations

Posted on March 31, 2012 by Jonathan Landrum
2

I wrote the other day about calculating Pascal’s Triangle using C++, but I didn’t include all the interesting facts about Pascal’s Triangle. One of the more interesting ones is its use in Combinatorics as a sort of shortcut to finding binomial coefficients. If you have the first few rows of the triangle memorized, you don’t have to calculate the coefficients of a binomial equation, such as (x + y)n.

These coefficients are useful in statistics when calculating the binomial distribution. As such, one frequently finds himself performing this calculation:

Binomial Calculation

Pascal’s Triangle is calculable with the pascal() function I wrote in the last post, but it is also calculable using this binomial calculation. This is the second method I talked about in that post, and it does use three calls to a factorial() function, as you can see.

I have not written this version to produce a Pascal Triangle. It can easily be made to do so, as this function calculates each coefficient just as the pascal() function does. Simply placing the call in a for loop will return successive values. Instead, this version returns an individual coefficient, which is also the value of a Binomial equation. This value is the number of combinations that can be made from a set of size n when making r choices.

If you have a set of size 4 — say, 4 apples — and you want to choose 3, how many different combinations can you make? Such a trivial equation is easy to solve: the answer is 4. But what about for larger sets and larger selections? An interesting thing about Pascal’s Triangle is you can immediately find your answer by selecting the row that is the same number as the size of the group, and the element of that row that is the same number as the size of the selection.

Calculating Binomial coefficients with Pascal's Triangle

You begin counting with 0 in both cases, and that makes sense, as you can select 0 items from a set of size 0 in exactly 1 way: by selecting nothing at all. In the example above, you count down to row 4 (since there are four apples from which to choose), and you count over to the third number (since you are selecting three apples). The number in that position is your answer: 4. This program does this for you, using the factorial() function and the aforementioned binomial algorithm.

An interesting thing to note, if the number of choices is greater than the size of the group, the program returns 0. There is a simple explanation for this behavior. In our example above, if you wanted to instead pick 5 apples from the group of 4, you would get your wish 0 times. It cannot be done. There was actually a question quite similar to this on one of my tests in Probability and Statistics. If you think of the region beyond the triangle as being populated with 0’s, then the result is perfectly plausable: row 4, column 5. And this program correctly returns 0 in this case. Combinatorics is a fascinating field of mathematics.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

// ==================================================
// Programmer:  Jonathan Landrum
// Date:        29 March 2012
// ==================================================
// Program:     combinations.cpp
// Purpose:     Calculates the number of combinations
//		that can be made with given input of
//		discrete items.
// Assumptions: - Input is an integer. Real input
//		  will be cast to the next lowest
//		  integer.
// Issues:      - The function factorial() slows down
//		  significantly for input greater
//		  than 23 due to the fact that it
//		  uses recursion to calculate its
//		  result.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
 
// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
long int factorial (long int in);
 
 
// --------------------------------------------------
// main():
// Calls factorial() and returns results.
// --------------------------------------------------
int main () {
 
	// Variables
	float n, r;
	int   group, choose;
 
	// Introduce the program
	cout << endl;
	cout << "-----------------------------------" << endl;
	cout << "-     Combinations Calculator     -" << endl;
	cout << "-----------------------------------" << endl;
	cout << endl;
	cout << "              /n\\      n!" << endl;
	cout << "        nCr = | | = --------" << endl;
	cout << "              \\r/   r!(n-r)!" << endl;
	cout << endl;
	cout << "This program calculates how many" << endl;
	cout << "combinations can be made of a given" << endl;
	cout << "number of choices, and a given sized" << endl;
	cout << "group from which to choose." << endl;
 
	// Get user input
	try {
		do {
			cout << endl;
 
			cout << "Size of the group (n): ";
 
			cin  >> n;
		} while (n < 0);
 
		do {
			cout << endl;
 
			cout << "Number of choices (r): ";
 
			cin  >> r;
		} while (r < 0);
 
		cout << endl;
 
		group  = (int)n;
		choose = (int)r;
	}
	catch (...) {
		cout << "Error: << Unexpected Input >>" << endl;
		return (-1);
	}
 
	if (choose > group) {
		cout << 0 << endl << endl;
		return (0);
	}
 
	cout << (factorial(group)/(factorial(choose) * factorial(group - choose))) << endl << endl;
 
	return (0);
} // End main
 
 
// --------------------------------------------------
// factorial():
//
// Recursive function.
// Returns long int, accepts (long int).
// 
// Calculates the factorial of the given number.
// --------------------------------------------------
long int factorial (long int in) {
	long int result = 0;
 
	if (in == 0 )
		result = 1;
	else
		result = in * factorial(in - 1);
 
	return result;
} // End factorial

Pascal’s Triangle

Posted on March 30, 2012 by Jonathan Landrum
3

This program calculates Pascal’s Triangle to the size specified by the user, using a recursive function. Pascal’s Triangle is an array of related numbers, where a given digit is equal to the number above it to the left plus the number above it to the right. Here are the first five rows of Pascal’s Triangle as an example:

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1

Row three from the top is “1 2 1”. The two is calculated by adding the two 1’s on the row above it. Likewise, the 6 on row five is calculated by adding the two 3’s on the row above it. This continues ad infinitum for all positive integers.

Because this is a recursive method, output slows to a crawl as input approaches 23 or 24. There is at least one other method for calculating Pascal’s Triangle, but it uses three factorial calls, which is actually less efficient than what I have here, and as such would slow down earlier than this method does.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

// ==================================================
// Programmer:  Jonathan Landrum
// Date:        29 March 2012
// ==================================================
// Program:     pascal.cpp
// Purpose:     Takes user input of an integer and
//		returns a Pascal Triangle of the
//		specified depth.
// Assumptions: 1.) Input is an integer. Real input
//		    will be cast to the next lowest
//		    integer.
//		2.) Input is positive. Negative
//		    input and text input will simply
//		    return nothing.
// Issues:      1.) Output looks normal for row
//		    numbers less than 6. Output is
//		    skewed to the left for row
//		    numbers greater than 5, due to
//		    the introduction of large digits.
//		2.) The function pascal() slows down
//		    significantly for input greater
//		    than 23 due to the fact that it
//		    uses recursion to calculate its
//		    result.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
 
// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
int pascal (int row, int column);
 
 
// --------------------------------------------------
// main():
// Calls pascal() and returns results.
// --------------------------------------------------
int main () {
 
	// Variables
	float in;
	int   input;
	int   counter;
	int   row;
	int   column;
	int   spaces;
 
	// Introduce the program
	cout << endl;
	cout << "-----------------------------" << endl;
	cout << "-     Pascal's Triangle     -" << endl;
	cout << "-----------------------------" << endl;
	cout << endl;
	cout << "              1" << endl;
	cout << "            1   1" << endl;
	cout << "          1   2   1" << endl;
	cout << "        1   3   3   1" << endl;
	cout << "      1   4   6   4   1" << endl;
	cout << endl;
	cout << "This program asks for an" << endl;
	cout << "integer, and returns a Pascal" << endl;
	cout << "Triangle of that depth." << endl;
 
	// Get user input
	try {
		cout << endl;
		cout << "Enter a natural number for" << endl;
		cout << "the size of your triangle: ";
 
		cin  >> in;
		cout << endl;
 
		input = (int)in;
	}
	catch (...) {
		cout << "Error: << Unexpected Input >>" << endl;
		return (-1);
	}
 
	counter = input;
 
	// Main processing loop
	for (int n = 0; n < input; ++n) {
		cout << "    ";
 
		for (int c = counter; c > 0; --c)
			cout << "  ";
 
		for (int c = 0; c <= n; ++c)
			cout << pascal(n + 1, c + 1) << "   ";
 
		cout << endl;
		--counter;
	}
 
	cout << endl;
 
	return (0);
} // End main
 
 
// --------------------------------------------------
// pascal():
//
// Recursive function.
// Returns int, accepts (int row, int column).
// 
// Calculates the value of the number at the 
// specified row and column of a Pascal Triangle.
// --------------------------------------------------
int pascal (int row, int column) {
	int result = 0;
 
	if ((column == 1) || (row == column))
		result = 1;
	else
		result = pascal(row - 1, column - 1) + pascal(row - 1, column);
 
	return result;
}