From f279107065146a4940f5e73602a1c3c09e58b31d Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 18 Oct 2020 18:56:43 +0200 Subject: chore: name of first year folder --- 1_anno/Programmazione_2/algorithms/binarysearch.cc | 33 ++++++++++++++ 1_anno/Programmazione_2/algorithms/cbrt.cc | 37 +++++++++++++++ .../Programmazione_2/algorithms/insertionsort.cc | 42 +++++++++++++++++ 1_anno/Programmazione_2/algorithms/log.cc | 25 +++++++++++ 1_anno/Programmazione_2/algorithms/mergesort.cc | 52 ++++++++++++++++++++++ 1_anno/Programmazione_2/algorithms/pow.cc | 25 +++++++++++ 1_anno/Programmazione_2/algorithms/quicksort.cc | 38 ++++++++++++++++ .../Programmazione_2/algorithms/selectionsort.cc | 46 +++++++++++++++++++ 1_anno/Programmazione_2/algorithms/sqrt.cc | 46 +++++++++++++++++++ 9 files changed, 344 insertions(+) create mode 100644 1_anno/Programmazione_2/algorithms/binarysearch.cc create mode 100644 1_anno/Programmazione_2/algorithms/cbrt.cc create mode 100644 1_anno/Programmazione_2/algorithms/insertionsort.cc create mode 100644 1_anno/Programmazione_2/algorithms/log.cc create mode 100644 1_anno/Programmazione_2/algorithms/mergesort.cc create mode 100644 1_anno/Programmazione_2/algorithms/pow.cc create mode 100644 1_anno/Programmazione_2/algorithms/quicksort.cc create mode 100644 1_anno/Programmazione_2/algorithms/selectionsort.cc create mode 100644 1_anno/Programmazione_2/algorithms/sqrt.cc (limited to '1_anno/Programmazione_2/algorithms') diff --git a/1_anno/Programmazione_2/algorithms/binarysearch.cc b/1_anno/Programmazione_2/algorithms/binarysearch.cc new file mode 100644 index 0000000..c9b4cd7 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/binarysearch.cc @@ -0,0 +1,33 @@ +#include + +using namespace std; + +bool bs(int a[], int i, int j, int x) { + if(j 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 << ' '< + +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 new file mode 100644 index 0000000..9b309d6 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/insertionsort.cc @@ -0,0 +1,42 @@ +#include + +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 new file mode 100644 index 0000000..1e49a2e --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/log.cc @@ -0,0 +1,25 @@ +#include + +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 new file mode 100644 index 0000000..68d28cb --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/mergesort.cc @@ -0,0 +1,52 @@ +#include + +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 new file mode 100644 index 0000000..16cf419 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/pow.cc @@ -0,0 +1,25 @@ +#include + +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 new file mode 100644 index 0000000..795bd7b --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/quicksort.cc @@ -0,0 +1,38 @@ +#include + +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 new file mode 100644 index 0000000..57dcc17 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/selectionsort.cc @@ -0,0 +1,46 @@ +#include +#include + +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 new file mode 100644 index 0000000..aa6b032 --- /dev/null +++ b/1_anno/Programmazione_2/algorithms/sqrt.cc @@ -0,0 +1,46 @@ +#include + +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; +} -- cgit v1.2.3-18-g5258