Czy w tablicy n-elementowej jakaś liczba występuje więcej niż n/2 razy
-- Sebastian Pawlak, 1997.
Kod źródłowy pliku "n_div_2.c":
/* Szukanie czy w tablicy n-elementowej
* wystepuje jakas liczba wiecej niz n/2.
* autor: Sebastian Pawlak
*/
#include <stdio.h>
#define n 14 /* ilosc elementow tablicy (TYLKO WARTOSCI PARZYSTE !!!) */
#define n_pol (n/2)
int main ()
{
short t[n] = { 2,2,2,1,1,1,1,1,1,1,1,0,1,0 };
short i, a, c;
short buf;
short l1 = -10000, l2 = -10000, il1 = 0, il2 = 0;
/********************************************************************
* TYPOWANIE KANDYDATOW, KTORZY MOGA WYSTEPOWAC WIECEJ NIZ n/2 RAZY *
********************************************************************/
/* W petli, od 1 do n-1, do kazdego indeksu tablicy zagladamy tylko 2 razy !
* oprocz indeksow skrajnych, do ktorych zagladamy tylko 1 raz.
*/
for (i = 1; i < n; i++) {
a = t[i - 1];
c = t[i];
if (a == c) {
if (a == l1)
il1++;
else if (a == l2) {
il2++;
if (il2 > il1) {
buf = l1;
l1 = l2;
l2 = buf;
buf = il1;
il1 = il2;
il2 = buf;
}
} else {
l2 = a;
il2 = 1;
}
}
}
/****************************************************
* TU SPRAWDZANE JEST CZY KTORAS Z WYTYPOWANYCH *
* LICZB RZECZYWISCIE WYSTEPUJE WIECEJ NIZ n/2 RAZA *
****************************************************/
il1 = 0;
il2 = 0;
for (i = 0; ((i < n) && (il1 < = n_pol) &&
(il2 < = n_pol)); i++) {
a = t[i];
if (a == l1)
il1++;
else if (a == l2)
il2++;
}
if (il1 > n_pol)
printf("liczba %d wystepuje wiecej niz n/2 razy !\n", l1);
else if (il2 > n_pol)
printf ("liczba %d wystepuje wiecej niz n/2 razy !\n", l2);
else
printf ("nie znaleziono liczby, ktora wystepuje wiecej niz n/2 razy\n");
return 0;
}
