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:
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 101Representing rational numbers
Implement a data structure to represent rational numbers in the form of nominator / denominator. Write operations between rational numbers.
Solution
Video:
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.