Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #define MAX 20 // abbiamo definito una costante MAX con valore 20
- /*
- 4 2 7 9 14 15 5 0 1 8 17 19 20 22 23 i=dim-l
- FI: 2 4 7 9 14 15 5 0 1 8 17 19 20 22 (23) i= dim-2
- F2: 2 4 7 9 14 5 0 1 8 15 17 19 20 (22) 23 i=dim-3
- F3: 2 4 7 9 5 0 1 8 14 15 17 19 (20) 22 23 i=dim-4
- F4: 2 4 7 5 0 1 8 9 14 15 17 (19) 20 22 23 i=dim-5
- F5: 2 4 5 0 1 7 8 9 14 15 (17) 19 20 22 23 i=dim-6
- F6: 2 4 0 1 5 7 8 9 14 (15) 17 19 20 22 23 i=dim-7
- F7: 2 0 1 4 5 7 8 9 (14) 15 17 19 20 22 23 i=dim-8
- F8: 0 1 2 4 5 7 8 (9) 14 15 17 19 20 22 23 i=dim-9
- F9: 0 1 2 4 5 7 8 9 14 15 17 19 20 22 23
- */
- /* PROTOTIPO DI FUNZIONE */
- int lettura(int vettore[]);
- void bubble_sort(int vett[], int dim);
- int ricerca_binaria(int vettore[],int dim, int x);
- int main()
- {
- int i;
- // questi servono il riordinamento e la ricerca binaria
- int v1[MAX];
- int dim;
- int k;
- int pos; // indichera la posizione ricercata
- dim=lettura(v1);
- /* STAMPA IL VETTORE */
- /* cioe i=dim-1 */
- printf("\nVettore:\n");
- for(i=0; i<dim; i++)
- {
- printf("%d ", v1[i]);
- }
- /* all'interno del main richiamiamo il bubble_sort */
- bubble_sort(v1, dim);
- // ristampiamo il vettore ordinato
- printf("\n\nVettore Ordinato:\n");
- for(i=0; i<dim; i++)
- {
- printf("%d ", v1[i]);
- }
- printf("\n\nInserisci elemento da ricercare: ");
- scanf("%d", &k);
- pos=ricerca_binaria(v1, dim, k);
- if(pos!=-1) /// quindi se posizione e diverso da -1 allora l'elemento e stato trovato
- printf("\nElemento trovato in posizione %d\n", pos);
- else
- printf("\nElemento non trovato\n"); // perche vorra dire che pose=-1
- return 0;
- }
- /* DEFINIZIONE DI FUNZIONE */
- /* FUNZIONE DI LETTURA */
- int lettura(int vettore[])
- {
- int i=0;
- FILE *fp;
- fp=fopen("numeri.txt", "r");
- while(!feof(fp))
- {
- fscanf(fp, "%d", &vettore[i]);
- i++;
- }
- fclose(fp);
- return i; /* ritorna i che e il numero di elementi letti e inserendola
- nella dimensionedima allinterno del main che sarebbe ** dim=lettura(v1); */
- }
- void bubble_sort(int vett[], int dim)
- {
- int i, j, temp;
- for(i=dim-1; i>0; i--)
- {
- for(j=0; j<i; j++)
- {
- /** scambiando > con < otterremo un ordinamento in maniera decrescente cioe dal piu grande al piu piccolo **/
- if(vett[j]>vett[j+1]) // dobbiamo confrontare l'elemento di sinistra con l'elemento di destra
- {
- temp=vett[j];
- vett[j]=vett[j+1];
- vett[j+1]=temp;
- }
- }
- }
- }
- int ricerca_binaria(int vettore[],int dim, int x)
- {
- int p;
- int u;
- int m;
- p=0; // p indica il primo elemento
- u=dim-1; // u indica l'ultimo elemento
- while(p<=u)
- {
- m=(p+u)/2;
- if(vettore[m]==x)
- return m;
- else if(vettore[m]<x)
- p=m+1;
- else
- u=m-1;
- }
- return -1; /* se la ricerca non ha dato nessun risultato si restituisce -1. perche se uscira fuori dal cilo
- while significa che p sara diventato maggiore di u, qindi l'elemento che stiamo cercando non e presente
- all'inteno del vettore */
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement