Introduction to Computer Science - Exercise 10

Name: Saggi Mizrahi • ID: 032493124 • Group: מעוף א' • Date: December 23, 2013

Recursion

6.

Code:

/* minmaxdesc.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

void printInBinary(int num);

// print the value of input num in binary
void printInBinary(int num) {
    int d = num % 2;
    num /= 2;
    if (num > 0) {
        printInBinary(num);
    }
    cout << d;
}

// prints out the input number's value in binary.
// input: an integer
// output: the inputs representation in binary.
int main()
{
    int num;
    cout << "enter a number: ";
    cin >> num;
    printInBinary(num);
    cout << endl;
}

Outputs:

enter a number: 20
10100

enter a number: 0
0

enter a number: 204
11001100

7.

Code:

/* stringrec.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

const int MAX_STEPS = 2;

int numWays(int n);

// returns the number of ways an n long ledder can be climbed
int numWays(int n) {
    int res = 0;
    if (n == 0) {
        return 1;
    } else {
        for (int i = 1; i <= MAX_STEPS && i <= n; i++) {
            res += numWays(n - i);
        }
        return res;
    }
}


// prints out the number of ways an n long ledder can be climbed
// input: the length of the ladder
// output: the number of ways the ladder can be climbed
int main()
{
    int n;
    cout << "enter a number: ";
    cin >> n;
    cout << "there are " << numWays(n) << " ways to climb this ledder";
}

Outputs:

enter a number: 4
there are 5 ways to climb this ledder

enter a number: 10
there are 89 ways to climb this ledder

enter a number: 22
there are 28657 ways to climb this ledder

8.

Code:

/* stringrec.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

void printPrimeFactors(int num);

// prints out the prime factors of num
void printPrimeFactors(int num) {
    for (int i = 2; i < num; i++) {
        if ((num % i) == 0) {
            cout << i << " ";
            printPrimeFactors(num / i);
            return;
        }
    }
    cout << num << endl;
    return;
}

// prints out the prime factors of num
// input: a number
// output: the the prime factors of num
int main()
{
    int n;
    cout << "enter a number: ";
    cin >> n;
    printPrimeFactors(n);
}

Outputs:

enter a number: 20
2 2 5

enter a number: 2
2

enter a number: 22
2 11

9.

Code:

/* stringrec.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

void find2factor(int num, int& k, int& m);

void find2factor(int num, int& k, int& m) {
    if (num == 2) {
        k = 1;
        m = 0;
    } else if ((num % 2) == 1) {
        k = 0;
        m = num;
    } else {
        find2factor(num / 2, k, m);
        k++;
    }
}

// prints out the prime factors of num
// input: a number
// output: the the prime factors of num
int main()
{
    int n, k, m;
    cout << "enter a number: ";
    cin >> n;
    find2factor(n, k, m);
    cout << "2^" << k << " * " << m << endl;
}

Outputs:

enter a number: 40
2^3 * 5

enter a number: 41
2^0 * 41

enter a number: 22
2^1 * 11

Arrays

14.

Code:

/* elements.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

bool haveSameElems(int arr1[], int arr2[], int size);
void swap(int a[], int i1, int i2);
void readArray(int arr[], int n);

void swap(int a[], int i1, int i2) {
    int tmp = a[i1];
    a[i1] = a[i2];
    a[i2] = tmp;
}


// checks if both arrays contain the same items.
bool haveSameElems(int arr1[], int arr2[], int size) {
    if (size == 0) {
        return true;
    }
    for (int i = 0; i < size; i++) {
        if (arr2[i] == arr1[0]) {
            swap(arr2, 0, i);
            return haveSameElems(arr1 + 1, arr2 + 1, size - 1);
        }
    }
    return false;
}


void readArray(int arr[], int n) {
    cout << "enter " << n << " numbers: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
}

// checks if both input arrays contain the same items
// input: 2 integer arrays
// output: whether they both have the same items.
int main()
{
    const int SIZE = 5;
    int arr1[SIZE];
    int arr2[SIZE];
    readArray(arr1, SIZE);
    readArray(arr2, SIZE);
    cout << "both arrays ";
    if (!haveSameElems(arr1, arr2, SIZE)) {
        cout << "don't ";
    }
    cout << "have the same elements" << endl;
}

Outputs:

enter 5 numbers: 2 5 6 2 1
enter 5 numbers: 1 2 6 5 2
both arrays have the same elements

enter 5 numbers: 2 5 6 2 1
enter 5 numbers: 1 2 6 5 1
both arrays don't have the same elements

15.

Code:

/* sumparts.cpp
 *
 * Saggi Mizrahi 16 December 2013
 */
#include <iostream>

using namespace std;

bool subsetSum(int numbers[], int size, int sum);
void swap(int a[], int i1, int i2);
void readArray(int arr[], int n);

void swap(int a[], int i1, int i2) {
    int tmp = a[i1];
    a[i1] = a[i2];
    a[i2] = tmp;
}


bool subsetSum(int numbers[], int size, int sum) {
    if (size == 0) {
        return sum == 0;
    }
    if (numbers[0] <= sum) {
        if (subsetSum(numbers + 1, size - 1, sum - numbers[0])) {
            return true;
        }
    }
    return subsetSum(numbers + 1, size - 1, sum);
}


void readArray(int arr[], int n) {
    cout << "enter " << n << " numbers: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
}

// checks if sum exists inside aray
// input: an integer array and a sum
// output: whether the sum can be composed of any array elements
int main()
{
    const int SIZE = 5;
    int arr[SIZE];
    int sum;
    readArray(arr, SIZE);
    cout << "please enter sum: ";
    cin >> sum;
    cout << "sum does ";
    if (!subsetSum(arr, SIZE, sum)) {
        cout << "not ";
    }
    cout << "exist in array" << endl;
}

Outputs:

enter 5 numbers: 1 5 3 9 10
please enter sum: 14
sum does exist in array

enter 5 numbers: 1 5 3 9 10
please enter sum: 19
sum does exist in array

enter 5 numbers: 1 5 3 9 10
please enter sum: 28
sum does exist in array

enter 5 numbers: 1 5 3 9 10
please enter sum: 29
sum does not exist in array