EECE 230 Homework, Spring 2008
American University of Beirut · Introduction to Programming · 177 pages
Showing the first 10 of 177 pages. Download the PDF to see all of it.
More EECE 230 files
Show the text of this homework
#include <iostream>
#include <ctime>
using namespace std;
int partition(int *,int,int);
void swap(int *,int *);
void printArray(const int *A,int n);
void randQuickSort(int A[], int start, int end);
void quickSort(int A[], int start, int end);
int main()
{
int A[]= {16, 3, 5,9,6,18,7,8,11,2};
cout<<"orginal array:"<<endl;
printArray(A,10);
quickSort(A,0,9);
cout<<"after calling quicksort:"<<endl;
printArray(A,10);
cout<<endl;
cout<<"Now we are using the random quicksort function."<<endl;
srand((unsigned)time(NULL));
randQuickSort(A, 0, 9);
printArray(A,10);
return 0;
}
void quickSort(int A[], int start, int end){
if(end>start){
int k = partition(A,start,end);
quickSort(A,start,k-1);
quickSort(A,k+1,end);
}
}
void randQuickSort(int A[], int start, int end){
if(end>start){
int rx = start + rand()%(end-start+1);
swap(A[rx],A[end]);
int m = partition(A,start,end);
quickSort(A,start,m-1);
quickSort(A,m+1,end);
}
}
int partition(int A[],int start,int end)
{
//repeat the process until we reach some boundary conditions (when i==j we swap
with the number if greater
//and we swap with the next one if its smaller)
if(end-start<1) return 0;
int i=0;
int j=end-1;
while (i<j)
{
while (A[i]<=A[end] && i<j) i++;
while (A[j]>=A[end] && i<j) j--;
//exchange A[i] and A[j] use swap function.
swap(A[i],A[j]);
}
if(A[i]>=A[end]) { swap(A[i],A[end]);
return i; }
else {
swap(A[i+1],A[end]);
return i+1;
}
}
void printArray(const int *A,int n)
{
for (int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
//At the end we place A[n - 1] in its right position.
void swap(int *p, int *q)
{
int temp = *p;
*p = *q;
*q = temp;
return;
}
#include <iostream>
using namespace std;
const int length = 4;
void printArray(const int *A,int n);
void printAll(char c[],int currentindex,int stringlength);
void storeAll(char s[],int currentIndex,char C[][length+1], int& counter);
void printAllC(char str[], int currentindex,int stringlength,int weight);
void main()
{
char c[100];
printAll(c,0,2);
char s[length+1];
char C[1000][length+1];
int counter = 0;
storeAll(s,0,C,counter);
for(int i=0;i<counter;i++) cout << C[i] << endl;
char str[100];
printAllC(str,0,5,2);
}
void printAll(char c[],int index,int length){
if(index==length){
c[index]='\0';
cout << c << endl;
return;}
c[index]='a';
printAll(c,index+1,length);
c[index]='b';
printAll(c,index+1,length);
c[index]='c';
printAll(c,index+1,length);
}
//storeAll instead of printing to the screen, prints to an array.
void storeAll(char c[],int index,char C[][length+1], int& counter){
if(index==length)
{
for(int j=0;j<length;j++)
C[counter][j]=c[j];
C[counter][length]='\0';
counter++;
return;
}
c[index]='a';
storeAll(c,index+1,C,counter);
c[index]='b';
storeAll(c,index+1,C,counter);
c[index]='c';
storeAll(c,index+1,C,counter);
}
void printAllC(char str[], int i ,int stringlength,int weight){
if(i==stringlength)
{
str[i]='\0';
cout << str << endl;
return;
}
str[i]='0';
printAllC(str,i+1,stringlength,weight);
if(weight>0){
str[i]='1';
printAllC(str,i+1,stringlength,weight-1);}
}
#include <iostream>
using namespace std;
const int rows=4;
const int columns=4;
const int listsize =16;
const int matrixsize=4;
void createArithmeticSeq(int *list, int listsize);
void printArray(const int*,int );
void matricize(int A[listsize],int B[columns][rows]);
void printMatrix(int B[columns][rows]);
void reverseDiagonal(int B[columns][rows]);
void magicCheck(int A[listsize],int B[columns][rows]);
void main()
{
int A[16];
createArithmeticSeq(A,16);
printArray(A,16);
int matrix[columns][rows];
matricize(A,matrix);
printMatrix(matrix);
reverseDiagonal(matrix);
printMatrix(matrix);
magicCheck(A,matrix);
}
void createArithmeticSeq(int *A , int listsize)
{
int first,diff;
cout << "Please enter the first term of the arithmetic sequence" <<endl;
cin >> first;
cout << "Please enter the difference between 2 consecutive terms"<<endl;
cin >> diff;
int current = first;
for(int i=0;i<16;i++){
A[i]=current;
current= current + diff;
}
/*this also works:
A[0] = first;
for(int i=1;i<16;i++){
A[i]=A[i-1]+diff;
}*/
}
void printArray(const int *A,int n)
{
for (int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
void matricize(int A[listsize],int B[columns][rows])
{
int q=0;
for(int i=0;i<columns;i++)
for(int j=0;j<rows;j++)
B[i][j]=A[q++];
}
void printMatrix(int B[columns][rows])
{
cout<<endl;
for(int i=0;i<columns;i++){
for(int j=0;j<rows;j++){
cout << B[i][j] << " " ;
}
cout <<endl<<endl ;
}
}
void reverseDiagonal(int B[columns][rows])
{
for(int i=0;i<matrixsize/2;i++)
{
swap(B[i][i],B[matrixsize-i-1][matrixsize-i-1]);
swap(B[i][matrixsize-i-1],B[matrixsize-i-1][i]);
}
}
void magicCheck(int A[listsize],int B[columns][rows]){
int sum=0;
int i,j;
for(i=0;i<listsize;i++)
sum = A[i] + sum;
int
magicNumber = sum/4;
int sumofrow[rows]={0};
int sumofcol[columns]={0};
int sumofdiagonal1=0;
int sumofdiagonal2=0;
bool magic=true;
for(i=0;i<columns;i++){
for(j=0;j<rows;j++){
sumofrow[i]= B[i][j] + sumofrow[i];
sumofcol[j]= B[i][j] + sumofcol[j];
if(i==j) sumofdiagonal1=B[i][j]+sumofdiagonal1;
if(i==matrixsize-1-j) sumofdiagonal2=B[i][j]+sumofdiagonal2;
}
}
if((sumofdiagonal1!=magicNumber)||(sumofdiagonal2!=magicNumber)) magic = false;
for(i=0;i<matrixsize;i++){
if((sumofrow[i]!=magicNumber)||(sumofcol[i]!=magicNumber))
{
magic = false;
break;
}
}
if(magic==true) cout << "It is a magic square" << endl;
else cout << "it is not a magic number" << endl;
}
//Partition:
#include <iostream>
using namespace std;
void swap(int *,int *);
int partition(int *,int);
void printArray(const int *,int);
void quickSort(int [], int , int )
//prototype:
int main()
{
cout<<"please enter an integer n"<<endl;
int *A;
int n;
cin>>n;
A= new int[n];
cout<<"enter "<<n<<" elements"<<endl;
int counter; // to fill the array with the user input.
for (counter = 0; counter <n; counter++)
cin >> A[counter];
int q= partition(A,n);
cout<< q<< endl;
printArray(A,n);
cout<< quickSort(A, 0, n - 1);
return 0;
}
void quickSort(int A[], int start, int end)
{
int partition(int *A,int n)
{
//repeat the process until we reach some boundary conditions (when i==j we swap
with the number if greater
//and we swap with the next one if its smaller)
int i=0;
int j= n-2;
while ( i<j)
{
while ( A[i] <=A[n-1] && i<j) i++;
while ( A[j] >=A[n-1] && i<j) j--;
//exchange A[i] and A[j] use swap function.
swap(A[i],A[j]);
}
if (A[i]>= A[n-1]) {swap(A[i],A[n-1]);
return i;}
else {swap(A[i+1],A[n-1]);
return i+1;}
}
//At the end we place A[n - 1] in its right position.
void swap(int *p, int *q) {
int temp = *p;
*p = *q;
*q = temp;
return;
}
void printArray(const int *A,int n)
{
for (int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
EECE 230 Introduction to Programming, Sections 2,6,10
Programming Assignment 8
Tue April 24, 2007
• This programming assignment consists of 3 problems.
• It is due in the MAKEUP LAB SESSION:
– Time: Thursday May 3 from 6:30 to 9:00 pm
– Place: Lab rooms 4,5, and 6.
• Related material: Recursion (... Merge Sort, Tower of Hanoi) and 2-dimensional arrays.
• Lab structure and regulations:
⋆ The 3 hours Lab session is on Tuesdays in Lab rooms 2,3, and 4 from 3:30 pm to 6:30 pm. It
consists of three parts:
- Occasional Solving Session (not graded but attendance mandatory)
- Programming Assignment (graded)
Programming Assignments will be posted on WebCT on weekly basis. Typically, a Pro-
gramming Assignment requires much more than the time allocated for this part in the
Lab, so you are supposed to complete the major part of the assignment at home. The Lab
instructor will grade your assignment and can help you with the problems you are facing.
- Occasional graded weekly quiz
⋆ You are supposed to submit your own work. Cheating will not be tolerated and will be dealt
with severely: zero grades on the programming assignments, disciplinary committee, Dean’s
warning.
⋆ Lab attendance is mandatory. Violating this rule can lead to a failing grade.
Problem 1 (Quick Sort)
a) Quick Sort
The idea of the Quick Sort algorithm is the following. To sort an array A[0 . . . n − 1]:
1. Let x = A[n−1]. Partition A around x using the partition algorithm [Programming Assignment
6, Problem 4], and let q be the new index of x in the reordered array (q is returned by the
partition function). Thus now A is rearranged in such a way that:
i. Each element of A[0 . . . q − 1] is less than or equal to x
ii. A[q] = x
iii. Each element of A[q + 1 . . . n − 1] is greater than or equal to x
2. Recursively sort A[0 . . . q − 1] if the size of this subarray is greater than one
3. Recursively sort A[q + 1 . . . n − 1] if the size of this subarray is greater than one
1
Try the idea on a small example, write a pseudocode, then implement the quickSort function
void quickSort(int A[], int start, int end).
As usual the initial call is quickSort(A, 0, n − 1).
Use the code of your partition function from PA 6.
Note that, unlike mergeSort, quickSort does not use temporary arrays, which makes it very practical
b) Randomized Quick Sort
Now, instead of partitioning the array A around the last element A[n − 1], consider partitioning
A around a random element of A. We can do this by swapping the last element A[n − 1] with a
(uniformly) random element element of A (i.e., an element A[r] of A, where r is an element chosen
(uniformly) at random from the set of indices {0, . . ., n−1}), and then using the partition function.
Do this, not only at the initial call, but each time the partition function is called.
Implement this randomized version of Quick Sort and call your function randQuickSort.
To generate (pseudo) random numbers, use the rand() function [Malik, page 1480]. In the main
function use the command
srand((unsigned)time( NULL ));
to seed the pseudo-random-number generator with the current time so that the numbers will be
different every time we run. Here is an example illustrating the usage of the rand() function: to
generate a random element from the set {5, 6, 7, 8, 9, 10, 11}, we can use 5 + rand()%7.
This is the randomized Quick Sort algorithm, which is one of the fastest known sorting algorithms.
The randomness introduced in randomized Quick Sort guarantees that the split generated by par-
tition is well balanced with a high probability.
Write a program to test both functions.
Problem 2 (String Enumerator)
a) Print All
A length-n abc-string is a C-string s[0 . . . n] such that: for i = 0, . . . , n−1, s[i] is either the character
’a’, or the character ’b’, or the character ’c’ (as usual s[n] is the NULL character).
Write a recursive function printAll, which given an integer n > 1, prints all possible length-n
abc-strings.
For example, if n = 2, printAll is supposed to print:
aa
ab
ac
ba
bb
bc
ca
cb
cc
Write a program to test your function.
(Hints:
⋆ printAll makes 3 recursive calls
⋆ You have to use a temporary char-array to keep track of the string under consideration. You
can pass it (by reference) to the function, or declare it as a static variable in the function. You
can also make it global but you are encouraged to avoid this.
2
⋆ The code is very compact. You can do it in around 10 statements.)
The following two parts ((b) and (c)) are both related to (a) but they are independent.
b) Store All
In this part, we are interested in length-4 abc-strings.
Modify printAll so that instead of printing all possible length-4 abc-strings, it stores them in a
two-dimensional array M[0 . . .34 − 1][0 . . .4].
Call this recursive function storeAll.
You are not supposed to use global variables. Compared to printAll, storeAll has two additional
parameters: the matrix M (passed by reference) and a counter passed by reference also.
Write a program to test your function (the test program simply calls the function and prints the
matrix).
c) Weight
This part is probably more difficult than the previous ones, so please give it enough time.
Now, we are interested in length-n binary strings.
An length-n binary-string is a C-string x[0 . . . n] such that: for i = 0, . . . , n − 1, x[i] is either the
character ’0’, or the character ’1’ (as usual x[n] is the NULL character).
If x[0 . . . n] is length-n binary-string, we define the weight w of x to be the number of entries of x
which are equal to 1, i.e., w is equal to the number of indices i, 0 ≤ i ≤ n − 1, such that x[i] = 1.
Inspired by printAll, write a recursive function printAllC, which given a integer n > 1 and an
integer k ≥ 0, prints all length-n binary-strings of weigh less than or equal to k.
For example, if n = 5 and k = 2, printAllC is supposed to print (not necessarily in the shown
order):
00000
10000
01000
00100
00010
00001
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011
(Hint: printAllC makes either 2 recursive calls or 1 recursive call depending on some conditions. If
you implement the function in such a way that it always makes two recursive calls (i.e., the straight
forward modification of part (a)), it will take thousands of years (in principle) when n = 1000 and
k = 1. If you smartly decide on whether you need one or two recursive calls, it will take seconds
on n = 1000 and k = 1.)
d) (Optional) Permutation enumerator
A length-n permutation is a reordering of the integers 1, 2, . . ., n.
Note that each integer from 1 to n appears in the reordering exactly once.
For instance 1432 and 4123 are length-4 permutations.
3
Write a recursive function printAllPermutations which given an integer n, prints all length-n
permutations.
For example, if n = 4, printAllPermutations is supposed to print:
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3214
3241
3124
3141
3421
3412
4231
4213
4324
4313
4123
4132
Write a program to test your function.
Problem 3 (Magic Square)
Do Programming Exercise 9.13 [Malik, page 547] (page 494 in the second edition).
4
class myDynmkArray
{
public:
myDynmkArray(int n);
myDynmkArray();
int sqSearch(int x) const;
void insertionSort();
void copy(const myDynmkArray&);
void concatenate(const myDynmkArray&);
void print() const;
~myDynmkArray();
int* index;
int size;
};
#include <iostream>
using namespace std;
#include "DynmkArray.h"
void testfunction(myDynmkArray X)
{
cout<<"X.index[0]= "<<X.index[0]<<endl;
cout<<"X.size= "<<X.size<<endl;
}
void main()
{
int a,b;
cout<<"Size of A: ";cin>>a;cout<<endl;
cout<<"Size of B: ";cin>>b;cout<<endl;
myDynmkArray A(a);
myDynmkArray B(b);
cout<<"Elements os A:"<<endl;
for (int i=0;i<5;i++)
cin>>A.index[i];
cout<<endl<<"Elements of B:"<<endl;
for (i=0;i<7;i++)
cin>>B.index[i];
cout<<"------------------------------------------------------------------"<<endl
;
cout<<"A: ";A.print();cout<<endl;
cout<<"B: ";B.print();cout<<endl;
int x;
cout<<"Enter search item: ";cin>>x;cout<<endl;
cout<<endl;
cout<<"Sorting A...."<<endl;
A.insertionSort();
cout<<"Done sorting...."<<endl;
A.print();cout<<endl<<endl;
cout<<"Seraching B for "<<x<<"...."<<endl;
cout<<"index of: "<<x<<" int B is "<<B.sqSearch(x)<<endl<<endl;
cout<<"Concatenating A with B..."<<endl;
A.concatenate(B);
cout<<"A is now: "<<endl;
A.print();cout<<endl<<endl;
cout<<"Copying A to B..."<<endl;
B.copy(A);
cout<<"B is now: "<<endl;
B.print();cout<<endl<<endl;
cout<<"Cahnging A.size to destroy.."<<endl;
A.size=0;cout<<endl<<endl;
cout<<"Testing function call..."<<endl;
//testfunction(B);
}
#include <iostream>
using namespace std;
#include "DynmkArray.h"
myDynmkArray::myDynmkArray(int n)
{
index=new int [n];
size=n;
for (int i=0; i<size;i++)
index[i]=-1;
}
myDynmkArray::myDynmkArray()
{
index=new int [1];
size=1;
index[0]=-1;
}
int myDynmkArray::sqSearch(int x) const
{
for (int i=0; i<size;i++)
if (index[i]==x)
return i;
return -1;
}
void myDynmkArray::concatenate(const myDynmkArray &B)
{
int i;
int* temp=new int [size];
for (i=0;i<size;i++)
temp[i]=index[i];
delete [] index;
index=new int[size+B.size];
for (i=0;i<size;i++)
index[i]=temp[i];
for (i=size;i<size+B.size;i++)
index[i]=B.index[i-size];
size=size+B.size;
delete [] temp;
}
void myDynmkArray::copy(const myDynmkArray& B)
{
index=new int[B.size];
for (int i=0;i<B.size;i++)
index[i]=B.index[i];
size=B.size;
}
void myDynmkArray::insertionSort()
{
for(int j=1;j<size;j++)
{
int key = index[j];
int i = j-1;
while(i>=0 && index[i] > key)
{
index[i+1] = index[i];
i =i-1;
}
index[i+1] = key;
}
}
void myDynmkArray::print() const
{
for (int i=0;i<size;i++)
cout<<index[i]<<' ';
}
myDynmkArray::~myDynmkArray()
{
delete [] index;
}
#include <iostream>
using namespace std;
#include "rectangle.h"
point::point(double a,double b)
{
x=a;
y=b;
}
point::point()
{
x=0;
y=0;
}
void point::add(const point& A)
{
x=x+A.x;
y=y+A.y;
}
void point::scale(double a)
{
x=a*x;
y=a*y;
}
void point::xSelectioinSort(point* A,int n)
{
int i,j,index;
point temp;
for (i=0;i<n-1;i++)
{
int w=A[i].x;
index=i;
for ( j=i+1;j<n;j++)
{
if (A[j].x<w)
{
w=A[j].x;
index=j;
}
}
temp=A[i];
A[i]=A[index];
A[index]=temp;
}
}
void point::print() const
{
cout<<'('<<x<<','<<y<<')'<<endl;
}
#include <iostream>
using namespace std;
#include "rectangle.h"
void main()
{
cout<<"***********************************************"<<endl
<<"****************** Points**********************"<<endl;
point A(1,1);
point B(4,2);
point C(2,2);
cout<<"The points are:"<<endl;
cout<<"A ";A.print();
cout<<"B ";B.print();
cout<<"C ";C.print();
line();
cout<<"Testing point.add....."<<endl;
cout<<"A.add(B)= ";A.add(B);A.print();cout<<endl<<endl;
cout<<"Testing point.scale...."<<endl;
cout<<"B.scale(2)= ";B.scale(2);B.print();cout<<endl<<endl;
point list[]={A,B,C};
cout<<"Testing xSelectionSort....."<<endl;
cout<<"Sorting the points in ascending order:";
list[0].xSelectioinSort(list,3);
for (int i=0;i<3;i++)
list[i].print();
line();
line();
cout<<"***********************************************************************"<
<endl
<<"*******************************RECTANGLES******************************"<<end
l;
cout<<endl;
point a(1,1);
point b(4,2);
point c(2,2);
cout<<"The points are:"<<endl;
cout<<"a ";a.print();
cout<<"b ";b.print();
cout<<"c ";c.print();
line();
cout<<"The rectangle is formed of a and b"<<endl;
rectangle R(a,b);
cout<<"Testing area....."<<endl;
cout<<"Area= "<<R.area()<<endl<<endl;
cout<<"Testing contains point...."<<endl;
if (R.containsPoint(c))
{
cout<<" Rectangle contains point c";c.print();cout<<endl<<endl;}
else
{
cout<<"Rectangle does not contain point
c";c.print();cout<<endl<<endl;}
cout<<"Testing R.scale......"<<endl;
cout<<"R.scale(3) ";R.scale(3);cout<<"Corner points are now: ";cout<<"Lb
";R.L.print();cout<<"Ru ";R.R.print();cout<<endl;//cout<<endl<<"a
";a.print();cout<<"b ";b.print();cout<<endl;
cout<<"Testing R.translate....."<<endl;
R.translate(c);cout<<"After translation by c";c.print();
cout<<"Ru ";R.R.print();cout<<"Lb ";R.L.print();
cout<<endl;
point x(5,5);
point y(5,1);
point z(6,2);
point w(3,3);
point pointList[]={x,y,z,w};
cout<<" List of points is:";
for (i=0;i<4;i++)
{
pointList[i].print();
}
int count;
point pointListinR[4];
R.pointSetIntersection(pointList,4,pointListinR,count);
cout<<"There are "<<count<<" present in rectangle R, and they are of
coordinates:"<<endl;
for (i=0;i<count;i++)
pointListinR[i].print();
cout<<endl;
line();
}
class point
{
public:
point(double ,double);
point();
void scale(double);
void add(const point &);
void xSelectioinSort (point*,int );
void print() const;
double x;
double y;
};
void line();
class rectangle
{
public:
rectangle(const point&,const point&);
rectangle();
double area();
void scale(double);
void translate(const point&);
bool containsPoint (const point&) const;
void pointSetIntersection(const point[],int,point[],int&) const;
point L;
point R;
};
#include "rectangle.h"
#include <iostream>
using namespace std;
rectangle::rectangle(const point &A,const point &B)
{
if (A.x>B.x && A.y>B.y)
{
L=B;
R=A;
}
else
{
L=A;
R=B;
}
}
rectangle::rectangle()
{
L.x=0;L.y=0;
R.x=4;R.y=1;
}
double rectangle::area()
{
return (R.x-L.x)*(R.y-L.y);
}
void rectangle::scale(double a)
{
R.scale(a);
L.scale(a);
}
void rectangle::translate(const point& q)
{
R.add(q);
L.add(q);
}
bool rectangle::containsPoint(const point& p) const
{
//For a point to be inside a rectangle
if (p.x>=L.x&&p.x<=R.x&&p.y>=L.y&&p.y<=R.y)
return true;
return false;
}
void rectangle::pointSetIntersection(const point A[],int n,point B[],int &m)
const
{
m=0;
for (int i=0;i<n;i++)
if (containsPoint(A[i]))
{
B[i]=A[i];
m++;
}
}
void line()
{
cout<<"---------------------------------------------------------------"<<endl;
}
//Complex number class
#include <iostream>
#include <cmath>
using namespace std;
class complexNumber
{
public:
double temp;
void add( complexNumber & c);
void multiply( complexNumber & c);
void divide( complexNumber & c);
double norm() const;
void print() ;
complexNumber(double x, double y); // constructor
complexNumber(); // default constructor
//or i put them as private but i cannot set the w.Re=1 coz Re become
unaccessable.
double Re;
double Im;
};
int main()
{
complexNumber z(2,3);
z.print(); // z = 2+3i
complexNumber w;
w.print(); // w = 0+0i
w = z;
w.print(); // w = 2+3i
w.Re=1;
w.print(); //w=1+3i
z.add(w);
z.print(); // z = 3+6i
z.multiply(w); // z = (3+6i)(1+3i)
z.print(); // z = -15 + 15 i
cout<< w.norm(); // 3.1623
cout<<endl;
return 0;
}
complexNumber::complexNumber(double x, double y) // constructor
{
Re=x;
Im=y;
}
complexNumber::complexNumber() // default constructor
{
Re=0;
Im=0;
}
void complexNumber::add( complexNumber &c)
{
Re= Re + c.Re;
Im= Im + c.Im;
}
void complexNumber::multiply( complexNumber &c)
{
double temp= Re;
Re= Re*c.Re - Im*c.Im;
Im= c.Im*temp + c.Re*Im;
}
void complexNumber::divide( complexNumber &c)
{
double temp= Re;
Re= ( Re*c.Re + Im*c.Im ) / ( c.Re*c.Re + c.Im*c.Im);
Im= ( c.Re*Im - c.Im*temp ) / ( c.Re*c.temp + c.Im*c.Im);
}
double complexNumber::norm() const // the norm of x + iy
{
return pow( Re*Re + Im*Im , 0.5 );
}
void complexNumber::print()
{
cout<<"the complex number is " << Re <<" + "<<Im<<"i"<<endl;
}
//point and rectangle classes
#include <iostream>
#include <cmath>
using namespace std;
// point:
class point
{
public:
double x;
double y;
point( double a, double b);
point();
void scale ( double k );
void add ( point q );
void print();
void Input();
void xSelectionSortPoints(point A[], int n);
void swap(point &, point &);
int arraySmallest(point *A,int start,int finish);
};
point::point(double a, double b)
{
x=a;
y=b;
}
point::point()
{
x=0;
y=0;
}
void point::scale(double k)
{
x=k*x;
y=y*k;
}
void point::add( point q)
{
x=x+q.x;
y=y+q.y;
}
void point::Input()
{
int a,b;
cin>>a>>b;
x=a;
y=b;
}
void point::print()
{
cout<<x<<" "<<y;
}
//rectangle:
class rectangle
{
public:
rectangle ( point l , point r );
rectangle ();
double area();
void scale(double k);
void translate(point q);
bool containsPoint(point p);
void pointSetIntersect(point A[],int n,point B[],int &m);
point left;
point right;
};
rectangle::rectangle( point l, point r)
{
left = l;
right= r;
}
rectangle::rectangle()
{
left.x =0;
left.y =0;
right.x=0;
right.y=0;
}
double rectangle::area()
{
return ( ((right.y)-(left.y)) *(( right.x)-(left.x)) );
}
void rectangle::scale(double k)
{
left.x =k*left.x;
left.y =k*left.y;
right.x=k*right.x;
right.y=k*right.y;
}
void rectangle::translate(point q)
{
left.x =q.x + left.x;
left.y = q.y +left.y;
right.x= q.x +right.x;
right.y= q.y +right.y;
}
bool rectangle::containsPoint(point p)
{
if((p.x<=right.x)&&(p.x>=left.x)&&(p.y<=right.y)&&(p.y>=left.y))
return true;
else
return false;
}
void rectangle::pointSetIntersect(point A[], int n, point B[], int &m)
{
int i=0,j=0;
for (i=0;i<n;i++)
{
if (containsPoint(A[i])==true)
{
B[j]=A[i];
j++;
}
}
m=j;
}
//selection sort:
int point::arraySmallest(point *A,int start,int end)
{
int min=start;
for(int i=start;i<=end;i++){
if (A[i].x<A[min].x)
min=i;
}
return min;
}
void point::swap(point &a, point &b)
{
point temp = a;
a = b;
b = temp;
}
void point::xSelectionSortPoints(point A[], int n)
{
for(int i=0;i<n-1;i++){
swap(A[i],A[arraySmallest(A,i,n-1)]);
}
for (int j=0;j<n;j++){
cout<<A[j].x<<" ";
cout<<A[j].y<<" ";
cout<<endl;
}
}
int main()
{
//point:
point x(2,2);
point y(4,4);
x.scale(5);
x.print();
cout<<endl;
x.add(y);
x.print();
cout<<endl;
point A[4];
A[0].x=6; A[0].y=6;
A[1].x=2; A[1].y=2;
A[2].x=1; A[2].y=1;
A[3].x=4; A[3].y=4;
A[0].xSelectionSortPoints(A,4);
// rectangle:
point left(2,2);
point right(4,4);
rectangle R(left ,right);
cout<<"the area is:"<<R.area()<<endl;
R.scale(2);
cout<<"after scaling:"<<endl;
cout<<"the first point is:";
R.left.print();
cout<<endl;
cout<<"the second point is:";
R.right.print();
cout<<endl;
point b(1,1);
R.translate(b);
cout<<"after translating:"<<endl;
cout<<"the first point is:";
R.left.print();
cout<<endl;
cout<<"the second point is:";
R.right.print();
cout<<endl;
point c(6,6);
if(R.containsPoint(c) )
cout<<"the point c(6,6) is inside"<<endl;
else cout<<"not inside"<<endl;
point B[4];
int n;
R.pointSetIntersect(A,4,B,n);
for (int i=0; i<n; i++)
B[i].print();
cout<<endl;
return 0;
}
#include <iostream>
using namespace std;
class myDynamicArray
{
public:
int * A;
int size;
myDynamicArray(int v);
myDynamicArray();
~myDynamicArray();
int sequentialSearch(int );
void print();
void insertionSort();
void copy(myDynamicArray & );
void concatenate(myDynamicArray & );
void InputArray();
};
int main()
{
int n;
cin>>n;
cout<<endl;
myDynamicArray a(n);
a.InputArray();
cout<<a.sequentialSearch(2)<<endl;
cout<<endl;
a.insertionSort();
cout<<endl;
a.print();
cout<<endl;
return 0;
}
myDynamicArray::myDynamicArray()
{
A=NULL;
size=0;
}
myDynamicArray::myDynamicArray(int v)
{
size=v;
A=new int[size];
for(int i=0;i<size;i++)
A[i]=0;
}
myDynamicArray::~myDynamicArray()
{
if (A!=NULL)
delete [] A;
}
int myDynamicArray::sequentialSearch(int x)
{
for(int i=0; i<size; i++)
if(A[i]==x) return i;
return -1;
}
void myDynamicArray::print()
{
for(int i=0;i<size;i++)
cout<<A[i]<<" ";
cout<<endl;
}
void myDynamicArray::InputArray()
{
for(int i=0;i<size;i++)
cin>>A[i];
cout<<endl;
}
void myDynamicArray::insertionSort()
{
for(int j=1;j<size;j++)
{
int key = A[j];
int i = j-1;
while(i>=0 && A[i] > key)
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
return;
}
void myDynamicArray::copy(myDynamicArray & B )
{
delete []A;
A=new int[B.size];
size=B.size;
for(int i=0; i<size; i++)
A[i]=B.A[i];
}
void myDynamicArray::concatenate(myDynamicArray & Q )
{
int *temp= new int [ size + Q.size];
for(int i=0;i<size;i++)
temp[i]=A[i];
for(int j=size; j< size+ Q.size ; j++)
temp[j]= Q.A[j-size];
delete[] A;
A=temp;
size=size + Q.size;
}
EECE 230 Introduction to Programming, Sections 2,6,10
Programming Assignment 9
Thur May 3, 2007
• This programming assignment consists of 3 problems.
• It is due on Tue May 8 in the Lab
• Related material: Structures and Classes up to Lecture 21 (Tue May 8).
You can do Problems 1 and 2 using the material up to Lecture 20 (Thurs May 3). In Problem 3,
you need material from Lecture 21. You are expected to do it in the Lab on Tue May 8.
• Lab structure and regulations:
⋆ The 3 hours Lab session is on Tuesdays in Lab rooms 2,3, and 4 from 3:30 pm to 6:30 pm. It
consists of three parts:
- Occasional Solving Session (not graded but attendance mandatory)
- Programming Assignment (graded)
Programming Assignments will be posted on WebCT on weekly basis. Typically, a Pro-
gramming Assignment requires much more than the time allocated for this part in the
Lab, so you are supposed to complete the major part of the assignment at home. The Lab
instructor will grade your assignment and can help you with the problems you are facing.
- Occasional graded weekly quiz
⋆ You are supposed to submit your own work. Cheating will not be tolerated and will be dealt
with severely: zero grades on the programming assignments, disciplinary committee, Dean’s
warning.
⋆ Lab attendance is mandatory. Violating this rule can lead to a failing grade.
Problem 1 (Complex number class)
Design a class complexNumber that defines complex numbers as an Abstract Data Type (ADT).
Include the member functions:
• complexNumber :: complexNumber(double, double) // constructor
• complexNumber :: complexNumber() // default constructor
• void complexNumber :: add(complexNumber &)
• void complexNumber :: multiply(complexNumber &)
• void complexNumber :: divide(complexNumber &)
• double complexNumber :: norm() // the norm of x + iy is
�
x2 + y2
• void complexNumber :: print()
For example you should be able to use the class as follows:
1
complexNumber
z(2,3);
cout<<’’z = ’’;z.print();
// z = 2+3i
complexNumber
w;
cout<<’’w = ’’;w.print();
// w = 0+0i
w = z;
cout<<’’w = ’’;w.print();
// w = 2+3i
w.x = 1;
cout<<’’w = ’’;w.print();
// w = 1+3i
z.add(w);
cout<<’’z = ’’;z.print();
// z = 3+6i
z.multiply(w); // z = (3+6i)(1+3i)
cout<<’’z = ’’;z.print();
// z = -15 + 15 i
cout<< w.norm();
// 3.1623
Use the above program to test your class.
(Note: We will study later a better implementation of this class based on operator overloading.)
Problem 2 (point and rectangle classes)
a) Design a class point that defines a planar point as an Abstract Data Type.
Include the member functions:
• Non-default constructor which allows the user to initialize a planar point by specifying its x
and y coordinates
• Default constructor
• Scale function
void point :: scale(double a)
This function is supposed to scale the coordinates of the point by a, i.e., multiply each by the
real number a.
• Add function
void point :: add(point q)
If p and q are of type point. The function p.add(q) should modify p in such a way that p.x is
assigned p.x + q.x, and p.y is assigned p.y + q.y.
(Note: We will study later a better implementation of this class based on operator overloading.)
b) Modify the selectionSort function so that, instead of taking an array of integers, it takes an array
of points and sorts them in order of increasing x-coordinates.
Call it xSelectionSortPoints. Its prototype is thus
void
xSelectionSortPoints(point A[], int n)
c) Based on the class point, design a class rectangle that defines a rectangle as an Abstract Data
Type.
In this problem, by a rectangle we mean a rectangle whose edges are either vertical or horizontal
(i.