summaryrefslogtreecommitdiff
path: root/1_anno/Programmazione_2/algorithms
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
committerSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
commitd2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch)
treea51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /1_anno/Programmazione_2/algorithms
parent98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff)
conf: rename
Diffstat (limited to '1_anno/Programmazione_2/algorithms')
-rw-r--r--1_anno/Programmazione_2/algorithms/binarysearch.cc33
-rw-r--r--1_anno/Programmazione_2/algorithms/cbrt.cc37
-rw-r--r--1_anno/Programmazione_2/algorithms/insertionsort.cc42
-rw-r--r--1_anno/Programmazione_2/algorithms/log.cc25
-rw-r--r--1_anno/Programmazione_2/algorithms/mergesort.cc52
-rw-r--r--1_anno/Programmazione_2/algorithms/pow.cc25
-rw-r--r--1_anno/Programmazione_2/algorithms/quicksort.cc38
-rw-r--r--1_anno/Programmazione_2/algorithms/selectionsort.cc46
-rw-r--r--1_anno/Programmazione_2/algorithms/sqrt.cc46
9 files changed, 0 insertions, 344 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;
-}