COMP 104 : Programming

Week 7 : Extra Programming Exercise (Answer)


// extra7-1.cpp
// Program to demonstrate the recursive function for linear search

#include <iostream>
#include <fstream>
using namespace std;

const int Array_Size = 10;

void search(const int A[], int start, int size, int key, bool& found, int& location);

int main(){
    int A[Array_Size];
    const int final_index = Array_Size -1;
    ifstream in;
    in.open("data.dat");
    for(int i=0; i< Array_Size; i++)
        in >> A[i];
    in.close();
    int key, location;
    bool found = false;
    cout << "Enter number to be located: ";
    cin >> key;
    search(A, 0, final_index, key, found, location);
    if (found)
        cout << key << " is in index location " << location + 1 << endl;
    else
        cout << key << " is not in the array." << endl;
    return 0;
}

void search(const int A[], int start, int size, int key, bool& found, int& location){
    if(start<=size)
    {
        if (key == A[start])
        {
            found = true;
            location = start;
        }
        else
            search(A, start+1, size, key, found, location);
    }
}

// extra7-2.cpp
// Find the Greatest Common Divisor for two number

#include <iostream>
using namespace std;

int gcd(int m, int n);

void main(){
    int m, n, ans;
    cout << "Input the two integers: \n";
    cin >> m >> n;
    if (m < n)
    {
        int temp;
        temp = n;
        n = m;
        m = temp;
    }
    ans = gcd(m,n);
    cout << "The GCD of " << m << " and " << n << " is " << ans << endl;
}

int gcd(int m, int n)
{
    if(m%n == 0)                                        // Terminate Condition that m is divisible by n
        return n;
    else
        return gcd(m, m%n);
}


// extra7-3.cpp
// Program to demonstrate the recursive function for binary search

#include <iostream>
#include <fstream>
using namespace std;

const int Array_Size = 10;

void search(const int A[], int first, int last, int key, bool& found, int& location);

int main(){
    int A[Array_Size];
    const int final_index = Array_Size -1;
    ifstream in;
    in.open("sort_data.dat");
    for(int i=0; i< Array_Size; i++)
        in >> A[i];
    in.close();
    int key, location;
    bool found;
    cout << "Enter number to be located: ";
    cin >> key;
    search(A, 0, final_index, key, found, location);

    if (found)
        cout << key << " is in index location " << location + 1 << endl;
    else
        cout << key << " is not in the array." << endl;
    return 0;
}

void search(const int A[], int first, int last, int key, bool& found, int& location){
    int mid;
    if (first > last)                               // Terminate condition
        found = false;
    else {
        mid = (first + last) / 2;
        if (key == A[mid])
        {
            found = true;
            location = mid;
        }
        else if (key < A[mid])                     // If the value smaller than the mid value,
                                                   // it must lay on the front of the list.
            search(A, first, mid-1, key, found, location);
        else if (key > A[mid])                     // If the value larger that the mid value,
                                                   // it must lay on the back of the list.
            search(A, mid+1, last, key, found, location);
    }
}

// extra7-4.cpp
// Program to demonstrate the recursive function for selection sort

#include <iostream>
#include <fstream>
using namespace std;

int select(int number[], int size);
int number[10];

void main(){
    ifstream in;
    in.open("data.dat");
    for (int i = 0; i< 10; i++)
        in >> number[i];
    in.close();
    select(number, 10);
    for (int j = 0; j< 10; j++)
        cout << number [j] << " ";
    cout << endl;
}

int select(int number[], int size)
{
    int temp;
    int max_index;
    if(size <= 0)
        return -1;
    else
    {
        max_index = 0;
        for (int i = 1; i<=size-1; i++)
            if (number[i] > number[max_index])
                max_index = i;
        // Swap two number
        if (number[max_index] > number[size-1]){
            temp = number[max_index];
            number[max_index] = number[size-1];
            number[size-1] = temp;
        }
        return (select(number, size-1));
    }
}

// extra7-5.cpp
// Program to demonstrate the recursive function for bubble sort

#include <iostream>
#include <fstream>
using namespace std;

int bubble(int number[], int size);
int number[10];

void main(){
    ifstream in;
    in.open("data.dat");
    for (int i = 0; i< 10; i++)
        in >> number[i];
    in.close();
    bubble(number, 10);
    for (int j = 0; j< 10; j++)
        cout << number [j] << " ";
    cout << endl;
}

int bubble(int number[], int size)
{
    int temp;
    if(size <= 0)
        return -1;
    else
    {
        for (int i = 0; i<size-1; i++){
            if (number[i] > number[i+1]){
                temp = number[i];
                number[i] = number[i+1];
                number[i+1] = temp;
            }
        }
        return (bubble(number, size-1));
   }
}