57 lines
937 B
C
57 lines
937 B
C
// Laboratorio 3 - Esercizio 1
|
|
// Matteo Schiff - s295565
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
int majority(int * a, int N) {
|
|
if (N == 1) {
|
|
return a[0];
|
|
}
|
|
|
|
int m = N/2;
|
|
|
|
int x = majority(a, m);
|
|
int y = majority(a+m, m);
|
|
|
|
if (x == y)
|
|
return x;
|
|
|
|
if (x != -1) {
|
|
int c = 0;
|
|
for (int i = 0; i < N; i++) {
|
|
if (a[i] == x)
|
|
c++;
|
|
}
|
|
if (c > (N/2))
|
|
return x;
|
|
}
|
|
|
|
if (y != -1) {
|
|
int c = 0;
|
|
for (int i = 0; i < N; i++) {
|
|
if (a[i] == y)
|
|
c++;
|
|
}
|
|
|
|
if (c > (N/2))
|
|
return y;
|
|
}
|
|
|
|
return -1;
|
|
}
|
|
|
|
int main(int argc, char ** argv) {
|
|
int N = argc - 1;
|
|
|
|
if (argc < 2)
|
|
return 1;
|
|
|
|
int * vec = malloc(N * sizeof(int));
|
|
for (int i = 0; i < N; i++) {
|
|
vec[i] = atoi(argv[i+1]);
|
|
}
|
|
|
|
printf("major: %d\n", majority(vec, N));
|
|
}
|