diff options
Diffstat (limited to '1_anno/Programmazione_2')
56 files changed, 0 insertions, 5320 deletions
diff --git a/1_anno/Programmazione_2/algorithms/binarysearch.cc b/1_anno/Programmazione_2/algorithms/binarysearch.cc deleted file mode 100644 index c9b4cd7..0000000 --- a/1_anno/Programmazione_2/algorithms/binarysearch.cc +++ /dev/null @@ -1,33 +0,0 @@ -#include<iostream> - -using namespace std; - -bool bs(int a[], int i, int j, int x) { - if(j<i) return false; - int mid = i+(j-i)/2; - if(a[mid] == x) - return true; - if(a[mid] > x) - return bs(a, i, mid-1, x); - return bs(a, mid+1, j, x); -} - -bool bs2(int a[], int i, int j, int x) { - while(i <= j) { - int mid = i+(j-i)/2; - if(a[mid] == x) return true; - if(a[mid] < x) - i = mid+1; - else - j = mid-1; - } - return false; -} - -int main() { - int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; - for(int i = 0; i < 12; ++i) - cout << i << ' '<<bs(a, 0, 9, i) << ' ' << bs2(a, 0, 9, i) << endl; - return 0; -} - diff --git a/1_anno/Programmazione_2/algorithms/cbrt.cc b/1_anno/Programmazione_2/algorithms/cbrt.cc deleted file mode 100644 index 30c7792..0000000 --- a/1_anno/Programmazione_2/algorithms/cbrt.cc +++ /dev/null @@ -1,37 +0,0 @@ -#include<iostream> - -using namespace std; - -int cbrt(int n) { - int i = 0; - int j = n; - int q = (i+j)/2; - while(q*q*q != n) { - q = (i+j)/2; - if(q*q*q < n) - i=q; - else - j=q; - } - return q; -} - -double cbrt2(int n) { - int i = 1; - while(i*i*i <= n) - ++i; - // precision - - --i; - while(i*i*i < n) - i+=0.000001; - - return i; -} - -int main() { - int i; - cin >> i; - cout << i << ' ' << cbrt(i) << endl; - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/insertionsort.cc b/1_anno/Programmazione_2/algorithms/insertionsort.cc deleted file mode 100644 index 9b309d6..0000000 --- a/1_anno/Programmazione_2/algorithms/insertionsort.cc +++ /dev/null @@ -1,42 +0,0 @@ -#include<iostream> - -using namespace std; - -void insertionsort(int a[], int n) { - for(int i = 1; i < n; ++i) { - int j = i-1; - int key = a[i]; - while(j > -1 && a[j] > key) { - swap(a[j+1], a[j]); - --j; - } - a[j+1] = key; - } -} - -void insertionsort_rec(int a[], int n) { - if(n < 2) return; - insertionsort_rec(a, n-1); - - int key = a[n-1]; - int j = n-2; - - while(j > -1 && a[j] > key) { - swap(a[j+1], a[j]); - --j; - } - - a[j+1] = key; - -} - -int main() { - int arr[10] = {3, 450, 12, 4, -1, 0, 24, 95, 123, 0}; - for(int i = 0; i < 10; ++i) - cout << *(arr+i) << ' '; - cout << endl; - insertionsort_rec(arr, 10); - for(int i = 0; i < 10; ++i) - cout << *(arr+i) << ' '; - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/log.cc b/1_anno/Programmazione_2/algorithms/log.cc deleted file mode 100644 index 1e49a2e..0000000 --- a/1_anno/Programmazione_2/algorithms/log.cc +++ /dev/null @@ -1,25 +0,0 @@ -#include<iostream> - -using namespace std; - -double log(double n) { - if(n <= 2) return 1.0; - return 1.0 + log(n/2); -} - -int log2(double n) { - int a = 1; - - while(n > 2) { - n /= 2; - ++a; - } - - return a; -} - -int main() { - for(int i = 0; i < 25; ++i) - cout << i << ' ' << log(i) << ' ' << log2(i) << endl; - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/mergesort.cc b/1_anno/Programmazione_2/algorithms/mergesort.cc deleted file mode 100644 index 68d28cb..0000000 --- a/1_anno/Programmazione_2/algorithms/mergesort.cc +++ /dev/null @@ -1,52 +0,0 @@ -#include<iostream> - -using namespace std; - -void merge(int A[], int l, int q, int r) { - int i = l; - int j = q+1; - int k = l; - int B[r]; - - while((i <= q) && (j <= r)) { - if(A[i] <= A[j]) - B[k] = A[i++]; - else - B[k] = A[j++]; - - k++; - } - - while(i <= q) - B[k++] = A[i++]; - - while(j <= r) - B[k++] = A[j++]; - - for(k = l; k <= r; ++k) - A[k] = B[k]; -} - -void mergesort(int A[], int l, int r) { - if(l < r) { - int q = (l+r)/2; - mergesort(A, l, q); - mergesort(A, q+1, r); - merge(A, l, q, r); - } -} - - -int main() { - int a[] = {7,1,22,3,2,12,27,31,6}; - for(int i = 0; i < 9; ++i) { - cout << a[i] << ' '; - } - cout << endl; - mergesort(a, 0, 8); - for(int i = 0; i < 9; ++i) { - cout << a[i] << ' '; - } - - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/pow.cc b/1_anno/Programmazione_2/algorithms/pow.cc deleted file mode 100644 index 16cf419..0000000 --- a/1_anno/Programmazione_2/algorithms/pow.cc +++ /dev/null @@ -1,25 +0,0 @@ -#include<iostream> - -using namespace std; - -int pow(int x, int y) { - int a = 1; - - for(int i = 0; i < y; ++i) - a*=x; - - return a; -} - - -int pow2(int x, int y) { - if(y < 1) return 1; - - return x*pow(x, y-1); -} - -int main() { - cout << pow(2, 5) << endl; - cout << pow2(2, 5) << endl; - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/quicksort.cc b/1_anno/Programmazione_2/algorithms/quicksort.cc deleted file mode 100644 index 795bd7b..0000000 --- a/1_anno/Programmazione_2/algorithms/quicksort.cc +++ /dev/null @@ -1,38 +0,0 @@ -#include<iostream> - -using namespace std; - -int partition(int A[], int l, int r) { - int x = A[r]; - int i = l-1; - - for(int j = l; j < r; ++j) { - if(A[j] <= x) { - swap(A[++i], A[j]); - } - } - swap(A[++i], A[r]); - return i; -} - -void quicksort(int A[], int l, int r) { - if(l < r) { - int q = partition(A, l, r); - quicksort(A, l, q-1); - quicksort(A, q+1, r); - } -} - -int main() { - int a[] = {7,1,22,3,2,12,27,31,6}; - for(int i = 0; i < 9; ++i) { - cout << a[i] << ' '; - } - cout << endl; - quicksort(a, 0, 8); - for(int i = 0; i < 9; ++i) { - cout << a[i] << ' '; - } - - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/selectionsort.cc b/1_anno/Programmazione_2/algorithms/selectionsort.cc deleted file mode 100644 index 57dcc17..0000000 --- a/1_anno/Programmazione_2/algorithms/selectionsort.cc +++ /dev/null @@ -1,46 +0,0 @@ -#include<iostream> -#include<algorithm> - -using namespace std; - -void selectionsort(int a[], int n) { - for(int i = 0; i < n-1; ++i) { - int min = i; - for(int j = i+1; j < n; ++j) { - if(a[j] < a[min]) - min = j; - } - - swap(a[min], a[i]); - } -} - -int min_i(int a[], int i, int j) { - if(i == j) return i; - - int k = min_i(a, i+1, j); - return (a[i] < a[k]) ? i : k; -} - -void selectionsort_rec(int* a, int b, int e=0) { - if(b == e) return; - - int key = min_i(a, e, b-1); - if(key != e) - swap(a[key], a[e]); - - selectionsort_rec(a, b, e+1); -} - -int main() { - int arr[] = {3,450,12,4,-1,0,24,95,123,0}; - for(int i = 0; i < 10; ++i) { - cout << *(arr+i) << ' '; - } - cout << endl; - selectionsort_rec(arr, 10); - for(int i = 0; i < 10; ++i) { - cout << *(arr+i) << ' '; - } - return 0; -} diff --git a/1_anno/Programmazione_2/algorithms/sqrt.cc b/1_anno/Programmazione_2/algorithms/sqrt.cc deleted file mode 100644 index aa6b032..0000000 --- a/1_anno/Programmazione_2/algorithms/sqrt.cc +++ /dev/null @@ -1,46 +0,0 @@ -#include<iostream> - -using namespace std; - -double abs(double n) { - if(n < 0) return -n; - - return n; -} - - -double sq(int n) { - double x = n; - double y = 1; - while(x-y > 0.0000001) { - x = (x+y)/2; - y = n/x; - } - return x; -} - -double sq2_n(double n, double a) { - if(abs(a*a - n) <= 0.000001) { - return a; - } - - return sq2_n(n, (a+n/a)/2); -} - -double sq2(int n) { - return sq2_n(n, n/2); -} - -double sqrt_d(int n) { - double x = 1; - while(abs(x*x-n)>=0.0000001) { - x = ((n/x)+x)/2; - } - return x; -} - -int main() { - cout << sq(81) << endl; - cout << sq2(81) << endl; - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/dolcetti.cpp b/1_anno/Programmazione_2/coding_contest/dolcetti.cpp deleted file mode 100644 index c3409a4..0000000 --- a/1_anno/Programmazione_2/coding_contest/dolcetti.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include<iostream> -#include<fstream> -#include<queue> -#include<vector> - -using namespace std; - -int main() { - using tii = tuple<int, int, int>; - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int N; - in >> N; - - priority_queue<tii, vector<tii>> pq; - tii qq; - for(int i = 0; i < N; ++i) { - int e1, e2; - in >> e1 >> e2; - get<0>(qq) = e1-e2; - get<1>(qq) = e1; - get<2>(qq) = e2; - - pq.push(qq); - } - - int counter = N; - int sum{}; - - while(counter-- > N/2) { - qq = pq.top(); - sum += get<1>(qq); - pq.pop(); - } - - while(!pq.empty()) { - qq = pq.top(); - sum += get<2>(qq); - pq.pop(); - } - - out << sum << endl; - } - - in.close(); - out.close(); - return 0; -} - diff --git a/1_anno/Programmazione_2/coding_contest/gita.cpp b/1_anno/Programmazione_2/coding_contest/gita.cpp deleted file mode 100644 index cbb4910..0000000 --- a/1_anno/Programmazione_2/coding_contest/gita.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include<iostream> -#include<fstream> -#include<vector> -#include<map> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int c = 0; c < 100; ++c) { - int N, L; - in >> N >> L; - vector<pair<short, int>> students; - for(int i = 0; i < N; ++i) { - int num; - in >> num; - students.push_back({num, 0}); - } - - int index, val; - for(int i = 0; i < L; ++i) { - in >> index >> val; - students[index].second += val; - } - - vector<pair<short, int>> errors; - short _j{}; - for(auto const& i : students) { - if(i.second < i.first) { - errors.push_back({_j, i.first-i.second}); - } - _j++; - } - - out << errors.size() << ' '; - for(auto const& i : errors) { - out << i.first << ' ' << i.second << ' '; - } - out << endl; - } - out.close(); - in.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/gribaudo.cpp b/1_anno/Programmazione_2/coding_contest/gribaudo.cpp deleted file mode 100644 index 39d0e42..0000000 --- a/1_anno/Programmazione_2/coding_contest/gribaudo.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include<iostream> -#include<vector> -#include<fstream> - -using namespace std; - -int maxpath(vector<vector<int>>& v) { - for(int i = v.size()-2; i >= 0; --i) { - for(int j = 0; j <= i; ++j) { - if(v[i+1][j] > v[i+1][j+1]) { - v[i][j] += v[i+1][j]; - } else { - v[i][j] += v[i+1][j+1]; - } - } - } - - return v[0][0]; -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 1; ++ts) { - int N; - in >> N; - vector<vector<int>> triangle; - - for(int i = 0; i < N; ++i) { - int e; - triangle.push_back(vector<int>{}); - int j; - for(j = 0; j <= i; ++j) { - in >> e; - triangle[i].push_back(e); - } - for(; j < N; ++j) - triangle[i].push_back(0); - } - out << maxpath(triangle) << endl; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/gualtieri.cpp b/1_anno/Programmazione_2/coding_contest/gualtieri.cpp deleted file mode 100644 index f8a0ecf..0000000 --- a/1_anno/Programmazione_2/coding_contest/gualtieri.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include<iostream> -#include<fstream> -#include<map> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string P{}, L{}; - in >> P; - in >> L; - map<char, int> chars; - - for(auto const& c : P) { - (chars.find(c) == chars.end()) ? chars[c] = 1 : chars[c]+=1; - } - int lenn = L.length(); - int lenp = P.length(); - int counter{}; - - for(int i = 0; i < lenn-lenp+1; ++i) { - map<char, int> tmp; - bool check{true}; - for(int j = i; j < i+lenp; ++j) { - (tmp.find(L[j]) == tmp.end()) ? tmp[L[j]] = 1 : tmp[L[j]]+=1; - } - for(auto const &i : tmp) { - if(chars[i.first] != tmp[i.first]) { - check = false; - break; - } - } - if(check) - ++counter; - } - out << counter << endl; - - } - - out.close(); - in.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/ladri.cpp b/1_anno/Programmazione_2/coding_contest/ladri.cpp deleted file mode 100644 index 04e8e65..0000000 --- a/1_anno/Programmazione_2/coding_contest/ladri.cpp +++ /dev/null @@ -1,53 +0,0 @@ -#include<iostream> -#include<fstream> -#include<vector> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(short _ = 0; _ < 100; ++_) { - int N, K, M; - in >> N >> K >> M; - int* path = new int[N+1]; - int i; - for(i = 0; i < N; ++i) - in >> path[i]; - - path[i] = M; - int start = 0; - vector<int> values; - /* 1 31 33 38 62 69 93 97 98 99 */ - /* x x x x x x - * K = 30 - */ - for(int i = 0; i < N+1; ++i) { - if(path[i] - start > K) { - for(int j = i-1; j >= 0; --j) { - if(path[i] - path[j] <= K) { - values.push_back(path[j]); - start = path[j]; - i = j; - break; - } - } - } - } - - // Stampa la path corretta per debug - for(auto const& i: values) - cout << i << ' '; - - cout << endl; - out << values.size() << endl; - delete[] path; - } - - - out.close(); - in.close(); - - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/pizzini.cpp b/1_anno/Programmazione_2/coding_contest/pizzini.cpp deleted file mode 100644 index 4fcb4ab..0000000 --- a/1_anno/Programmazione_2/coding_contest/pizzini.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include<iostream> -#include<fstream> -#include<vector> - -using namespace std; - -void get_fib(vector<int> &v, int N) { - int a = v.at(0); - int b = v.at(1); - while(b <= N) { - a += b; - v.push_back(a); - swap(a, b); - } - v.pop_back(); -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(short _ = 0; _ < 100; ++_) { - int N; - in >> N; - vector<int> fib {1, 2}; - get_fib(fib, N); - vector<int> seq(fib.size(), 0); - - int sum{}; - for(int i = fib.size()-1; i >= 0; --i) { - if(fib.at(i) + sum > N) continue; - - sum += fib.at(i); - seq[i] = 1; - } - - - for(auto const& i : seq) - out << i; - - out << endl; - } - - out.close(); - in.close(); - - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/scheletri.cpp b/1_anno/Programmazione_2/coding_contest/scheletri.cpp deleted file mode 100644 index 2389d25..0000000 --- a/1_anno/Programmazione_2/coding_contest/scheletri.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include<iostream> -#include<fstream> -#include<vector> -#include<algorithm> - -using namespace std; - -int find_i(int index, vector<int> cms) { - for(int i = index; i < cms.size(); ++i) { - if(cms.at(i) != 0) - return i; - } - - return 0; -} - -int find_j(int index, vector<int> cms) { - for(int j = index; j < cms.size()-1; ++j) { - if(cms.at(j+1) == 0) - return j+1; - } - - return cms.size(); -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - short N; - for(int __c = 0; __c < 100; ++__c) { - in >> N; - vector<int> cms; - int el; - for(short i = 0; i < N; ++i) { - in >> el; - cms.push_back(el); - } - - int counter{}; - int i{}, j{}; - while(count_if(begin(cms), end(cms), [](int num) { return num == 0; } ) != cms.size() ) { - i = find_i(i, cms); - j = find_j(i, cms); - for(int ii = i; ii < j; ++ii) { - --cms[ii]; - } - ++counter; - } - out << counter << endl; - } - - out.close(); - in.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/stazioni.cpp b/1_anno/Programmazione_2/coding_contest/stazioni.cpp deleted file mode 100644 index 29ede44..0000000 --- a/1_anno/Programmazione_2/coding_contest/stazioni.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include<iostream> -#include<fstream> -#include<algorithm> -#include<vector> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 1; ++ts) { - int N, S; - in >> N >> S; - vector<long> st; - vector<vector<long>> paths; - vector<vector<long>> paths2; - vector<vector<long>> paths3; - - int e; - for(int i = 0; i < N; ++i) { - in >> e; - st.push_back(e); - } - - int index{}; - for(int i = 0; i < N-S+1; ++i) { - for(int j = 0; j < N; ++j) { - paths.push_back(vector<long>{}); - paths[index].push_back(i); - for(int k = j; paths[index].size() < S; ++k) { - int t = (k == N) ? 0 : k; - if(k > N) break; - paths[index].push_back(t); - } - sort(begin(paths[index]), end(paths[index])); - if(paths[index].size() == S) - paths2.push_back(paths[index]); - ++index; - } - } - for(int i = 0; i < paths2.size(); ++i) { - bool check{true}; - if(paths2[i].size() != S) continue; - for(int j = 0; j < paths2[i].size()-1; ++j) { - if(paths2[i].at(j) == paths2[i].at(j+1)) { - check = false; - break; - } - } - if(check) - paths3.push_back(paths2[i]); - } - - for(auto const& i : paths3) { - for(auto const& j : i) - cout << st[j] << ' '; - - cout << endl; - } - cout << endl; - - int major{}; - for(int i = 0; i < paths3.size(); ++i) { - vector<long> diffs; - for(int j = 0; j < paths3[i].size()-1; ++j) { - int p1 = st[paths3[i][j+1]]; - int p2 = st[paths3[i][j]]; - diffs.push_back(p1 - p2); - } - int miner = *min_element(begin(diffs), end(diffs)); - if(miner > major) - major = miner; - } - cout << ts << ' ' << major << endl; - out << major << endl; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/tastevin.cpp b/1_anno/Programmazione_2/coding_contest/tastevin.cpp deleted file mode 100644 index 301ebcf..0000000 --- a/1_anno/Programmazione_2/coding_contest/tastevin.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include<iostream> -#include<fstream> -#include<vector> -#include<algorithm> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int N; - in >> N; - vector<int> arr(N); - for(int i = 0; i < N; ++i) { - in >> arr.at(i); - } - - vector<int> paths(N, 1); - - for(int i = N-2; i >= 0; --i) { - int mx = 0; - for(int j = i+2; j < N; ++j) { - if(mx < paths[j] && arr[j] >= arr[i]) { - mx = paths[j]; - } - } - paths[i] += mx; - } - - out << *max_element(begin(paths), end(paths)) << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp b/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp deleted file mode 100644 index eb7da54..0000000 --- a/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp +++ /dev/null @@ -1,67 +0,0 @@ -// It prints all possible paths - -#include<iostream> -#include<fstream> -#include<vector> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int N; - in >> N; - vector<int> arr; - int e; - for(int i = 0; i < N; ++i) { - in >> e; - arr.push_back(e); - } - - int max_value{}; - int value; - - for(int i = 0; i < N; ++i) { - vector<int> tmp; - tmp.push_back(i); - value = arr[i]; - for(int j = i+2; j < N; ++j) { - if(arr[j] >= value) { - tmp.push_back(j); - value = arr[j]; - ++j; - } - } - while(!tmp.empty()) { - if(tmp.size() > max_value) { - for(auto const&i : tmp) { - cout << i << ' '; - } - cout << endl; - max_value = tmp.size(); - } - int k = tmp.back(); - tmp.pop_back(); - if(tmp.size() > 0) - value = arr[tmp.back()]; - else - value = arr[k]; - for(int j = k+1; j < N; ++j) { - if(arr[j] >= value) { - value = arr[j]; - tmp.push_back(j); - ++j; - } - } - } - } - - out << max_value << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/bfs.cc b/1_anno/Programmazione_2/data_structures/bfs.cc deleted file mode 100644 index 2b4efbd..0000000 --- a/1_anno/Programmazione_2/data_structures/bfs.cc +++ /dev/null @@ -1,186 +0,0 @@ -#include<iostream> -#include<vector> -#include<queue> -#define W -1 -#define G 0 -#define B 1 - -using namespace std; - -template<class H> -class node { -public: - explicit node(H key, node<H>* next) : _key{key}, _next(next) {} - const H& key() const { return _key; } - H& key() { return _key; } - const node<H>*& next() const { return _next; } - node<H>*& next() { return _next; } -private: - H _key; - node<H>* _next; -}; - -template<class H> -class list { -public: - list() : _head{nullptr} {} - ~list() { - while(_head) { - auto tmp = _head; - _head = _head->next(); - delete tmp; - } - } - list<H>* push(H val) { - auto iter = _head; - while(iter && iter->next()) - iter = iter->next(); - - if(!iter) - _head = new node<H>{val, nullptr}; - else - iter->next() = new node<H>{val, nullptr}; - - return this; - } - void print() { - auto iter = _head; - while(iter) { - cout << iter->key() << ' '; - iter = iter->next(); - } - } - vector<H> as_vector() { - vector<H> v; - auto iter = _head; - while(iter) { - v.push_back(iter->key()); - iter = iter->next(); - } - return v; - } - node<H>* search(H val) { - auto iter = _head; - while(iter && iter->key() != val) { - iter = iter->next(); - } - - return iter; - } -private: - node<H>* _head; -}; - -template<class H> -class graph { -public: - -private: - int _len, _nodes, _edges; - int* _parents; - int* _distances; - H** _k; // it works like a dictionary, it saves the keys - list<int>** _adj; - int _index(H val) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == val) return i; - - return -1; - } -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new list<int>*[_len]; - _parents = new int[_len]; - _distances = new int[_len]; - for(int i = 0; i < _len; ++i) { - _k[i] = nullptr; - _adj[i] = new list<int>{}; - } - } - - graph<H>* add_node(H k) { - if(_nodes == _len) return this; - if(_index(k) >= 0) return this; // node is already there - - _k[_nodes++] = new H(k); - - return this; - } - - void bfs(int s) { - int colors[_len]; - queue<int> q; - - for(int i = 0; i < _nodes; ++i) { - colors[i] = W; - _parents[i] = -1; - _distances[i] = 999999999; - } - q.push(s); - colors[s] = G; - _distances[s] = 0; - while(!q.empty()) { - int x = q.front(); - q.pop(); - for(auto const& j : _adj[x]->as_vector()) { - if(colors[j] == W) { - colors[j] = G; - q.push(j); - _parents[j] = x; - _distances[j] = _distances[x] + 1; - } - } - colors[x] = B; - } - - for(int i = 0; i < _nodes; ++i) { - cout << "[" << i << "]->"; - if(_distances[i]==999999999) cout << "inf." << endl; - else cout << _distances[i] << endl; - } - } - - void bfs(H x) { - int s = _index(x); - if(s != -1) - bfs(s); - } - - graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - - if(!_adj[i]->search(j)) { - _adj[i]->push(j); - _edges++; - } - - return this; - } - - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << i << ", " << *_k[i] << "): "; - for(auto const& j : _adj[i]->as_vector()) - cout << "(" << j << ", " << *_k[j] << "), "; - cout << '\n'; - } - } -}; - - -int main() { - graph<string>* g = new graph<string>(5); - g->add_node("hello")->add_node("greg")->add_node("yes"); - g->add_node("nop")->add_node("ok"); - g->add_edge("hello", "ok"); - g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); - g->add_edge("yes", "nop"); - g->print(); - g->bfs("hello"); - - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/bst.cc b/1_anno/Programmazione_2/data_structures/bst.cc deleted file mode 100644 index 9223e04..0000000 --- a/1_anno/Programmazione_2/data_structures/bst.cc +++ /dev/null @@ -1,225 +0,0 @@ -#include<iostream> - -using namespace std; - -template<class T> -struct node { - T key; - node<T>* prev; - node<T>* right; - node<T>* left; -}; - -template<class T> -class bst { -public: - bst() : root{nullptr} {} - - ~bst() { - // TODO - } - - bst<T>* insert(initializer_list<T>&& list) { - for(auto const& i : list) - insert(i); - - return this; - } - - bst<T>* insert(T k) { - node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr}; - node<T>* iter = root; - node<T>* prev = nullptr; - - while(iter) { - prev = iter; - iter = (k < iter->key) ? iter->left : iter->right; - } - - nodus->prev = prev; - if(!prev) - root = nodus; - else if(k < prev->key) - prev->left = nodus; - else - prev->right = nodus; - - return this; - } - - bst<T>* remove(initializer_list<T>&& list) { - for(auto const& i : list) - remove(i); - - return this; - } - - bst<T>* remove(T k) { - node<T>* nodus = search(k); - if(!nodus) return this; - - if(!nodus->left) { - _transplant(nodus, nodus->right); - } else if(!nodus->right) { - _transplant(nodus, nodus->left); - } else { - node<T>* iter = _min(nodus->right); - if(iter->prev != nodus) { - _transplant(iter, iter->right); - iter->right = nodus->right; - iter->right->prev = iter; - } - _transplant(nodus, iter); - iter->left = nodus->left; - iter->left->prev = iter; - } - - delete nodus; - return this; - } - - node<T>* min() { - return _min(root); - } - - node<T>* min(node<T>* nodus) { - return _min(nodus); - } - - node<T>* max() { - return _max(root); - } - - node<T>* max(node<T>* nodus) { - return _max(nodus); - } - - node<T>* search(T k) { - node<T>* iter = root; - while(iter && iter->key != k) - iter = (iter->key > k) ? iter->left : iter->right; - - return iter; - } - - node<T>* successor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->right) - return min(nodus->right); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->right) { - nodus = prev; - prev = prev->prev; - } - - return prev; - - } - node<T>* predecessor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->left) - return max(nodus->left); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->left) { - nodus = prev; - prev = prev->prev; - } - - return prev; - } - - friend ostream& operator<<(ostream& os, bst<T>* tree) { - tree->_preorder(os, tree->root); - return os; - } -private: - void _transplant(node<T>* u, node<T>* v) { - if(!u->prev) { - root = v; - } else if(u == u->prev->left) { - u->prev->left = v; - } else { - u->prev->right = v; - } - - if(v) - v->prev = u->prev; - } - - node<T>* _min(node<T>* root) { - node<T>* iter = root; - while(iter && iter->left) - iter = iter->left; - - return iter; - } - - node<T>* _max(node<T>* root) { - node<T>* iter = root; - while(iter && iter->right) - iter = iter->right; - - return iter; - } - - void _inorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - os << root->key << ' '; - _inorder(os, root->right); - } - } - - void _preorder(ostream& os, node<T>* root) { - if(root) { - os << root->key << ' '; - _inorder(os, root->left); - _inorder(os, root->right); - } - } - - void _postorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - _inorder(os, root->right); - os << root->key << ' '; - } - } - node<T>* root; -}; - -int main() { - bst<int>* b = new bst<int>{}; - - // b->insert(12)->insert(5)->insert(18)->insert(2)->insert(9); - // b->insert(15)->insert(13)->insert(17)->insert(19); - - b->insert({12, 5, 18, 2, 9, 15, 13, 17, 19}); - cout << b << endl; - cout << (b->search(5) != nullptr) << endl; - cout << (b->search(1) != nullptr) << endl; - cout << b->max()->key << ' ' << b->min()->key << endl; - for(auto const& i : {12, 9, 14, 18}) { - auto elem = b->successor(i); - if(elem) - cout << "(" << i << ", " << elem->key << ") "; - } - cout << endl; - - for(auto const& i : {9, 2, 5, 15, 18, 12, 19}) { - auto elem = b->predecessor(i); - if(elem) - cout << "(" << i << ", " << elem->key << ") "; - } - cout << endl; - b->remove({5, 12}); - cout << b << endl; - - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/circle_double_list.cc b/1_anno/Programmazione_2/data_structures/circle_double_list.cc deleted file mode 100644 index f162e57..0000000 --- a/1_anno/Programmazione_2/data_structures/circle_double_list.cc +++ /dev/null @@ -1,185 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node* prev; - node* next; -}; - - -template<typename T> -class list { -public: - list() : _head{nullptr} {} - - ~list() { - node<T>* iter = _head; - while(iter->next != _head) { - node<T>* tmp = iter; - delete tmp; - iter = iter->next; - } - node<T>* tmp = iter; - delete tmp; - } - - list* push_front(T val) { - auto elem = _last(); - if(!_head) { - _head = new node<T>{val, nullptr, nullptr}; - _head->prev = _head->next = _head; - } else { - _head = new node<T>{val, elem, _head}; - elem->next = _head->next->prev = _head; - } - - return this; - } - - list* push_back(T val) { - if(!_head) return this->push_front(val); - - auto last_e = _last(); - last_e->next = new node<T>{val, last_e, _head}; - _head->prev = last_e->next; - - return this; - } - - list* push_after_value(T val, T newval) { - node<T>* iter = _search(val); - if(iter) { - node<T>* nod = new node<T>{newval, iter, iter->next}; - iter->next = nod; - nod->next->prev = nod; - } - - return this; - } - - list* push_before_value(T val, T newval) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - - if(iter->value == val) - return this->push_front(newval); - - while(iter->next != elem) - iter = iter->next; - - node<T>* nod = new node<T>{newval, iter, iter->next}; - iter->next = nod; - nod->next->prev = nod; - - return this; - } - - list* pop(int val) { - node<T>* elem = _search(val); - if(!elem) return this; - - if(elem == _head) return this->pop_front(); - - node<T>* iter = elem->prev; - node<T>* temp = iter->next; - iter->next = iter->next->next; - iter->next->prev = iter; - delete temp; - - return this; - } - - list* pop_front() { - if(!_head) - return this; - - auto last_e = _last(); - node<T>* elem = _head; - _head = _head->next; - _head->prev = last_e; - last_e->next = _head; - delete elem; - - return this; - } - - list* pop_back() { - if(!_head) - return this; - - auto last_e = _last(); - - if(last_e == _head) { - delete _head; - _head = nullptr; - } else { - auto iter = last_e->prev; - delete iter->next; - iter->next = _head; - _head->prev = iter; - } - - return this; - } - - void print() { - node<T>* iter = _head; - while(iter != nullptr) { - cout << iter->value << ' '; - cout << "[[ " << iter->prev->value << ", "; - cout << iter->next->value << " ]], "; - iter = iter->next; - if(iter == _head) break; - } - } -private: - node<T>* _last() { - node<T>* iter = _head; - while(iter && iter->next != _head) { - iter = iter->next; - } - - return iter; - } - - node<T>* _search(T val) { - node<T>* iter = _head; - if(iter->value == val) return iter; - - while(iter && iter->value != val) { - iter = iter->next; - if(iter == _head) return nullptr; - } - - return iter; - } - - node<T>* _head; -}; - -int main() { - list<int>* l = new list<int>{}; - l->push_front(2); - l->push_back(1)->push_back(3); - l->push_front(5)->push_front(9); - l->push_back(0)->push_back(6); - l->print(); cout << '\n'; - l->push_after_value(7, -2); - l->push_before_value(9, 10); - l->print(); cout << '\n'; - l->pop_front(); - l->pop_front(); - l->pop_back(); - l->pop_front(); - l->print(); cout << '\n'; - l->pop(2); - l->print(); cout << '\n'; - - delete l; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/circle_list.cc b/1_anno/Programmazione_2/data_structures/circle_list.cc deleted file mode 100644 index 2143ac1..0000000 --- a/1_anno/Programmazione_2/data_structures/circle_list.cc +++ /dev/null @@ -1,189 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node* next; -}; - - -template<typename T> -class list { -public: - list() : _head{nullptr} {} - - ~list() { - node<T>* iter = _head; - while(iter->next != _head) { - node<T>* tmp = iter; - delete tmp; - iter = iter->next; - } - node<T>* tmp = iter; - delete tmp; - } - - list* push_front(T val) { - auto elem = _last(); - _head = new node<T>{val, _head}; - if(!elem) - elem = _head; - - elem->next = _head; - - return this; - } - - list* push_back(T val) { - if(!_head) return this->push_front(val); - - auto last_e = _last(); - last_e->next = new node<T>{val, _head}; - - return this; - } - - list* push_after_value(T val, T newval) { - node<T>* iter = _search(val); - if(iter) - iter->next = new node<T>{newval, iter->next}; - - return this; - } - - list* push_before_value(T val, T newval) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - - if(iter->value == val) - return this->push_front(newval); - - while(iter->next != elem) - iter = iter->next; - - iter->next = new node<T>{newval, iter->next}; - - return this; - } - - list* pop(int val) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - if(iter == elem) return this->pop_front(); - - while(iter->next != elem) - iter = iter->next; - - node<T>* temp = iter->next; - iter->next = iter->next->next; - delete temp; - - return this; - } - - list* pop_front() { - if(!_head) - return this; - - auto last_e = _last(); - - if(last_e == _head) { - delete _head; - _head = nullptr; - } else { - node<T>* elem = _head; - _head = _head->next; - last_e->next = _head; - delete elem; - } - - return this; - } - - list* pop_back() { - if(!_head) - return this; - - node<T>* iter = _head; - auto last_e = _last(); - - if(last_e == _head) { - delete iter; - _head = nullptr; - } else { - while(iter->next != last_e) { - iter = iter->next; - } - - delete iter->next; - iter->next = _head; - } - - return this; - } - - void print() { - node<T>* iter = _head; - while(iter) { - cout << iter->value << ' '; - iter = iter->next; - if(iter == _head) break; - } - } -private: - node<T>* _last() { - node<T>* iter = _head; - while(iter && iter->next != _head) { - iter = iter->next; - } - - return iter; - } - - node<T>* _search(T val) { - node<T>* iter = _head; - if(iter->value == val) return iter; - - while(iter && iter->value != val) { - iter = iter->next; - if(iter == _head) return nullptr; - } - - return iter; - } - - node<T>* _head; -}; - -int main() { - list<int>* l = new list<int>{}; - l->push_before_value(4, 1); - l->push_back(4); - l->push_back(1); - l->push_back(0); - l->push_front(2); - l->print(); cout << endl; - l->pop_back(); - l->print(); cout << endl; - l->pop_front(); - l->print(); cout << endl; - l->pop_back(); - l->print(); cout << endl; - l->push_front(3); - l->print(); cout << endl; - l->push_after_value(4, 7); - l->print(); cout << endl; - l->push_before_value(3, 5); - l->print(); cout << endl; - l->pop(5); - l->print(); cout << endl; - - delete l; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/dfs.cc b/1_anno/Programmazione_2/data_structures/dfs.cc deleted file mode 100644 index 744f153..0000000 --- a/1_anno/Programmazione_2/data_structures/dfs.cc +++ /dev/null @@ -1,191 +0,0 @@ -#include<iostream> -#include<vector> -#include<queue> -#define W -1 -#define G 0 -#define B 1 - -using namespace std; - -template<class H> -class node { -public: - explicit node(H key, node<H>* next) : _key{key}, _next(next) {} - const H& key() const { return _key; } - H& key() { return _key; } - const node<H>*& next() const { return _next; } - node<H>*& next() { return _next; } -private: - H _key; - node<H>* _next; -}; - -template<class H> -class list { -public: - list() : _head{nullptr} {} - ~list() { - while(_head) { - auto tmp = _head; - _head = _head->next(); - delete tmp; - } - } - list<H>* push(H val) { - auto iter = _head; - while(iter && iter->next()) - iter = iter->next(); - - if(!iter) - _head = new node<H>{val, nullptr}; - else - iter->next() = new node<H>{val, nullptr}; - - return this; - } - void print() { - auto iter = _head; - while(iter) { - cout << iter->key() << ' '; - iter = iter->next(); - } - } - vector<H> as_vector() { - vector<H> v; - auto iter = _head; - while(iter) { - v.push_back(iter->key()); - iter = iter->next(); - } - return v; - } - node<H>* search(H val) { - auto iter = _head; - while(iter && iter->key() != val) { - iter = iter->next(); - } - - return iter; - } -private: - node<H>* _head; -}; - -template<class H> -class graph { -private: - int _len, _nodes, _edges; - int* _parents; - int* _radixes; - int* _distances; - int* _finishes; - int* _colors; - int _time; - int _current; - H** _k; // it works like a dictionary, it saves the keys - list<int>** _adj; - int _index(H val) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == val) return i; - - return -1; - } - void _dfsvisit(int u) { - _colors[u] = G; - _distances[u] = _time++; - _radixes[u] = _current; - for(auto const& v : _adj[u]->as_vector()) { - if(_colors[v] == W) { - _parents[v] = u; - _dfsvisit(v); - } - } - _colors[u] = B; - _finishes[u] = _time++; - } -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new list<int>*[_len]; - _parents = new int[_len]; - _radixes = new int[_len]; - _distances = new int[_len]; - _finishes = new int[_len]; - _colors = new int[_len]; - for(int i = 0; i < _len; ++i) { - _k[i] = nullptr; - _adj[i] = new list<int>{}; - } - } - - graph<H>* add_node(H k) { - if(_nodes == _len) return this; - if(_index(k) >= 0) return this; // node is already there - - _k[_nodes++] = new H(k); - - return this; - } - - - void dfs() { - _time = 0; - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - _parents[i] = -1; - } - - for(int i = 0; i < _nodes; ++i) { - if(_colors[i] == W) { - _current = i; - _dfsvisit(i); - } - } - for(int i = 0; i < _nodes; ++i) { - cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl; - } - } - - graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - - if(!_adj[i]->search(j)) { - _adj[i]->push(j); - _edges++; - } - - return this; - } - - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << i << ", " << *_k[i] << "): "; - for(auto const& j : _adj[i]->as_vector()) - cout << "(" << j << ", " << *_k[j] << "), "; - cout << '\n'; - } - } -}; - - -int main() { - graph<char>* g = new graph<char>(6); - g->add_node('u')->add_node('v')->add_node('x')->add_node('y'); - g->add_node('w')->add_node('z'); - g->add_edge('u', 'v'); - g->add_edge('u', 'x'); - g->add_edge('x', 'v'); - g->add_edge('y', 'x'); - g->add_edge('v', 'y'); - g->add_edge('w', 'y'); - g->add_edge('w', 'z'); - g->add_edge('z', 'z'); - - g->print(); - g->dfs(); - - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/graph.cc b/1_anno/Programmazione_2/data_structures/graph.cc deleted file mode 100644 index 12837be..0000000 --- a/1_anno/Programmazione_2/data_structures/graph.cc +++ /dev/null @@ -1,164 +0,0 @@ -#include<iostream> -#include<vector> - -using namespace std; - -template<class H> -class node { -public: - explicit node(H key, node<H>* next) : _key{key}, _next(next) {} - const H& key() const { return _key; } - H& key() { return _key; } - const node<H>*& next() const { return _next; } - node<H>*& next() { return _next; } -private: - H _key; - node<H>* _next; -}; - -template<class H> -class list { -public: - list() : _head{nullptr} {} - ~list() { - while(_head) { - auto tmp = _head; - _head = _head->next(); - delete tmp; - } - } - list<H>* push(H val) { - auto iter = _head; - while(iter && iter->next()) - iter = iter->next(); - - if(!iter) - _head = new node<H>{val, nullptr}; - else - iter->next() = new node<H>{val, nullptr}; - - return this; - } - list<H>* pop(H val) { - auto elem = search(val); - if(!elem) - return this; - - auto iter = _head; - // This is the case when head is the element we want to pop - if(iter == elem) { - delete _head; - _head = nullptr; - return this; - } - - while(iter && iter->next() != elem) - iter = iter->next(); - - auto tmp = iter->next(); - if(iter->next()->next()) { - iter->next() = iter->next()->next(); - } else { // the element we want to pop is the tail - iter->next() = nullptr; - } - delete tmp; - - return this; - } - void print() { - auto iter = _head; - while(iter) { - cout << iter->key() << ' '; - iter = iter->next(); - } - } - vector<H> as_vector() { - vector<H> v; - auto iter = _head; - while(iter) { - v.push_back(iter->key()); - iter = iter->next(); - } - return v; - } - node<H>* search(H val) { - auto iter = _head; - while(iter && iter->key() != val) { - iter = iter->next(); - } - - return iter; - } -private: - node<H>* _head; -}; - -template<class H> -class graph { -public: - -private: - int _len, _nodes, _edges; - H **_k; - list<int> **_adj; - int _index(H val) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == val) return i; - - return -1; - } -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new list<int>*[_len]; - for(int i = 0; i < _len; ++i) { - _k[i] = nullptr; - _adj[i] = new list<int>{}; - } - } - - graph<H>* add_node(H k) { - if(_nodes == _len) return this; - if(_index(k) >= 0) return this; // node is already there - - _k[_nodes++] = new H(k); - - return this; - } - - graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - - if(!_adj[i]->search(j)) { - _adj[i]->push(j); - _edges++; - } - - return this; - } - - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << i << ", " << *_k[i] << "): "; - for(auto const& j : _adj[i]->as_vector()) - cout << "(" << j << ", " << *_k[j] << "), "; - cout << '\n'; - } - } -}; - - -int main() { - graph<string>* g = new graph<string>(5); - g->add_node("hello")->add_node("greg")->add_node("yes"); - g->add_node("nop")->add_node("ok"); - g->add_edge("hello", "ok"); - g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); - g->add_edge("yes", "nop"); - g->print(); - - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/graph_stl.cc b/1_anno/Programmazione_2/data_structures/graph_stl.cc deleted file mode 100644 index 5381747..0000000 --- a/1_anno/Programmazione_2/data_structures/graph_stl.cc +++ /dev/null @@ -1,221 +0,0 @@ -#include<iostream> -#include<vector> -#include<algorithm> -#include<queue> -#include<stack> -#define INF 99999999 -#define W -1 -#define G 0 -#define B 1 - -using namespace std; - -template<class H> -class graph { -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new vector<int>[len]; - _colors = new int[len]; - _d = new int[len]; - _f = new int[len]; - _p = new int[len]; - - for(int i = 0; i < len; ++i) { - _k[i] = nullptr; - } - } - ~graph() { - delete[] _k; - delete[] _adj; - } - - graph<H>* add_node(H x) { - if(_index(x) > -1) return this; - if(_nodes == _len) return this; - _k[_nodes++] = new H(x); - - return this; - } - graph<H>* add_edge(H u, H v) { - int i = _index(u); - int j = _index(v); - if(i < 0 || j < 0) return this; - - if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) { - _adj[i].push_back(j); - } - return this; - } - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): "; - for(auto const& j : _adj[i]) { - cout << "(" << *_k[j] << ", " << j << ") "; - } - cout << endl; - } - } - void dfsvisit(int u, bool visited[]) { - visited[u] = true; - cout << "(" << *_k[u] << ", " << u << ") "; - for(auto const& i : _adj[u]) { - if(!visited[i]) - dfsvisit(i, visited); - } - } - int dfsvisit(int u) { - int cycle = 0; - _colors[u] = G; - _d[u] = _time++; - - for(auto const& j : _adj[u]) { - if(_colors[j] == W) - cycle |= dfsvisit(j); - } - - _colors[u] = B; - _stack.push(u); - _f[u] = _time++; - return cycle; - } - int dfs() { - int cycle = 0; - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - } - _time = 0; - for(int i = 0; i < _nodes; ++i) { - if(_colors[i] == W) - cycle |= dfsvisit(i); - else if(_colors[i] == G) - cycle = 1; - } - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl; - } - return cycle; - } - - void top_sort() { - int cycle = dfs(); - if(cycle) { - cout << "cyclic graph!" << endl; - return; - } - int* s = new int[_nodes]; - for(int i = 0; i < _nodes; ++i) s[i] = i; - _sort(s, _nodes, _f); - for(int i = 0; i < _nodes; ++i) { - cout << "(" << s[i] << ", " << _f[s[i]] << ") "; - } - - } - - void bfs(H v) { - int s = _index(v); - if(s < 0) return; - - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - _d[i] = INF; - _p[i] = -1; - } - _colors[s] = G; - _d[s] = 0; - queue<int> q; - q.push(s); - while(!q.empty()) { - int u = q.front(); - q.pop(); - for(auto const& j : _adj[u]) { - if(_colors[j] == W) { - _colors[j] = G; - _d[j] = _d[u]+1; - _p[j] = u; - q.push(j); - } - } - _colors[u] = B; - } - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl; - } - } - void ssc() { - dfs(); - cout << endl << endl; - auto gr = _transpose(); - bool* visited = new bool[_nodes]; - for(int i = 0; i < _nodes; ++i) - visited[i] = false; - - while(!_stack.empty()) { - int v = _stack.top(); - _stack.pop(); - if(!visited[v]) { - gr->dfsvisit(v, visited); - cout << endl; - } - } - delete[] visited; - } -private: - graph<H>* _transpose() { - graph<H>* g = new graph<H>{_len}; - for(int i = 0; i < _nodes; ++i) { - g->add_node(*_k[i]); - } - - for(int i = 0; i < _nodes; ++i) { - for(auto const& j : _adj[i]) { - g->add_edge(j, i); - } - } - - return g; - } - void _sort(int* d, int n, int* s) { - for(int i = -1; i < n; ++i) { - int j = i-1; - while(j > -1 && s[d[j+1]]>s[d[j]]) { - swap(d[s[j+1]], d[s[j]]); - --j; - } - } - } - int _index(H x) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == x) return i; - - return -1; - } - stack<int> _stack; - H** _k; - vector<int>* _adj; - int _len, _nodes, _edges; - int* _colors; - int _time; - int* _d; - int* _f; - int* _p; -}; - -int main() { - graph<int>* g = new graph<int>{5}; - for(auto const& i : {0, 1, 2, 3, 4}) - g->add_node(i); - g->add_edge(1, 0); - g->add_edge(2, 1); - g->add_edge(0, 2); - g->add_edge(0, 3); - g->add_edge(3, 4); - //g->print(); - cout << endl; - //g->top_sort(); - g->ssc(); - cout << endl; - //g->bfs(0); - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/list.cc b/1_anno/Programmazione_2/data_structures/list.cc deleted file mode 100644 index 8ddcbf9..0000000 --- a/1_anno/Programmazione_2/data_structures/list.cc +++ /dev/null @@ -1,164 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node* next; -}; - - -template<typename T> -class list { -public: - list() : _head{nullptr} {} - - ~list() { - while(_head) { - node<T>* tmp = _head->next; - delete tmp; - _head = tmp; - } - } - - list* push_front(T val) { - _head = new node<T>{val, _head}; - - return this; - } - - list* push_back(T val) { - if(!_head) return this->push_front(val); - - node<T>* iter = _head; - while(iter->next) { - iter = iter->next; - } - iter->next = new node<T>{val, nullptr}; - - return this; - } - - list* push_after_value(T val, T newval) { - node<T>* iter = _search(val); - if(iter) - iter->next = new node<T>{newval, iter->next}; - - return this; - } - - list* push_before_value(T val, T newval) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - - if(iter->value == val) - return this->push_front(newval); - - while(iter->next != elem) - iter = iter->next; - - iter->next = new node<T>{newval, iter->next}; - - return this; - } - - list* pop(int val) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - if(iter == elem) return this->pop_front(); - - while(iter->next != elem) - iter = iter->next; - - node<T>* temp = iter->next; - iter->next = iter->next->next; - delete temp; - - return this; - } - - list* pop_front() { - if(!_head) - return this; - - node<T>* elem = _head; - _head = _head->next; - delete elem; - - return this; - } - - list* pop_back() { - if(!_head) - return this; - - node<T>* iter = _head; - - while(iter->next && iter->next->next) { - iter = iter->next; - } - - if(!iter->next) { - delete iter; - _head = nullptr; - } else if(iter->next->next) { - delete iter->next->next; - } else { - delete iter->next; - } - - iter->next = nullptr; - - return this; - } - - void print() { - node<T>* iter = _head; - while(iter) { - cout << iter->value << ' '; - iter = iter->next; - } - } -private: - node<T>* _search(T value) { - node<T>* iter = _head; - while(iter && iter->value != value) - iter = iter->next; - - return iter; - } - - node<T>* _head; -}; - -int main() { - list<int>* l = new list<int>{}; - l->push_front(2)->push_front(1); - l->print(); cout << endl; - l->push_back(5); - l->print(); cout << endl; - l->push_back(10)->push_back(15); - l->print(); cout << endl; - l->push_after_value(5, 6); - l->print(); cout << endl; - l->push_before_value(5, 4); - l->print(); cout << endl; - l->push_before_value(4, 3); - l->print(); cout << endl; - l->pop_back(); - l->print(); cout << endl; - l->pop_front(); - l->print(); cout << endl; - l->push_front(1); - l->print(); cout << endl; - l->pop(1); - l->print(); cout << endl; - - delete l; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/list_double.cc b/1_anno/Programmazione_2/data_structures/list_double.cc deleted file mode 100644 index fa0af26..0000000 --- a/1_anno/Programmazione_2/data_structures/list_double.cc +++ /dev/null @@ -1,182 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node* prev; - node* next; -}; - - -template<typename T> -class list { -public: - list() : _head{nullptr} {} - - ~list() { - while(_head != nullptr) { - node<T>* tmp = _head->next; - delete tmp; - _head = tmp; - } - } - - list* push_front(T val) { - if(!_head) { - _head = new node<T>{val, nullptr, nullptr}; - } else { - _head = new node<T>{val, nullptr, _head}; - _head->next->prev = _head; - } - - return this; - } - - list* push_back(T val) { - if(!_head) return this->push_front(val); - - node<T>* iter = _head; - while(iter->next) { - iter = iter->next; - } - iter->next = new node<T>{val, iter, nullptr}; - - return this; - } - - list* push_after_value(T val, T newval) { - node<T>* elem = _search(val); - if(elem) { - node<T>* nod = new node<T>{newval, elem, elem->next}; - elem->next = nod; - nod->next->prev = nod; - } - - return this; - } - - list* push_before_value(T val, T newval) { - node<T>* elem = _search(val); - if(!elem) return this; - - node<T>* iter = _head; - - if(iter->value == val) - return this->push_front(newval); - - while(iter->next != elem) - iter = iter->next; - - node<T>* nod = new node<T>{newval, iter, iter->next}; - iter->next = nod; - nod->next->prev = nod; - - return this; - } - - list* pop(int val) { - node<T>* elem = _search(val); - if(!elem) return this; - - if(elem == _head) return this->pop_front(); - - node<T>* iter = elem->prev; - node<T>* temp = iter->next; - iter->next = iter->next->next; - iter->next->prev = iter; - delete temp; - - return this; - } - - list* pop_front() { - if(!_head) - return this; - - node<T>* elem = _head; - _head = _head->next; - _head->prev = nullptr; - delete elem; - - return this; - } - - list* pop_back() { - if(!_head) - return this; - - node<T>* iter = _last()->prev; - - if(iter->next == nullptr) { - delete iter; - _head = nullptr; - } else if(iter->next->next) { - delete iter->next->next; - } else { - delete iter->next; - } - - iter->next = nullptr; - - return this; - } - - void print() { - node<T>* iter = _head; - while(iter) { - cout << iter->value << ' '; - cout << "[[ " << (iter->prev!=nullptr ? iter->prev->value : -1) << ", "; - cout << (iter->next!=nullptr ? iter->next->value : -1) << " ]], "; - iter = iter->next; - } - } -private: - node<T>* _last() { - node<T>* iter = _head; - while(iter->next) { - iter = iter->next; - } - - return iter; - } - - node<T>* _search(T value) { - node<T>* iter = _head; - while(iter && iter->value != value) - iter = iter->next; - - return iter; - } - - node<T>* _head; -}; - -int main() { - list<int>* l = new list<int>{}; - l->push_front(2)->push_front(1); - l->print(); cout << endl; - l->push_back(5); - l->print(); cout << endl; - l->push_back(10)->push_back(15); - l->print(); cout << endl; - l->push_after_value(5, 6); - l->print(); cout << endl; - l->push_after_value(5, 7); - l->print(); cout << endl; - l->push_before_value(5, 4); - l->print(); cout << endl; - l->push_before_value(5, 3); - l->print(); cout << endl; - l->pop_back(); - l->print(); cout << endl; - l->pop_front(); - l->print(); cout << endl; - l->pop(2); - l->print(); cout << endl; - - delete l; - - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/matrix-graph.cc b/1_anno/Programmazione_2/data_structures/matrix-graph.cc deleted file mode 100644 index a644ec1..0000000 --- a/1_anno/Programmazione_2/data_structures/matrix-graph.cc +++ /dev/null @@ -1,81 +0,0 @@ -#include<iostream> -#include<list> - -using namespace std; - -template<class H> -class matrix_graph { -public: - ~matrix_graph() { - delete[] _m; - delete[] _k; - } - matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _m = new int*[len]; - _k = new H*[len]; - for(int i = 0; i < len; ++i) { - _m[i] = new int[len]; - _k[i] = nullptr; - for(int j = 0; j < len; ++j) - _m[i][j] = 0; - } - } - - matrix_graph<H>* add_node(H k) { - if(_len == _nodes) return this; // no more space for new nodes - if(_index(k) > -1) return this; // nodes already exists - - _k[_nodes++] = new H(k); - - return this; - } - - matrix_graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - if(!_m[i][j]) { - _m[i][j] = 1; - _edges++; - } - return this; - } - void print() { - for(int i = 0; i < _len; ++i) { - cout << i << ' ' << *_k[i] << ": "; - for(int j = 0; j < _len; ++j) { - if(_m[i][j]) - cout << *_k[j] << ' '; - } - cout << '\n'; - } - cout << endl; - for(int i = 0; i < _len; ++i) { - for(int j = 0; j < _len; ++j) { - cout << _m[i][j] << ' '; - } - cout << '\n'; - } - } -private: - int _len, _nodes, _edges; - int** _m; - H** _k; - int _index(H x) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == x) return i; - return -1; - } -}; - -int main() { - matrix_graph<string>* g = new matrix_graph<string>(5); - g->add_node("hello")->add_node("greg")->add_node("yes"); - g->add_node("nop")->add_node("ok"); - g->add_edge("hello", "ok"); - g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); - g->add_edge("yes", "nop"); - g->print(); - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/queue.cc b/1_anno/Programmazione_2/data_structures/queue.cc deleted file mode 100644 index 8398459..0000000 --- a/1_anno/Programmazione_2/data_structures/queue.cc +++ /dev/null @@ -1,72 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node<T>* next; -}; - -template<class T> -class queue { -public: - queue() : _head{nullptr} {} - - ~queue() { - auto iter = _head; - while(iter) { - delete iter; - iter = iter->next; - } - } - - queue<T>* enqueue(T val) { - - if(!_head) { - _head = new node<T>{val, nullptr}; - _tail = _head; - } else { - _tail->next = new node<T>{val, nullptr}; - _tail = _tail->next; - } - - return this; - } - - node<T>* dequeue() { - if(!_head) return nullptr; - auto iter = _head; - delete _head; - _head = iter->next; - return iter; - } - - void print() { - auto iter = _head; - while(iter) { - cout << iter->value << ' '; - iter = iter->next; - } - cout << endl; - } -private: - node<T>* _head; - node<T>* _tail; -}; - -int main() { - queue<int>* q = new queue<int>(); - - q->dequeue(); - q->enqueue(4)->enqueue(2)->enqueue(8); - q->print(); - auto e = q->dequeue(); - if(e) - cout << e->value << endl; - q->enqueue(1); - q->print(); - - delete q; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/queue_w_array.cc b/1_anno/Programmazione_2/data_structures/queue_w_array.cc deleted file mode 100644 index fb92d68..0000000 --- a/1_anno/Programmazione_2/data_structures/queue_w_array.cc +++ /dev/null @@ -1,66 +0,0 @@ -#include<iostream> - -using namespace std; - -template<class H> -class queue { -public: - queue(int n) : _size{n}, _counter{0}, _head{0}, _tail{0} { - _arr = new H[n]; - } - ~queue() { - delete _arr; - } - bool is_empty() { - return _counter == 0; - } - bool is_full() { - return _counter == _size; - } - - queue<H>* enqueue(H x) { - if(!is_full()) { - _arr[_tail] = x; - if(_tail == _size-1) - _tail = 0; - else - ++_tail; - _counter++; - } - - return this; - } - H dequeue() { - if(is_empty()) return -1; - H x = _arr[_head]; - - if(_head == _size-1) - _head = 0; - else - ++_head; - - _counter--; - return x; - } -private: - H* _arr; - int _size; - short _counter; - short _head; - short _tail; -}; - -int main() { - queue<int>* q = new queue<int>{4}; - q->enqueue(5)->enqueue(13)->enqueue(3); - cout << q->dequeue() << '\n'; - q->enqueue(4)->enqueue(6)->enqueue(7); - q->dequeue(); - q->enqueue(7); - - for(int i = 0; i < 6; ++i) { - cout << q->dequeue() << ' '; - } - delete q; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/stack.cc b/1_anno/Programmazione_2/data_structures/stack.cc deleted file mode 100644 index ffff780..0000000 --- a/1_anno/Programmazione_2/data_structures/stack.cc +++ /dev/null @@ -1,70 +0,0 @@ -#include<iostream> - -using namespace std; - -template<typename T> -struct node { - T value; - node<T>* next; -}; - -template<class T> -class stack { -public: - stack() : _head{nullptr} {} - - ~stack() { - auto iter = _head; - while(iter) { - delete iter; - iter = iter->next; - } - } - - stack<T>* push(T val) { - - if(!_head) { - _head = new node<T>{val, nullptr}; - } else { - _head = new node<T>{val, _head}; - } - - return this; - } - - node<T>* pop() { - if(!_head) return nullptr; - node<T>* elem = _head; - delete _head; - _head = elem->next; - - return elem; - } - - void print() { - auto iter = _head; - while(iter) { - cout << iter->value << ' '; - iter = iter->next; - } - cout << endl; - } -private: - node<T>* _head; -}; - -int main() { - stack<int>* s = new stack<int>(); - - s->pop(); - s->push(4)->push(2)->push(8); - s->print(); - auto e = s->pop(); - if(e) - cout << e->value << endl; - s->push(1); - s->print(); - - delete s; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/stack_w_array.cc b/1_anno/Programmazione_2/data_structures/stack_w_array.cc deleted file mode 100644 index c20db90..0000000 --- a/1_anno/Programmazione_2/data_structures/stack_w_array.cc +++ /dev/null @@ -1,50 +0,0 @@ -#include<iostream> - -using namespace std; - -template<class H> -class stack { -public: - stack(int n) : _size{n}, _top{-1} { - _arr = new H[n]; - } - ~stack() { - delete _arr; - } - bool is_empty() { - return _top == -1; - } - bool is_full() { - return _top == _size-1; - } - stack<H>* push(H x) { - if(!is_full()) { - _arr[++_top] = x; - } - return this; - } - H pop() { - if(is_empty()) - return -1; - _top--; - return _arr[_top+1]; - } -private: - int _size; - H* _arr; - short _top; -}; - -int main() { - stack<int>* s = new stack<int>{7}; - - s->push(15)->push(6)->push(2)->push(9)->push(17)->push(3); - cout << s->pop() << '\n'; - s->push(18)->push(19)->push(12); - - for(int i = 0; i < 7; ++i) - cout << s->pop() << ' '; - - delete s; - return 0; -} diff --git a/1_anno/Programmazione_2/data_structures/top-sort.cc b/1_anno/Programmazione_2/data_structures/top-sort.cc deleted file mode 100644 index 7441ee9..0000000 --- a/1_anno/Programmazione_2/data_structures/top-sort.cc +++ /dev/null @@ -1,212 +0,0 @@ - -#include<iostream> -#include<vector> -#include<queue> -#define W -1 -#define G 0 -#define B 1 - -using namespace std; - -template<class H> -class node { -public: - explicit node(H key, node<H>* next) : _key{key}, _next(next) {} - const H& key() const { return _key; } - H& key() { return _key; } - const node<H>*& next() const { return _next; } - node<H>*& next() { return _next; } -private: - H _key; - node<H>* _next; -}; - -template<class H> -class list { -public: - list() : _head{nullptr} {} - ~list() { - while(_head) { - auto tmp = _head; - _head = _head->next(); - delete tmp; - } - } - list<H>* push(H val) { - auto iter = _head; - while(iter && iter->next()) - iter = iter->next(); - - if(!iter) - _head = new node<H>{val, nullptr}; - else - iter->next() = new node<H>{val, nullptr}; - - return this; - } - void print() { - auto iter = _head; - while(iter) { - cout << iter->key() << ' '; - iter = iter->next(); - } - } - vector<H> as_vector() { - vector<H> v; - auto iter = _head; - while(iter) { - v.push_back(iter->key()); - iter = iter->next(); - } - return v; - } - node<H>* search(H val) { - auto iter = _head; - while(iter && iter->key() != val) { - iter = iter->next(); - } - - return iter; - } -private: - node<H>* _head; -}; - -template<class H> -class graph { -private: - int _len, _nodes, _edges; - int* _parents; - int* _radixes; - int* _distances; - int* _finishes; - int* _colors; - int _time; - int _current; - H** _k; // it works like a dictionary, it saves the keys - list<int>** _adj; - int _index(H val) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == val) return i; - - return -1; - } - bool _dfsvisit(int u) { - bool cycle = false; - _colors[u] = G; - _distances[u] = _time++; - _radixes[u] = _current; - for(auto const& v : _adj[u]->as_vector()) { - if(_colors[v] == W) { - _parents[v] = u; - _dfsvisit(v); - } else if(_colors[v] == G) { - cycle = true; - } - } - _colors[u] = B; - _finishes[u] = _time++; - return cycle; - } -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new list<int>*[_len]; - _parents = new int[_len]; - _radixes = new int[_len]; - _distances = new int[_len]; - _finishes = new int[_len]; - _colors = new int[_len]; - for(int i = 0; i < _len; ++i) { - _k[i] = nullptr; - _adj[i] = new list<int>{}; - } - } - - graph<H>* add_node(H k) { - if(_nodes == _len) return this; - if(_index(k) >= 0) return this; // node is already there - - _k[_nodes++] = new H(k); - - return this; - } - - - bool dfs() { - bool cycle = 0; - _time = 0; - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - _parents[i] = -1; - } - - for(int i = 0; i < _nodes; ++i) { - if(_colors[i] == W) { - _current = i; - cycle |= _dfsvisit(i); - } - } - for(int i = 0; i < _nodes; ++i) { - cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl; - } - return cycle; - } - - void top_sort() { - bool cycle = dfs(); - if(cycle) { - cerr << "Grafo ciclico\n"; - return; - } - vector<int> s(_finishes, _finishes+_nodes); - sort(begin(s), end(s)); - for(auto const& i : s) { - cout << "(" << i << ", " << _finishes[i] << ") "; - } - } - - graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - - if(!_adj[i]->search(j)) { - _adj[i]->push(j); - _edges++; - } - - return this; - } - - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << i << ", " << *_k[i] << "): "; - for(auto const& j : _adj[i]->as_vector()) - cout << "(" << j << ", " << *_k[j] << "), "; - cout << '\n'; - } - } -}; - - -int main() { - graph<char>* g = new graph<char>(6); - g->add_node('u')->add_node('v')->add_node('x')->add_node('y'); - g->add_node('w')->add_node('z'); - g->add_edge('u', 'v'); - g->add_edge('u', 'x'); - g->add_edge('x', 'v'); - g->add_edge('y', 'x'); - g->add_edge('v', 'y'); - g->add_edge('w', 'y'); - g->add_edge('w', 'z'); - g->add_edge('z', 'z'); - - g->print(); - g->dfs(); - g->top_sort(); - - delete g; - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/carattere-maggiore.cc b/1_anno/Programmazione_2/exercises/carattere-maggiore.cc deleted file mode 100644 index 2e89fcd..0000000 --- a/1_anno/Programmazione_2/exercises/carattere-maggiore.cc +++ /dev/null @@ -1,40 +0,0 @@ -#include<iostream> -#include<map> -#include<fstream> - -using namespace std; - - - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string line; - getline(in, line); - map<char, int> chs; - for(auto const& c : line) { - if(c == ' ') continue; - if(chs.find(c) != chs.end()) - chs[c]++; - else - chs[c] = 1; - } - int n = 0; - char c = 'a'; - for(auto const& i : chs) { - if(i.second >= n) { - if(i.first >= c) { - n = i.second; - c = i.first; - } - } - } - out << c << ' ' << n << endl; - } - - out.close(); - in.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/dequeue.cc b/1_anno/Programmazione_2/exercises/dequeue.cc deleted file mode 100644 index 4b012c4..0000000 --- a/1_anno/Programmazione_2/exercises/dequeue.cc +++ /dev/null @@ -1,137 +0,0 @@ - -#include<iostream> -#include<fstream> - -using namespace std; - -template<class T> -class node { -public: - node(T key, node<T>* next) : _key{key}, _next{next} {} - node(T key) : _key{key}, _next{nullptr} {} - const T& key() const { return _key; } - T& key() { return _key; } - const node<T>*& next() const { return _next; } - node<T>*& next() { return _next; } -private: - T _key; - node<T>* _next; -}; - -template<class T> -class Coda { -public: - Coda() : _head{nullptr}, _tail{nullptr} {} - ~Coda() { - - } - Coda<T>* enqueue(T val) { - if(!_head) { - _head = new node<T>{val, nullptr}; - _tail = _head; - } else { - _tail->next() = new node<T>{val, nullptr}; - _tail = _tail->next(); - } - - return this; - } - node<T>* dequeue() { - if(!_head) return nullptr; - node<T>* elem = _head; - delete _head; - _head = elem->next(); - - return elem; - } - - bool is_empty() { return _head == nullptr; } -private: - node<T>* _head; - node<T>* _tail; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t; - int n; - in >> t; - switch(t.at(0)) { - case 'b': { - Coda<bool>* queue = new Coda<bool>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - queue->enqueue(s.at(1) - '0'); - } else { - queue->dequeue(); - } - } - while(!queue->is_empty()) - out << queue->dequeue()->key() << ' '; - out << endl; - break; - } - case 'd': { - Coda<double>* queue = new Coda<double>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - queue->enqueue(stod(s.substr(1, s.length()-1))); - } else { - queue->dequeue(); - } - } - while(!queue->is_empty()) - out << queue->dequeue()->key() << ' '; - out << endl; - break; - } - case 'c': { - Coda<char>* queue = new Coda<char>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - queue->enqueue(s.at(1)); - } else { - queue->dequeue(); - } - } - while(!queue->is_empty()) - out << queue->dequeue()->key() << ' '; - out << endl; - break; - } - case 'i': { - Coda<int>* queue = new Coda<int>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - queue->enqueue(stoi(s.substr(1, s.length()-1))); - } else { - queue->dequeue(); - } - } - while(!queue->is_empty()) - out << queue->dequeue()->key() << ' '; - out << endl; - break; - } - } - } - in.close(); - out.close(); - return 0; -} - diff --git a/1_anno/Programmazione_2/exercises/doppioni.cc b/1_anno/Programmazione_2/exercises/doppioni.cc deleted file mode 100644 index fdd3e88..0000000 --- a/1_anno/Programmazione_2/exercises/doppioni.cc +++ /dev/null @@ -1,77 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -template<class T> -class node { -public: - node(T key, node* parent, node* right, node* left) : _key{key}, _parent{parent}, _right{right}, _left{left} {} - T& key() { return _key; } - const T& key() const { return _key; } - node<T>*& parent() { return _parent; } - const node<T>*& parent() const { return _parent; } - node<T>*& right() { return _right; } - const node<T>*& right() const { return _right; } - node<T>*& left() { return _left; } - const node<T>*& left() const { return _left; } -private: - T _key; - node<T>* _parent; - node<T>* _right; - node<T>* _left; -}; - -class bst { -public: - bst() : _duplicates{0}, _root{nullptr} {} - bst* add(int val) { - node<int>* iter = _root; - node<int>* prev = nullptr; - while(iter) { - prev = iter; - if(iter->key() == val) { - _duplicates++; - return this; - } - - if(iter->key() > val) - iter = iter->right(); - else - iter = iter->left(); - } - - node<int>* nodus = new node<int>{val, prev, nullptr, nullptr}; - if(!prev) - _root = nodus; - else if(prev->key() > val) - prev->right() = nodus; - else - prev->left() = nodus; - - return this; - } - const int& duplicates() const { return _duplicates; } -private: - int _duplicates; - node<int>* _root; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - for(int ts = 0; ts < 100; ++ts) { - bst* b = new bst{}; - int n; - in >> n; - int e; - for(int i = 0; i < n; ++i) { - in >> e; - b->add(e); - } - out << b->duplicates() << endl; - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/estremi-uguali.cc b/1_anno/Programmazione_2/exercises/estremi-uguali.cc deleted file mode 100644 index 63ac019..0000000 --- a/1_anno/Programmazione_2/exercises/estremi-uguali.cc +++ /dev/null @@ -1,32 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -int result(string s) { - if(s.at(0) == s.at(s.length()-1)) - return 1; - - return 0; -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int _; - string s; - int size{}; - for(int i = 0; i < 3; ++i) { - in >> _ >> s; - size += result(s); - } - out << size << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/even-length.cc b/1_anno/Programmazione_2/exercises/even-length.cc deleted file mode 100644 index 2d3d6a4..0000000 --- a/1_anno/Programmazione_2/exercises/even-length.cc +++ /dev/null @@ -1,27 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -string result(string s) { - if(s.length() % 2 == 0) - return s; - - return s.substr(0, s.length()-1); -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string s; - in >> s; - out << result(s) << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/exam_08_10_14.cc b/1_anno/Programmazione_2/exercises/exam_08_10_14.cc deleted file mode 100644 index c9c33be..0000000 --- a/1_anno/Programmazione_2/exercises/exam_08_10_14.cc +++ /dev/null @@ -1,202 +0,0 @@ -#include<iostream> - -using namespace std; - -template<class H> class MultiBST { - virtual MultiBST<H>* ins(H x) = 0; - virtual int multiplicity(H x) = 0; - virtual void inorder() = 0; -}; - -template<class H> -class node { -public: - node(H val) : _key{val}, _parent{nullptr}, _left{nullptr}, _right{nullptr}, _rk{1} {} - H& key() { return _key; } - const H& key() const { return _key; } - node<H>*& parent() { return _parent; } - const node<H>*& parent() const { return _parent; } - node<H>*& left() { return _left; } - const node<H>*& left() const { return _left; } - node<H>*& right() { return _right; } - const node<H>*& right() const { return _right; } - int& rk() { return _rk; } - const int& rk() const { return _rk; } -private: - H _key; - node<H>* _parent; - node<H>* _left; - node<H>* _right; - int _rk; -}; - -template<class H> -class MyMultiBST : public MultiBST<H> { -public: - MyMultiBST() : _root{nullptr} {} - node<H>*& root() { return _root; } - const node<H>*& root() const { return _root; } - int multiplicity(H x) { - auto elem = _search(x); - if(elem) - return elem->rk(); - return 0; - } - MyMultiBST<H>* ins(H x) { - auto iter = _search(x); - if(iter) { - iter->rk() = iter->rk()+1; - } else { - iter = _root; - node<H>* y{nullptr}; - - while(iter) { - y = iter; - if(iter->key() > x) - iter = iter->left(); - else - iter = iter->right(); - } - - node<H>* nodus = new node<H>{x}; - nodus->parent() = y; - if(!y) { - _root = nodus; - } else if(y->key() > x) { - y->left() = nodus; - } else { - y->right() = nodus; - } - } - - return this; - } - void inorder() { - _inorder(_root); - } - MyMultiBST<H>* del(H x) { - node<H>* y; - node<H>* z = _search(x); - - if(!z) return this; - - if(z->rk() > 1) { - z->rk() = z->rk()-1; - } else { - if(!z->left()) { - _transplant(z, z->right()); - } else if(!z->right()) { - _transplant(z, z->left()); - } else { - y = _min(z->right()); - if(y->parent() != z) { - _transplant(y, y->right()); - y->right() = z->right(); - y->right()->parent() = y; - } - _transplant(z, y); - y->left() = z->left(); - y->left()->parent() = y; - delete z; - } - } - - return this; - } - node<H>* predecessor(H x) { - auto iter = _search(x); - if(!iter) return nullptr; - if(iter->left()) - return _max(iter->left()); - - auto y = iter->parent(); - while(y && iter == y->left()) { - iter = y; - y = y->parent(); - } - - return y; - } - int rank(H x) { - auto iter = predecessor(x); - int sum{1}; - while(iter) { - sum+=iter->rk(); - iter = predecessor(iter->key()); - } - return sum; - } -private: - void _transplant(node<H>* u, node<H>* v) { - if(!u->parent()) _root = v; - else if(u == u->parent()->left()) - u->parent()->left() = v; - else - u->parent()->right() = v; - - if(v) - v->parent() = u->parent(); - } - node<H>* _max(node<H>* x) { - if(!x) return nullptr; - - auto iter = x; - while(iter->right()) { - iter = iter->right(); - } - - return iter; - } - node<H>* _min(node<H>* x) { - if(!x) return nullptr; - - auto iter = x; - while(iter->left()) { - iter = iter->left(); - } - - return iter; - } - void _inorder(node<H>* p) { - if(p) { - _inorder(p->left()); - for(int i = 0; i < p->rk(); ++i) { - cout << p->key() << ' '; - } - _inorder(p->right()); - } - } - node<H>* _search(H val) { - auto iter = _root; - while(iter && iter->key() != val) { - if(iter->key() > val) - iter = iter->left(); - else - iter = iter->right(); - } - - return iter; - } - node<H>* _root; -}; - -int main() { - MyMultiBST<int>* t = new MyMultiBST<int>{}; - - for(auto const& i : {10, 7, 7, 23, 30, 4, 1, 5, 9, 5, 1, 7, 1, 9}) - t->ins(i); - - t->inorder(); - cout << '\n'; - for(auto const& i : {5, 7, 17}) - cout << i << ": " << t->multiplicity(i) << endl; - - for(auto const& i : {7, 4, 23, 7, 7}) - t->del(i); - t->inorder(); - cout << '\n'; - for(auto const& i: {5, 9, 30}) - cout << t->rank(i) << ' '; - delete t; - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp deleted file mode 100644 index 4f08a74..0000000 --- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp +++ /dev/null @@ -1,39 +0,0 @@ -#include<iostream> -#include<sstream> -#include<fstream> -#include<vector> - -using namespace std; -int insertionsort(vector<int>& a, int n) { - int c = 0; - for(int i = 1; i < n; ++i) { - int j = i-1; - int key = a[i]; - while(j > -1 && a[j] > key) { - swap(a[j+1], a[j]); - --j; - c++; - } - a[j+1] = key; - } - return c; -} -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int N; - in >> N; - int a, b; - vector<int> v; - for(int i = 0; i < N; ++i) { - in >> a >> b; - v.push_back(a+b); - } - out << insertionsort(v, v.size()) << endl; - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp deleted file mode 100644 index aed25e4..0000000 --- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include<iostream> -#include<sstream> -#include<fstream> -#include<queue> - -using namespace std; -using pi = tuple<int, int, vector<int>>; - -class comp { -public: - bool operator()(const pi& lhs, const pi& rhs) const { - auto xl = get<0>(lhs); - auto yl = get<0>(rhs); - - auto il = get<1>(lhs); - auto jl = get<1>(rhs); - if(xl == yl) - return il > jl; - return xl > yl; - } -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int R, C; - in >> R >> C; - vector<vector<int>> v; - priority_queue<pi, vector<pi>, comp> pq; - int k; - for(int i = 0; i < R; ++i) { - v.push_back(vector<int>{}); - for(int j = 0; j < C; ++j) { - in >> k; - v[i].push_back(k); - } - } - - int index = 0; - for(auto const& i : v) { - int s = 0; - pi qq; - for(auto const& j : i) - s += j; - get<0>(qq) = s; - get<1>(qq) = index++; - get<2>(qq) = i; - pq.push(qq); - } - while(!pq.empty()) { - auto q = pq.top(); - pq.pop(); - for(auto const& i : get<2>(q)) - out << i << ' '; - } - out << endl; - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp deleted file mode 100644 index 71f9c65..0000000 --- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp +++ /dev/null @@ -1,284 +0,0 @@ -#include<iostream> -#include<sstream> -#include<fstream> - -using namespace std; - -template<class T> -struct node { - T key; - node<T>* prev; - node<T>* right; - node<T>* left; -}; - -template<class T> -class bst { -public: - bst() : root{nullptr} , _val{0}{} - - ~bst() { - // TODO - } - - bst<T>* insert(initializer_list<T>&& list) { - for(auto const& i : list) - insert(i); - - return this; - } - - bst<T>* insert(T k) { - node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr}; - node<T>* iter = root; - node<T>* prev = nullptr; - - while(iter) { - prev = iter; - iter = (k < iter->key) ? iter->left : iter->right; - } - - nodus->prev = prev; - if(!prev) - root = nodus; - else if(k < prev->key) - prev->left = nodus; - else - prev->right = nodus; - - return this; - } - - bst<T>* remove(initializer_list<T>&& list) { - for(auto const& i : list) - remove(i); - - return this; - } - - bst<T>* remove(T k) { - node<T>* nodus = search(k); - if(!nodus) return this; - - if(!nodus->left) { - _transplant(nodus, nodus->right); - } else if(!nodus->right) { - _transplant(nodus, nodus->left); - } else { - node<T>* iter = _min(nodus->right); - if(iter->prev != nodus) { - _transplant(iter, iter->right); - iter->right = nodus->right; - iter->right->prev = iter; - } - _transplant(nodus, iter); - iter->left = nodus->left; - iter->left->prev = iter; - } - - delete nodus; - return this; - } - - node<T>* min() { - return _min(root); - } - - node<T>* min(node<T>* nodus) { - return _min(nodus); - } - - node<T>* max() { - return _max(root); - } - - node<T>* max(node<T>* nodus) { - return _max(nodus); - } - - node<T>* search(T k) { - node<T>* iter = root; - while(iter && iter->key != k) - iter = (iter->key > k) ? iter->left : iter->right; - - return iter; - } - - node<T>* successor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->right) - return min(nodus->right); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->right) { - nodus = prev; - prev = prev->prev; - } - - return prev; - - } - node<T>* predecessor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->left) - return max(nodus->left); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->left) { - nodus = prev; - prev = prev->prev; - } - - return prev; - } - - friend ostream& operator<<(ostream& os, bst<T>* tree) { - tree->_inorder(os, tree->root); - return os; - } - T sol(T k) { - return _max(search(k))->key; - } -private: - int _val; - void _transplant(node<T>* u, node<T>* v) { - if(!u->prev) { - root = v; - } else if(u == u->prev->left) { - u->prev->left = v; - } else { - u->prev->right = v; - } - - if(v) - v->prev = u->prev; - } - - node<T>* _min(node<T>* root) { - node<T>* iter = root; - while(iter && iter->left) - iter = iter->left; - - return iter; - } - - node<T>* _max(node<T>* root) { - node<T>* iter = root; - while(iter && iter->right) - iter = iter->right; - - return iter; - } - - void _inorder(ostream& os, node<T>* root) { - if(root) { - if(root->right && root->left) { - _val++; - } - _inorder(os, root->left); - os << root->key << ' '; - _inorder(os, root->right); - } - } - - void _preorder(ostream& os, node<T>* root) { - if(root) { - os << root->key << ' '; - _inorder(os, root->left); - _inorder(os, root->right); - } - } - - void _postorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - _inorder(os, root->right); - os << root->key << ' '; - } - } - node<T>* root; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t, comm; - in >> t; - int n; - switch(t.at(0)) { - case 'd': - { - bst<double>* b = new bst<double>{}; - in >> n; - double k; - for(int i = 0; i < n; ++i) { - in >> comm; - stringstream tcomm(comm); - int ex= 0; - while(getline(tcomm, comm, ':')) { - if(ex == 0) { - if(comm == "ins") - ex = 1; - else - ex = 2; - } else { - if(ex == 1) - b->insert(stod(comm)); - else - b->remove(stod(comm)); - ex = 0; - } - } - } - in >> k; - cout << b << endl; - out << b->sol(k) << endl; - - delete b; - break; - } - case 'i': - { - bst<int>* b = new bst<int>{}; - in >> n; - int k; - for(int i = 0; i < n; ++i) { - in >> comm; - stringstream tcomm(comm); - int ex= 0; - while(getline(tcomm, comm, ':')) { - if(ex == 0) { - if(comm == "ins") - ex = 1; - else - ex = 2; - } else { - if(ex == 1) - b->insert(stoi(comm)); - else - b->remove(stoi(comm)); - ex = 0; - } - } - } - in >> k; - cout << b << endl; - out << b->sol(k) << endl; - - delete b; - break; - } - } - } - - in.close(); - out.close(); - return 0; -} - diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp deleted file mode 100644 index e234363..0000000 --- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp +++ /dev/null @@ -1,293 +0,0 @@ -#include<iostream> -#include<sstream> -#include<fstream> - -using namespace std; - -template<class T> -struct node { - T key; - node<T>* prev; - node<T>* right; - node<T>* left; -}; - -template<class T> -class bst { -public: - bst() : root{nullptr} , _val{0}{} - - ~bst() { - // TODO - } - - bst<T>* insert(initializer_list<T>&& list) { - for(auto const& i : list) - insert(i); - - return this; - } - - bst<T>* insert(T k) { - node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr}; - node<T>* iter = root; - node<T>* prev = nullptr; - - while(iter) { - prev = iter; - iter = (k < iter->key) ? iter->left : iter->right; - } - - nodus->prev = prev; - if(!prev) - root = nodus; - else if(k < prev->key) - prev->left = nodus; - else - prev->right = nodus; - - return this; - } - - bst<T>* remove(initializer_list<T>&& list) { - for(auto const& i : list) - remove(i); - - return this; - } - - bst<T>* remove(T k) { - node<T>* nodus = search(k); - if(!nodus) return this; - - if(!nodus->left) { - _transplant(nodus, nodus->right); - } else if(!nodus->right) { - _transplant(nodus, nodus->left); - } else { - node<T>* iter = _min(nodus->right); - if(iter->prev != nodus) { - _transplant(iter, iter->right); - iter->right = nodus->right; - iter->right->prev = iter; - } - _transplant(nodus, iter); - iter->left = nodus->left; - iter->left->prev = iter; - } - - delete nodus; - return this; - } - - node<T>* min() { - return _min(root); - } - - node<T>* min(node<T>* nodus) { - return _min(nodus); - } - - node<T>* max() { - return _max(root); - } - - node<T>* max(node<T>* nodus) { - return _max(nodus); - } - - node<T>* search(T k) { - node<T>* iter = root; - while(iter && iter->key != k) - iter = (iter->key > k) ? iter->left : iter->right; - - return iter; - } - - node<T>* successor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->right) - return min(nodus->right); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->right) { - nodus = prev; - prev = prev->prev; - } - - return prev; - - } - node<T>* predecessor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->left) - return max(nodus->left); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->left) { - nodus = prev; - prev = prev->prev; - } - - return prev; - } - - friend ostream& operator<<(ostream& os, bst<T>* tree) { - tree->_inorder(os, tree->root); - return os; - } - T sol(T k) { - auto x = search(k); - auto m = _max(x)->key; - auto mnn = _min(x); - T mn; - if(mnn->right) - mn = _min(mnn->right)->key; - else - mn = mnn->key; - cout << m << ' ' << mn << endl; - return m - mn; - } -private: - int _val; - void _transplant(node<T>* u, node<T>* v) { - if(!u->prev) { - root = v; - } else if(u == u->prev->left) { - u->prev->left = v; - } else { - u->prev->right = v; - } - - if(v) - v->prev = u->prev; - } - - node<T>* _min(node<T>* root) { - node<T>* iter = root; - while(iter && iter->left) - iter = iter->left; - - return iter; - } - - node<T>* _max(node<T>* root) { - node<T>* iter = root; - while(iter && iter->right) - iter = iter->right; - - return iter; - } - - void _inorder(ostream& os, node<T>* root) { - if(root) { - if(root->right && root->left) { - _val++; - } - _inorder(os, root->left); - os << root->key << ' '; - _inorder(os, root->right); - } - } - - void _preorder(ostream& os, node<T>* root) { - if(root) { - os << root->key << ' '; - _inorder(os, root->left); - _inorder(os, root->right); - } - } - - void _postorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - _inorder(os, root->right); - os << root->key << ' '; - } - } - node<T>* root; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t, comm; - in >> t; - int n; - switch(t.at(0)) { - case 'd': - { - bst<double>* b = new bst<double>{}; - in >> n; - double k; - for(int i = 0; i < n; ++i) { - in >> comm; - stringstream tcomm(comm); - int ex= 0; - while(getline(tcomm, comm, ':')) { - if(ex == 0) { - if(comm == "ins") - ex = 1; - else - ex = 2; - } else { - if(ex == 1) - b->insert(stod(comm)); - else - b->remove(stod(comm)); - ex = 0; - } - } - } - in >> k; - cout << b << endl; - out << b->sol(k) << endl; - - delete b; - break; - } - case 'i': - { - bst<int>* b = new bst<int>{}; - in >> n; - int k; - for(int i = 0; i < n; ++i) { - in >> comm; - stringstream tcomm(comm); - int ex= 0; - while(getline(tcomm, comm, ':')) { - if(ex == 0) { - if(comm == "ins") - ex = 1; - else - ex = 2; - } else { - if(ex == 1) - b->insert(stoi(comm)); - else - b->remove(stoi(comm)); - ex = 0; - } - } - } - in >> k; - cout << b << endl; - out << b->sol(k) << endl; - - delete b; - break; - } - } - } - - in.close(); - out.close(); - return 0; -} - diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp deleted file mode 100644 index dd8fc98..0000000 --- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp +++ /dev/null @@ -1,285 +0,0 @@ -#include<iostream> -#include<vector> -#include<algorithm> -#include<queue> -#include<stack> -#include<fstream> -#define INF 99999999 -#define W -1 -#define G 0 -#define B 1 - -using namespace std; - -template<class H> -class graph { -public: - graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _k = new H*[len]; - _adj = new vector<int>[len]; - _colors = new int[len]; - _d = new int[len]; - _f = new int[len]; - _p = new int[len]; - - for(int i = 0; i < len; ++i) { - _k[i] = nullptr; - } - } - ~graph() { - delete[] _k; - delete[] _adj; - } - - graph<H>* add_node(H x) { - if(_index(x) > -1) return this; - if(_nodes == _len) return this; - _k[_nodes++] = new H(x); - - return this; - } - graph<H>* add_edge(H u, H v) { - int i = _index(u); - int j = _index(v); - if(i < 0 || j < 0) return this; - - if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) { - _adj[i].push_back(j); - } - return this; - } - void print() { - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): "; - for(auto const& j : _adj[i]) { - cout << "(" << *_k[j] << ", " << j << ") "; - } - cout << endl; - } - } - void dfsvisit(int u, bool visited[]) { - visited[u] = true; - cout << "(" << *_k[u] << ", " << u << ") "; - for(auto const& i : _adj[u]) { - if(!visited[i]) - dfsvisit(i, visited); - } - } - int dfsvisit(int u) { - int cycle = 0; - _colors[u] = G; - _d[u] = _time++; - - for(auto const& j : _adj[u]) { - if(_colors[j] == W) - cycle |= dfsvisit(j); - } - - _colors[u] = B; - _stack.push(u); - _f[u] = _time++; - return cycle; - } - int dfs() { - int cycle = 0; - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - } - _time = 0; - for(int i = 0; i < _nodes; ++i) { - if(_colors[i] == W) - cycle |= dfsvisit(i); - else if(_colors[i] == G) - cycle = 1; - } - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl; - } - return cycle; - } - - void top_sort() { - int cycle = dfs(); - if(cycle) { - cout << "cyclic graph!" << endl; - return; - } - int* s = new int[_nodes]; - for(int i = 0; i < _nodes; ++i) s[i] = i; - _sort(s, _nodes, _f); - for(int i = 0; i < _nodes; ++i) { - cout << "(" << s[i] << ", " << _f[s[i]] << ") "; - } - - } - - void bfs(H v) { - int s = _index(v); - if(s < 0) return; - - for(int i = 0; i < _nodes; ++i) { - _colors[i] = W; - _d[i] = INF; - _p[i] = -1; - } - _colors[s] = G; - _d[s] = 0; - queue<int> q; - q.push(s); - while(!q.empty()) { - int u = q.front(); - q.pop(); - for(auto const& j : _adj[u]) { - if(_colors[j] == W) { - _colors[j] = G; - _d[j] = _d[u]+1; - _p[j] = u; - q.push(j); - } - } - _colors[u] = B; - } - for(int i = 0; i < _nodes; ++i) { - cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl; - } - } - int ssc() { - dfs(); - cout << endl << endl; - bool* visited = new bool[_nodes]; - for(int i = 0; i < _nodes; ++i) - visited[i] = false; - int count = 0; - while(!_stack.empty()) { - int v = _stack.top(); - _stack.pop(); - if(!visited[v]) { - dfsvisit(v, visited); - count++; - cout << endl; - } - } - delete[] visited; - return count; - } -private: - graph<H>* _transpose() { - graph<H>* g = new graph<H>{_len}; - for(int i = 0; i < _nodes; ++i) { - g->add_node(*_k[i]); - } - - for(int i = 0; i < _nodes; ++i) { - for(auto const& j : _adj[i]) { - g->add_edge(j, i); - } - } - - return g; - } - void _sort(int* d, int n, int* s) { - for(int i = -1; i < n; ++i) { - int j = i-1; - while(j > -1 && s[d[j+1]]>s[d[j]]) { - swap(d[s[j+1]], d[s[j]]); - --j; - } - } - } - int _index(H x) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == x) return i; - - return -1; - } - stack<int> _stack; - H** _k; - vector<int>* _adj; - int _len, _nodes, _edges; - int* _colors; - int _time; - int* _d; - int* _f; - int* _p; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int n, e; - in >> n>>e; - string t; - in >> t; - char _t; - switch(t.at(0)){ - case 'd':{ - graph<double>* g = new graph<double>{n}; - double x, y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - for(int i = 0; i < e; ++i) { - in >>_t; - in >> x >> y; - in >> _t; - g->add_edge(x, y); - g->add_edge(y, x); - } - g->print(); - cout << endl << endl; - out << g->ssc()<<endl; - delete g; - break; - } - case 'i':{ - - graph<int>* g = new graph<int>{n}; - int x, y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - for(int i = 0; i < e; ++i) { - in >>_t; - in >> x >> y; - in >> _t; - g->add_edge(x, y); - g->add_edge(y, x); - } - g->print(); - cout << endl << endl; - out << g->ssc()<<endl; - delete g; - break; - } - case 'c': { - - graph<char>* g = new graph<char>{n}; - char x, y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - for(int i = 0; i < e; ++i) { - in >>_t; - in >> x >> y; - in >> _t; - g->add_edge(x, y); - g->add_edge(y, x); - } - g->print(); - cout << endl << endl; - out << g->ssc()<<endl; - delete g; - break; - } - } - } - in.close(); - out.close(); - return 0; -} - diff --git a/1_anno/Programmazione_2/exercises/inizia-con.cc b/1_anno/Programmazione_2/exercises/inizia-con.cc deleted file mode 100644 index 97f0c39..0000000 --- a/1_anno/Programmazione_2/exercises/inizia-con.cc +++ /dev/null @@ -1,33 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -string result(string s, char c) { - if(s.at(0) == c) - return s + ' '; - - return ""; -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int _; - string s; - char c; - in >> c; - for(int i = 0; i < 3; ++i) { - in >> _ >> s; - out << result(s, c); - } - out << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/inserimento-coda.cc b/1_anno/Programmazione_2/exercises/inserimento-coda.cc deleted file mode 100644 index 6775ca2..0000000 --- a/1_anno/Programmazione_2/exercises/inserimento-coda.cc +++ /dev/null @@ -1,119 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -template<class T> -class node { -public: - node(T key, node<T>* next) : _key{key}, _next{next} {} - node(T key) : _key{key}, _next{nullptr} {} - const T& key() const { return _key; } - T& key() { return _key; } - const node<T>*& next() const { return _next; } - node<T>*& next() { return _next; } -private: - T _key; - node<T>* _next; -}; - -template<class T> -class Coda { -public: - Coda() : _head{nullptr}, _tail{nullptr} {} - ~Coda() { - - } - Coda<T>* enqueue(T val) { - if(!_head) { - _head = new node<T>{val, nullptr}; - _tail = _head; - } else { - _tail->next() = new node<T>{val, nullptr}; - _tail = _tail->next(); - } - - return this; - } - node<T>* pop() { - if(!_head) return nullptr; - node<T>* elem = _head; - delete _head; - _head = elem->next(); - - return elem; - } - - bool is_empty() { return _head == nullptr; } -private: - node<T>* _head; - node<T>* _tail; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t; - int n; - in >> t; - switch(t.at(0)) { - case 'b': { - Coda<bool>* queue = new Coda<bool>{}; - in >> n; - bool e; - for(int i = 0; i < n; ++i) { - in >> e; - queue->enqueue(e); - } - while(!queue->is_empty()) - out << queue->pop()->key() << ' '; - out << endl; - break; - } - case 'd': { - Coda<double>* queue = new Coda<double>{}; - in >> n; - double e; - for(int i = 0; i < n; ++i) { - in >> e; - queue->enqueue(e); - } - while(!queue->is_empty()) - out << queue->pop()->key() << ' '; - out << endl; - break; - } - case 'c': { - Coda<char>* queue = new Coda<char>{}; - in >> n; - char e; - for(int i = 0; i < n; ++i) { - in >> e; - queue->enqueue(e); - } - while(!queue->is_empty()) - out << queue->pop()->key() << ' '; - out << endl; - break; - } - case 'i': { - Coda<int>* queue = new Coda<int>{}; - in >> n; - int e; - for(int i = 0; i < n; ++i) { - in >> e; - queue->enqueue(e); - } - while(!queue->is_empty()) - out << queue->pop()->key() << ' '; - out << endl; - break; - } - } - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/inserimento-pila.cc b/1_anno/Programmazione_2/exercises/inserimento-pila.cc deleted file mode 100644 index 0dbe99b..0000000 --- a/1_anno/Programmazione_2/exercises/inserimento-pila.cc +++ /dev/null @@ -1,116 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -template<class T> -class node { -public: - node(T key, node<T>* next) : _key{key}, _next{next} {} - node(T key) : _key{key}, _next{nullptr} {} - const T& key() const { return _key; } - T& key() { return _key; } - const node<T>*& next() const { return _next; } - node<T>*& next() { return _next; } -private: - T _key; - node<T>* _next; -}; - -template<class T> -class Pila { -public: - Pila() : _head{nullptr}{} - ~Pila() { - - } - Pila<T>* push(T val) { - if(!_head) { - _head = new node<T>{val, nullptr}; - } else { - _head = new node<T>{val, _head}; - } - - return this; - } - node<T>* pop() { - if(!_head) return nullptr; - node<T>* elem = _head; - delete _head; - _head = elem->next(); - - return elem; - } - - bool is_empty() { return _head == nullptr; } -private: - node<T>* _head; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t; - int n; - in >> t; - switch(t.at(0)) { - case 'b': { - Pila<bool>* stack = new Pila<bool>{}; - in >> n; - bool e; - for(int i = 0; i < n; ++i) { - in >> e; - stack->push(e); - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'd': { - Pila<double>* stack = new Pila<double>{}; - in >> n; - double e; - for(int i = 0; i < n; ++i) { - in >> e; - stack->push(e); - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'c': { - Pila<char>* stack = new Pila<char>{}; - in >> n; - char e; - for(int i = 0; i < n; ++i) { - in >> e; - stack->push(e); - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'i': { - Pila<int>* stack = new Pila<int>{}; - in >> n; - int e; - for(int i = 0; i < n; ++i) { - in >> e; - stack->push(e); - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - } - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/matrice-adj.cc b/1_anno/Programmazione_2/exercises/matrice-adj.cc deleted file mode 100644 index 7830f97..0000000 --- a/1_anno/Programmazione_2/exercises/matrice-adj.cc +++ /dev/null @@ -1,151 +0,0 @@ -#include<iostream> -#include<vector> -#include<fstream> -#include<sstream> - -using namespace std; - -template<class H> -class matrix_graph { -public: - ~matrix_graph() { - delete[] _m; - delete[] _k; - } - matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} { - _m = new int*[len]; - _k = new H*[len]; - for(int i = 0; i < len; ++i) { - _m[i] = new int[len]; - _k[i] = nullptr; - for(int j = 0; j < len; ++j) - _m[i][j] = 0; - } - } - - matrix_graph<H>* add_node(H k) { - if(_len == _nodes) return this; // no more space for new nodes - if(_index(k) > -1) return this; // nodes already exists - - _k[_nodes++] = new H(k); - - return this; - } - - matrix_graph<H>* add_edge(H x, H y) { - int i = _index(x); - int j = _index(y); - if(i < 0 || j < 0) return this; - if(!_m[i][j]) { - _m[i][j] = 1; - _edges++; - } - return this; - } - vector<vector<H>> print() { - vector<vector<H>> v; - for(int i = 0; i < _len; ++i) { - v.push_back(vector<H>{*_k[i]}); - vector<H> temp; - for(int j = 0; j < _len; ++j) { - if(_m[i][j]) { - temp.push_back(*_k[j]); - } - } - sort(begin(temp), end(temp)); - for(auto const& j : temp) - v[i].push_back(j); - } - - sort(begin(v), end(v)); - return v; - } -private: - int _len, _nodes, _edges; - int** _m; - H** _k; - int _index(H x) { - for(int i = 0; i < _nodes; ++i) - if(*_k[i] == x) return i; - return -1; - } -}; - -template<class H> -string result(vector<vector<H>> v) { - string s{""}; - ostringstream ss; - for(auto const& i : v) { - s += "("; - for(auto const& j : i) { - ss << j; - s+= ss.str(); - s+= ' '; - ss.str(""); ss.clear(); - } - s.pop_back(); - s += ") "; - } - return s; -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - for(int ts = 0; ts < 100; ++ts) { - int n, m; - in >> n >> m; - string t; - in >> t; - if(t == "int") { - matrix_graph<int>* g = new matrix_graph<int>(n); - int x,y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - char ex; - for(int i = 0; i < m; ++i) { - in >> ex >> x >> y >> ex; - g->add_edge(x, y); - } - auto v = g->print(); - out << result(v) << endl; - delete g; - } else if(t == "double") { - matrix_graph<double>* g = new matrix_graph<double>(n); - double x,y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - char ex; - for(int i = 0; i < m; ++i) { - in >> ex >> x >> y >> ex; - g->add_edge(x, y); - } - auto v = g->print(); - out << result(v) << endl; - delete g; - } else { - matrix_graph<char>* g = new matrix_graph<char>(n); - char x,y; - for(int i = 0; i < n; ++i) { - in >> x; - g->add_node(x); - } - char ex; - for(int i = 0; i < m; ++i) { - in >> ex >> x >> y >> ex; - g->add_edge(x, y); - } - - auto v = g->print(); - out << result(v) << endl; - delete g; - } - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/minore.cc b/1_anno/Programmazione_2/exercises/minore.cc deleted file mode 100644 index 677da76..0000000 --- a/1_anno/Programmazione_2/exercises/minore.cc +++ /dev/null @@ -1,27 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string s; - in >> s; - int minor = stoi(s); - for(in >> s; s != "STOP"; in >> s) { - int si = stoi(s); - if(si < minor) - minor = si; - } - - out << minor << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/pop-stack.cc b/1_anno/Programmazione_2/exercises/pop-stack.cc deleted file mode 100644 index 3739450..0000000 --- a/1_anno/Programmazione_2/exercises/pop-stack.cc +++ /dev/null @@ -1,132 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -template<class T> -class node { -public: - node(T key, node<T>* next) : _key{key}, _next{next} {} - node(T key) : _key{key}, _next{nullptr} {} - const T& key() const { return _key; } - T& key() { return _key; } - const node<T>*& next() const { return _next; } - node<T>*& next() { return _next; } -private: - T _key; - node<T>* _next; -}; - -template<class T> -class Pila { -public: - Pila() : _head{nullptr}{} - ~Pila() { - - } - Pila<T>* push(T val) { - if(!_head) { - _head = new node<T>{val, nullptr}; - } else { - _head = new node<T>{val, _head}; - } - - return this; - } - node<T>* pop() { - if(!_head) return nullptr; - node<T>* elem = _head; - delete _head; - _head = elem->next(); - - return elem; - } - - bool is_empty() { return _head == nullptr; } -private: - node<T>* _head; -}; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string t; - int n; - in >> t; - switch(t.at(0)) { - case 'b': { - Pila<bool>* stack = new Pila<bool>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - stack->push(s.at(1) - '0'); - } else { - stack->pop(); - } - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'd': { - Pila<double>* stack = new Pila<double>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - stack->push(stod(s.substr(1, s.length()-1))); - } else { - stack->pop(); - } - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'c': { - Pila<char>* stack = new Pila<char>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - stack->push(s.at(1)); - } else { - stack->pop(); - } - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - case 'i': { - Pila<int>* stack = new Pila<int>{}; - in >> n; - string s; - for(int i = 0; i < n; ++i) { - in >> s; - if(s.at(0) == 'i') { - stack->push(stoi(s.substr(1, s.length()-1))); - } else { - stack->pop(); - } - } - while(!stack->is_empty()) - out << stack->pop()->key() << ' '; - out << endl; - break; - } - } - } - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/prima-maiuscola.cc b/1_anno/Programmazione_2/exercises/prima-maiuscola.cc deleted file mode 100644 index 6273219..0000000 --- a/1_anno/Programmazione_2/exercises/prima-maiuscola.cc +++ /dev/null @@ -1,30 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -string result(string s) { - s.at(0) = toupper(s.at(0)); - - return s; -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int _; - string s; - for(int i = 0; i < 3; ++i) { - in >> _ >> s; - out << result(s) << ' '; - } - out << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/ripetute.cc b/1_anno/Programmazione_2/exercises/ripetute.cc deleted file mode 100644 index 23d151a..0000000 --- a/1_anno/Programmazione_2/exercises/ripetute.cc +++ /dev/null @@ -1,20 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string s; - in >> s; - out << s+s << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/sol-ripetute.cc b/1_anno/Programmazione_2/exercises/sol-ripetute.cc deleted file mode 100644 index 1518d76..0000000 --- a/1_anno/Programmazione_2/exercises/sol-ripetute.cc +++ /dev/null @@ -1,25 +0,0 @@ -#include<iostream> -#include<string> -#include<fstream> - -using namespace std; - -string result(string s) { - int half = s.length()/2; - return s.substr(0, half); -} - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - string s; - in >> s; - out << result(s) << '\n'; - } - - in.close(); - out.close(); - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/sottosequenza.cc b/1_anno/Programmazione_2/exercises/sottosequenza.cc deleted file mode 100644 index 1d7c481..0000000 --- a/1_anno/Programmazione_2/exercises/sottosequenza.cc +++ /dev/null @@ -1,26 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int n; string s; - in >> n >> s; - string tm; - for(int i = 0; i < n; ++i) { - in >> tm; - if(tm.find(s) != string::npos) - out << tm << ' '; - } - out << '\n'; - } - - in.close(); - out.close(); - - return 0; -} diff --git a/1_anno/Programmazione_2/exercises/stringa-inversa.cc b/1_anno/Programmazione_2/exercises/stringa-inversa.cc deleted file mode 100644 index 5c37718..0000000 --- a/1_anno/Programmazione_2/exercises/stringa-inversa.cc +++ /dev/null @@ -1,26 +0,0 @@ -#include<iostream> -#include<fstream> - -using namespace std; - -int main() { - ifstream in("input.txt"); - ofstream out("output.txt"); - - for(int ts = 0; ts < 100; ++ts) { - int n; - in >> n; - for(int i = 0; i < 3; ++i) { - string s; - in >> s; - for(int j = s.length()-1; j > -1; --j) { - out << s.at(j); - } - out << ' '; - } - out << endl; - } - - out.close(); - in.close(); -} |