-
Notifications
You must be signed in to change notification settings - Fork 1
/
exercize_8.cpp
114 lines (90 loc) · 1.87 KB
/
exercize_8.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
Si scriva un sottoprogramma C/C++ che effettui la ricerca di un intero in un vettore
ordinato (in senso crescente) in maniera ricorsiva, restituendo
l' indice della prima occorrenza nel vettore del valore cercato.
// Restituisce l' indice della cella contenente un valore
// uguale a x; oppure -1
*/
#include <iostream>
#include <ctime>
using namespace std;
#define N 55
int dicotomica(int v[], int left, int right, int x);
int cerca(int v[], int len, int x);
void genera(int a[N]);
int scegli_numero();
void bubble_sort(int a[N], int n);
int main()
{
int a[N];
int pos = -1;
int numero;
genera(a);
bubble_sort(a, N);
numero = scegli_numero();
pos = cerca(a, N, numero);
if (pos != -1)
cout << "numero trovato in posizione: " << pos << endl;
else
cout << "numero non trovato";
return 0;
}
void genera(int a[N])
{
int i;
srand(time(NULL));
for (i = 0; i < N; i++)
{
a[i] = rand() % 100 + 1;
}
cout << "Array generato " << endl;
for (i = 0; i < N; i++)
cout << a[i] << "\t";
}
int scegli_numero(void)
{
int numero = 0;
do
{
cout << endl;
cout << "Scegli un numero da cercare [1, 100]:" << endl;
cin >> numero;
} while (numero < 1 || numero > 100);
return numero;
}
void bubble_sort(int vet[], int n)
{
int tmp;
for (int j = 0; j < n; j++)
{
for (int i = n - 1; i >= j; i--)
{
if (vet[i] > vet[i + 1])
{
tmp = vet[i];
vet[i] = vet[i + 1];
vet[i + 1] = tmp;
}
}
}
}
int dicotomica(int v[], int left, int right, int x)
{
int middle;
if (left > right)
return -1;
middle = (left + right) / 2;
if (x < v[middle])
{
return dicotomica(v, left, middle - 1, x);
}
if (x == v[middle])
{
return middle;
}
return dicotomica(v, middle + 1, right, x);
}
int cerca(int v[], int len, int x)
{
return dicotomica(v, 0, len - 1, x);
}