Znajdowanie lidera w zbiorze
Liderem nazywamy taki element n- elementowego zbioru, którego liczba wystąpień jest większa niż n/2.
Działanie algorytmu polega na sprawdzaniu, czy wyznaczona wartość występuje w zbiorze więcej niż n/2 razy. Jeżeli ten warunek jest spełniony, to lider został znaleziony, w przeciwnym wypadku w zbiorze nie ma lidera.
Specyfikacja algorytmu:
Dane: Liczba naturalna: n>0 (liczba elementów tablicy T)
n- elementowa tablica jednowymiarowa zawierająca liczby rzeczywiste: T[0..n-1]
Wynik: Lider znaleziony w tablicy T[0..n-1] lub komunikat informujący, że w tablicy nie ma lidera
Lista kroków:
0. Wczytaj wartości danych n, T[0..n-1]
1. Przypisz lider=T[0] i pom=1
2. Dla kolejnych wartości i: 1, 2, ?, n-1 wykonuj kroki 3- 5, następnie przejdź do kroku 6
3. Jeśli pom=0, wykonaj krok 4, w przeciwnym wypadku przejdź do kroku 5
4. Przypisz lider=T[i] i pom=1
5. Jeśli T[i]=lider, zwiększ pom o 1, w przeciwnym wypadku zmniejsz pom o 1
6. Jeśli pom=0, wypisz komunikat W ZBIORZE NIE MA LIDERA i zakończ algorytm, w przeciwnym wypadku przejdź do kroku 7
7. Przypisz ilosc=0
8. Dla kolejnych wartości i:0, 1,..,n-1 wykonuj krok 9, a następnie przejdź do kroku 10
9. Jeśli T[i]= lider, zwiększ ilosc o 1
10. Jeśli iloss>n/2, wypisz wartość zmiennej lider, w przeciwnym wypadku wypisz komunikat W ZBIORZE NIE MA LIDERA. Zakończ algorytm
Projekt aplikacji desktopowej
Wskazówka
Najłatwiejszy sposób wczytania danych do tablicy z kontrolki TextBox to jest wykorzystanie metody Split z klasy String. Tak samo jak robiliśmy to przy obsłudze plików. Metoda Split dzieli wczytany łańcuch znaków na tablicę podłańcuchów. Podział jest zgodny z podanym znakiem separatora.
Wskazówka:
string[] lancuchy = textBox1.Text.Split(' ');
//rozmiar tablict odpowiada rozmiarowi tablicy lancychy
int n=lancuchy.GetLength(0);
t=new int[n];
//wczytaj dane do tablicy
for (int i = 0; i < n; i++)
t[i] = Convert.ToInt32(lancuchy[i]);
Funkcja działająca według podanych kroków algorytmu
Wskazówka:
string SzukajLidera(int[] t)
{
string wynik = "BRAK LIDERA";
int lider = t[0];
int pom = 1, ilosc = 0;
for (int i = 1; i < t.GetLength(0); i++)
if (pom == 0)
{
lider = t[i];
pom = 1;
}
else if (t[i] == lider) pom++;
else pom--;
if(pom == 0)wynik = "BRAK LIDERA";
else
{
for (int i = 1; i < t.GetLength(0); i++)
if (t[i] == lider) ilosc++;
if (ilosc > t.GetLength(0) / 2)
wynik = String.Format("Liczba {0} jest liderem", lider);
else wynik = "BRAK LIDERA";
}
return wynik;
}
Zadanie
1. Narysuj schemat blokowy algorytmu znajdującego lidera w zbiorze
2. Na podstawie podanego algorytmu napisz aplikację konsolową, w której dane wczytywane są z klawiatury.
Pełne rozwiązanie aplikacji desktopowej
Wskazówka:
using System;
using System.Windows.Forms;
namespace Lider_w_zbiorze
{
public partial class Form1 : Form
{
int[] t;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
string[] lancuchy = textBox1.Text.Split(' ');
//rozmiar tablict odpowiada rozmiarowi tablicy lancychy
int n=lancuchy.GetLength(0);
t=new int[n];
//wczytaj dane do tablicy
for (int i = 0; i < n; i++)
t[i] = Convert.ToInt32(lancuchy[i]);
Text="Rozmiar tablicy zbioru "+n.ToString();
MessageBox.Show(SzukajLidera(t),
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
}
string SzukajLidera(int[] t)
{
string wynik = "BRAK LIDERA";
int lider = t[0];
int pom = 1, ilosc = 0;
for (int i = 1; i < t.GetLength(0); i++)
if (pom == 0)
{
lider = t[i];
pom = 1;
}
else if (t[i] == lider) pom++;
else pom--;
if(pom == 0)wynik = "BRAK LIDERA";
else
{
for (int i = 1; i < t.GetLength(0); i++)
if (t[i] == lider) ilosc++;
if (ilosc > t.GetLength(0) / 2)
wynik = String.Format("Liczba {0} jest liderem", lider);
else wynik = "BRAK LIDERA";
}
return wynik;
}
}
}
