Lider i idol
Czym jest lider?
Lider zbioru to liczba, która występuje w nim najwięcej razy.
{12, 4, 12, 1, 56} Liderem takiego zbioru jest 12.
W algorytmie znajdującym lidera użyjemy funkcji sort, która posortuje nam tablicę. Funkcja przyjmuje dwa argumenty – sort(nazwa_tablicy, nazwa_tablicy+rozmiar_tablicy).
Przykładowa implementacja algorytmu:
#include<iostream>
#include<algorithm>
//dodajemy bibliotekę algorithm, aby posortować dane za pomocą funkcji sort
using namespace std;
int main()
{
int n;
cin>>n;
int tab[n];
//wczytujemy ilość elementów w zbiorze i deklarujemy tablicę
//o odpowienim rozmiarze
for(int i=0;i<n;i++)
cin>>tab[i]; //wczytujemy dane do tablicy za pomocą funkcji for
sort(tab,tab+n); //sortujemy tablicę za pomocą funkcji sort
int ile=0,liczba=0,i=0;
//deklarujemy zmienną ile, w której będziemy zapisywać ile razy w zbiorze
//występuje lider, zmienną liczba, w któej będziemy zapisywać lidera
//oraz i, które będzie nam potrzebne do iteracji po tablicy tab
while(i<n) //dopóki i jest mniejsze od rozmiaru tablicy
{
int j=i+1;
//deklarujemy zmienną j, która jest indeksem kolejnej wartości w tablicy
while(j<n&&tab[j]==tab[i])
//sprawdzamy czy sąsiadujące elementy w tablicy są sobie równe
j++; //jeśli tak jest, to do zmiennej j dodajemy 1
if(j-i>ile)
//ilość występować tab[i] jest równa j-i jeżeli więc ta wartość
//jest większa od wartości zmiennej ile to zmienia ona swą wartość na i-j
{
ile=j-i;
liczba=tab[i];
//w takim wypadku również zmienna liczba zmienia swoją wartość na tab[i]
}
i=j;
//będziemy przechodzić tablicę w dalszym ciągu zaczynając od pierwszego
//elementu który nie był równy tab[i]
}
cout<<liczba<<" "<<ile;
//wyświetlamy lidera oraz to ile razy wystąpił w zbiorze
}
Czym jest idol?
Idolem zbioru jest element, który występuje w zbiorze co najmniej n/2+1 razy.
{1, 1, 1, 2, 3} Idolem takiego zbioru jest 1.
{1, 2, 3, 3, 3, 5, 11} Ten zbiór nie ma idola, ponieważ najczęściej powtarzająca się liczba to 3, które występuje w zbiorze 3 razy. Zbiór zawiera 7 elementów, więc lider musi występować co najmniej 4 razy.
Przykładowa implementacja algorytmu:
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int tab[n]; //deklarujemy zmienną z długością ciągu i tworzymy tablicę
for(int i = 0; i < n; i++)
cin>>tab[i]; //wpisujemy dane
int k=-1; // Potencjalny kandydat na lidera
int licznik=0;
// Licznik wystąpień potencjalnego kandydata znalezienie potencjalnego
//kandydata na lidera
for(int i=0;i<n;i++)
{
if(licznik==0)
//jeżeli licznik jest równy 0, to potencjalnym liderem zostaje tab[i]
{
k=tab[i];
licznik=1;
}
else
//w przeciwnym przypadku, jeśli tab[i] jest równe k
//to do licznika odejmujemy 1, jeśli nie to odejmujemy 1
{
if(tab[i]==k)
licznik++;
else
licznik--;
}
}
licznik=0; // Resetujemy licznik
// Sprawdzenie czy potencjalny kandydat jest liderem, czyli czy
//występuje w ciągu co najmniej n/2+1 razy
for(int i=0;i<n;i++)
{
if(tab[i]==k)
licznik++;
}
// Jeśli potencjalny kandydat jest liderem, wypisujemy go
if(licznik>n/2)
cout<<k;
else
cout<<"Brak lidera w zbiorze.";
//w przeciwnym przypadku informujemy, że ciąg nie ma lidera
}
Idealne miejsce aby zacząć swoją przygodę z programowaniem.
Odwiedź nasze social media!
Skontaktuj się z nami
- kontakt@returnhelp.pl
Copyright © 2024 return help;