C++ Algorithm and Data Structure Code Examples
Eratosthenes
Prime Number Checker
This code checks if a given number is prime using the Sieve of Eratosthenes algorithm.
#include
#include
#include
using namespace std;
const int Max = 1000;
int main() {
vector es_primer(1000001, true);
es_primer[0] = es_primer[1] = false;
for (int i = 2; i < Max; ++i) {
if (es_primer[i]) {
for (int m = 2 * i; m <= Max * Max; m += i) {
es_primer[m] = false;
}
}
}
int x;
while (cin >> x) {
cout << x;
if (es_primer[x])
cout << " es primer" << endl;
else
cout << " no es primer" << endl;
}
}
Intersection of Arrays
Finding Common Elements
This code finds the intersection of two sorted arrays.
#include
#include
using namespace std;
vector interseccio(const vector& v1, const vector& v2) {
int tam1 = v1.size();
int tam2 = v2.size();
vector aux(tam1 + tam2);
int i, j, k;
i = j = k = 0;
while (i < tam1 and j < tam2) {
if (v1[i] > v2[j])
++j;
else if (v1[i] < v2[j])
++i;
else {
double x = v1[i];
++i;
while (i < tam1 and (v1[i] == x))
++i;
++j;
while (j < tam2 and (v2[j] == x))
++j;
aux[k] = x;
++k;
}
}
vector resultat(k);
for (i = 0; i < k; ++i)
resultat[i] = aux[i];
return resultat;
}
int main() {
vector v1(5);
vector v2(5);
for (int i = 0; i < 5; ++i)
cin >> v1[i];
for (int i = 0; i < 5; ++i)
cin >> v2[i];
vector intr;
intr = interseccio(v1, v2);
for (int i = 0; i < intr.size(); ++i)
cout << intr[i] << ' ';
cout << endl;
}
Digital Rivers
Finding the Meeting Point
This code calculates the meeting point of digital rivers.
#include
#include
using namespace std;
int suma_digits(int n) {
if (n == 0)
return 0;
else
return n % 10 + suma_digits(n / 10);
}
int seguent(int n) {
return n + suma_digits(n);
}
int trobada_de_rius(int n) {
int r1 = 1, r3 = 3, r9 = 9;
while (n != r1 and n != r3 and n != r9) {
if (r1 > n and r3 > n and r9 > n)
n = seguent(n);
if (r3 < n)
r3 = seguent(r3);
if (r9 < n)
r9 = seguent(r9);
if (r1 < n)
r1 = seguent(r1);
}
return n;
}
Sorting
Sorting an Array in Descending Order
This code sorts an array in descending order.
#include
#include
#include
using namespace std;
bool ordena(int a, int b) {
return a > b;
}
int main() {
int n;
while (cin >> n) {
vector v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
sort(v.begin(), v.end(), ordena);
bool c = true;
for (int i = 0; i < n; ++i) {
if (c)
c = false;
else
cout << " ";
cout << v[i];
}
cout << endl;
}
}
Anagrams
Checking for Anagrams
This code checks if two phrases are anagrams of each other.
#include
#include
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
vector frase1(26, 0);
vector frase2(26, 0);
char c;
while (cin >> c and c != '.') {
if (c >= 'A' and c <= 'Z')
frase1[c - 'A'] += 1;
}
while (cin >> c and c != '.') {
if (c >= 'A' and c <= 'Z')
frase2[c - 'A'] += 1;
}
if (frase1 == frase2)
cout << "SI" << endl;
else
cout << "NO" << endl;
}
}