Programming: Week 2

By: Rokas Paulauskas / November 20, 2014 /

/ No Comments

Arrays and functions … this has long become the “traditional” point in learning a programming language where I would quit it altogether. This was the case with Pascal like 12 years ago and then with C++ a few years ago.

But this time it’s serious – it’s part of formal studies so there’s no way I’m quitting now.

Ex. 1

Write a program that calls a function called Square. The function takes a float parameter and returns its square (also a float).

#include "stdafx.h"
#include "iostream"

float square(float a)
{
	a = a*a;
	return a;
}

int main(int argc, _TCHAR* argv[])
{
	float num;
	std::cout << "Please enter a number to be squared." <> num;
	std::cout << "The square is " << square(num) << std::endl;
	return 0;
}

That’s how I would intuitively define the function and include it in the program. However, the function can be simplified by combining lines 6 and 7 into a single line, i.e. returning the desired expression instead of first assigning it to a variable and then returning the variable.

So we get

#include "stdafx.h"
#include "iostream"

float square(float a)
{
	return a*a;
}

int main(int argc, _TCHAR* argv[])
{
	float num;
	std::cout << "Please enter a number to be squared." <> num;
	std::cout << "The square is " << square(num) << std::endl;
	return 0;
}

Ex. 2-4

a) Define a function that converts input in Celsius to Fahrenheit.
b) Define a function that converts input in Fahrenheit to Celsius.
c) Write a program that asks the user to enter temperature in degrees and calls one of the above functions depending on which conversion the user wants.
d) If the user presses “q”, quit the program, repeat otherwise.

#include "stdafx.h"
#include "iostream"
#include "string" //to be able to use string variables

float C2F(float t) //Celsius to Fahrenheit
{
	return (float)9 / 5 * t + 32;
}

float F2C(float t) //Fahrenheit to Celsius
{
	return (float)5 / 9 * (t - 32);
}

int main(int argc, _TCHAR* argv[])
{
	float deg;
	char control;
	std::string mode = " mode selected. Enter a temperature in degrees.";
	std::cout < Fahrenheit, '2' for Fahrenheit -> Celsius, 'q' to quit." <> control;
	while (control != 113)
	{
		if (control == 49)
		{
			std::cout <F" << mode <> deg;
			std::cout << deg << " degrees in Celsius is " << C2F(deg) << " degrees in Fahrenheit." << std::endl;
		}
		else if (control == 50)
		{
			std::cout <C" << mode <> deg;
			std::cout << deg << " degrees in Fahrenheit is " << F2C(deg) << " degrees in Celsius." << std::endl;
		}
		else
			std::cout << "Wrong input! ";
		std::cout << "Choose mode again or 'q' to quit." <> control;
	};
	return 0;
}

A few comments about this program. At first, I was using separate variables, an int for controlling which conversion mode to enter, and a char for quitting the program. However, since both of these are actually doing control job, I felt I wanted to combine them to a single variable.

So a single variable, char control, serves to hold both conversion mode choice and if the app is to be quitted. And since it’s a char it accepts alphanumeric input – both numbers (such as 1 or 2) and letters (as q). When a user-entered value is assigned to char, the system is aware of both the value and its number in the ASCII table. So in lines 22, 24 and 30 I’m checking if char has the value of “1”, “2” or “q” respectively (verify in the ASCII table this is the case).

In the functions C2F and F2C, I’m casting temperature calculations to float. Even if the single function parameter t is a float, calculating 5/9 or 9/5 will perform integer division and give me 0 or 1, respectively instead of the expected ~0.556 and 1.8. So that’s why I have (float) in lines 7 and 12. As a sidenote, these are C-like casts and our teacher urged to use C++-like casts. Will try to move over to C++ casts in the future.

Ex. 5

Declare an array with 5 elements but do not initialize it. Then output the array elements. What result do you get, and why?

If you just declare an array like this

int array[5];

but never initialize it, the elements will be assigned those values which corresponding memory areas had from previous executions. For the user, it will look like some random gibberish.

Ex. 6

Write a program that fills elements of an integer array with random values. Use a function to generate the random values.

#include "stdafx.h"
#include "iostream"
#include "time.h"

int random()
{
	return rand() % 100;
}

int main(int argc, _TCHAR* argv[])
{
	srand((unsigned int)time(0));
	int array[5];
	for (int i = 0; i < 5; i++)
	{
		array[i] = random();
		std::cout << array[i] << "t";
	}
	std::cout << std::endl;
	return 0;
}

I output the value as soon as it is assigned. In such way, one loop suffices, no need for a second one to output the elements.

Ex. 7

Write a program that simulates Yahtzee game dice rolls. Let the user decide when to quit or roll again.

#include "stdafx.h"
#include "iostream"
#include "time.h"

int random()
{
	return 1 + rand() % 6;
}

int main(int argc, _TCHAR* argv[])
{
	srand((unsigned int)time(0));
	int array[5];
	char cont = 'R';
	while (cont == 'R')
	{
		for (int i = 0; i < 5; i++)
		{
			array[i] = random();
			std::cout << array[i] << "t";
		}
		std::cout << std::endl << "Roll again? 'R' to roll, any other character to quit." <> cont;
	}
	return 0;
}

This one is pretty simple. In Yahtzee, you roll 5 dice at the same time. So the program has to generate rolls of 5d6. We generate 5 random integer numbers from the interval [1;6].

Ex. 8-9

Write a program that sorts a randomly generated array
a) ascending
b) descending

Let’s begin by obtaining a random array. To make the task more interesting, let’s have the user enter the elements of an array. The length of the array will be fixed though, say 10. This is because array lengths must be explicitly defined upon declaring arrays.

So here is the code to implement this behaviour:

int array[10];
	for (int i = 0; i > array[i];
	};

Suppose a user entered a sequence of random numbers,

16 0 2 7 1 4 22 55 54 38

Now comes the most involving part, sorting.

Sorting: Bubble Sort algorithm

There are multiple sorting algorithms of varying efficiency. I looked for simple sorting algorithms and one of the first sorting algorithms I came across was Bubble Sort. It is quite inefficient yet simple to implement. So I chose Bubble Sort algorithm, for starters.

Bubble Sort works by comparing adjacent elements to determine if they are in order. If you are sorting ascending and have … 5 3 … somewhere in your array, you know they are out of order since 3 must precede 5 if they are to be ordered ascending.

When Bubble Sort stumbles upon such a pair of out of order elements, it swaps them so they are in order. If you do this for all the elements in you array, the result will be that the absolutely largest elements will be placed at the end, i.e. in correct position (considering we’re sorting ascending):

16 0 2 7 1 4 22 55 54 38 0 16 2 7 1 4 22 55 54 38 0 2 16 7 1 4 22 55 54 38 0 2 7 16 1 4 22 55 54 38 0 2 7 1 16 4 22 55 54 38 0 2 7 1 4 16 22 55 54 38 0 2 7 1 4 16 22 55 54 38 0 2 7 1 4 16 22 54 55 38 0 2 7 1 4 16 22 54 38 55

After 9 steps we completed iteration one moving the largest element, 55, to the end of the array.

Iteration 2 will bring the second largest element, 54, in its order, i.e. second to last. Note that only 8 steps will be required since the 9th element is already in place.

So that’s how Bubble Sort works. Sweep through the array, swapping out-of-order elements as you go and after as many iterations as there are elements in the array, it will be sorted.

Bubble Sort: complexity

Before implementing the algorithm I wanted to assess its complexity, i.e. how the number of steps required varies with the number of elements processed.

You would need $n-1$ iterations if the number of elements is $n$ . That is, once you have placed all the elements but the last one in order, you won’t need another iteration since bringing the other elements in order will also make the last element stand in order.

For each of the $n-1$ iterations, you will need as many comparison-swap steps as there are out-of-order elements, one fewer with each following iteration.

The table above lists how the numbers of sorted and remaining unsorted elements change after completing iterations.

After Completing Iter. #	Elements in Place	Elements to be Sorted	Steps Needed in Next Iter.
1	1	$n-1$	$n-2$
2	2	$n-2$	$n-3$
…	…	…	…
$i$	$i$	$n-i$	$n-i-1$
…	…	…	…
$n-2$	$n-2$	2	1
$n-1$	$n-1$	1	0

We are interested in the last column because it will let us calculate how many steps will be required to completely sort an array of length $n$ . So think like this …

How many steps were made in the first iteration? The answer is $n-1$ . Then, as shown in the table, $n-2$ (one less) will be needed in the second iteration and so on until only one step will be required in iteration $n-1$ .

The total of steps is given by the sum

$n-1+n-2+n-3+ldots+2+1=1+2+ldots+n-3+n-2+n-1$

That’s an arithmetic progression whose first term is 1, difference 1 and we’re adding the first $n-1$ terms. So the sum is equal to

$S_{n-1}=dfrac{1+n-1}{2}(n-1)=dfrac{n(n-1)}{2}=dfrac{n^2-n}{2}=dfrac{n^2}{2}-dfrac{n}{2}$

As the number of elements in the array increases, the quadratic term $n^2$ dominates, leading to

$Oleft(dfrac{n^2}{2}-dfrac{n}{2}right)=O(n^2)$

So the complexity of Bubble Sort is a second-order algorithm.

The Program

Below is the program which implements Bubble Sort:

#include "stdafx.h"
#include "iostream"

void selective_swap(int& n1, int& n2)
{
	if (n1 > n2)
	{
		int temp;
		temp = n1;
		n1 = n2;
		n2 = temp;
	}
}


int main(int argc, _TCHAR* argv[])
{
	int array[10], copy[10];
	for (int i = 0; i > array[i];
		copy[i] = array[i];
	};
	std::cout << "Your array (unsorted):" << std::endl;
	for (int i = 0; i < 10; i++)
	{
		std::cout << copy[i] << "t";
		for (int j = 0; j < 9-i; j++)
			selective_swap(array[j], array[j + 1]);
	};
	std::cout << "The sorted array:" << std::endl;
	for (int i = 0; i < 10; i++)
		std::cout << array[i] << "t";
	return 0;
}

A few words. Have a look at line 22. I’m using another array, copy[10], to store the unsorted array so that I will be able to display the array entered by the user after the original one is changed (sorted).

To avoid having an additional loop only to output the original array entered by the user, I’m outputting the elements of copy[10] at the same time I begin next run of the outer iteration (line 27). Once an element from user-entered array (copy[10]) is output, the inner loop sweeps through the array array[10], pushing another element to the end of the array, in its respective place.

Run the program and verify it correctly sorts arrays with 10 elements. This algorithm also works correctly when there are several elements that have the same values (negative integers can also be used). E.g., try this one

17 9 -5 -5 2 0 6 8 -1 0

The program sorts ascending. Making it sort descending is now trivial – just change the “>” sign to “<” in the selective_swap function (line 6). It will now swap elements if the left element is less than the element to the right, making larger elements move to the left, thus establishing descending order.

About Rokas Paulauskas

2014 Programming

View all posts by Rokas Paulauskas →

Tags: 2014