Kompendium_programisty_12.doc

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

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 a1, a2, .., an 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...