Strona główna

Kompendium programisty vb. Net nr 13


Pobieranie 44.18 Kb.
Data19.06.2016
Rozmiar44.18 Kb.

Kompendium wiedzy programisty VB .NET – nr 13 autor: Janusz Białowąs

Kompendium programisty VB .NET - nr 13


Algorytmika, algorytmika… W bieżącym numerze dwa problemy algorytmiczne - wyszukiwanie najczęstszego elementu oraz poszukiwanie lidera w zbiorze. Majowe matury za pasem, algorytmy trzeba ćwiczyć.




Wyszukiwanie najczęściej występującego elementu w zbiorze


Wyszukanie najczęściej występującego elementu w zbiorze można zrealizować na kilka sposobów. W poprzednim numerze kompendium, omawiając zadanie: Najlepsze sumy, pokazaliśmy, jak wykorzystać sortowanie, by wyszukać najczęściej występujący element. Problem ten można także rozwiązać bez konieczności porządkowania zbioru danych.

Algorytm wyszukiwania najczęściej występującego elementu

Szukanie najpopularniejszego elementu, możemy zrealizować w następujący sposób:


Dane:

Zbiór danych t.



Wynik:

Najczęściej występujący element w zbiorze t (lub elementy)



Algorytm:

Krok1: Wyszukaj minimum i maksimum w zbiorze t.

Krok2: Utwórz tablicę l o indeksach od minimum do maksimum i wyzeruj jej elementy.

Krok3. Odczytaj kolejne elementy tablicy t, dla każdego elementu tablicy t, odszukaj odpowiadający mu element tablicy l i zwiększ jego wartość o 1.

l(t(i))=l(t(i)) +1

Krok4: Wyszukaj maksimum w tablicy l.

Krok5: Odszukaj elementy tablicy l, które są równe znalezionemu maksimum, indeksy tych elementów to najczęściej występujące liczby w zbiorze.
Jak widać, jest to algorytm o złożoności liniowej.
Praktyczna implementacja tego prostego algorytmu może mieć różny stopień trudności
w zależności od języka oprogramowania. W bieżącym kompendium opiszemy, jak to zdanie wykonać
w VB. Net.

Odszukanie najpopularniejszego elementu - aplikacja VB. Net

Program odszukujący najpopularniejsze liczby utworzymy jako aplikację konsolową odczytującą dane z pliku tekstowego.



W procedurze Main zadeklarujemy następujące zmienne:

Sub Main()

Dim t() As Integer

Dim liczniki() As Integer

Dim min, max As Integer

Tablice t i liczniki mają rozmiar zerowy; zostanie on dopasowany do liczby wprowadzonych elementów w przypadku tablicy t oraz maksimum i minimum w przypadku tablicy liczniki.


Procedura odczyt odczyta dane z pliku tekstowego i zapamięta je w tablicy t, jednocześnie odnajdując wartości maksymalne i minimalne w zbiorze.
Sub odczyt(ByRef t() As Integer, ByRef min As Integer, ByRef max As Int

Procedura posiada 4 parametry przekazywane przez referencję.


Const plik As String = "..\dane5-4.txt"

Stała zapamiętuje plik zawierający dane.


Dim nrPliku As Integer = FreeFile()

Przydzielenie wolnego numeru (uchwytu) plikowi, z którego odbędzie się odczyt danych.


Dim ile As Integer = 0

Wyzerowanie zmiennej przechowującej informację o liczbie elementów w zbiorze.


FileOpen(nrPliku, plik, OpenMode.Input)

Otwarcie pliku w trybie do odczytu.


Do While Not EOF(nrPliku)

Otwarcie pętli odczytującej kolejne elementy pliku.


ReDim Preserve t(ile)

Zmiana rozmiaru tablicy.


t(ile) = LineInput(nrPliku)

Console.Write(t(ile) & " ")

Odczytanie elementu z pliku i zapamiętanie go w tablicy t.
If ile = 0 Then

min = t(ile)

max = t(ile)

Else


If t(ile) > max Then max = t(ile)

If t(ile) < min Then min = t(ile)

End If

Szukanie wartości maksymalnej i minimalnej w zbiorze.


ile += 1

Loop


Console.WriteLine("Liczby z pliku zostały odczytane")

FileClose(nrPliku)

End Sub

Zamknięcie pętli oraz zakończenie połączenia z plikiem.



Procedura szukaj wyszukuje najpopularniejszy element w tablicy t.
Sub szukaj(ByVal t() As Integer, ByRef liczniki() As Integer, ByVal min As Integer, ByVal max As Integer)

Deklaracja procedury z jednym parametrem przekazywanym przez referencje oraz trzema przekazywanymi przez wartość.


Dim i, naj, indeks As Integer

ReDim Preserve liczniki(max - min)

Ustalenie rozmiaru tablicy służącej do zliczania częstości występowania elementów Ponieważ nie ma w VB .Net indeksów ujemnych różnica max – min będzie określać maksymalny rozmiar tablicy.
For i = 0 To liczniki.Length - 1 : liczniki(i) = 0 : Next

Wyzerowanie tablicy liczniki.


For i = 0 To t.Length - 1

liczniki(t(i) - min) += 1

Next

Zliczanie częstości występowania elementów tablicy t (różnica t(i) i- min) określa indeks zliczanego elementu w tablicy liczniki.


naj = liczniki(0)

indeks = 0

For i = 1 To liczniki.Length - 1

If liczniki(i) > naj Then naj = liczniki(i)

Next

Wyszukanie największej wartości w zbiorze liczniki.



For i = 0 To liczniki.Length - 1

If liczniki(i) = naj Then

Console.WriteLine("Najczęstszy element to : " & min + i)

End If


Next

Ustalenie, które elementy mają częstość występowania równą odnalezionemu maksimum.

Ostatnim elementem aplikacji jest wywołanie napisanych podprogramów.
Sub Main()

Dim t() As Integer

Dim liczniki() As Integer

Dim min, max As Integer

odczyt(t, min, max)

szukaj(t, liczniki, min, max)

Console.ReadLine()

End Sub

Lider zbioru


Lider zbioru jest to element występujący w zbiorze n-elementowym więcej niż n/2 razy.

Algorytm wyszukiwania lidera zbioru

Algorytm szukania lidera w zbiorze można opisać następująco:


Dane:

Zbiór t zawierający n elementów.



Wynik:

Lider zbioru t lub informacja o jego braku.



Algorytm:

Krok1: Przyjmij pierwszy elementy zbioru za kandydata na lidera oraz ustal wartość zmiennej ile na 0

Krok2: Dla kolejnych elementów zbioru wykonaj kroki od 3. do 5.

Krok3: Jeśli ile = 0, wykonaj krok 4.; w przeciwnym przypadku krok 5.

Krok4: Przyjmij bieżący element zbioru jako nowego kandydata na lidera i ustal wartość zmiennej ile na 1.

Krok5:Sprawdź, czy kolejny element zbioru jest równy kandydatowi na lidera; jeżeli tak, zwiększ wartość zmiennej ile o1, w przeciwnym przypadku zmniejsz wartość zmiennej ile o 1.

Krok6:Jeżeli zmienna ile = 0, zbiór nie ma lidera, zakończ algorytm.

Krok7: Jeżeli zmienna ile>0, sprawdź, ile razy w zbiorze występuje kandydat na lidera. Jeśli liczba wystąpień jest większa od n/2, element ten jest liderem zbioru.

(Algorytm opracowanie na bazie książki: Maciej M. Sysło, Algorytmy, WSiP, Warszawa 1997)


Algorytm wyszukiwania lidera zbioru aplikacja w VB .Net.

Program odszukujący lidera utworzymy jako aplikację konsolową odczytującą dane z pliku tekstowego.



Algorytm będzie realizowany w jednej procedurze z parametrem.
Sub szukanie_lidera(ByRef tablica() As Integer)

Deklaracja procedury z jednym parametrem.


Dim nrPliku As Integer = FreeFile()

Dim ile, ile_e As Integer

Dim lider_k, i As Integer

Deklaracja zmiennych lokalnych w procedurze.


ile = 0

ile_e = 0

FileOpen(nrPliku, "..\zbior.txt", OpenMode.Input)

Utajenie wartości początkowych zmiennych lokalnych i otwarcie pliku z danym w trybie do odczytu.


Do While Not EOF(nrPliku)

ReDim Preserve tablica(ile_e)

Rozpoczęcie pętli odczytującej kolejne liczby z pliku i zwiększenie rozmiaru tablicy.
If ile = 0 Then

lider_k = LineInput(nrPliku)

tablica(ile_e) = lider_k

ile = 1


ile_e += 1

Ustalenie nowego kandydata na lidera zbioru.


Else

tablica(ile_e) = LineInput(nrPliku)

If lider_k = tablica(ile_e) Then

ile += 1


Else

ile -= 1


End If

ile_e += 1

End If

Loop


Sprawdzenie, czy kandydat jest równy odczytanemu elementowi; jeżeli tak, zwiększenie licznika o 1, w przeciwnym przypadku zmniejszenie licznika o 1.
If ile = 0 Then

Console.WriteLine("W tym zbiorze nie ma lidera")

Informacja o braku lidera w zbiorze.
Else

ile = 0


For i = 0 To tablica.Length - 1

If tablica(i) = lider_k Then

ile += 1

End If


Next

Sprawdzenie, ile razy występuje w zbiorze kandydat na lidera.


If ile > tablica.Length \ 2 Then

Console.WriteLine("Liderem zbioru jest " & lider_k)

Else

Console.WriteLine("W tym zbiorze nie ma lidera")



End If

End If


Stwierdzenie istnienia lidera lub jego braku.

Bibliografia


[1] H.Gantenbein, G. Dunn, A. Kalani, Ch. Payne, T. Thangarathinam, MS Visual Basic .NET 2003 Księga eksperta, Helion, Gliwice 2006.

[2] P. Kimmel, Visual Basic .NET Księga eksperta, Helion Gliwice 2003.

[3] M. MacDonald, MS Visual Basic .NET księga przykładów, MicrosoftPress Warszawa 2004.

[4] D. Mackenzie, K. Shakery, Visual Basic .NET dla każdego, Helion Gliwice 2003.



[5] Maciej M. Sysło, Algorytmy, WSiP, Warszawa 1997.



Algorytmika i programowanie



©snauka.pl 2016
wyślij wiadomość