Kompendium programisty VB .NET - nr 12

Zadań maturalnych ciąg dalszy. Najlepsze sumy to przykład z roku 2005. Dodatkowo małe zabawy matematyczne czyli liczby doskonałe
i zaprzyjaźnione. Dla wielbicieli tajników VB .Net przykład jak wykorzystać rejestr systemowy do przechowywania informacji
o ustawieniach aplikacji.

Zadanie maturalne Najlepsze sumy

Najlepszą sumą ciągu liczb a₁, a₂, .., a_n nazywamy największą wartość wśród sum złożonych
z sąsiednich elementów tego ciągu. Na przykład dla ciągu: 1, 2, - 5, 7 mamy następujące sumy:

1, 1+2 = 3, 1+2+(-5) = -2, 1+2+(-5)+7 = 5, 2, 2+(-5) = -3, 2+(-5)+7 = 4, -5, -5+7 = 2, 7.

Zatem najlepszą sumą jest 7 (zwróć uwagę, że jeden element także uznajemy za sumę).

Wykonaj poniższe polecenia.

a) Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb całkowitych. Na jego podstawie napisz program do obliczenia najlepszych sum ciągów liczb podanych w plikach dane5-1.txt, dane5-2.txt,
dane5-3.txt).

b) Wyznacz „najpopularniejszy” element w ciągu, czyli element występujący największą liczbę razy. Zaprojektuj jak najszybszy algorytm wyznaczania najpopularniejszego elementu ciągu oraz oszacuj liczbę wykonywanych przez niego operacji (czas działania) jako funkcję od liczby elementów w ciągu. Zaprogramuj swój algorytm
i zastosuj go do ciągów znajdujących się w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. W przypadku,
gdy w ciągu jest więcej niż jeden najpopularniejszy element, jako wynik podajemy dowolny z nich. Na przykład dla ciągu 1, 3, 5, 1, 3 poprawną odpowiedzią jest zarówno 1, jak i 3 (oba elementy występują dwa razy).

Celem zadania jest nabycie i doskonalenie umiejętności rozwiązywania zadań maturalnych.

Obliczenie najlepszych sum

Szukając rozwiązania zadania, należy zwrócić uwagę na dwa zagadnienia:

- poszukujemy tylko najlepszej sumy, natomiast nie musimy zapamiętać, jakie elementy ją tworzą;

- sumę tworzą tylko sąsiadujące elementy, czyli jest to ciąg kolejnych elementów.

Rozwiązanie polega na obliczeniu sum wszystkich podciągów badanego zbioru i porównywanie ich z aktualnie największą sumą. Jeśli obliczona suma jest większa od zapamiętanej największej wartości, podstawiamy ją jako najlepszą sumę.

Zadanie rozpoczniemy od wczytania danych pliku tekstowego do tworzonej dynamicznie tablicy. Realizuje to procedura odczytPliku z jednym parametrem (tablicą), przekazywanym przez referencję.

Sub odczytPliku(ByRef ciag() As Integer)

Const Plik As String = "dane5-3.txt"

Deklaracja stałej, przechowującej nazwę pliku z danymi.

Dim nrPliku As Integer = FreeFile()

FileOpen(nrPliku, Plik, OpenMode.Input)

Otwarcie pliku z danymi w trybie do odczytu.

Dim indeks As Integer = 0

Ustalenie wartości indeksu tablicy na 0.

Do While Not EOF(nrPliku)

Otwarcie pętli odczytującej kolejne wiesze w pliku.

ReDim Preserve ciag(indeks)

Zwiększenie rozmiaru tablicy o jeden element.

ciag(indeks) = LineInput(nrPliku)

Odczytanie wiersza z danymi z pliku i zapamiętanie wartości w tablicy.

indeks += 1

Zwiększenie indeksu tablicy o jeden.

Loop

FileClose(nrPliku)

Zamknięcie połączenia z plikiem

End Sub

Wyszukaniem najlepszej sumy zajmuje się funkcja najlepsza.

Function NajlepszaSuma(ByVal ciag() As Integer)

Dim suma, sumaMax, i, j As Integer

sumaMax = ciag(0)

Deklaracja zmiennych lokalnych i ustalenie początkowej wartości najlepszej sumy.

For i = 0 To ciag.Length - 1

suma = 0

Rozpoczęcie pętli, wyznaczającej początek badanych podciągów i wyzerowanie wartości obliczanych sum.

For j = i To ciag.Length - 1

suma = suma + ciag(j)

Obliczanie sumy dla kolejnych podciągów zbioru.

If suma > sumaMax Then sumaMax = suma

Sprawdzenie, czy obliczona suma jest większa od aktualnie zapamiętanej najlepszej sumy. Jeżeli tak, zostaje ona zapamiętana jako największa wartość.

Next

Next

Return sumaMax

End Function

Odszukanie najpopularniejszego elementu

W drugiej części zadania należy odnaleźć najpopularniejszy element. Przez słowo „najpopularniejszy” rozumiemy taki, który występuje najwięcej razy w zbiorze bez żadnych dodatkowych warunków (np. by odnaleźć lidera, musi on występować minimum n/2 razy w zbiorze n-elementowym). By rozwiązać ten problem, musimy posortować ciąg za pomocą jak najszybszego algorytmu porządkowania. Wykorzystamy tu sortowanie szybkie, zwane także quicksortem.

Sub Quicksort(ByVal lewy As Integer, ByVal prawy As Integer, ByRef ciag() As Integer)

Dim i, j, x, w As Integer

i = lewy

j = prawy

x = ciag((lewy + prawy) \ 2)

Do

While ciag(i) < x

i = i + 1

End While

While x < ciag(j)

j = j - 1

End While

If i <= j Then

w = ciag(i)

ciag(i) = ciag(j)

ciag(j) = w

i = i + 1

j = j - 1

End If

Loop Until i > j

If lewy < j Then

Quicksort(lewy, j, ciag)

End If

If i < prawy Then

Quicksort(i, prawy, ciag)

End If

End Sub

W posortowanym zbiorze będziemy zliczali wystąpienia powtarzających się elementów, zapamiętując ten, który powtarza się najczęściej.

Function Najpopularniejszy(ByVal ciag() As Integer) As Integer

Dim ile, maxIle, Naj, i As Integer

maxIle = 1

ile = 1

Naj = ciag(0)

Deklaracja zmiennych pomocniczych oraz ustalenie ich początkowych wartości.

For i = 1 To ciag.Length - 1

If ciag(i) <> ciag(i - 1) Then

If ile > maxIle Then

maxIle = ile

Naj = ciag(i - 1)

W przypadku zmiany wartości w przeszukiwanym ciągu sprawdzenie wartości liczby wystąpień. Jeśli jest ona większa od aktualnego maksimum, zapamiętanie jej oraz liczby, która tyle razy występuje.

End If

ile = 1

Ustalenie liczby wystąpień na 1.

Else

ile += 1

Jeżeli wartość w ciągu się nie zmienia, zwiększenie licznika wystąpień o 1.

End If

Next

Return Naj

Zwrócenie liczby, która najczęściej występuje w zbiorze.

End Function

Opisane wyżej procedury wywołujemy w programie głównym.

Sub Main()

Dim ciag() As Integer

odczytPliku(ciag)

Console.WriteLine(" Najlepsza suma to : " & NajlepszaSuma(ciag))

Quicksort(0, ciag.Length - 1, ciag)

Console.WriteLine("Najczęściej występująca liczba to: " & Najpopularniejszy(ciag))

Console.ReadLine()

End Sub

Liczby zaprzyjaźnione

Liczby zaprzyjaźnione to takie pary liczb, z których każda jest równa sumie podzielników drugiej. Przykładem takiej pary mogą być 284 i 220 ponieważ:

podzielniki 220 to:

1+ 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

i podzielniki 284 to:

1+ 2 + 4 + 71 +142 = 220.

Rozwiązanie problemu liczb zaprzyjaźnionych polega na zauważeniu, że relacja pomiędzy liczbami jest zwrotna. Obliczamy sumę podzielników liczby n, po czym sprawdzamy obliczoną sumę - czyli odszukujemy i sumujemy jej podzielniki. Jeżeli wynik obliczeń jest równy n, otrzymaliśmy parę liczb zaprzyjaźnionych.

Pierwszym krokiem jest napisanie funkcji obliczającej sumę podzielników.

Function zaprzyjaznione(ByVal n As Integer) As Integer

Dim suma, i As Integer

suma = 0

For i = 1 To n \ 2

If n Mod i = 0 Then

suma += i

End If

Next

Return suma

End Function

Wyszukanie liczb zaprzyjaźnionych, polega na sprawdzeniu:

jeżeli suma = zaprzyjaznione(a)

to

a= zaprzyjaznione(suma).

Praktyczna implementacja tej zasady dla badanego zakresu liczb wygląda następująco:

Sub wyszukaj()

Dim a, b, i, n As Integer

Console.WriteLine("Podaj liczbę a:")

a = Console.ReadLine

Console.WriteLine("Podaj liczbę b:")

b = Console.ReadLine

Wprowadzenie przedziału liczbowego, w którym będziemy szukali liczb zaprzyjaźnionych.

For i = a To b - 1

n = zaprzyjaznione(i)

Obliczenie sumy podzielników dla liczby i.

If (n > i) And (n <= b) Then

If i = zaprzyjaznione(n) Then

Sprawdzenie, jaka jest wartość sumy podzielników, dla wyliczonej wcześniej sumy; jeżeli jest równa i, liczby te są zaprzyjaźnione.

Console.WriteLine(i & " " & n)

End If

End If

Next

End Sub

Liczby doskonałe

Liczby doskonałe, to takie liczby, których suma podzielników jest równa im samym. Przykładem liczby doskonałej jest 6 ponieważ:

6 = 1 + 2 + 3.

Wyszukanie liczby doskonałej w podanym przedziale jest proste. Należy odnaleźć tylko wszystkie jej podzielniki i następnie je zsumować. Procedura realizująca to zdanie jest krótka i jasna.

Private Sub btnSzukaj_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSzukaj.Click

Dim liczba, suma, i, j As Integer

liczba = nupLiczba.Value

lbxLiczby.Items.Clear()

For i = 2 To liczba

suma = 0

For j = 1 To i \ 2

If i Mod j = 0 Then suma += j

Sprawdzenie, czy liczba j jest podzielnikiem liczby i; jeżeli tak, dodajemy ją do sumy podzielników.

Next

If suma = i Then lbxLiczby.Items.Add(i)

Sprawdzenie, czy obliczona suma podzielników jest równa liczbie badanej; jeżeli tak, dodanie liczby i do kolekcji elementów kontrolki typu ListBox.

Next

End Sub

Zapisanie ustawień aplikacji

Projektując aplikację, często chcemy, by ustawienia programu, np. położenie oka i jego rozmiar w chwili zmykania, zostały zapamiętane. W tym celu można wykorzystać rejestr systemowy. Tworzymy własny klucz, a w nim umieszczamy, np. informacje dotyczące parametrów Left, Top, Width i Heigth formularza.

W celu uzyskania dostępu do rejestru wykorzystamy klasę RegistryKey, zawartą w przestrzeni nazw System.Win32. W tym celu należy zaimportować tę przestrzeń nazw.

Imports Microsoft.Win32

Deklarujemy zmienną globalną klasy RegistryKey.

Dim klucz As RegistryKey

Procedura zapiszUstawienia zapisuje w rejestrze informacje o położeniu i wielkości formularza.

Sub zapiszUstawienia(ByVal formularz As System.Windows.Forms.Form)

klucz.SetValue("Height", formularz.Height)

klucz.SetValue("Width", formularz.Width)

klucz.SetValue("Left", formularz.Left)

klucz.SetValue("Top", formularz.Top)

End Sub

Procedura ustawUstawienia, odczytuje informacje z rejestru systemowego i modyfikuje pozycję i rozmiar formularza.

Sub ustawUstawienia(ByVal formularz As System.Windows.Forms.Form)

formularz.Height = CType(klucz.GetValue("Height", formularz.Height), Integer)

formularz.Width = CType(klucz.GetValue("Width", formularz.Width), Integer)

formularz.Left = CType(klucz.GetValue("Left", formularz.Left), Integer)

formularz.Top = CType(klucz.GetValue("Top", formularz.Top), Integer)

End Sub

Odczytanie ustawień jest dokonywane podczas ładowania formularza.

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Try

klucz = Registry.LocalMachine.CreateSubKey("Software\MyApp\" & Me.Name)

Utworzenie klucza, jeśli nie istnieje.

ustawUstawienia(Me)

Odczytanie ustawień i modyfikacja parametrów formularza.

Catch ex As Exception

MessageBox.Show("Brak dostępu do rejestru", "Błąd", MessageBoxButtons.OK, MessageBoxIcon.Error)

End Try

End Sub

Odczyt z rejestru jest dokonywany w bloku kodu chronionego, by obsłużyć wyjątki, jakie mogą wystąpić, gdy np. użytkownik nie ma prawa edycji rejestru systemowego.

Zapis ustawień jest dokonywany podczas zamykania formularza, w procedurze obsługi zdarzenia Closing formularza.

Private Sub Form1_Closing(ByVal sender As Object, ByVal e As System.ComponentModel.CancelEventArgs) Handles MyBase.Closing

Try

zapiszUstawienia(Me)

Catch ex As Exception

MessageBox.Show("Brak dostępu do rejestru - ustawiebia ni zostały zapisane", "Błąd", MessageBoxButtons.OK, MessageBoxIcon.Error)

End Try

End Sub

Oczywiście, można tworzyć dowolne wpisy w rejestrze, zapamiętując w ten sposób różne informacje charakterystyczne dla danej aplikacji.

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] Sz. Jeleński, Śladami Pitagorasa, WSiP, Warszawa 1988.

Kompendium wiedzy programisty VB .NET - nr 12 autor: Janusz Białowąs

Algorytmika i programowanie 1

---