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;
        }
    }
}