[WikiDyd] [TitleIndex] [WordIndex

Wstęp

Zadania wyszukiwania i sortowania były omawiane na wykładzie [wiki:self:AiSD_E/MateriałyDoWykładu Materiały do wykładu]. W przypadku algorytmów, o których nie było mowy na wykładzie dla każdego zadania dodany został link do strony z omówieniem tego algorytmu.

Pierwsze samodzielne zajęcia mają charakter wprowadzający do samodzielnej implementacji algorytmów. Z uwagi na to przedstawione zadania są stosunkowo proste.

Szablony programów do wykorzystania

1. Klasa Wektor.BR

   1     // Klasa Wektor jest kontenerem tablicy liczb.
   2     // Zwykla tablica liczb nie potrafi sie np. wypisac na ekranie lub posortowac,
   3     // lub znalezc elementow ekstremalnych (czyli maksimum i minimum).
   4     class Wektor
   5     {
   6         // to jest nasza tablica, ktora w bedzie przechowywac rzeczywiste dane
   7         private double[] v;
   8         public int Length = 0;
   9 
  10         // konstruktor inicjalizujacy klase
  11         // wartosc int n podawana jako argument oznacza rozmiar tworzonego wektora
  12         public Wektor(int n)
  13         {
  14             v = new double[n];
  15             for (int i = 0; i < v.Length; i++)
  16                 v[i] = 0;
  17             Length = v.Length;
  18         }
  19 
  20         public void set(int i, double value)
  21         {
  22             v[i] = value;
  23         }
  24 
  25         public double get(int i)
  26         {
  27             return v[i];
  28         }
  29 
  30         // To jest tzw operator indeksujacy lub po angielsku indexer.
  31         // Wprowadzamy, ja zeby nie trzeba bylo uzywac metod get i set,
  32         // ktore wymagaja wiecej pracy czyli pisania.
  33         // Wiecej informacji na temat takich metod:
  34         // http://msdn2.microsoft.com/en-us/library/6x16t2tx(VS.80).aspx
  35         // (Link 26.03.2007)
  36         public double this[int i]
  37         {
  38             get { return v[i]; }
  39             set { v[i] = value; }
  40         }
  41 
  42         // Po wywolaniu tej metody spodziewamy sie na ekranie
  43         // zawartosci wektora w postaci: [ 34 2.5 5.2 8 ]
  44         // gdzie liczby są brane z wewnętrznej tablicy v
  45         public void wypiszNaEkran()
  46         {
  47             System.Console.Write("[");
  48             for (int i = 0; i < v.Length; i++)
  49                 System.Console.Write("{0:F} ", v[i]);
  50             System.Console.WriteLine("]");
  51         }
  52     }

2. Klasa WektorUtils.BR

   1     class WektorUtils
   2     {
   3         // sortowanie przez wstawianie
   4         public static void incrInSort(Wektor w)
   5         {
   6             for (int i = 1; i < w.Length; i++)
   7             {
   8                 double tmp = w.get(i);
   9                 int j;
  10                 for (j = i; j > 0 && w.get(j - 1) > tmp; j--)
  11                     w.set(j, w.get(j - 1));
  12                 w.set(j, tmp);
  13             }
  14         }
  15 
  16         // sortowanie przez wstawianie malejaco
  17         public static void decrInSort(Wektor w)
  18         {
  19             for (int i = 1; i < w.Length; i++)
  20             {
  21                 double tmp = w.get(i);
  22                 int j;
  23                 for (j = i; j > 0 && w.get(j - 1) < tmp; j--)
  24                     w.set(j, w.get(j - 1));
  25                 w.set(j, tmp);
  26             }
  27         }
  28 
  29     }

3. Klasa programu testującego Wektor.BR

   1     class Program
   2     {
   3         static void Main(string[] args)
   4         {
   5             int n = int.Parse(args[0]);
   6             Wektor w = new Wektor(n);
   7             w.wypiszNaEkran();
   8             Random r = new Random();
   9             for (int i = 0; i < w.Length; i++)
  10                 w.set(i, r.NextDouble() * 100);
  11             w.wypiszNaEkran();
  12             System.Console.WriteLine("v[{0}]= {1:F}", n / 2, w.get(n / 2));
  13             WektorUtils.incrInSort(w);
  14             w.wypiszNaEkran();
  15             WektorUtils.decrInSort(w);
  16             w.wypiszNaEkran();
  17 
  18             System.Console.ReadLine();
  19         }
  20     }

4. Szablon klasy do operacji na Stringu.BR

   1     class MyStringUtils
   2     {
   3         /* Przyklad funkcji wykonujacej odwrocenie kolejnosci znakow w napisie.
   4            1. Funkcja otrzymuje jako argument napis.
   5            2. Deklaruje robocza zmienna lokalna String tmp.
   6            3. Iteruje od konca po znakach napisu, i dopisuje po kolei znaki do zmiennej roboczej.
   7            4. Funckja zwraca kopie zmiennej roboczej tmp jako wynik. */
   8         public static String reverse(String str)
   9         {
  10             String tmp = "";
  11             int i;
  12             for (i = str.Length - 1; i >= 0 ; i--)
  13             {
  14                 tmp += str[i];
  15             }
  16 
  17             return tmp;
  18         }
  19 
  20         public int find( String s, char c )
  21         {
  22              ... tu np. wypelnic ....
  23         }
  24     }

5. Klasa programu testującego operacje na Stringu.BR

   1     /* Przykladowy program testujace funkcje odwracajaca kolejnosc znakow
   2        w napisie. Klase te nalezy dostosowac do przetestowania algorytmow
   3        zadanych przez prowadzacego.
   4     */
   5     class ProgramStringUtilsTest
   6     {
   7         static void Main(string[] args)
   8         {
   9             String napis = args[0];
  10             String wynik = MyStringUtils.reverse(napis);
  11 
  12             Console.WriteLine("Napis oryginalny: {0}", napis);
  13             Console.WriteLine("Napis po odwroceniu: {0}", wynik);
  14 
  15             Console.ReadLine();
  16         }
  17     }

Przykładowe zadania

Na zajęciach będzie do wykonania 5 wybranych zadań z poniższej listy. Za każde zadanie będzie można otrzymać 1 punkt.

Podkreślam, że zaprezentowane zadania są przykładowe i mogą (a nawet powinny) ulec niewielkim modyfikacjom. Modyfikacja nie może zmieniać sensu zadania a jedynie pozwolić zweryfikować stopień zrozumienia algorytmu przez osobę wykonującą.

1. Napisz funkcję swap, która dokona zamiany wartości dwóch elementów o wskazanych indeksach.

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode swap...
   5 
   6         public void swap(int i, int j)
   7         {
   8         }
   9     }

2. Napisz funkcję, która zwróci wartość oraz indeks elementu wektora o wartości maksymalnej (pamiętaj o ref z pierwszych zajęć).

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode getMax...
   5 
   6         public double getMax(ref double maxValue)
   7         {
   8         }
   9     }

3. Napisz funkcję, która zwróci wartość oraz indeks elementu wektora o wartości minimalnej (pamiętaj o ref z pierwszych zajęć).

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode getMin...
   5 
   6         public double getMin(ref double minValue)
   7         {
   8         }
   9     }

4. Napisz funkcję, która wyszuka zarówno wartość maksymalną jak i minimalną wektora.

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode getMaxMin...
   5 
   6         public void getMaxMin(out double maxValue, out double minValue)
   7         {
   8         }
   9     }

5. Napisz funkcję, która zwróci indeks elementu o zadanej wartości.

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find(double toFindValue)
   7         {
   8         }
   9     }

6. Napisz funkcję, która zwróci tablicę indeksów do elementów wektora które są równe zadanej wartości.

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int[] find(double toFindValue)
   7         {
   8         }
   9     }

7. Napisz funkcję, która zwróci indeks elementu o zadanej wartości wykorzystując algorytm sekwencyjny.

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find(double toFindValue)
   7         {
   8         }
   9     }

8. Napisz funkcję, która zwróci indeks elementu o zadanej wartości wykorzystując algorytm binarny (bisekcji).

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find(double toFindValue)
   7         {
   8         }
   9     }

9. Napisz funkcję, która zwróci indeks elementu o zadanej wartości wykorzystując algorytm interpolacyjny (http://www.eioba.com/a2262/algorytmy_wyszukujace_wyszukiwanie_interpolacyjne).

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find(double toFindValue)
   7         {
   8         }
   9     }

10. Napisz funkcję, która zwróci indeks elementu o zadanej wartości wykorzystując algorytm z wartownikiem (http://www.eioba.com/a2253/algorytmy_wyszukujace_wyszukiwanie_z_wartownikiem).

   1     class Wektor
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find(double toFindValue)
   7         {
   8         }
   9     }

11. Napisz funkcję, która odnajdzie indeks pierwszego wystąpienia od początku zadanego znaku w napisie (String).

   1     class MyStringUtils
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find( String str, char c)
   7         {
   8         }
   9     }

12. Napisz funkcję, która odnajdzie indeks pierwszego wystąpienia od końca zadanego znaku w napisie (String).

   1     class MyStringUtils
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find( String str, char c)
   7         {
   8         }
   9     }

13. Napisz funkcję, która odnajdzie indeks pierwszego wystąpienia napisu w innym napisie.

   1     class MyStringUtils
   2     {
   3         // (...)  tu jest reszta metod, ktore pozostawiamy niezmienione,
   4         // dodajemy tylko metode find...
   5 
   6         public int find( String str, String sToFind)
   7         {
   8         }
   9     }

2015-09-23 06:32