Free C# / Java / JavaScript / Python / C++ Programming Books » Глава 23. Примерна тема от изпит по програмиране

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

Съдържание

Задача 1: Извличане на текста от HTML документ

Даден е HTML файл с име Problem1.html. Да се напише програма, която отстранява от него всички HTML тагове и запазва само текста вътре в тях. Изходът да се изведе във файла Рroblem1.txt.

Примерен входен файл Рroblem1.html:

<html>

<head><title>Welcome to our site!</title></head>

<body>

<a href="/contacts.html">Contacts</a>

<a href="/about.html">About</a>

</center>

</body>

</html>

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

Welcome to our site!

Home

Contacts

About

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

Първото, което ни хрумва, като идея за решение на тази задача е да четем последователно (примерно ред по ред или буква по буква) входния файл и да махаме всички тагове. Лесно се вижда, че всички тагове започват със символа "<" и завършват със символа ">". Това се отнася и за отварящите и за затварящите тагове. Това означава, че от всеки ред във файла трябва да се премахнат всички поднизове, започващи с "<" и завършващи с ">".

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

Имаме идея за решаване на задачата. Дали идеята е вярна? Първо трябва да я проверим. Можем да я проверим дали е вярна за примерния входен файл, а след това да помислим дали няма някакви специални случаи, за които идеята би могла да е некоректна.

Взимаме лист и химикал и проверяваме на ръка идеята дали е вярна. Задраскваме всички поднизове от текста, които започват със символа "<" и завършват със символа ">". Като го направим, виждаме, че остава само чистият текст и всички тагове изчезват:

~~<html>~~

~~<head><title>~~Welcome to our site!~~</title></head>~~

~~<body>~~

~~<center>~~

~~<img src="/en/img/logo.gif" width="130" height="70" alt="Logo">~~

~~ ~~

~~<a href="/index.html">~~Home~~</a>~~

~~<a href="/contacts.html">~~Contacts~~</a>~~

~~<a href="/about.html">~~About~~</a>~~

~~</center>~~

~~</body>~~

~~</html>~~

Сега остава да измислим някакви по-специални случаи. Нали не искаме да напишем 200 реда код и чак тогава да се сетим за тях и да трябва да преправяме цялата програма? Затова е важно да проверим проблемните ситуации, за които се сетим, още сега, преди да сме почнали да пишем кода на решението.

Можем да се сетим за следния специален пример:

Click<a href="info.html">on this

link</a>for more info.

This isboldtext.

</body></html>

В него има две особености:

- Има тагове, съдържащи текст, които се отварят и затварят на различни редове.

- Има тагове, които съдържат хем текст, хем други тагове в себе си.

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

Clickon this

linkfor more info.

This isboldtext.

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

Click on this link for more info.

This is bold text.

Има и други варианти, например да слагаме всяко парче текст, което не е таг, на нов ред:

Click

on this

link

for more info.

This is

bold

text.

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

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

on this

link

bold

От условието не става ясно още как се визуализира текст, който е разположен на няколко реда във вътрешността на някой таг.

Изясняване на условието на задачата

Първото, което трябва да направим, когато открием неясен момент в условието на задачата, е да го прочетем внимателно. В случая условието наистина не е ясно и не ни дава отговор на въпросите. Най-вероятно не трябва да следваме HTML правилата, защото те не са описани в условието, но не става ясно дали долепяме думите в съседни тагове или си разделяме с нов ред.

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

Приемаме, че трябва да се отпечата всичкия текст, който остава като премахнем всички отварящи и затварящи тагове, като използваме за разделител между отделните текстове празен ред. Ако в текста има празни редове, запазваме ги. За нашия пример трябва да получим следния изход:

Click

on this

link

for more info.

This is

bold

text.

Нова идея за решаване на задачата

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

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

Разбиваме задачата на подзадачи

Задачата лесно можем да разбием на подзадачи:

- Прочитане на входния файл.

- Обработка на един ред от входния файл: заместване на таговете със символ за нов ред.

- Записване на резултата в изходния файл.

Какво структури от данни да ползваме?

В тази задача трябва да извършваме проста текстообработка и работа с файлове. Въпросът какви структури от данни да ползваме не стои пред нас – за четене и писане във файл ще ползваме съответните класове от пакета java.io, а за текстообработката ще ползваме класа String и ако се наложи – StringBuilder.

Да помислим за ефективността

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

Може би проблеми ще създаде изчистването на празните редове. Ако събираме всички редове в някакъв буфер (StringBuilder) и след това премахваме двойните празни редове, този буфер ще заеме много памет при големи входни файлове (примерно при 500 MB входен файл).

За да спестим памет, ще се опитаме да чистим излишните празни редове още след заместване на таговете със символа за празен ред.

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

Стъпка 1 – прочитане на входния файл

Първата стъпка от решението на поставената задача е прочитането входния файл. В нашия случай той е HTML файл. Това не трябва да ни притеснява, тъй като HTML е текстов формат. Затова, за да го прочетем, ще използваме класа Scanner. Ще обходим входния файл ред по ред и за всеки ред ще извличаме (засега не ни интересува как) нужната ни информация (ако има) и ще я за писваме в един StringBuilder. Извличането ще реализираме в следващата стъпка (стъпка 2), а записването в някоя от по-следващите стъпки. Да напишем нужния код за реализацията на нашата първа стъпка:

Scanner scanner = new Scanner(new File("Problem1.html"));

while (scanner.hasNextLine()) {

// Find what we need and save it in the result

}

scanner.close();

Чрез написания код ще прочетем входния файл ред по ред. Да помислим дали сме реализирали добре първата стъпка. Сещате ли се какво пропуснахме?

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

За да избегнем тези проблеми трябва да използваме конструкцията try-catch-finally. Така, ако възникне изключение ще го обработим и накрая винаги ще затваряме файла, с които сме работили. Не трябва да забравяме, че обекта от Scanner трябва да е деклариран извън try блока, защото иначе ще е недостъпен във finally блока. Това не е фатална грешка, но често се допуска от начинаещите програмисти.

Добре е да дефинираме името на входния файл като константа, защото вероятно ще го ползваме на няколко места.

Още нещо: при четене от текстов файл е редно да зададем кодирането на файла. В случая ще използваме кодиране windows-1251.

Да видим до какво стигнахме:

import java.io.*;

public class HtmlTagRemover {

private static final String INPUT_FILE_NAME =

"Problem1.html";

private static final String CHARSET = "windows-1251";

public static void main(String args[]) {

Scanner scanner = null;

StringBuilder result = new StringBuilder();

try {

scanner = new Scanner(

new File(INPUT_FILE_NAME), CHARSET);

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

// Process the next line here

}

} catch (IOException ioex) {

System.err.println(

"Can not read file " + INPUT_FILE_NAME + ".");

} finally {

if (scanner != null) {

scanner.close();

}

Справихме се с описаните проблеми и изглежда вече имаме коректно реализирано четенето на входния файл. За да сме напълно сигурни можем да тестваме. Например да изпишем съдържанието на входния файл на конзолата, а след това да пробваме с несъществуващ файл. Изписването ще става в while цикъла чрез System.out.println(scanner.nextLine()).

Ако тестваме с примера от условието на задачата, резултатът е следният:

<html>

<head>

<title>Welcome to our site!</title>

</head>

<body>

<a href="/index.html">Home</a> -

<a href="/contenst.html">Contacts</a> -

<a href="/about.html">About</a>

</center>

</body>

</html>

Сега, нека пробваме с несъществуващ файл. Да заменим името на файла Problem1.html с Problem2.html. Резултатът от това е следният:

File Problem2.html not found

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

Стъпка 2 – премахване на таговете

Сега трябва да измислим подходящ начин да премахнем всички тагове. Какъв да бъде начинът?

Един възможен начин е като проверяваме реда символ по символ. За всеки символ от текущия ред ще търсим символа "<". От него надясно ще знаем, че е имаме някакъв таг (отварящ или затварящ). Краят на тага символът ">". Така можем да откриваме таговете и да ги премахваме. За да не получим долепяне на думите в съседни тагове, ще заместваме всеки таг със символа за празен ред "\n".

Алгоритъмът не е сложен за имплементиране, но дали няма по-хитър начин? Можем ли да използваме регулярни изрази? С тях лесно можем да търсим тагове и да ги заместваме с "\n", нали? Същевременно кодът няма да е сложен и при възникване на грешки по–лесно ще бъдат отстранени. Ще се спрем на този вариант. Какво трябва да направим? Първо трябва да напишем регулярния израз. Ето как изглежда той:

<[^>]*>

Идеята е проста: всеки низ, който започва с "<", продължава с произволи символи, различни от ">" и завършва с ">", е HTML таг. Ето как можем да заместим таговете със символ за нов ред:

private static String removeAllTags(String str) {

String strWithoutTags = str.replaceAll("<[^>]*>", "\n");

return strWithoutTags;

}

След като написахме тази стъпка, трябва да я тестваме. За целта отново ще изписваме намерените низове на конзолата чрез System.out. println(). Да тестваме кода, който получихме:

HtmlTagRemover.java

import java.io.*;

import java.util.*;

public class HtmlTagRemover {

private static final String INPUT_FILE_NAME =

"Problem1.html";

private static final String CHARSET = "windows-1251";

public static void main(String args[]) {

Scanner scanner = null;

try {

scanner = new Scanner(

new File(INPUT_FILE_NAME), CHARSET);

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

line = removeAllTags(line);

System.out.println(line);

}

} catch (IOException ioex) {

System.err.println("Can read file " + INPUT_FILE_NAME);

} finally {

if (scanner != null) {

scanner.close();

}

private static String removeAllTags(String str) {

String strWithoutTags = str.replaceAll("<[^>]*>", "\n");

return strWithoutTags;

}

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

(празен ред)

Click

on this

link

for more info.

(празен ред)

This is

bold

text.

(празен ред)

Всичко е работи отлично, само, че имаме излишни празни редове. Можем ли да ги премахнем? Това ще е следващата ни стъпка.

Стъпка 3 – премахване на празните редове

Можем да премахнем излишните празни редове, като заменяме двоен празен ред "\n\n" с единичен празен ред "\n". Ето примерен метод, който извършва замяната:

private static String removeDoubleNewLines(String str) {

String result = str.replaceAll("\n\n", "\n");

return result;

}

Както, винаги, преди да продължим напред, тестваме метода дали работи коректно. Пробваме с текст, в който няма празни редове, а след това добавяме 2, 3, 4 и 5 празни реда, включително в началото и в края на текста.

Установяваме, че методът не работи коректно, когато има 4 празни реда един след друг. Например ако подадем като входни данни "ab\n\n\n\ncd", получаваме "ab\n\n\cd" вместо "ab\ncd". Този дефект се получава, защото replaceAll() намира и замества съвпаденията еднократно отляво надясно. Ако в резултат на заместване се появи отново търсеният низ, той бива прескочен.

Видяхте колко е полезно всеки метод да бъде тестван на момента, а не накрая да се чудим защо програмата не работи и да имаме 200 реда код, пълен с грешки. Ранното откриване на дефектите е много полезно и трябва да го правите винаги, когато е възможно. Ето поправения код:

private static String removeDoubleNewLines(String str) {

while (str.indexOf("\n\n") != -1) {

str = str.replaceAll("\n\n", "\n");

}

return str;

}

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

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

line = removeAllTags(line);

line = removeDoubleNewLines(line);

System.out.println(line);

}

Изглежда пак има празни редове. От къде ли идват? Вероятно, ако имаме ред, който съдържа само тагове, той ще създаде проблем. Следователно трябва да предвидим този случай. Добавяме следната проверка:

if (! line.equals("\n")) {

System.out.println(line);

}

Това ни спасява от повечето празни редове, но не и от всички.

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

private static String trimNewLines(String str) {

int start = 0;

while (start < str.length() && str.charAt(start)=='\n') {

start++;

}

int end = str.length()-1;

while (end >= 0 && str.charAt(end)=='\n') {

end--;

}

if (start > end) {

return "";

}

String trimmed = str.substring(start, end+1);

return trimmed;

}

Методът работи много просто: преминава отляво надясно пред входния символен низ и прескача всички символи за празен ред. След това преминава отдясно наляво и отново прескача всички символи за празен ред. Ако лявата и дясната позиция са се разминали, това означава, че низът или е празен, или съдържа само символи за празен ред. Тогава връщаме празен низ. Иначе връщаме всичко надясно от стартовата позиция и наляво от крайната позиция.

Както винаги, тестваме въпросния метод дали работи коректно с няколко примера, сред които празен низ, низ без нови редове, низ с нови редове отляво или отдясно или и от двете страни и низ само с нови редове. Убеждаваме се, че методът работи коректно.

Сега остава да модифицираме логиката на обработката на входния файл:

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

line = removeAllTags(line);

line = removeDoubleNewLines(line);

line = trimNewLines(line);

if (! line.equals("")) {

writer.println(line);

}

Този път тестваме и се убеждаваме, че всичко работи коректно.

Стъпка 4 – записване на резултата във файл

Остава ни да запишем резултата в изходен файл. За да записваме резултата в изходния файл ще използваме PrintStream. Тази стъпка е тривиална. Трябва да се съобразим само, че писането във файл може да предизвика изключение и затова трябва да променим леко логиката за обработка на грешки и за отварянето и затварянето на потоците за входния и изходния файл.

Ето какво се получава най-накрая като изход от програмата:

HtmlTagRemover.java

import java.io.*;

import java.util.*;

public class HtmlTagRemover {

private static final String INPUT_FILE_NAME = "Problem1.html";

private static final String OUTPUT_FILE_NAME = "Problem1.txt";

private static final String CHARSET = "windows-1251";

public static void main(String args[]) {

Scanner scanner = null;

PrintWriter writer = null;

try {

scanner = new Scanner(

new File(INPUT_FILE_NAME), CHARSET);

writer = new PrintWriter(OUTPUT_FILE_NAME, CHARSET);

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

line = removeAllTags(line);

line = removeDoubleNewLines(line);

line = trimNewLines(line);

if (! line.equals("")) {

writer.println(line);

}

} catch (IOException ioex) {

System.err.println("Can read or write file " + ioex);

} finally {

if (scanner != null) {

scanner.close();

}

if (writer != null) {

writer.close();

}

private static String removeAllTags(String str) {

String strWithoutTags = str.replaceAll("<[^>]*>", "\n");

return strWithoutTags;

}

private static String trimNewLines(String str) {

int start = 0;

while (start < str.length() && str.charAt(start)=='\n') {

start++;

}

int end = str.length()-1;

while (end >= 0 && str.charAt(end)=='\n') {

end--;

}

if (start > end) {

return "";

}

String trimmed = str.substring(start, end+1);

return trimmed;

}

private static String removeDoubleNewLines(String str) {

while (str.indexOf("\n\n") != -1) {

str = str.replaceAll("\n\n", "\n");

}

return str;

}

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

Досега тествахме отделните стъпки от решението на задачата. Чрез извършените тестове на отделните стъпки намаляваме възможността за грешки, но това не значи, че не трябва да тестваме цялото решение. Може да сме пропуснали нещо, нали?

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

Тестваме с нашия "сложен" пример. Всичко работи добре.

Задължително трябва да тестваме граничните случаи и да пуснем тест за производителност.

Започваме с празен файл. Изходът е коректен – празен файл.

Тестваме с файл, който съдържа само една дума "Hello" и не съдържа тагове. Резултатът е коректен – изходът съдържа само "Hello".

Тестваме с файл, който съдържа само тагове и не съдържа текст. Резултатът е отново коректен – празен файл.

Пробваме да сложим празни редове на най-невероятни места във входния файл. Пускаме следния тест:

Hello

I am here

I am not here

Изходът е следният:

Hello

am here

I am not

here

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

Добавяме следния код при обработката на поредния ред от входния файл:

line = line.trim();

Дефектът не се премахва. Пускаме дебъгера и забелязваме защо се получава така. Причината е, че отпечатваме в изходния файл символен низ със стойност "I\n am here" и така получаваме интервал след празен ред. Можем да поправим дефекта, като навсякъде от празен ред, следван от празно пространство (празен ред, интервал, табулация и т.н.). Ето поправката:

private static String removeDoubleNewLines(String str) {

str = str.replaceAll("\n\\s+", "\n");

return str;

}

Направихме метода хем по-кратък, хем по-коректен. Единствено трябва да му сменим името с някакво по-адекватно, примерно нещо като removeNewLinesWithWhiteSpace().

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

Остана един последен тест – за производителност. Лесно можем да създадем обемен входен файл. Дърпаме някой известен сайт, примерно http://java.sun.com/, взимаме му сорс кода и го копираме 1000 пъти. Получаваме достатъчно голям входен файл. В нашия случай се получи 44 MB файл с 947 000 реда. За обработката му бяха нужни под 10 секунди, което е напълно приемлива скорост.

Като надникнем в резултата, обаче, забелязваме много неприятен проблем. В него има части от тагове. По-точно виждаме следното:

<!--

var s_pageName="home page"

//-->

Бързо става ясно, че сме изпуснали един много интересен случай. В HTML може един таг да бъде затворен няколко реда след отварянето си, т.е. един таг може да е разположен на няколко последователни реда. Точно такъв е нашият случай: имаме таг с коментари, който съдържа JavaScript код. Ако програмата работеше коректно, щеше да отреже целия таг вместо да го запази в изходния файл.

Видяхте колко е полезно тестването и колко е важно. В някои сериозни фирми (като например Майкрософт) решение без тестове се счита за готово на 50%. Това означава, че ако пишете код 2 часа, трябва да отделите за тестване (ръчно или автоматизирано) поне още 2 часа! Само така можете да създадете качествен софтуер.

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

Как да оправим проблема с тагове на два реда?

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

Очевидно не можем да четем файла ред по ред. Можем ли да го четем символ по символ? Ако можем, как ще обработваме таговете? Хрумва ни, че ако четем файла символ по символ, можем във всеки един момент да знаем дали сме в таг или сме извън таг и ако сме извън таг, можем да печатаме всичко, което прочетем. Ще се получи нещо такова:

boolean inTag = false;

while (! <end of file is reached>) {

char ch = <read next character>

if (ch == '<') {

inTag = true;

} else if (ch == '>') {

inTag = false;

} else {

if (! inTag) {

print(ch);

}

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

boolean inTag = false;

StringBuilder buffer = new StringBuilder();

while (! <end of file is reached>) {

char ch = <read next character>

if (ch == '<') {

if (! inTag) {

printBuffer(buffer);

}

buffer.clear();

inTag = true;

} else if (ch == '>') {

inTag = false;

} else {

if (! inTag) {

buffer.append(ch);

}

printBuffer(buffer);

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

import java.io.FileInputStream;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

public class SimpleHtmlTagRemover {

private static final String INPUT_FILE_NAME = "Problem1.html";

private static final String OUTPUT_FILE_NAME = "Problem1.txt";

private static final String CHARSET = "windows-1251";

public static void main(String[] args) throws IOException {

InputStreamReader reader = new InputStreamReader(

new FileInputStream(INPUT_FILE_NAME), CHARSET);

PrintWriter writer = new PrintWriter(

OUTPUT_FILE_NAME, CHARSET);

try {

boolean inTag = false;

StringBuilder buffer = new StringBuilder();

while (true) {

int nextChar = reader.read();

if (nextChar == -1) {

// End of file reached

printBuffer(writer, buffer);

break;

}

char ch = (char) nextChar;

if (ch == '<') {

if (! inTag) {

printBuffer(writer, buffer);

}

buffer.setLength(0);

inTag = true;

} else if (ch == '>') {

inTag = false;

} else {

// We have other character (not "<" or ">")

if (! inTag) {

buffer.append(ch);

}

} finally {

reader.close();

writer.close();

}

private static void printBuffer(PrintWriter writer,

StringBuilder buffer) {

String str = buffer.toString();

String trimmed = str.trim();

String textOnly = removeNewLineWithWhiteSpace(trimmed);

if (textOnly.length() != 0) {

writer.println(textOnly);

}

private static String removeNewLineWithWhiteSpace(String str){

str = str.replaceAll("\n\\s+", "\n");

return str;

}

За простота сме пропуснали обработката на грешки при четене и писане във файл. При възникване на изключение го изхвърляме от главния метод и оставяме виртуалната машина да го отпечата в конзолата.

Входният файл чете символ по символ с класа InputStreamReader. За съжаление не можем да ползваме любимият ни клас Scanner, защото той няма метод за четене на единичен символ.

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

- Ако стигнем до края на файла, отпечатваме каквото има в буфера и алгоритъмът приключва.

- При срещане на символ "<" (начало на таг) първо отпечатваме буфера (ако установим, че преминаваме от текст към таг). След това зачистваме буфера и установяваме isTag = true.

- При срещане на символ ">" (край на таг) установяваме isTag = false. Това ще позволи следващите след тага символи да се натрупват в буфера.

- При срещане на някой друг символ (текст или празно пространство), той се добава към буфера, ако сме извън таг. Ако сме в таг, символът се игнорира.

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

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

Остава да тестваме задълбочено новото решение. Изпълняваме всички тестове, които проведохме за предното решение. Добавяме тест с тагове, които се разпростират на няколко реда. Отново тестваме за производителност със сайта на Java 1000 пъти. Уверяваме се, че и за него програмата работи коректно и дори е по-бърза.

Най-накрая вече сме готови за следващата задача.

Задача 2: Лабиринт

Даден е лабиринт, който се състои от N x N квадратчета, всяко от които може да е проходимо (0) или не (x). В едно от квадратчетата се намира нашият герой Минчо (*):

x	x	x	x	x	x
0	x	0	0	0	x
x	*	0	x	0	x
x	x	x	x	0	x
0	0	0	0	0	x
0	x	x	x	0	x

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

Входните данни се четат от текстов файл с име Problem2.in. На първия ред във файла стои числото N (2 < N < 100). На следващите N реда стоят по N символа, всеки от които е или "0" или "x" или "*". Изходът представлява едно число и трябва да се изведе във файла Problem2.out.

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

xxxxxx

0x000x

x*0x0x

xxxx0x

00000x

0xxx0x

Примерен изходен файл Problem2.out:

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

Имаме лабиринт и трябва да намерим най-краткия път в него. Това не е лесна задача и трябва доста да помислим или да сме прочели някъде как се решават такива задачи.

Нашият алгоритъм ще започва от работата си от началната точка, която ни е дадена. Знаем, че можем да се предвижваме в съседна клетка хоризонтално и вертикално, но не и по диагонал. Нашият алгоритъм трябва да обхожда лабиринта по някакъв начин, за да намери в него най-късия път. Как да обхождаме клетките в лабиринта?

Един възможен начин за обхождане е следният: стартираме от началната клетка. Преместваме се в съседна клетка на текущата (която е проходима), след това в съседна клетка на нея (която е проходима и все още непосетена), след това в съседна на последната посетена (която е проходима е все още непосетена) и така продължаваме рекурсивно напред, докато или стигнем изход от лабиринта, или стигнем до място, от където няма продължение (няма съседна клетка, която е свободна и непосетена). В този момент се връщаме от рекурсията (към предходната клетка, от която сме стигнали текущата) и посещаваме друга клетка на предходната клетка. Ако няма продължение, се връщаме още назад. Описаният рекурсивен процес представлява обхождане на лабиринта в дълбочина (спомнете си главата "Рекурсия").

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

Ако при връщане от рекурсията отбелязваме като свободна клетката, която напускаме, ще позволим до една и съща клетка да стигаме многократно, идвайки по различен път. Пълното рекурсивно обхождане на лабиринта на практика ще намери всички възможни пътища от началната клетка до всяка други клетка. От всички тези пътища можем да вземем най-късия път до клетка на границата на лабиринта (изход) и така ще намерим решение на задачата.

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

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

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

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

Изглежда имаме правилна идея за решаване на задачата. Да преминем напред и да помислим за структурите от данни.

Какви структури от данни да използваме?

Първо трябва да преценим как да съхраняваме лабиринта. Съвсем естествено е да ползваме матрица от символи, точно като тази на картинката. Ще считаме, че една клетка е проходима и можем да влезем в нея, ако съдържа символ, различен от символа 'x'. Може да пазим лабиринта и в матрица с числа или булеви стойности, но разликата не е съществена. Матрицата от символи е удобна за отпечатване, а това ще ни помогне докато дебъгваме. Няма много възможности за избор. Ще съхраняваме лабиринта в матрица от символи.

След това трябва да решим в каква структура да запомняме обходените до момента клетки по време на рекурсията (текущия път). На нас ни трябва винаги последната обходена клетка. Това ни навежда на мисълта за структура, която спазва "последен влязъл, пръв излязъл", тоест стек. Можем да ползваме Stack<Cell>, където Cell е клас, съдържащ координатите на една клетка (номер на ред и номер на колона).

Остава да помислим в какво да запомняме намерените пътища, за да можем да извлечем накрая най-късия от тях. Ако се замислим малко, не е нужно да пазим всички пътища. Достатъчно е да помним текущия път и най-късият път за момента. Дори не е необходимо да пазим най-късия път за момента, ами само неговата дължина. Всеки път, когато намерим път до изход от лабиринта, можем да взимаме неговата дължина и ако тя е по-малка от най-късата дължина за момента, да я запомняме.

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

Да помислим за ефективността

Нека да проверим идеята си от следна точка на ефективността? Какво правим ние? Намираме всички възможни пътища и от тях взимаме най-късия. Няма спор, че алгоритъмът ще работи, но ако лабиринтът стане много голям, дали ще работи бързо?

За да отговорим на този въпрос, трябва да помислим колко за пътищата. Ако вземем празен лабиринт, то на всяка стъпка на рекурсията ще имаме средно по 3 свободни продължения (като изключим клетката, от която идваме).

Така, ако имаме примерно лабиринт 10 на 10, пътят може да стане дълъг до 100 клетки и по време на обхождането на всяка стъпка ще имаме по 3 съседни клетки. Изглежда броят пътища е число от порядъка на 3 на степен 100. Очевидно алгоритъмът ще приспи компютъра много бързо.

Намерихме сериозен проблем на алгоритъма. Той ще работи много бавно, дори при малки лабиринти, а при големи изобщо няма да работи!

Да измислим нова идея

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

Нека започнем от началната клетка и да обходим всички нейни съседни и да ги маркираме като обходени. За всяка обходена клетка ще запомняме едно число, което е равно на броя клетки, през които сме преминали, за да достигнем до нея (дължина на пътя от началната клетка до текущата).

За началната клетка дължината на пътя е 0. За нейните съседи дължината на пътя трябва да е 1, защото с 1 движение можем да ги достигнем от началната клетка. За съседните клетки на съседите на началната клетка дължината на пътя е 2. Можем да продължим да разсъждаваме по този начин и ще стигнем до следния алгоритъм:

1. Записваме дължина на пътя 0 за началната клетка. Отбелязваме я като посетена.

2. За всяка съседна клетка на началната отбелязваме, че пътят до нея е с дължина 1. Отбелязваме тези клетки като посетени.

3. За всяка клетка, която е съседна на клетка с дължина 1 и не е посетена, записваме, че е дължината на пътя до нея е 2. Отбелязваме въпросните клетки като посетени.

4. Продължавайки аналогично, на N-тата стъпка намираме всички непосетени все още клетки, които са на разстояние N премествания от началната клетка и ги отбелязваме като посетени.

Можем да визуализираме процеса по следния начин (взимаме друг лабиринт, за да покажем по-добра идеята):

Стъпка 0 – отбелязваме разстоянието от началната клетка до нея самата с 0 (за удобство на картинката отбелязваме свободните клетки с "-"):

x	x	x	x	x	x
-	x	-	-	-	x
x	0	-	x	-	x
x	-	-	x	-	x
x	-	-	-	-	x
-	x	x	x	-	x

Стъпка 1 – отбелязваме с 1 всички проходими съседи на клетки със стойност 0:

x	x	x	x	x	x
-	x	-	-	-	x
x	0	1	x	-	x
x	1	-	x	-	x
x	-	-	-	-	x
-	x	x	x	-	x

Стъпка 2 – отбелязваме с 2 всички проходими съседи на клетки със стойност 1:

x	x	x	x	x	x
-	x	2	-	-	x
x	0	1	x	-	x
x	1	2	x	-	x
x	2	-	-	-	x
-	x	x	x	-	x

Стъпка 3 – отбелязваме с 3 всички проходими съседи на клетки със стойност 2:

x	x	x	x	x	x
-	x	2	3	-	x
x	0	1	x	-	x
x	1	2	x	-	x
x	2	3	-	-	x
-	x	x	x	-	x

Продължавайки така, е ведно, че в един момент или ще достигнем клетка на границата на лабиринта (т.е. изход) или ще установим, че такава не е достижима.

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

Понеже никога не посещаваме повече от веднъж една и съща клетка, броят стъпки, които извършва този алгоритъм, не би трябвало да е голям. Примерно, ако имаме лабиринт с размери 100 на 100, той ще има 10 000 клетки, всяка от които ще посетим най-много веднъж и за всяка посетена клетка ще проверим всеки неин съсед дали е свободен, т.е. ще извършим по 4 проверки. В крайна сметка ще извършим най-много 40 000 проверки и ще обходим най-много 10 000 клетки. Общо ще направим около 50 000 операции. Това означава, че алгоритъмът ще работи мигновено.

Проверяване коректността на новия алгоритъм

Изглежда този път нямаме проблем с производителността. Имаме бърз алгоритъм.

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

След това пробваме с лабиринт без изход. Изглежда алгоритъмът завършва, но не намира изход. Следователно работи коректно.

Пробваме още 2-3 примера и се убеждаваме, че този алгоритъм винаги намира най-краткия път до някой изход и винаги работи бързо, защото обхожда всяка клетка от лабиринта най-много веднъж.

Какви структури от данни да използваме?

С новия алгоритъм обхождаме последователно всички съседни клетки на началната клетка. Можем да ги сложим в някаква структура данни, примерно масив или по-добре списък, че в масива не можем да добавяме.

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

Така получаваме списък₀, който съдържа началната клетка, списък₁, който съдържа проходимите съседни на началната клетка, след това списък₂, който съдържа проходимите съседи на списък₁ и т.н. На n-тата стъпка получаваме списък_n, който съдържа всички клетки, достижими за точно n стъпки, т.е. клетките на разстояние n от стартовата клетка.

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

Можем да достигнем и до по-генерален извод: Клетките се обработват в реда на постъпване: когато свършват клетките от стъпка k, чак тогава се обработват клетките от стъпка k+1, а едва след тях – клетките от стъпка k+2 и т.н. Процесът прилича на опашка – по-рано постъпилите клетки се обработват по-рано.

За да реализираме алгоритъма, можем да използваме опашка от клетки. За целта трябва да дефинираме клас клетка (Cell), който да съдържа координатите на дадена клетка (ред и колона). Можем да пазим в матрицата за всяка клетка на какво разстояние се намира от началната клетка или -1, ако разстоянието още не е пресметнато.

Ако се замислим още малко, разстоянието от стартовата клетка може да се пази в самата клетка (в класа Cell) вместо да се прави специална матрица за разстоянията. Така ще се спести памет.

Вече имаме яснота за структурите данни. Остава да реализираме алгоритъма – стъпка по стъпка.

Стъпка 1 – класът Cell

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

private class Cell {

int row;

int col;

int distance;

}

Може да му добавим и конструктор за удобство:

public Cell(int row, int col, int distance) {

this.row = row;

this.col = col;

this.distance = distance;

}

Стъпка 2 – прочитане на входния файл

Ще четем входния файл ред по ред чрез познатия ни клас Scanner. На всеки ред ще анализираме символите и ще ги записваме в матрица от символи. При достигане на символ "*" ще запомним координатите му в инстанция на класа Cell, за да знаем от къде да започнем търсенето на най-краткия път за излизане от лабиринта.

Можем да дефинираме клас Maze и в него да пазим матрицата на лабиринта и стартовата клетка:

Maze.java

public class Maze {

private char[][] maze;

private int size;

private Cell startCell = null;

public void readFromFile(String fileName)

throws FileNotFoundException {

Scanner scanner = new Scanner(new File(fileName));

try {

// Read maze size

this.size = scanner.nextInt();

scanner.nextLine();

// Create the maze

this.maze = new char[this.size][this.size];

// Read the maze cells from the file

for (int row=0; row<this.size; row++) {

String line = scanner.nextLine();

for (int col = 0; col < line.length(); col++) {

char ch = line.charAt(col);

maze[row][col] = ch;

if (ch == '*') {

this.startCell = new Cell(row, col, 0);

}

} finally {

scanner.close();

}

Вече имаме класа Maze и подходящо представяне на данните от входния файл. За да сме сигурни, че написаното дотук е вярно трябва да тестваме. Можем да проверим дали матрицата е вярно попълнена, като я отпечатаме на конзолата. Друг вариант е да се разгледат стойностите на полетата от класа Maze през дебъгера на Eclipse.

След като тестваме написаното дотук продължаваме със следващата стъпка, а именно търсенето на най-краткия път.

Стъпка 3 – намиране на най-къс път

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

public int findShortestPath(Cell startCell) {

// Queue for traversing the cells in the maze

Queue<Cell> visitedCells = new LinkedList<Cell>();

visitCell(visitedCells, startCell.row, startCell.col, 0);

// Perform Breath-First-Search (BFS)

while (! visitedCells.isEmpty()) {

Cell currentCell = visitedCells.remove();

int row = currentCell.row;

int col = currentCell.col;

int distance = currentCell.distance;

if ((row == 0) || (row == size-1)

|| (col == 0) || (col == size-1)) {

// We are at the maze border

return distance + 1;

}

visitCell(visitedCells, row, col + 1, distance + 1);

visitCell(visitedCells, row, col - 1, distance + 1);

visitCell(visitedCells, row + 1, col, distance + 1);

visitCell(visitedCells, row - 1, col, distance + 1);

}

// We didn't reach any cell at the maze border -> no path

return -1;

}

private void visitCell(Queue<Cell> visitedCells,

int row, int col, int distance) {

if (maze[row][col] != 'x') {

// Cell is free. Visit it

maze[row][col] = 'x';

Cell cell = new Cell(row, col, distance);

visitedCells.add(cell);

}

Проверка след стъпка 3

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

Нека да пробваме случая, в който имаме дължина нула на квадратната матрица във входния файл:

Exception in thread "main" java.lang.NullPointerException

at Maze.findShortestPath(Maze.java:59)

at Maze.main(Maze.java:104)

Допуснали сме грешка. Проблемът е в това, че при създаване на обект от класа Maze, променливата, в която ще помним началната клетка, се инициализира с null. Ако лабиринтът няма клетки (дължина 0) или липсва стартовата клетка, би трябвало програмата да връща резултат -1, а не да дава изключение. Можем да добавим проверка в началото на метода findShortestPath():

public int findShortestPath(Cell startCell) {

if (startCell == null) {

// Start cell is missing -> no path

return -1;

}

…

В останалите случаи изглежда, че алгоритъмът работи.

Стъпка 4 – записване на резултата във файл

Остава да запишем резултата от метода FindShortestWay() в изходния файл. Това е тривиална задача:

public void saveResult(String fileName, int result)

throws IOException {

FileWriter writer = new FileWriter(fileName);

try {

writer.write("" + result);

} finally {

writer.close();

}

Ето как изглежда пълният код на решението на задачата:

Maze.java

import java.io.*;

import java.util.*;

public class Maze {

private static final String INPUT_FILE_NAME = "Problem2.in";

private static final String OUTPUT_FILE_NAME = "Problem2.out";

private class Cell {

int row;

int col;

int distance;

public Cell(int row, int col, int distance) {

this.row = row;

this.col = col;

this.distance = distance;

}

private char[][] maze;

private int size;

private Cell startCell = null;

public void readFromFile(String fileName)

throws FileNotFoundException {

Scanner scanner = new Scanner(new File(fileName));

try {

// Read maze size

this.size = scanner.nextInt();

scanner.nextLine();

// Create the maze

this.maze = new char[this.size][this.size];

// Read the maze cells from the file

for (int row=0; row<this.size; row++) {

String line = scanner.nextLine();

for (int col = 0; col < line.length(); col++) {

char ch = line.charAt(col);

maze[row][col] = ch;

if (ch == '*') {

this.startCell = new Cell(row, col, 0);

}

} finally {

scanner.close();

}

public int findShortestPath(Cell startCell) {

if (startCell == null) {

// Start cell is missing -> no path

return -1;

}

// Queue for traversing the cells in the maze

Queue<Cell> visitedCells = new LinkedList<Cell>();

visitCell(visitedCells, startCell.row, startCell.col, 0);

// Perform Breath-First-Search (BFS)

while (! visitedCells.isEmpty()) {

Cell currentCell = visitedCells.remove();

int row = currentCell.row;

int col = currentCell.col;

int distance = currentCell.distance;

if ((row == 0) || (row == size-1)

|| (col == 0) || (col == size-1)) {

// We are at the maze border

return distance + 1;

}

visitCell(visitedCells, row, col + 1, distance + 1);

visitCell(visitedCells, row, col - 1, distance + 1);

visitCell(visitedCells, row + 1, col, distance + 1);

visitCell(visitedCells, row - 1, col, distance + 1);

}

// We didn't reach any cell at the maze border -> no path

return -1;

}

private void visitCell(Queue<Cell> visitedCells,

int row, int col, int distance) {

if (maze[row][col] != 'x') {

// Cell is free. Visit it

maze[row][col] = 'x';

Cell cell = new Cell(row, col, distance);

visitedCells.add(cell);

}

public void saveResult(String fileName, int result)

throws IOException {

FileWriter writer = new FileWriter(fileName);

try {

writer.write("" + result);

} finally {

writer.close();

}

public static void main(String[] args) throws IOException {

Maze maze = new Maze();

maze.readFromFile(INPUT_FILE_NAME);

int pathLength = maze.findShortestPath(maze.startCell);

maze.saveResult(OUTPUT_FILE_NAME, pathLength);

}

Тестване на решението на задачата

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

Остава да тестваме с голям лабиринт, например 1000 на 1000. Можем да си направим такъв лабиринт много лесно – с copy/paste. Изпълняваме теста и се убеждаваме, че програмата работи коректно за големия тест и работи изключително бързо – не се усеща каквото и да е забавяне.

При тестването трябва да се опитваме по всякакъв начин да счупим нашето решение. Пускаме още няколко по-трудни примера (примерно лабиринт с проходими клетки във формата на спирала). Можем да сложим голям лабиринт с много пътища, но без изход. Можем да сложим и каквото още се сетим.

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

Задача 3: Магазин за авточасти

Фирма планира създаване на система за управление на магазин за авточасти. Една част може да се използва при различни модели автомобили и има следните характеристики:

Код, наименование, категория (за ходовата част, гуми и джанти, за двигателя, аксесоари и т.н.), покупна цена, продажна цена, списък с модели автомобили, за които може да се използва (даден автомобил се описва с марка, модел и година на производство, примерно BMW 316i, 1992), фирма-производител.

Фирмите-производители се описват с наименование, държава, адрес, телефон и факс.

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

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

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

Кои са тези съществителни, които ни интересуват? Имаме магазин, авточасти, автомобили и фирми-производители. Трябва да създадем клас описващ магазин. Той ще се казва Shop. Другите класове съответно са Part, Car и Manufacturer. В условието на задачата има и други съществителни, например код на една част или година на производство на дадена кола. За тези съществителни няма да създаваме отделни класове, защото можем да използваме примитивните типове в Java. Това означава, че в класа Part ще има примерно поле code от тип String.

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

Каква структури от данни да използване, за да опишем връзката между два класа?

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

По-удобен е ArrayList<T>. Той притежава предимствата на масив, а освен това е с променлива дължина и с него лесно се реализира въвеждане и изтриване на елементи.

Засега изглежда, че ArrayList<T> е най-подходящ. За да се убедим ще разгледаме още няколко структури от данни. Например хеш-таблица – не е удобна в този случаи, понеже структурата "части" не от типа ключ-стойност. Тя би била подходяща, ако в магазина всяка част има уникален номер (например баркод). Тогава ще можем да ги търсим по този уникален номер. Структури като стек и опашка са неуместни.

Структурата "множество" и нейните имплементации TreeSet и HashSet се ползват, когато имаме уникалност по даден ключ. Може би на места, ще е добра да ползваме тази структура, за да избегнем повторения. Трябва да имаме предвид, че ползването на HashSet<T> изисква да имаме методи hashCode() и equals(), дефинирани коректно в типа T.

В крайна сметка избираме да ползваме ArrayList<T> и HashSet<T>.

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

Сега остава да си изясним въпроса от къде да започнем написването на задачата. Ако започнем да пишем класа Shop, ще се нуждаем от класа Part. Това ни подсеща, че трябва да започнем от клас, който не зависи от другите. Ще разделим написването на всеки клас на подзадача, като ще започнем от независещите от другите класове:

- Клас описващ автомобил – Car

- Клас описващ производител на части – Manufacturer

- Клас описващ част за автомобили – Part

- Клас за магазина – Shop

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

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

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

Стъпка 1: класът Car

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

Car.java

public class Car {

private String brand;

private String model;

private String productionYear;

public Car(String brand, String model, String productionYear){

this.brand = brand;

this.model = model;

this.productionYear = productionYear;

}

@Override

public String toString() {

return "<" + this.brand + "," + this.model + ","

+ this.productionYear + ">";

}

Стъпка 2: класът Manufacturer

Следва да реализираме дефиницията на класа Manufacturer, който описва производителя на дадена част. Той ще има пет полета – име, държава, адрес, телефонен номер и факс. Класът ще има и два метода – getName() и стандартния метод toString(). Първият ще връща низ с името за даден производител, а вторият – цялата информация за него.

Manufacturer.java

public class Manufacturer {

private String name;

private String country;

private String address;

private String phoneNumber;

private String fax;

public Manufacturer(String name,String country,

String address, String phoneNumber, String fax) {

this.name = name;

this.country = country;

this.address = address;

this.phoneNumber = phoneNumber;

this.fax = fax;

}

public String getName(){

return this.name;

}

@Override

public String toString(){

return this.name + " <"+this.country+ "," + this.address +

"," + this.phoneNumber + "," + this.fax + ">";

}

Стъпка 3: класът Part

Сега трябва да дефинираме класа Part. Дефиницията му ще включва следните полета – име, код, категория, списък с коли, с които може да се използва дадената част, начална и крайна цена и производител. Тук вече ще използваме избраната от нас структура от данни ArrayList<T>. В случая ще бъде ArrayList<Car>. Полето показващо производителя на частта ще бъде от тип Manufacturer, защото задача изисква да се помни допълнителна информация за производителя. Ако се искаше да се знае само името на производителя (както случая с класа Car) нямаше да има нужда от този клас. Щяхме да имаме поле от тип String. За полето, което описва категорията на частта ще използваме enum:

PartCategory.java

public enum PartCategory {

ENGINE, TIRES, EXHAUST, SUSPENSION, BRAKES

}

Ще създадем и метод, който ще отпечатва на конзолата полетата. Той ще се казва printParts(PrintStream output). Нужен ни е метод за добавяне на кола (обект от тип Car) в списъка с колите (в HashSet<Car>). Той ще се казва addSupportedCar(Car car). Ето го и кода на класа Part:

Part.java

import java.util.HashSet;

public class Part {

private String name;

private String code;

private PartCategory category;

private HashSet<Car> supportedCars;

private double buyPrice;

private double sellPrice;

private Manufacturer manufacturer;

public Part(String name, double buyPrice, double sellPrice,

Manufacturer manufacturer, String code,

PartCategory category) {

this.name = name;

this.buyPrice = buyPrice;

this.sellPrice = sellPrice;

this.manufacturer = manufacturer;

this.code = code;

this.category = category;

this.supportedCars = new HashSet<Car>();

}

public void аddSupportedCar(Car car) {

this.supportedCars.add(car);

}

@Override

public String toString() {

StringBuilder result = new StringBuilder();

result.append("Part: " + this.name + "\n");

result.append("-code: " + this.code + "\n");

result.append("-category: " + this.category + "\n");

result.append("-buyPrice: " + this.buyPrice + "\n");

result.append("-sellPrice: " + this.sellPrice + "\n");

result.append("-manufacturer: " + this.manufacturer +"\n");

result.append("---Supported cars---" + "\n");

for (Car car:this.supportedCars) {

result.append(car);

result.append("\n");

}

result.append("----------------------\n");

return result.toString();

}

Понеже ползваме HashSet<Car> е необходимо да дефинираме методите hashCode() и equals(). За по-лесно ползваме функцията в Eclipse за автоматично генериране на код, достъпна от контекстното меню (Source à Generate hashCode() и equals()…):

Получаваме следния автоматично генериран код:

@Override

public int hashCode() {

final int prime = 31;

int result = 1;

result = prime * result + ((brand == null) ? 0 :

brand.hashCode());

result = prime * result + ((model == null) ? 0 :

model.hashCode());

result = prime * result + ((productionYear == null) ? 0 :

productionYear.hashCode());

return result;

}

@Override

public boolean equals(Object obj) {

if (this == obj)

return true;

if (obj == null)

return false;

if (getClass() != obj.getClass())

return false;

Car other = (Car) obj;

if (brand == null) {

if (other.brand != null)

return false;

} else if (!brand.equals(other.brand))

return false;

if (model == null) {

if (other.model != null)

return false;

} else if (!model.equals(other.model))

return false;

if (productionYear == null) {

if (other.productionYear != null)

return false;

} else if (!productionYear.equals(other.productionYear))

return false;

return true;

}

Стъпка 4: класът Shop

Вече имаме всички нужни класове за създаване на класа Shop. Той ще има две полета – име и списък от части, които се продават. Списъкът ще бъде ArrayList<Part>. Ще си добавим и два метода addPart(Part part) и toString(). Чрез първия ще добавяме нова част, а чрез втория ще отпечатаме името на магазина и частите в него. Ето примерна реализация:

Shop.java

import java.util.ArrayList;

public class Shop {

private String name;

private ArrayList<Part> parts;

public Shop(String name){

this.name = name;

parts = new ArrayList<Part>();

}

public void addPart(Part part){

parts.add(part);

}

@Override

public String toString() {

StringBuilder result = new StringBuilder();

result.append("Shop: " + this.name + "\n\n");

for(Part part : parts) {

result.append(part);

result.append("\n");

}

return result.toString();

}

Стъпка 5: класът ТestShop

Създадохме всички нужни класове. Остава да създадем още един, с който да демонстрираме използването на всички останали класове. Той ще се казва ТestShop. В main() метода ще създадем два производителя и няколко коли. Ще ги добавим към две части. Частите ще добавим към обект от тип Shop. Накрая ще отпечатаме всичко на конзолата. Ето примерния код:

TestShop.java

public class TestShop {

public static void main(String args[]) {

Manufacturer bmw = new Manufacturer("BWM",

"Germany", "Bavaria", "665544", "876666");

Manufacturer lada = new Manufacturer("Lada",

"Russia", "Moscow", "653443", "893321");

Car bmw316i = new Car("BMW", "316i", "1994");

Car ladaSamara = new Car("Lada", "Samara", "1987");

Car mazdaMX5 = new Car("Mazda", "MX5", "1999");

Car mercedesC500 = new Car("Mercedes", "C500", "2008");

Car trabant = new Car("Trabant", "super", "1966");

Car opelAstra = new Car("Opel", "Astra", "1997");

Part cheapPart = new Part("Tires 165/50/13", 302.36,

345.58, lada, "T332", PartCategory.TIRES);

cheapPart.аddSupportedCar(ladaSamara);

cheapPart.аddSupportedCar(trabant);

Part expensivePart = new Part("BMW Engine Oil",

633.17, 670.0, bmw, "Oil431", PartCategory.ENGINE);

expensivePart.аddSupportedCar(bmw316i);

expensivePart.аddSupportedCar(mazdaMX5);

expensivePart.аddSupportedCar(mercedesC500);

expensivePart.аddSupportedCar(opelAstra);

Shop newShop = new Shop("Tunning shop");

newShop.addPart(cheapPart);

newShop.addPart(expensivePart);

System.out.println(newShop);

}

Това е резултатът от изпълнението на нашата програма:

Shop: Tunning shop

Part: Tires 165/50/13

-code: T332

-category: TIRES

-buyPrice: 302.36

-sellPrice: 345.58

-manufacturer: Lada <Russia,Moscow,653443,893321>

---Supported cars---

<Lada,Samara,1987>

<Trabant,super,1966>

----------------------

Part: BMW Engine Oil

-code: Oil431

-category: ENGINE

-buyPrice: 633.17

-sellPrice: 670.0

-manufacturer: BWM <Germany,Bavaria,665544,876666>

---Supported cars---

<Opel,Astra,1997>

<BMW,316i,1994>

<Mazda,MX5,1999>

<Mercedes,C500,2008>

----------------------

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

Накрая остава да тестваме нашата задача. Всъщност ние направихме това с класа TestShop. Това обаче не означава, че сме изтествали напълно нашата задача. Трябва да се проверят граничните случаи, например когато някои от списъците са празни. Да променим малко кода в main() метода, за да пуснем задачата с празен списък:

TestShop.java

public class TestShop {

public static void main(String args[]) {

Manufacturer bmw = new Manufacturer("BWM",

"Germany", "Bavaria", "665544", "876666");

Manufacturer lada = new Manufacturer("Lada",

"Russia", "Moscow", "653443", "893321");

Car bmw316i = new Car("BMW", "316i", "1994");

Car ladaSamara = new Car("Lada", "Samara", "1987");

Car mazdaMX5 = new Car("Mazda", "MX5", "1999");

Car mercedesC500 = new Car("Mercedes", "C500", "2008");

Car trabant = new Car("Trabant", "super", "1966");

Car opelAstra = new Car("Opel", "Astra", "1997");

Part cheapPart = new Part("Tires 165/50/13", 302.36,

345.58, lada, "T332", PartCategory.TIRES);

Part expensivePart = new Part("BMW Engine Oil",

633.17, 670.0, bmw, "Oil431", PartCategory.ENGINE);

expensivePart.аddSupportedCar(bmw316i);

expensivePart.аddSupportedCar(mazdaMX5);

expensivePart.аddSupportedCar(mercedesC500);

expensivePart.аddSupportedCar(opelAstra);

Shop newShop = new Shop("Tunning shop");

newShop.addPart(cheapPart);

newShop.addPart(expensivePart);

System.out.println(newShop);

}

Резултатът от този тест е следният:

Shop: Tunning shop

Part: Tires 165/50/13

-code: T332

-category: TIRES

-buyPrice: 302.36

-sellPrice: 345.58

-manufacturer: Lada <Russia,Moscow,653443,893321>

---Supported cars---

----------------------

Part: BMW Engine Oil

-code: Oil431

-category: ENGINE

-buyPrice: 633.17

-sellPrice: 670.0

-manufacturer: BWM <Germany,Bavaria,665544,876666>

---Supported cars---

<Opel,Astra,1997>

<BMW,316i,1994>

<Mazda,MX5,1999>

<Mercedes,C500,2008>

----------------------

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

Упражнения

1. Даден входен файл mails.txt, който съдържа имена на потребители и техните email адреси. Всеки ред от файла изглежда така:

Има изискване за имейл адресите – <username> може да е последователност от латински букви (a-z, A-Z) и долна черна (_), < host> е последователност от малки латински букви (a-z), а <domain> има ограничение от 2 до 4 малки латински букви (a-z). Да се напише програма, която намира валидните email адреси и ги записва заедно с имената на потребителите в изходен файл validMails.txt.

2. Даден е лабиринт, който се състои от N x N квадратчета, всяко от които може да е проходимо (0) или не (x):

x	x	x	0	x	x
0	x	0	0	0
0	*	0	x	0	0
x	x	x	x	0	x
0	0	0	0	0	x
0	x	0	x	x	0

В едно от квадратчетата се намира отново нашият герой Минчо (*). Две квадратчета са съседни, ако имат обща стена. Минчо може на една стъпка да преминава от едно проходимо квадратче в съседно на него проходимо квадратче. Напишете програма, която по даден лабиринт отпечатва броя на възможните изходи от лабиринта.

Входните данни се четат от текстов файл с име Problem.in. На първия ред във файла стои числото N (2 < N < 1000). На следващите N реда стоят по N символа, всеки от които е или "0" или "x" или "*". Изходът представлява едно число и трябва да се изведе във файла Problem.out.

3. Даден е лабиринт, който се състои от N x N квадратчета, всяко от които може да е проходимо или не. Проходимите клетки съдържат малка латинска буква между "а" и "z", а непроходимите – '#'. В едно от квадратчетата се намира Минчо. То е означено с "*".

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

a	#	#	k	m	#
z	#	a	d	a	#
a	*	m	#	#	#
#	d	#	#	#	#
r	i	f	i	d	#
#	d	#	d	#	t

Входните данни се четат от текстов файл с име Problem.in. На първия ред във файла стои числото N (2 < N < 10). На следващите N реда стоят по N символа, всеки от които е или "0" или "#" или "*". Изходът представлява едно число и трябва да се изведе във файла Problem.out.

4. Фирма планира създаване на система за управление на звукозаписна компания. Звукозаписната компания има име, адрес, собственик и изпълнители. Всеки изпълнител има име, псевдоним и създадени албуми. Албумите се описват с име, жанр, година на издаване, брой на продадените копия и списък от песни. Песните, от своя страна се описват с име и времетраене. Да се проектира съвкупност от класове с връзки между тях, които моделират данните за звукозаписната компания. Да се реализира тестов клас, който демонстрира работата на всички останали класове.

5. Фирма планира създаване на система за управление на компания за недвижими имоти. Компанията има име, собственик, Булстат, служители и разполага със списък от имоти за продажба. Служители се описват с име, длъжност и стаж. Компанията продава няколко вида имоти – апартаменти, къщи, незастроени площи и магазини. Всички те се характеризират с площ, цена на квадратен метър и местоположение. За някои от тях има допълнителна информация. За апартамента има данни за номер на етажа, дали в блока има асансьор и дали е обзаведен. За къщите се зная квадратните метри на застроена част и на незастроената (двора), на колко етажа е и дали е обзаведена. Да се проектира съвкупност от класове с връзки между тях, които моделират данните за компанията. Да се реализира тестов клас, който демонстрира работата на всички останали класове.

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

1. Задачата е подобна на първата от примерния изпит. Отново трябва да чете ред по ред от входния файл и чрез подходящ регулярен израз да извличате имейл адресите.

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

Ivan Dimitrov [email protected]

Svetlana Todorova [email protected]

Kiril Kalchev [email protected]

Todor Ivanov todo*[email protected]

Ivelina Petrova ivel&[email protected]

Petar Petrov pesho<5.mail.bg

Изходен файл:

Ivan Dimitrov [email protected]

Svetlana Todorova [email protected]

Kiril Kalchev [email protected]

Тествайте внимателно решението си преди да преминете към следващата задача.

2. Възможните изходи от лабиринта са всички клетки, които се намират на границата на лабиринта и са достижими от стартовата клетка. Задачата се решава с дребна модификация на решението на задачата за лабиринта.

3. Задачата е изглежда подобна на предната, но се искат всички възможни пътища до изхода. Можете да направите рекурсивно търсене с връщане назад (backtracking) и да натрупвате в StringBuilder буквите до изхода, за да образувате думите, които трябва да се отпечатат. При големи лабиринти задачата няма решение (защото се използва пълно изчерпване и броят пътища до някой от изходите може да е ужасно голям).

4. Трябва да напишете нужните класове – MusicCompany, Singer, Album, Song. Помислете за връзките между класовете и какви структури данни да ползвате за тях. За отпечатването припокривайте метода toString() от java.lang.Object. Тествайте всички методи и граничните случаи.

5. Класовете, които трябва да напишете са EstateCompany, Employee, Apartment, House, Shop и Area. Забележете, че класовете, които ще описват недвижимите имоти имат някои еднакви характеристики. Изнесете тези характеристики в базов отделен клас Estate. Създайте метод toString(), който да изписва на конзолата данните от този клас. Пренапишете метода за класовете, които наследяват този клас, за да показва цялата информация за всеки клас. Тествайте всички методи и граничните случаи.

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

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

Коментирай

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

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

Съдържание

Какво структури от данни да ползваме?

Проверка след стъпка 3

Каква структури от данни да използване, за да опишем връзката между два класа?

Стъпка 1: класът Car

Стъпка 2: класът Manufacturer

Стъпка 3: класът Part

Стъпка 4: класът Shop

Стъпка 5: класът ТestShop

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

Коментирай