Глава 25. Примерна тема от изпит по програмиране – 11.12.2005 г.

Автор

Теодор Стоев

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

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

Съдържание

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

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

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

clip_image002

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

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

Да започнем с избора на структура от данни за представяне на матрицата. Удобно е да имаме директен достъп до всеки елемент на матрицата, затова ще се спрем на двумерен масив 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. Разписваме алгоритъма набързо на лист хартия. Изглежда работи. Пробваме за N=1. Работи. Пробваме за N=2. Работи. Пробваме за N=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 на Eclipse за постъп­ково проследяване на изпълнението на кода. По този начин лесно ще открием къде е грешката, ако има такава.

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

Ясно е, че броят на итерациите на цикъла е точно 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++) {

        System.out.printf("%3d ", matrix[i][j]);

    }

    System.out.println();

}

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

MatrixSpiral.java

import java.util.*;

 

public class MatrixSpiral {

    public static void printMatrix(int[][] matrix, int n) {

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

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

                System.out.printf("%3d ", matrix[i][j]);

            }

            System.out.println();

        }

    }

   

    public 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;

            }

        }

    }

   

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        System.out.print("N = ");

        int n = input.nextInt();

       

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

       

        fillMatrix(matrix, n);

       

        printMatrix(matrix, n);

    }

}

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

След като сме имплементирали решението, уместно е да го тестваме с достатъчен брой стойности на 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 National Academy for Software Development is a center for professional training for software engineers. The Academy offers courses designed to develop practical computer programming skills. Students finished the Academy are guaranteed to have a job as a software developers.

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

for – 3

academy – 3

student – 1

develop – 3

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

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

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

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

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

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

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

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

1.  Прочитаме файла words.txt и добавяме всяка дума от него към списък words (за целта използваме ArrayList реализацията). За четенето на текстови файлове е удобно да използваме класа Scanner, който вече подробно сме разглеждали.

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

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

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

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

WordsCounter.java

import java.util.*;

import java.io.*;

 

public class WordsCounter {

    public static void main(String[] args)

        throws FileNotFoundException {

 

        ArrayList<String> words = new ArrayList<String>();

        Scanner wordsFile = new Scanner(new File("words.txt"));

        while (wordsFile.hasNextLine()) {

            words.add(wordsFile.nextLine().toLowerCase());

        }

        wordsFile.close();

       

        int[] wordsCount = new int[words.size()];

        Scanner sampleFile = new Scanner(new File("sample.txt"));

        while (sampleFile.hasNext()) {

            String sampleWord = sampleFile.next().toLowerCase();

            for (String word : words) {

                if (sampleWord.contains(word)) {

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

                }

            }

        }

        sampleFile.close();

       

        PrintStream resultFile = new PrintStream("result.txt");

        for (String word : words) {

            resultFile.format("%s - %s%n", word,

                wordsCount[words.indexOf(word)]);

        }

        resultFile.close();

    }

}

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

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

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

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

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

WordsCounter.java

import java.util.*;

import java.io.*;

 

public class WordsCounter {

    public static void main(String[] args)

        throws FileNotFoundException {

 

        ArrayList<String> words = new ArrayList<String>();

        Scanner wordsFile = new Scanner(new File("words.txt"));

        while (wordsFile.hasNextLine()) {

            words.add(wordsFile.nextLine().toLowerCase());

        }

        wordsFile.close();

       

        Hashtable<String, Integer> wordsCount =

            new Hashtable<String, Integer>();

        Scanner sampleFile = new Scanner(new File("sample.txt"));

        while (sampleFile.hasNext()) {

            String sampleWord = sampleFile.next().toLowerCase();

            for (String word : words) {

                if (sampleWord.contains(word)) {

                    if (wordsCount.containsKey(word)) {

                      wordsCount.put(word, wordsCount.get(word) + 1);

                    } else {

                      wordsCount.put(word, 1);

                    }

                }

            }

        }

        sampleFile.close();

       

        PrintStream resultFile = new PrintStream("result.txt");

        for (String word : words) {

            int count = wordsCount.containsKey(word) ?

                wordsCount.get(word) : 0;

            resultFile.format("%s - %s%n", word, count);

        }

        resultFile.close();

    }

}

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

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

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

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

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

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

while (sampleFile.hasNext()) {

    String sampleWord = sampleFile.next().toLowerCase();

    for (String word : words) {

        if (sampleWord.contains(word)) {

            if (wordsCount.containsKey(word)) {

                wordsCount.put(word, wordsCount.get(word) + 1);

            } else {

                wordsCount.put(word, 1);

            }

        }

    }

}

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

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

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

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

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

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

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

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

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

FastWordsCounter.java

import java.util.*;

import java.io.*;

 

public class FastWordsCounter {

    public static void main(String[] args)

        throws FileNotFoundException {

 

        ArrayList<String> words = new ArrayList<String>();

        Hashtable<String, Integer> wordsCount =

            new Hashtable<String, Integer>();

        Scanner wordsFile = new Scanner(new File("words.txt"));

        while (wordsFile.hasNextLine()) {

            String word = wordsFile.nextLine().toLowerCase();

            words.add(word);

            wordsCount.put(word, 0);

        }

        wordsFile.close();

       

        Scanner sampleFile = new Scanner(new File("sample.txt"));

        while (sampleFile.hasNext()) {

            String word = sampleFile.next().toLowerCase();

            Integer count = wordsCount.get(word);

            if (count != null) {

                wordsCount.put(word, count + 1);

            }

        }

        sampleFile.close();

       

        PrintStream resultFile = new PrintStream("result.txt");

        for (String word : words) {

            int count = wordsCount.get(word);

            resultFile.format("%s - %s%n", word, count);

        }

        resultFile.close();

    }

}

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

Остава да тестваме новия алгоритъм: дали е коректен и дали работи бързо. Дали е коректен лесно можем да проверим с примерите, с които сме тествали и преди. Дали работи бързо можем да тестваме с големия пример (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

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

Student.java

public class Student {

    private String firstName;

    private String lastName;

   

    public Student(String firstName, String lastName) {

        this.firstName = firstName;

        this.lastName = lastName;

    }

   

    public String getName() {

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

    }

}

Класът Group

Следващият клас, който дефинираме е Group. Избираме него, защото в дефиницията му се налага да използваме единствено класа Student. Полетата, които ще дефинираме представляват име на групата и списък с ученици, които посещават групата. За реализацията на списъка с ученици ще използваме класа ArrayList. Класът ще има методи getName() и getStudents(), които извличат стойностите на двете полета. Добавяме още два метода, които ни трябват – addStudent(…) и printStudents(…). Методът addStudent(…) добавя обект от тип Student към списъка students, a методът printStudents(…) отпечатва името на групата и имената на учениците в нея. Нека сега видим цялата реализация на класа:

Group.java

import java.util.ArrayList;

import java.io.PrintStream;

 

public class Group {

    private String name;

    private ArrayList<Student> students;

   

    public Group(String name) {

        this.name = name;

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

    }

   

    public String getName() {

        return this.name;

    }

   

    public ArrayList<Student> getStudents() {

        return this.students;

    }

   

    public void addStudent(Student student) {

        students.add(student);

    }

   

    public void printStudents(PrintStream output) {

        output.printf("Group name: %s%n", this.name);

        output.printf("Students in group:%n");

        for(Student student : this.students) {

            output.printf("  Name: %s%n", student.getName());

        }

    }

}

Класът Teacher

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

Teacher.java

import java.util.ArrayList;

import java.io.PrintStream;

 

public class Teacher {

    private String firstName;

    private String lastName;

    private ArrayList<Group> groups;

   

    public Teacher(String firstName, String lastName) {

        this.firstName = firstName;

        this.lastName = lastName;

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

    }

   

    public void addGroup(Group group) {

        this.groups.add(group);

    }

   

    public void printGroups(PrintStream output) {

        output.printf("Teacher name: %s %s%n", this.firstName,

            this.lastName);

        output.printf("Groups of teacher:%n");

        for(Group group : this.groups) {

            group.printStudents(output);

        }

    }

}

Класът School

Завършваме обектния модел с дефиницията на класа School, който изпол­зва всички вече дефинирани класове. Полетата му са име, списък с учители, списък с групи и списък с ученици. Методите getName() и getTeachers() използваме за извличане на нужните данни. Дефинираме методи addTeacher(…) и addGroup(…) за добавяне на съответните обекти. За удобство при създаването на обектите, в метода addGroup(…) импле­ментираме следната функционалност: освен добавянето на самата група като обект, добавяме към списъка с ученици и учениците, които попадат в тази група (но все още не са добавени в списъка на училището). Ето и целия код на класа:

School.java

import java.util.ArrayList;

 

public class School {

    private String name;

    private ArrayList<Teacher> teachers;

    private ArrayList<Group> groups;

    private ArrayList<Student> students;

   

    public School(String name) {

        this.name = name;

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

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

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

    }

   

    public String getName() {

        return name;

    }

   

    public ArrayList<Teacher> getTeachers() {

        return this.teachers;

    }

   

    public void addTeacher(Teacher teacher) {

        teachers.add(teacher);

    }

   

    public void addGroup(Group group) {

        groups.add(group);

        for(Student student : group.getStudents()) {

            if(!this.students.contains(student)) {

                this.students.add(student);

            }

        }

    }

}

Класът TestSchool

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

SchoolTest.java

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(String[] args) {

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

       

        addObjectsToSchool(school);

       

        for(Teacher teacher : school.getTeachers()) {

            teacher.printGroups(System.out);

            System.out.println();

        }

    }

}

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

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_image004

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

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

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

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

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

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

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

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

4.    Използвайте класа java.io.File и методите listRoots(), listFiles() и isDirectory().

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

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

Коментирай

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