1. Homepage of Dr. Zoltán Porkoláb
    1. Home
    2. Archive
  2. Teaching
    1. Timetable
    2. Bolyai College
    3. C++ (for mathematicians)
    4. Imperative programming (BSc)
    5. Multiparadigm programming (MSc)
    6. Programming (C in English)
    7. Programming languages (PhD)
    8. Software technology lab
    9. Theses proposals (BSc and MSc)
  3. Research
    1. CodeChecker
    2. CodeCompass
    3. Templight
    4. Projects
    5. Publications
    6. PhD students
  4. Affiliations
    1. Dept. of Programming Languages and Compilers
    2. Ericsson Hungary Ltd

Practice 7.

Bubble sort

Write a program which uses the Bubble sort algorithm to sort an
integer vector. Give the input vector as a local variable and initialize it, and print the values of the sorted vector at the end of the program.

Solution

Video:

cpp-mat-gyak7-1_bubblesort.mp4

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
#include <iostream>
#include <vector>

void sort(std::vector<int>& numbers);

int main()
{
  std::vector<int> nums = { 3, 7, 1, 8, 2, 0 };
  sort(nums);
  for (size_t i = 0; i < nums.size(); ++i)
  {
    std::cout << nums[i] << ", ";
  }
}

void sort(std::vector<int>& numbers)
{
  for (size_t i = 0; i < numbers.size() - 1; ++i)
  {
    for (size_t j = 0; j < numbers.size() - i - 1; ++j)
    {
      if (numbers[j] > numbers[j + 1])
      {
	/* traditional solution with temporary variable
        int temp = numbers[i];
	numbers[i] = numbers[j];
	numbers[j] = temp; 
	*/
	// cost-effective solution for integers 
        // using arithmetic operators
	numbers[j + 1] += numbers[j];
	numbers[j] = numbers[j + 1] - numbers[j];
	numbers[j + 1] = numbers[j + 1] - numbers[j];
      }
    }
  }
}

The expected output:

$ ./a.out 
0, 1, 2, 3, 7, 8,

Caesar cipher

Write a program which uses the caesar cipher algorithm to encoding the input from standard input and write the result to the standard output.

Solution

Video:

cpp-mat-gyak7-2_caesar.mp4

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
#include <iostream>
#include <sstream>

const int DEFAULT = 3;

char shift(const char& orig, const int offset);

int main(int argc, char** argv)
{
  if (argc > 1)
  {
    int offset;
    std::istringstream ss(argv[1]);

    int firstArg = 2;
    if (!(ss >> offset)) // read from ss to offset
    {
      // default value if offset is not provided
      offset = DEFAULT;  
      firstArg = 1;
    }
    // Shift every character of every word
    std::string current;
    for (int i = firstArg; i < argc; ++i)
    {
      current = argv[i];
      for (int j = 0; j < current.size(); ++j)
      {
        std::cout << shift(current.at(j), offset);  
        // same as: shift(current[j], offset);
      }
      std::cout << " ";
    }
    std::cout << std::endl;
  }
  else
  {
    std::cout << 
      "There are no command line arguments provided!" 
              << std::endl;
    return 1;
  }
}

char shift(const char& orig, const int offset)
{
  // If we try shifting a letter from the end of the alphabet,
  // we make it circular.
  if (orig >= 'A' + 26 - offset)
  {
    return (char)(orig + offset - 26);
  }
  return (char)(orig + offset);
}

The expected output:

$ ./a.out VENI VIDI VICI
YHQL YLGL YLFL 

Factorization

Write a program for prime factorization. Print the factors of integers.

Solution

Video:

cpp-mat-gyak7-3_factorization.mp4

The factorization.h header file:

1
2
3
4
5
6
7
8
9
#ifndef FACTORIZATION_H
#define FACTORIZATION_H

#include <vector>
bool isPrime(const int num);
std::vector<int> factorization(int num, 
                               const std::vector<int>& primes);
void printVector(const std::vector<int>& v);
#endif

The factorization.cpp source 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
#include <iostream>
#include <algorithm>
#include "factorization.h"

bool isPrime(const int num)
{
  for (int i = 3; i < num / 2; ++i)
  {
    if (num % i == 0)
    {
      return false;
    }
  }
  return true;
}

std::vector<int> factorization(int num,
                               const std::vector<int>& primes)
{
  std::vector<int> factors;
	
  while (num > 1)
  {
    // If a number is a prime, we return
    if (std::find(primes.begin(), primes.end(), num) 
                                             != primes.end())
    {
      factors.push_back(num);
      return factors;
    }
    for (size_t i = 0; i < primes.size(); ++i)
    {
      if (num % primes[i] == 0)  
                        // same as: if (!(num % primes[i]))
      {
        factors.push_back(primes[i]);
	num /= primes[i];
	break;
      }
    }
  }
  return factors;
}

void printVector(const std::vector<int>& v)
{
  for (size_t i = 0; i < v.size(); ++i)
  {
    std::cout << v.at(i) << " ";
  }
  std::cout << std::endl;
}

The main.cpp source to test the 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 "factorization.h"

int main()
{
  // Collect prime numbers up to 1000
  std::vector<int> primes;
  primes.push_back(2);
  for (int i = 3; i < 1000; i += 2)
  {
    if (isPrime(i))
    {
      primes.push_back(i);
    }
  }
  int test = 210;
  std::vector<int> fact = factorization(test, primes);
  printVector(fact);
	
  test = 244;
  fact = factorization(test, primes);
  printVector(fact);
	
  test = 6666;
  fact = factorization(test, primes);
  printVector(fact);
}

The expected output:

$ ./a.out
2 3 5 7
2 2 61
2 3 11 101

Representing rational numbers

Implement a data structure to represent rational numbers in the form of nominator / denominator. Write operations between rational numbers.

Solution

Video:

cpp-mat-gyak7-4_fractions.mp4

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
#include <iostream>
#include <vector>

struct Fraction
{
  int nominator;
  int denominator;
};

Fraction sum(Fraction, Fraction);
Fraction sub(Fraction, Fraction);
Fraction mul(Fraction, Fraction);
Fraction div(Fraction, Fraction);
Fraction operator +(Fraction x, Fraction y);
Fraction operator -(Fraction x, Fraction y);
Fraction operator *(Fraction x, Fraction y);
Fraction operator /(Fraction x, Fraction y);

int main()
{
  Fraction f1 = { 1, 4 };
  Fraction f2;
  f2.nominator = 1;
  f2.denominator = 2;
	
  Fraction f3 = sum(f1, f2);
  std::cout << f3.nominator << "/" << f3.denominator
                                   << std::endl;
  Fraction f3a = f1 + f2;
  std::cout << f3a.nominator << "/" << f3a.denominator 
                                    << std::endl;
	
  Fraction f4 = sub(f1, f2);
  std::cout << f4.nominator << "/" << f4.denominator 
                                   << std::endl;
	
  Fraction f5 = mul(f1, f2);
  std::cout << f5.nominator << "/" << f5.denominator 
                                   << std::endl;
	
  Fraction f6 = div(f1, f2);
  std::cout << f6.nominator << "/" << f6.denominator 
                                   << std::endl;
  
  // std::vector<Fraction> f;
}

Fraction sum(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator
                          + y.nominator * x.denominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction operator +(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator 
                          + y.nominator * x.denominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction sub(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator
                          - y.nominator * x.denominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction operator -(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator
                         - y.nominator * x.denominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction mul(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.nominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction operator *(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.nominator, 
                   x.denominator * y.denominator };
  return res;
}

Fraction div(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator, 
                   x.denominator * y.nominator };
  return res;
}

Fraction operator /(Fraction x, Fraction y)
{
  Fraction res = { x.nominator * y.denominator, 
                   x.denominator * y.nominator };
  return res;
}

The expected output:

$ ./a.out
6/8
6/8
-2/8
1/8
2/4

Financed from the financial support ELTE won from the Higher Education Restructuring Fund of the Hungarian Government.