Глава 26. Практически задачи за изпит по програмиране – тема 3

В тази тема...

В настоящата тема ще разгледаме условията и ще предложим решения на няколко примерни за изпит. При решаването на задачите ще се придържаме към съветите от главата "Как да решаваме задачи по програмиране".

Съдържание

Мисловни карти

Задача 1: Квадратна матрица

По дадено число N (въвежда се от клавиатурата) да се генерира и отпе­чата квадратна матрица, съдържаща числата от 0 до N2-1, разположени като спирала, започваща от центъра на матрицата и движеща се по часовниковата стрелка, тръгвайки в началото надолу (вж. примерите).

Примерен резултат при N=3 и N=4:

clip_image001

Решение на задачата

От условието лесно се вижда, че имаме поставена алгоритмична задача. Основната част от решението на задачата – да измислим подходящ алгоритъм за запълване на клетките на квадратна матрица по описания начин. Ще покажем на читателя типични­те разсъждения необходими за решаването на този конкретен проблем.

Да започнем с избора на структура от данни за представяне на матрицата. Удобно е да имаме директен достъп до всеки елемент на матрицата, затова ще се спрем на двумерен масив matrix от целочислен тип. При стартирането на програмата прочитаме от стандарт­ния вход размерността n на матрицата и я инициализираме по следния начин:

int[,] matrix = new int[n,n];

Измисляне на идея за решение

Следващата стъпка е да измислим идеята на алгоритъма, който ще имплементираме. Трябва да запълним матрицата с числата от 0 до N2-1 и веднага съобра­зяваме, че това може да стане с помощта на цикъл, който на всяка итерация поставя едно от числата в предназначената за него клетка на матрицата. Текущата позиция ще представяме чрез целочислените променливи positionX и positionY – двете координати на позицията. Да приемем, че знаем началната позиция – тази, на която трябва да поставим първото число. По този начин задачата се свежда до намиране на метод за определяне на всяка следваща позиция, на която трябва да бъде поставено число – това е нашата главна подзадача.

Подходът за определяне на следващата позиция спрямо текущата е следният: търсим строга закономерност на промяната на индексите при спираловидното движение по клетките. Започваме от най-очевидното нещо – движението винаги е по посока на часовниковата стрелка, като първоначално посоката е надолу. Дефинираме целочислена променлива direction, която ще показва текущата посока на движение. Тази променлива ще приема стойностите 0 (надолу), 1 (наляво), 2 (нагоре) и 3 (надясно). При смяна на посоката на движение просто увеличаваме с единица стойността на direction и делим по модул 4 (за да получаваме само стойности от 0 до 3).

Следващата стъпка при съставянето на алгоритъма е да установим кога се сменя посоката на движение (през колко итерации на цикъла). От двата примера можем да забележим, че броят на итерациите, през които се сменя посоката образува нестрого растящите редици 1, 1, 2, 2, 2 и 1, 1, 2, 2, 3, 3, 3. Ако разпишем на лист хартия по-голяма матрица от същия вид ясно виждаме, че редицата на смените на посоката следва същата схема – числата през едно нарастват с 1, като последното число не нараства. За моделирането на това поведение ще използваме променливите stepsCount (броят на итерациите в теку­щата посока), stepPosition (номерът на поредната итерация в тази посока) и stepChange (флаг, показващ дали на текущата итерация трябва да увеличим стойността на stepCount).

Проверка на идеята

Нека проверим идеята. След директно разписване на алгоритъма за N равно на 0, 1, 2 и 3 се вижда, че той е коректен и можем да преминем към неговата реализация.

Структури от данни и ефективност

При тази задачата избора на структурите от данни е еднозначен. Матри­цата ще пазим в двумерен масив. Други данни нямаме (освен числа). С ефективността няма да имаме проблем, тъй като програмата ще направи толкова стъпки, колкото са елементите в матрицата, т.е. имаме линейна сложност.

Реализация на идеята: стъпка по стъпка

Нека видим как можем да реали­зираме тази идея като код:

for (int i = 0; i < count; i++)

{

      matrix[positionY, positionX] = i;

      if (stepPosition < stepsCount)

      {

            stepPosition++;

      }

      else

      {

            stepPosition = 1;

            if (stepChange == 1)

            {

                  stepsCount++;

            }

            stepChange = (stepChange + 1) % 2;

            direction = (direction + 1) % 4;

      }

 

      switch (direction)

      {

            case 0:

                  positionY++;

                  break;

            case 1:

                  positionX--;

                  break;

            case 2:

                  positionY--;

                  break;

            case 3:

                  positionX++;

                  break;

      }

}

Тук е моментът да отбележим, че е голяма рядкост да съставим тялото на подобен цикъл от първия път, без да сгрешим. Вече знаем за правилото да пишем кода стъпка по стъпка, но за тялото на този цикъл то е трудно приложимо – нямаме ясно обособени подзадачи, които можем да тестваме независимо една от друга. Това не бива да ни притеснява – можем да използваме мощния debugger на Visual Studio за постъп­ково проследяване на изпълнението на кода. По този начин лесно ще открием къде е грешката, ако има такава.

След като имаме добре измислена идея на алгоритъм (дори да не сме напълно сигурни, че така написаният код работи безпроблемно), остава да дадем начални стойности на вече дефинираните променливи и да отпечатаме получената след изпълнението на цикъла матрица.

Ясно е, че броят на итерациите на цикъла е точно N2 и затова инициа­лизираме променливата count с тази стойност. От двата дадени примера и нашите собствени (написани на лист) примери определяме началната позиция в матрицата в зависимост от четността на нейната размерност:

int positionX = n / 2;

int positionY = n % 2 == 0 ? ((n / 2) - 1 : (n / 2));

На останалите променливи даваме еднозначно следните стойности (вече обяснихме каква е тяхната семантика):

int direction = 0;

int stepsCount = 1;

int stepPosition = 0;

int stepChange = 0;

Последната подзадача, която трябва да решим, за да имаме работеща програма, е отпечатването на матрицата на стандартния изход. Това става най-лесно с два вложени цикъла, които я обхождат по редове и на всяка итерация на вътрешния цикъл прилагаме подходящото форматиране:

for (int i = 0; i < n; i++)

{

      for (int j = 0; j < n; j++)

      {

            Console.Write("{0,3}", matrix[i, j]);

      }

      Console.WriteLine();

}

С това изчерпахме основните съставни елементи на програмата. Следва пълният изходен код на нашето решение:

MatrixSpiral.cs

public class MatrixSpiral

{

      static void Main()

      {

            Console.Write("N = ");

            int n = int.Parse(Console.ReadLine());

            int[,] matrix = new int[n, n];

 

            FillMatrix(matrix, n);

 

            PrintMatrix(matrix, n);

      }

 

      private static void FillMatrix(int[,] matrix, int n)

      {

            int count = n * n;

            int positionX = n / 2;

            int positionY = n % 2 == 0 ? ((n / 2) - 1 : (n / 2));

 

            int direction = 0;

            int stepsCount = 1;

            int stepPosition = 0;

            int stepChange = 0;

 

            for (int i = 0; i < count; i++)

            {

                  matrix[positionY, positionX] = i;

                  if (stepPosition < stepsCount)

                  {

                        stepPosition++;

                  }

                  else

                  {

                        stepPosition = 1;

 

                        if (stepChange == 1)

                        {

                              stepsCount++;

                        }

                        stepChange = (stepChange + 1) % 2;

                        direction = (direction + 1) % 4;

                  }

 

                  switch (direction)

                  {

                        case 0:

                              positionY++;

                              break;

                        case 1:

                              positionX--;

                              break;

                        case 2:

                              positionY--;

                              break;

                        case 3:

                              positionX++;

                              break;

                  }

            }

      }

 

      private static void PrintMatrix(int[,] matrix, int n)

      {

            for (int i = 0; i < n; i++)

            {

                  for (int j = 0; j < n; j++)

                  {

                        Console.Write("{0,3}", matrix[i, j]);

                  }

                  Console.WriteLine();

            }

      }

}

Тестване на решението

След като сме имплементирали решението, уместно е да го тестваме с достатъчен брой стойности на N, за да се уверим, че работи правилно. Започваме с примерните стойности 3 и 4, а после проверяваме и за 5, 6, 7, 8, 9, … Важно е да тестваме и за граничните случаи: 0 и 1. Провеждаме необходимите тестове и се убеждаваме, че всичко работи. В случая не е уместно да тестваме за скорост (примерно с N=1000), защото при голямо N изходът е прекалено обемен и задачата няма особен смисъл.

Задача 2: Броене на думи в текстов файл

Даден е текстов файл words.txt, който съдържа няколко думи, по една на ред. Да се напише програма, която намира броя срещания на всяка от дадените думи като подниз във файла sample.txt. Главните и малките букви се считат за еднакви. Резултатът да се запише в текстов файл с име result.txt във формат <дума> - <брой срещания>.

Примерен входен файл words.txt:

For

academy

student

develop

Примерен входен файл sample.txt:

The Telerik Academy for .NET software development engineers is a famous center for professional training of .NET experts. Telerik Academy offers courses designed to develop practical computer programming skills. Students graduated the Academy are guaranteed to have a job as a software developers in Telerik.

Примерен резултатен файл result.txt:

for – 2

academy – 3

student – 1

develop – 3

Решение на задачата

В дадената задача акцентът е не толкова върху алгоритъма за нейното решаването, а по-скоро върху техническата реализация. За да напишем решението, трябва да сме добре запознати с работата с файлове в C#, както и с основните структури от данни.

Измисляне на идея за решение

При тази задача идеята за решение е очевидна: прочитаме файла с думите, след това минаваме през текста и за всяка дума в него проверя­ваме дали е от интересните за нас думи и ако е увеличаваме съответния брояч. Измисляме решението бързо, защото от алгоритмична гледна точка е лесно и интуитивно.

Проверка на идеята

Идеята за решаване е тривиална, но все пак можем да я проверим като разпишем на лист хартия какво ще се получи за примерния входен файл. Лесно се убеждаваме, че тази идея е правилна.

Разделяме задачата на подзадачи

При реализацията на програмата можем да отделим три основни стъпки (подзадачи):

1.  Прочитаме файла words.txt и добавяме всяка дума от него към списък words (за целта използваме List<string> в реализацията). За четенето на текстови файлове е удобно да използваме методи на класа File, който вече сме разгледали в предходните глави.

2.  Обхождаме в цикъл всяка дума от файла sample.txt и проверяваме дали тя съвпада с някоя дума от списъка words. За четенето на думите от файла отново използваме класа File. При проверката игнори­раме разликата между малки и големи букви. В случай на съвпадение с вече добавена дума увеличаваме броя на срещанията на съответната дума от списъка words. Броят на срещанията на думите съхраняваме в целочислен масив wordsCount, в който елементите съвпадат позиционно с елементите на списъка words.

3.  Записваме резултата от така извършеното преброяване във файла result.txt, спазвайки формата, зададен в условието. За отваряне и писане във файла е удобно да използваме отново класа File.

Имплементация

Директно следваме стъпките, които идентифицирахме и ги реализираме. Получаваме следния сорс код:

WordsCounter.cs

using System.Collections.Generic;

using System.IO;

 

public class WordsCounter

{

      static void Main()

      {

            List<string> words = new List<string>();

            foreach(string word in File.ReadAllLines("words.txt"))

            {

                  words.Add(word.ToLower());

            }

           

            int[] wordsCount = new int[words.Count];

           

            string[] sampleFileWords =   

                  File.ReadAllText("sample.txt").Split(' ', '.');

 

            foreach(string sampleWordRaw in sampleFileWords)

            {

                  string sampleWord = sampleWordRaw.ToLower();

                  foreach (string word in words)

                  {

                        if (sampleWord.Contains(word))

                        {

                              wordsCount[words.IndexOf(word)]++;

                        }

                  }

            }

           

            using(StreamWriter resultFile  =
                  File.CreateText("result.txt"))

            {

                  foreach (string word in words)

                  {

                        resultFile.WriteLine("{0} - {1}", word,     

                              wordsCount[words.IndexOf(word)]);

                  }

            }

      }

}

Ефективност на решението

Май подценихме задачата и избързахме да напишем сорс кода. Ако се върнем към препоръките от главата: "Как да решаваме задачи по програ­миране", ще видим, че пропуснахме една важна стъпка: избор на подхо­дящи структури от данни. Написахме кода като използвахме първата възможна структура от данни, за която се сетихме, но не помислихме дали има по-добър вариант.

Време е да вмъкнем няколко думи за бързодействието (ефективността) на нашето реше­ние. В повечето случаи така написаната програма ще работи достатъчно бързо за голям набор от входни данни, което я прави приемливо решение при явяване на изпит. Въпреки това, е възможно да възникне ситуация, в която файлът words.txt съдържа много голям брой думи (примерно 10 000), което ще доведе до голям брой елементи на списъка words. Причината да се интересуваме от това е методът indexOf(…), който използваме за намиране на индекса на дадена дума. Неговото бързодействие е обратно пропорционално на броя на елементите на списъка и в този случай ще имаме осезаемо забавяне при работата на програмата. Например при 10 000 думи търсенето на една дума ще изисква 10 000 сравнения на двойки думи. Това ще се извърши толкова пъти, колкото са думите в текста, а те може да са много, да кажем 200 000. Тогава решението ще работи осезаемо бавно.

Можем да решим описания проблем като използваме хеш-таблица вместо целочисления масив wordsCount в горния код. Ще пазим в хеш-таблицата като ключове всички думи, които срещаме в текста, а като стойности ще пазим колко пъти се среща съответната дума. По този начин няма да се налага последователно търсене в списъка words, защото хеш-таблицата имплементира значително по-бързо асоциативно търсене сред своите еле­менти. Можеше да се сетим за това, ако бяхме помислили за структурите от данни преди да се хвърлим да пишем сорс кода. Май трябваше да се доверим на методологията за решаване на задачи, а не да действаме както си знаем, нали?

Нека видим подобрения по този начин вариант на решението:

WordsCounter.cs

using System.Collections.Generic;

using System.IO;

 

public class WordsCounter

{

      static void Main()

      {

            List<string> words = new List<string>();

            foreach(string word in File.ReadAllLines("words.txt"))

            {

                  words.Add(word.ToLower());

            }

 

            Dictionary<string, int> wordsCount =

                  new Dictionary<string, int>();

           

            string[] sampleFileWords =

                  File.ReadAllText("sample.txt").Split(' ', '.');

 

            foreach(string sampleWordRaw in sampleFileWords)

            {

                  string sampleWord = sampleWordRaw.ToLower();

                 

                  foreach (string word in words)

                  {

                        if (sampleWord.Contains(word))

                        {

                              if (wordsCount.ContainsKey(word))

                              {

                                    wordsCount[word] = wordsCount[word] + 1;

                              }

                              else

                              {

                                    wordsCount[word] = 1;

                              }

                        }

                  }

            }

           

            using(StreamWriter resultFile  =

                  File.CreateText("result.txt"))

            {

                  foreach (string word in words)

                  {

                        int count = wordsCount.ContainsKey(word) ?

                              wordsCount[word] : 0;

                        resultFile.WriteLine("{0} - {1}", word,      count);

                  }

            }

      }

}

Тестване на решението

Разбира се, както при всяка друга задача, е много важно да тестваме решението, което сме написали и е препоръчително да измислим свои собствени примери освен този, който е даден в условието, и да се убедим, че изходът е коректен.

Трябва да тестваме и граничните случаи: какво става, ако единият от входните файлове е празен или и двата са празни? Какво става, ако в двата файла има само по една дума? Трябва да проверим дали малки и главни букви се считат за еднакви.

Накрая трябва да тестваме за скорост. За целта с малко copy/paste правим списък от 10 000 думи във файла words.txt и копираме текста от файла sample.txt достатъчно на брой пъти, за да достигне до 5-10 MB. Старти­раме и се убеждаваме, че имаме проблем. Чакаме минута-две, но програ­мата не завършва. Нещо не е наред.

Търсене на проблема с бързодействието

Ако пуснем програмата през дебъгера, ще се забележим, че имаме много глупава грешка в следния фрагмент код:

foreach(string sampleWordRaw in sampleFileWords)

{

      string sampleWord = sampleWordRaw.ToLower();

      foreach (string word in words)

      {

            if (sampleWord.Contains(word))

            {

                  if (wordsCount.ContainsKey(word))

                  {

                        wordsCount[word] = wordsCount[word] + 1;

                  }

                  else

                  {

                        wordsCount[word] = 1;

                  }

            }

      }

}

Вижда се, че ако имаме 10 000 думи в масива words и 100 000 думи, които прочитаме една по една, за всяка от тях ще обходим във for-цикъл нашия масив и това прави 10 000 * 100 000 операции, които отнемат доста време. Как да оправим проблема?

Оправяне на проблема с бързодействието

За да работи коректно програмата очевидно трябва да преминем поне през веднъж през целия текст. Ако не прегледаме целия текст има опасност да не преброим някоя от думите. Следователно трябва да търсим ускорение на кода, който обработва всяка от думите. В текущата импле­ментация се върти цикъл до броя думи, които броим и ако те са много, този цикъл забавя чувствително програмата.

Идва ни идеята да заменим цикъла по думите, които броим с нещо по-бързо. Дали е възможно? Да помислим защо въртим този цикъл. Въртим го, за да видим дали думата, която сме прочели от текста е сред нашия списък от думи, за които броим колко пъти се срещат. Реално ни трябва бързо търсене в множество от думи. За целта може да се ползва HashSet или Dictionary, нали? Да си припомним структурите от данни множество и хеш-таблица. При тях може да се реализира изключително бързо търсене дори ако елементите са огромен брой.

Изводът е, че до момента сгрешихме на няколко пъти от прибързване. Ако бяхме помислили за структурите от данни и за ефективността преди да напишем кода, щяхме да си спестим много време и писане. Нека сега поправим грешката. Хрумва ни следната идея:

1.  Правим си хеш-таблица и в нея записваме като ключове всички думи от файла words.txt. Като стойност в тези ключове записваме числото 0. Това е броят срещания на всяка дума в текста в началния момент, преди да сме започнали да го сканираме.

2.  Сканираме текста дума по дума и търсим всяка от тях в хеш-таблицата. Това е бърза операция (търсене в хеш-таблица по ключ). Ако намерим думата, увеличаваме с 1 стойността в съответ­ния ключ. Така си осигуряваме, че всяко срещане се отбелязва и накрая за всяка дума ще получим броя на срещанията й.

3.  Накрая сканираме думите от файла words.txt и за всяка търсим в хеш-таблицата колко пъти се среща в текста и записваме резултата в изходния файл.

С новия алгоритъм при обработката на всяка дума от текста имаме по едно търсене в хеш-таблица и нямаме претърсване на масив, което е много бавна операция. Ето как изглежда новия алгоритъм:

FastWordsCounter.cs

using System.Collections.Generic;

using System.IO;

 

public class WordsCounter

{

      static void Main()

      {

            List<string> words = new List<string>();

            Dictionary<string, int> wordsCount =

                  new Dictionary<string, int>();

 

            foreach (string wordRaw in File.ReadAllLines("words.txt"))

            {

                  string word = wordRaw.ToLower();

                  words.Add(word);

                  wordsCount[word] = 0;

            }

 

            string[] sampleFileWords =

                  File.ReadAllText("sample.txt").Split(' ', '.');

            foreach(string wordRaw in sampleFileWords)

            {

                  string word = wordRaw.ToLower();

 

                  int count;

                  if (wordsCount.TryGetValue(word, out count))

                  {

                        wordsCount[word] = count + 1;

                  }

            }

           

            using(StreamWriter resultFile  =

                  File.CreateText("result.txt"))

            {

                  foreach (string word in words)

                  {

                        int count = wordsCount[word];

                        resultFile.WriteLine("{0} - {1}", word,      count);

                  }

            }

      }

}

Повторно тестване на проблема с бързодействието

Остава да тестваме новия алгоритъм: дали е коректен и дали работи бързо. Дали е коректен лесно можем да проверим с примерите, с които сме тествали и преди. Дали работи бързо можем да тестваме с големия пример (10 000 думи и 10 MB текст). Бързо се убеждаваме, че този път дори при големи обеми текстове програмата работи бързо. Дори пускаме 20 000 думи и 100 MB файл, за да видим дали ще работи. Уверяваме се, че дори и при такъв обем данни програмата работи стабилно и с прием­лива скорост (20-30 секунди на компютър от 2008 г.).

Задача 3: Училище

В едно училище учат ученици, които са разделени в учебни групи. На всяка група преподава един учител.

За учениците се пази следната информация: име и фамилия.

За всяка група се пази следната информация: наименование и списък на учениците.

За всеки учител се пази следната информация: име, фамилия и списък от групите, на които преподава. Един учител може да преподава на повече от една група.

За училището се пази следната информация: наименование, списък на учителите, списък на групите, списък на учениците.

1.  Да се проектира съвкупност от класове с връзки между тях, които моделират училището.

2.  Да се реализират методи за добавяне на учител, за добавяне на група и за добавяне на ученик. Списъците могат да се представят чрез масиви или чрез списъчни структури.

3.  Да се реализира метод за отпечатване на информация за даден учител: име, фамилия, списък на групите, на които преподава, и списък на учениците от всяка от тези групи.

4.  Да се напише примерна тестова програма, която демонстрира работата на реализираните класове и методи.

Пример:

Училище "Свобода". Учители: Димитър Георгиев, Христина Николова.

Група "английски език": Иван Петров, Васил Тодоров, Елена Михайлова, Радослав Георгиев, Милена Стефанова, учител Христина Николова.

Група "френски език": Петър Петров, Васил Василев, учител Христина Николова.

Група "информатика": Милка Колева, Пенчо Тошев, Ива Борисова, Милена Иванова, Христо Тодоров, учител Димитър Георгиев.

Решение на задачата

Това е добър пример за задача, чиято цел е да тества умението на кандидатите, явяващи се на изпита да използват ООП за моделиране на задачи от реалния свят. Ще моделираме предметната област като дефини­раме взаимно свързаните класове Student, Group, Teacher и School. За да бъде изцяло изпълнено условието на задачата ще имаме нужда и от клас SchoolTest, който демонстрира работата на дефинираните от нас класове и методи.

Измисляне на идея за решение

В тази задача няма нищо за измисляне. Тя не е алгоритмична и в нея няма какво толкова да мислим. Трябва за всеки обект от описаните в условието на задачата (студенти, учители, ученици, училище и т.н.) да дефинираме по един клас и след това в този клас да дефинираме свойства, които го описват и действия, които той може да направи. Това е всичко.

Разделяме задачата на подзадачи

Имплементацията на всеки един от класовете можем да разглеждаме като подзадача на дадената:

-    Клас за студентите – Student

-    Клас за групите – Group

-    Клас за учителите – Teacher

-    Клас за училището – School

-    Клас за тестване на останалите класове с примерни данни – SchoolTest

Имплементиране: стъпка по стъпка

Удачно е да започнем реализацията с класа Student, тъй като от усло­вието на задачата лесно се вижда, че той не зависи от останалите три.

Класът Student

В дефиницията имаме само две полета, представляващи име и фамилия на ученика и свойството Name, което връща низ с името на ученика. Дефинираме го по следния начин:

Student.cs

public class Student

{

      private string firstName;

      private string lastName;

 

      public Student(string firstName, string lastName)

      {

            this.firstName = firstName;

            this.lastName = lastName;

      }

 

      public string Name

      {

            get

            {

                  return this.firstName + " " + this.lastName;

            }

      }

}

Класът Group

Следващият клас, който дефинираме е Group. Избираме него, защото в дефиницията му се налага да използваме единствено класа Student. Полетата, които ще дефинираме представляват име на групата и списък с ученици, които посещават групата. За реализацията на списъка с ученици ще използваме класа List<Student>. Класът ще има свойствата Name и Students, които извличат стойностите на двете полета. Добавяме два метода, които ни трябват – АddStudent(…) и PrintStudents(…). Методът AddStudent(…) добавя обект от тип Student към списъка students, a методът PrintStudents(…) отпечатва името на групата и имената на учениците в нея. Нека сега видим цялата реализация на класа:

Group.cs

using System.Collections.Generic;

using System.IO;

 

public class Group

{

      private string name;

      private List<Student> students;

     

      public Group(string name)

      {

            this.name = name;

            this.students = new List<Student>();

      }

     

      public string Name

      {

            get

            {

                  return this.name;

            }

      }

     

      public IEnumerable<Student> Students

      {

            get

            {

                  return this.students;

            }

      }

     

      public void AddStudent(Student student)

      {

            students.Add(student);

      }

 

      public void PrintStudents(TextWriter output)

      {

            output.WriteLine("Group name: {0}", this.Name);

            output.WriteLine("Students in group:");

            foreach (Student student in this.Students)

            {

                  output.WriteLine("Name: {0}", student.Name);

            }

      }

}

Класът Teacher

Нека сега дефинираме класа Teacher, който използва класа Group. Неговите полета са име, фамилия и списък с групи. Той има методи AddGroup(…) и PrintGroups(…), аналогични на тези в класа Group. Методът PrintGroups(…) отпечатва името на учителя и извиква метода PrintStudents(…) на всяка група от списъка с групи:

Teacher.cs

using System.Collections.Generic;

using System.IO;

 

public class Teacher

{

      private string firstName;

      private string lastName;

      private List<Group> groups;

     

      public Teacher(string firstName, string lastName)

      {

            this.firstName = firstName;

            this.lastName = lastName;

            this.groups = new List<Group>();

      }

     

      public void AddGroup(Group group)

      {

            this.groups.Add(group);

      }

     

      public void PrintGroups(TextWriter output)

      {

            output.WriteLine("Teacher name: {0} {1}", this.firstName,

                  this.lastName);

            output.WriteLine("Groups of teacher:");

            foreach (Group group in this.groups)

            {

                  group.PrintStudents(output);

            }

      }

}

Класът School

Завършваме обектния модел с дефиницията на класа School, който изпол­зва всички вече дефинирани класове. Полетата му са име, списък с учители, списък с групи и списък с ученици. Пропъртитата Name и Teachers използваме за извличане на нужните данни. Дефинираме методи АddTeacher(…) и АddGroup(…) за добавяне на съответните обекти. За удобство при създаването на обектите, в метода АddGroup(…) импле­ментираме следната функционалност: освен добавянето на самата група като обект, добавяме към списъка с ученици и учениците, които попадат в тази група (но все още не са добавени в списъка на училището). Ето и целия код на класа:

School.cs

using System.Collections.Generic;

 

public class School

{

      private string name;

      private List<Teacher> teachers;

      private List<Group> groups;

      private List<Student> students;

     

      public School(string name) {

            this.name = name;

            this.teachers = new List<Teacher>();

            this.groups = new List<Group>();

            this.students = new List<Student>();

      }

     

      public string Name

      {

            return name;

      }

     

      public IEnumerable<Teacher> Teachers

      {

            get

            {

                  return this.teachers;

            }

      }

     

      public void AddTeacher(Teacher teacher)

      {

            teachers.Add(teacher);

      }

     

      public void AddGroup(Group group)

      {

            groups.Add(group);

            foreach (Student student in group.Students)

            {

                  if(!this.students.Contains(student))

                  {

                        this.students.Add(student);

                  }

            }

      }

}

Класът TestSchool

Следва реализацията на класа SchoolTest, който има за цел да демон­стрира класовете и методите, които дефинирахме. Това е и нашата последна подзадача – с нея решението е завършено. За демонстрацията използваме данните от примера в условието:

SchoolTest.cs

using System;

 

public class SchoolTest

{

      public static void AddObjectsToSchool(School school)

      {

            Teacher teacherGeorgiev = new Teacher("Димитър",

                  "Георгиев");

            Teacher teacherNikolova = new Teacher("Христина",

                  "Николова");

 

            school.AddTeacher(teacherGeorgiev);

            school.AddTeacher(teacherNikolova);

 

            // Add the English group

            Group groupEnglish = new Group("английски език");

            groupEnglish.AddStudent(new Student("Иван", "Петров"));

            groupEnglish.AddStudent(new Student("Васил", "Тодоров"));

            groupEnglish.AddStudent(new Student("Елена", "Михайлова"));

            groupEnglish.AddStudent(new Student("Радослав",

                  "Георгиев"));

            groupEnglish.AddStudent(new Student("Милена",

                  "Стефанова"));

            groupEnglish.AddStudent(new Student("Иван", "Петров"));

 

            school.AddGroup(groupEnglish);

            teacherNikolova.AddGroup(groupEnglish);

 

            // Add the French group

            Group groupFrench = new Group("френски език");

            groupFrench.AddStudent(new Student("Петър", "Петров"));

            groupFrench.AddStudent(new Student("Васил", "Василев"));

 

            school.AddGroup(groupFrench);

            teacherNikolova.AddGroup(groupFrench);

 

            // Add the Informatics group

            Group groupInformatics = new Group("информатика");

            groupInformatics.AddStudent(new Student("Милка",

                  "Колева"));

            groupInformatics.AddStudent(new Student("Пенчо", "Тошев"));

            groupInformatics.AddStudent(new Student("Ива",

                  "Борисова"));

            groupInformatics.AddStudent(new Student("Милена",

                  "Иванова"));

            groupInformatics.AddStudent(new Student("Христо",

                  "Тодоров"));

 

            school.AddGroup(groupInformatics);

            teacherGeorgiev.AddGroup(groupInformatics);

      }

 

      public static void Main() {

            School school = new School("Свобода");

           

            AddObjectsToSchool(school);

           

            foreach(Teacher teacher in school.Teachers)

            {

                  teacher.PrintGroups(Console.Out);

                  Console.WriteLine();

            }

      }

}

Изпълняваме програмата и получаваме очаквания резултат:

Teacher name: Димитър Георгиев

Groups of teacher:

Group name: информатика

Students in group:

  Name: Милка Колева

  Name: Пенчо Тошев

  Name: Ива Борисова

  Name: Милена Иванова

  Name: Христо Тодоров

 

Teacher name: Христина Николова

Groups of teacher:

Group name: английски език

Students in group:

  Name: Иван Петров

  Name: Васил Тодоров

  Name: Елена Михайлова

  Name: Радослав Георгиев

  Name: Милена Стефанова

  Name: Иван Петров

Group name: френски език

Students in group:

  Name: Петър Петров

  Name: Васил Василев

Разбира се, в реалния живот програмите не тръгват от пръв път, но в тази задача грешките, които можете да допуснете, са тривиални и няма смисъл да ги дискутираме. Всичко е въпрос на написване (ако познавате работата с класове и обектно-ориентираното програмиране като цяло).

Тестване на решението

Остава, както при всяка задача, да тестваме дали решението работи правилно. Ние вече го направихме. Може да направим и няколко теста с гранични данни, примерно група без студенти, празно училище и т.н. тестове за бързодействие няма да правим, защото задачата има неизчис­лителен характер. Това би било достатъчно, за да се уверим, че решението ни е коректно.

Упражнения

1.  Напишете програма, която отпечатва спирална квадратна матрица, започвайки от числото 1 в горния десен ъгъл и движейки се по часовниковата стрелка. Примери при N=3 и N=4:

clip_image003

2.  Напишете програма, която брои думите в текстов файл, но за дума счита всяка последователност от символи (подниз), а не само отделените с разделители. Например в текста "Аз съм студент в София" поднизовете "с", "сту", "а" и "аз съм" се срещат съответно 3, 1, 2 и 1 пъти.

3.  Моделирайте със средствата на ООП файловата система в един компютър. В нея имаме устройства, директории и файлове. Устрой­ствата са примерно твърд диск, флопи диск, CD-ROM устройство и др. Те имат име и дърво на директориите и файловете. Една директория има име, дата на последна промяна и списък от файлове и директории, които се съдържат в нея. Един файл има име, дата на създаване, дата на последна промяна и съдържание. Файлът се намира в някоя от директориите. Файлът може да е текстов или бинарен. Текстовите файлове имат за съдържание текст (string), а бинарните – поредица от байтове (byte[]). Направете клас, който тества другите класове и показва, че с тях можем да построим модел на устройствата, директо­риите и файловете в компютъра.

4.  Използвайки класовете от предходната задача с търсене в Интернет напи­шете програма, която взима истинските файлове от компютъра и ги записва във вашите класове (без съдържанието на файловете, защото няма да стигне паметта).

Решения и упътвания

1.  Задачата е аналогична на първата задача от примерния изпит. Можете да модифицирате примерното решение, дадено по-горе.

2.  Трябва да четете текста буква по буква и след всяка следваща буква да я долепяте към текущ буфер buf и да проверявате всяка от търсените думи за съвпадение с ЕndsWith(). Разбира се, няма да можете да ползвате ефективно хеш-таблица и ще имате цикъл по думите за всяка буква от текста, което не е най-бързото решение.

Реализирането на бързо решение изисква използването на сложна структура от данни, наречена суфиксно дърво. Можете да потърсите в Google следното: "suffix tree" "pattern matching" filetype:ppt.

3.  Задачата е аналогична на задачата с училището от примерния изпит и се решава чрез същия подход. Дефинирайте класове Device, Directory, File, ComputerStorage и ComputerStorageTest. Помислете какви свойства има всеки от тези класове и какви са отношенията между класовете. Когато тествате слагайте примерно съдържание за файловете (примерно по 1 думичка), а не оригиналното, защото то е много обемно. Помислете може ли един файл да е в няколко дирек­тории едновременно.

4.  Използвайте класа System.IO.Directory и неговите статични методи GetFiles(), GetDirectories() и GetLogicalDrives().

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.


2 отговора до “Глава 26. Практически задачи за изпит по програмиране – тема 3”

  1. Martin says:
    November 19, 2014 at 5:02 pm

    някой може ли да помогне???
    Даден е текстов файл със следната структура: ДУМА\t СРЕЩАНИЯ\n Списъкът с думи да се сортира в низхо/дящ ред по честота на срещане на думите по метода на пряката селекция и да се изведе на екран

  2. Наков says:
    November 19, 2014 at 5:11 pm

    Питай тука: https://softuni.bg/forum/

Коментирай

Трябва да сте влезнали, за да коментирате.