Глава 25. Практически задачи за изпит по програмиране – тема 2
В тази тема...
В настоящата тема ще разгледаме условията и ще предложим решения на няколко практически алгоритмични задачи от примерен изпит по програмиране. При решаването на задачите ще се придържаме към съветите от темата "Как да решаваме задачи по програмиране" и ще онагледим прилагането им в практиката.
Съдържание
- Мисловни карти
- В тази тема...
- Задача 1: Броене на думи в текст
- Задача 2: Матрица с прости числа
- Задача 3: Аритметичен израз
- Упражнения
- Решения и упътвания
- Дискусионен форум
Мисловни карти
Задача 1: Броене на думи в текст
Напишете програма, която преброява думите в даден текст, въведен от конзолата. Програмата трябва да извежда общия брой думи, броя думи, изписани изцяло с главни букви и броя думи, изписани изцяло с малки букви. Ако дадена дума се среща няколко пъти на различни места в текста, всяко срещане се брои като отделна дума. За разделител между думите се счита всеки символ, който не е буква.
Примерен вход:
|
Добре дошли на вашия първи изпит по програмиране! Можете ли да измислите и напишете решение на тази задача? УСПЕХ! |
Примерен изход:
|
Общо думи: 19 Думи с главни букви: 1 Думи с малки букви: 16 |
Намиране на подходяща идея за решение
Интуитивно ни идва наум, че можем да решим задачата, като разделим текста на отделни думи и след това преброим тези, които ни интересуват.
Тази идея очевидно е вярна, но е прекалено обща и не ни дава конкретен метод за решаването на проблема. Нека се опитаме да я конкретизираме и да проверим дали е възможно чрез нея да реализираме алгоритъм, който да доведе до решение на задачата. Може да се окаже, че реализацията е трудна или сложността на решението е прекалено голяма и нашата програма няма да може да завърши своето изпълнение, дори и с помощта на съвременните мощни компютри. Ако това се случи, ще се наложи да потърсим друго решение на задачата.
Разбиване на задачата на подзадачи
Полезен подход при решаването на алгоритмични задачи е да се опитаме да разбием задачите на подзадачи, които са по-лесно и бързо решими. Нека се опитаме да дефинираме стъпките, които са ни необходими, за решаването на проблема.
Най-напред трябва да разделим текста на отделни думи. Това, само по себе си, не е проста стъпка, но е първата ни крачка към разделянето на проблема на по-малки, макар и все още сложни подзадачи.
Следва преброяване на интересуващите ни думи. Това е втората голяма подзадача, която трябва да решим. Да разгледаме двата проблема по отделно и да се опитаме да ги раздробим на още по-прости задачи.
Как да разделим текста на отделни думи?
За да разделим текста на отделни думи, първо трябва да намерим начин да ги идентифицираме. В условието е казано, че за разделител се счита всеки символ, който не е буква. Следователно първо трябва да идентифицираме разделителите и след това да ги използваме за разделянето на текста на думи.
Ето, че се появиха още две подзадачи – намиране на разделителите в текста и разделяне на текста на думи спрямо разделителите. Решения на тези подзадачи можем да реализираме директно. Това беше и нашата първоначална цел – да разбием сложните задачи на по-малки и лесни подзадачи.
За намиране на разделителите е достатъчно да обходим всички символи и да извлечем тези, които не са букви.
След като имаме разделителите, можем да реализираме разделянето на текста на думи чрез метода Split(…) на класа String.
Как да броим думите?
Да предположим, че вече имаме списък с всички думи от текста. Искаме да намерим броя на всички думи на тези, изписани само с главни букви, и на тези, изписани само с малки букви.
За целта можем да обходим всяка дума от списъка и да проверим дали отговаря на някое от условията, които ни интересуват. На всяка стъпка увеличаваме броя на всички думи. Проверяваме дали текущата дума е изписана само с главни букви и, ако това е така, увеличаваме броя на думите с главни букви. Аналогично правим проверка и дали думата е изписана само с малки букви.
Така се появяват още две подзадачи – проверка дали дума е изписана само с главни букви и проверка дали е изписана само с малки букви? Те изглеждат доста лесни. Може би дори е възможно класът string да ни предоставя наготово такава функционалност. Проверяваме, но се оказва, че не е така. Все пак забелязваме, че има методи, които ни позволяват да преобразуваме символен низ в такъв, съставен само от главни или само от малки букви. Това може да ни помогне.
За да проверим дали една дума е съставена само от главни букви, е достатъчно да сравним думата с низа, който се получава, след като я преобразуваме в дума, съставена само от главни букви. Ако са еднакви, значи резултатът от проверката е истина. Аналогична е и проверката за малките букви.
Проверка на идеята
Изглежда, че идеята ни е добра. Разбихме задачата на подзадачи и знаем как да решим всяка една от тях. Дали да не преминем към имплементацията? Пропуснахме ли нещо?
Не трябваше ли да проверим идеята, разписвайки няколко примера на хартия? Вероятно ще намерим нещо, което сме пропуснали? Можем да започнем с примера от условието:
|
Добре дошли на вашия първи изпит по програмиране! Можете ли да измислите и напишете решение на тази задача? УСПЕХ! |
Разделителите ще са: интервали, ? и !. За думите получаваме: Добре, дошли, на, вашия, първи, изпит, по, програмиране, Можете, ли, да, измислите, и, напишете, решение, на, тази, задача, УСПЕХ.
Преброяваме думите и получаваме коректен резултат. Изглежда идеята е добра и работи. Можем да пристъпим към реализацията. За целта ще имплементираме алгоритъма стъпка по стъпка, като на всяка стъпка ще реализираме по една подзадача.
Да помислим за структурите от данни
Задачата е проста и няма нужда от кой знае какви сложни структури от данни.
За разделителите в текста можем да използваме типa char. При намирането им ще генерираме един списък с всички символи, които определим за разделители. Можем да използваме char[] или List<char>. В случая ще предпочетем втория вариант.
За думите от текста можем да използваме масив от низове string[] или List<string>.
Да помислим за ефективността
Има ли изисквания за ефективност? Колко най-дълъг може да е текстът? Тъй като текстът се въвежда от конзолата, той едва ли ще е много дълъг. Никой няма да въведе 1 MB текст от конзолата. Можем да приемем, че ефективността на решението в случая не е застрашена.
Да разпишем на хартия решението на задачата
Много добра стратегия е да се разписва решението на задачата на хартия преди да се започне писането му на компютър. Това помага за откриване отрано на проблеми в идеята или реализацията. Писането на самото решение после става доста по-бързо, защото имаме нещо разписано, а и мозъкът ни е асимилирал добре задачата и нейното решение.
Стъпка 1 – Намиране на разделителите в текста
Ще дефинираме метод, който извлича от текста всички символи, които не са букви, и ги връща в масив от символи, който след това можем да използваме за разделяне на текста на отделни думи:
|
private static char[] ExtractSeparators(string text) { List<char> separators = new List<char>(); foreach (char character in text) { // If the character is not a letter, // by our definition it is a separator if (!char.IsLetter(character)) { separators.Add(character); } } return separators.ToArray(); } |
Използваме списък от символи List<char>, където добавяме всички символи, които по нашата дефиниция са разделители в текста.
В цикъл обхождаме всеки един от символите в текста. С помощта на метода IsLetter(…) на примитивния тип char определяме дали текущия символ е буква и, ако не е, го добавяме към разделителите.
Накрая връщаме масив, съдържащ разделителите.
Изпробване на метода ExtractSeparators(…)
Преди да продължим нататък е редно да изпробваме дали намирането на разделителите работи коректно. За целта, ще си напишем два нови метода. Първият – TestExtractSeparators(), който ще тества извикването на метода ExtractSeparators(…), а вторият – GetTestData(), който ще ни връща няколко различни текста, с които ще можем да тестваме нашето решение:
|
private static void TestExtractSeparators() { List<string> testData = GetTestData(); foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Еnvironment.NewLine, testCase); Console.WriteLine("Result:"); foreach (char separator in ExtractSeparators(testCase)) { Console.Write("{0} ", separator); } Console.WriteLine(); } }
private static List<string> GetTestData() { List<string> testData = new List<string>(); testData.Add(String.Format("{0}{1}", "This is wonderful!!! All separators like ", "these ,.(? and these /* are recognized. It works.")); testData.Add("SingleWord"); testData.Add(string.Empty); testData.Add(">?!>?#@?"); return testData; }
static void Main() { string text = "This is wonderful!!! All separators like " + "these ,.(? and these /* are recognized. It works."; char[] separators = ExtractSeparators(text); Console.WriteLine(separators); }
|
Стартираме програмата и проверяваме дали разделителите са намерени коректно. Резултатът от първият тест е следният:
|
!!! ,.(? /* |
Изпробваме метода и в някои от граничните случаи – текст, състоящ се от една дума без разделители; текст, съставен само от разделители; празен низ. Всички тези тестове сме добавили в нашия метод GetTestData(). Изглежда, че методът работи и можем да продължим към реализацията на следващата стъпка.
Стъпка 2 – Разделяне на текста на думи
За разделянето на текста на отделни думи ще използваме разделителите и с помощта на метода Split(…) на класа string ще извършим разделянето.
Ето как изглежда нашият метод:
|
private static string[] ExtractWords(string text) { char[] separators = ExtractSeparators(text); List<string> extractedWords = new List<string>(); foreach(string extractedWord in text.Split(separators)) { // if the word is not empty add it to the // extracted words array if (!string.IsNullOrEmpty(extractedWord)) { extractedWords.Add(extractedWord); } } return extractedWords.ToArray(); } |
Преди да преминем към следващата стъпка остава да проверим дали методът работи коректно. За целта ще преизползваме вече написания метод за тестови данни GetTestData() и ще изтестваме новия метод ExtractWords(…):
|
private static void TestExtractWords() { List<string> testData = GetTestData(); foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Environment.NewLine, testCase); Console.WriteLine("Result:"); foreach(string word in ExtractWords(testCase)) { Console.Write("{0} ", word); } } } |
Резултатът от първия тест:
|
This is wonderful All separators like these and these are recognized IT works |
Стъпка 3 – Определяне дали дума е изписана изцяло с главни или изцяло с малки букви
Вече имаме идея как да имплементираме тези проверки и можем директно да реализираме методите:
|
private static bool IsUpperCase(string word) { bool result = word.Equals(word.ToUpper()); return result; }
private static bool IsLowerCase(string word) { bool result = word.Equals(word.ToLower()); return result; } |
Изпробваме ги, подавайки им думи, съдържащи само главни, само малки и такива, съдържащи главни и малки букви. Резултатите са коректни.
Стъпка 4 – Преброяване на думите
Вече можем да пристъпим към решаването на проблема – преброяването на думите. Трябва само да обходим списъка с думите и в зависимост каква е думата да увеличим съответните броячи, след което да отпечатаме резултата:
|
private static void CountWords(string[] words) { int allUpperCaseWordsCount = 0; int allLowerCaseWordsCount = 0; foreach (string word in words) { if (IsUpperCase(word)) { allUpperCaseWordsCount++; } else if (IsLowerCase(word)) { allLowerCaseWordsCount++; } }
Console.WriteLine("Total words count:{0}", words.Length); Console.WriteLine("Upper case words count:{0}", allUpperCaseWordsCount); Console.WriteLine("Lower case words count:{0}", allLowerCaseWordsCount); } |
Нека проверим дали броенето работи коректно. Ще си напишем още една тестова функция, използвайки тестовите данни от метода GetTestData() и вече написания и изтестван от нас метод ExtractWords(…):
|
private static void TestCountWords() { List<string> testData = GetTestData(); foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Environment.NewLine, testCase); Console.WriteLine("Result:"); CountWords(ExtractWords(testCase)); } } |
Стартираме приложението и получаваме верен резултат:
|
Total words count: 13 Upper case words count: 1 Lower case words count: 10 |
Проверяваме резултатите и в граничните случаи, когато списъкът съдържа думи само с главни или само с малки букви както и, когато списъкът е празен.
Стъпка 5 – Вход от конзолата
Остава да реализираме и последната стъпка, даваща възможност на потребителя да въвежда текст:
|
private static string ReadText() { Console.WriteLine("Enter text:"); return Console.ReadLine(); } |
Стъпка 6 – Сглобяване на всички части в едно цяло
След като сме решили всички подзадачи, можем да пристъпим към пълното решаване на проблема. Остава да добавим Main(…) метод, в който да съединим отделните парчета:
|
static void Main() { string text = ReadText(); string[] words = ExtractWords(text); CountWords(words); } |
Тестване на решението
Докато писахме решението, написахме методи за тестване на всеки един метод, като постепенно интегрирахме методите един с друг. Така в момента сме сигурни, че те работят добре заедно, не сме изпуснали нещо и нямаме метод, който да прави нещо, което не ни е нужно или да дава грешни резултати.
Ако имаме желание да тестваме решението с още данни, достатъчно е само да допишем още данни в метода GetTestData(…). Ако искаме, дори можем да модифицираме кода на метода GetTestData(…), така че да чете данните за тестване от външен източник – например текстов файл.
Ето как изглежда кодът на цялостното решение:
| WordsCounter.cs |
|
using System; using System.Collections.Generic;
public class WordsCounter { static void Main() { string text = ReadText(); string[] words = ExtractWords(text); CountWords(words); }
private static string ReadText() { Console.WriteLine("Enter text:"); return Console.ReadLine(); }
private static char[] ExtractSeparators(string text) { List<char> separators = new List<char>(); foreach (char character in text) { // If the character is not a letter, by our // definition it is a separator if (!char.IsLetter(character)) { separators.Add(character); } } return separators.ToArray(); }
private static string[] ExtractWords(string text) { char[] separators = ExtractSeparators(text); List<string> extractedWords = new List<string>(); foreach (string extractedWord in text.Split(separators.ToArray())) { // if the word is not empty add it to the extracted // words if (!string.IsNullOrEmpty(extractedWord)) { extractedWords.Add(extractedWord); } }
return extractedWords.ToArray(); }
private static bool IsUpperCase(string word) { bool result = word.Equals(word.ToUpper()); return result; }
private static bool IsLowerCase(string word) { bool result = word.Equals(word. ToLower()); return result; }
private static void CountWords(string[] words) { int allUpperCaseWordsCount = 0; int allLowerCaseWordsCount = 0;
foreach (string word in words) { if (IsUpperCase(word)) { allUpperCaseWordsCount++; } else if (IsLowerCase(word)) { allLowerCaseWordsCount++; } }
Console.WriteLine("Total words count:{0}", words.Length)); Console.WriteLine("Upper case words count: {0}", allUpperCaseWordsCount)); Console.WriteLine("Lower case words count: {0}", allLowerCaseWordsCount)); }
private static List<string> GetTestData() { List<string> testData = new List<string>(); testData.Add(String.Format("{0}{1}", "This is wonderful!!! All separators like ", "these ,.(? and these /* are recognized. IT works.")); testData.Add("SingleWord"); testData.Add(string.Empty); testData.Add(">?!>?#@?"); return testData; }
private static void TestExtractSeparators() { List<string> testData = GetTestData(); foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Environment.NewLine, testCase); Console.WriteLine("Result:"); foreach (char separator in ExtractSeparators(testCase)) { Console.Write("{0} ", separator); } Console.WriteLine(); } }
private static void TestExtractWords() { List<string> testData = GetTestData();
foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Environment.NewLine, testCase); Console.WriteLine("Result:"); foreach (string word in ExtractWords(testCase)) { Console.Write("{0} ", word); } } }
private static void TestCountWords() { List<string> testData = GetTestData(); foreach (string testCase in testData) { Console.WriteLine("Test Case:{0}{1}", Environment.NewLine, testCase); Console.WriteLine("Result:"); CountWords(ExtractWords(testCase)); } } }
|
Дискусия за производителността
Тъй като въпросът за производителността в тази задача не е явно поставен, само ще дадем идея как бихме могли да реагираме, ако евентуално се окаже, че нашият алгоритъм е бавен. Понеже разделянето на текста по разделящите символи предполага, че целият текст трябва да бъде прочетен в паметта и думите, получени при разделянето също трябва да се запишат в паметта, то програмата ще консумира голямо количество памет, ако входният текст е голям. Например, ако входът е 200 MB текст, програмата ще изразходва най-малко 800 MB памет, тъй като всяка дума се пази два пъти по 2 байта за всеки символ.
Ако искаме да избегнем консумацията на голямо количество памет, трябва да не пазим всички думи едновременно в паметта. Можем да измислим друг алгоритъм: сканираме текста символ по символ и натрупваме буквите в някакъв буфер (например StringBuilder). Ако срещнем в даден момент разделител, то в буфера би трябвало да стои поредната дума. Можем да я анализираме дали е с малки или главни букви и да зачистим буфера. Това можем да повтаряме до достигане на края на файла. Изглежда по-ефективно, нали?
За по-ефективно проверяване за главни/малки букви можем да направим цикъл по буквите и проверка на всяка буква. Така ще си спестим преобразуването в горен/долен регистър, което заделя излишно памет за всяка проверена дума, която след това се освобождава, и в крайна сметка това отнема процесорно време.
Очевидно второто решение е по-ефективно. Възниква въпросът дали трябва, след като сме написали първото решение, да го изхвърлим и да напишем съвсем друго. Всичко зависи от изискванията за ефективност. В условието на задачата няма предпоставки да смятаме, че ще ни подадат като вход стотици мегабайти. Следователно сегашното решение, макар и не оптимално, също е коректно и ще ни свърши работа.
Задача 2: Матрица с прости числа
Напишете програма, която прочита от стандартния вход цяло положително число N и отпечатва първите N2 прости числа в квадратна матрица с размери N x N. Запълването на матрицата трябва да става по редове от първия към последния и отляво надясно.
Забележка: Едно естествено число наричаме просто, ако няма други делители освен 1 и себе си. Числото 1 не се счита за просто.
Примерен вход:
|
2 3 4 |
Примерен изход:
|
2 3 2 3 5 2 3 5 7 5 7 7 11 13 11 13 17 19 17 19 23 23 29 31 37 41 43 47 53 |
Намиране на подходяща идея за решение
Можем да решим задачата като с помощта на два вложени цикъла отпечатаме редовете и колоните на резултатната матрица. За всеки неин елемент ще извличаме и отпечатваме поредното просто число.
Разбиване на задачата на подзадачи
Трябва да решим поне две подзадачи – намиране на поредното просто число и отпечатване на матрицата. Отпечатването на матрицата можем да направим директно, но за намирането на поредното просто число ще трябва да помислим малко. Може би най-интуитивният начин, който ни идва наум за това, е, започвайки от предходното намерено просто число, да проверяваме всяко следващо дали е просто и в момента, в който това се окаже истина, да го върнем като резултат. Така на хоризонта се появява още една подзадача – проверка дали дадено число е просто.
Проверка на идеята
Нашата идея за решение на задачата директно получава търсения в условието резултат. Разписваме 1-2 примера на хартия и се убеждаваме, че работи.
Да помислим за структурите от данни
В тази задача се ползва една единствена структура от данни – матрицата. Естествено е да използваме двумерен масив.
Да помислим за ефективността
Тъй като изходът е на конзолата, при особено големи матрици (например 1000 x 1000) резултатът няма да може да се визуализира добре. Това означава, че задачата трябва да се реши за разумно големи матрици, но не прекалено големи, например за N ≤ 200. При нашия алгоритъм при N=200 ще трябва да намерим първите 40 000 прости числа, което не би трябвало да е бавно.
Стъпка 1 – Проверка дали дадено число е просто
За проверката дали дадено число е просто можем да дефинираме метод IsPrime(…). За целта е достатъчно да проверим, че то не се дели без остатък на никое от предхождащите го числа. За да сме още по-точни, достатъчно е да проверим, че то не се дели на никое от числата между 2 и корен квадратен от числото. Това е така, защото, ако числото p има делител х, то р = х.у и поне едно от числата х и у ще е по-малко или равно на корен квадратен от р. Следва реализация на метода:
|
private static bool IsPrime (int number) { int maxDivider = (int)Math.Sqrt(number); for (int divider = 2; divider <= maxDivider; divider++) { if (number % divider == 0) { return false; } } return true; } |
Сложността на горния пример е O(Sqrt(number)), защото правим най-много корен квадратен от number проверки. Тази сложност ще ни свърши работа в тази задача, но дали не може този метод да се оптимизира още малко? Ако се замислим, всяко второ число е четно, а всички четни числа се делят на 2. Тогава горният метод безсмислено ще проверява всички четни числа до корен квадратен от number в случай, че числото, което проверяваме, е нечетно. Как можем да премахнем тези ненужни проверки? Още в началото на метода можем да проверим дали числото се дели на 2 и после да организираме основния цикъл така, че да прескача проверката на четните делители. Новата сложност, която ще получим е O(Sqrt(number) / 2).
Това е пример как можем да оптимизираме вече написан метод.
|
private static bool IsPrime(int number) { if (number == 2) { return true; } if (number % 2 == 0) { return false; }
int maxDivider = (int)Math.Sqrt(number); for (int divider = 3; divider <= maxDivider; divider += 2) { if (number % divider == 0) { return false; } } return true; } |
Както виждаме, кодът на метода се е изменил минимално спрямо неоптимизираната версия.
Можем да се уверим, че и двата метода работят коректно, подавайки им последователно различни числа, някои от които прости, и проверявайки върнатия резултат.
|
|
Преди да оптимизирате даден метод трябва да го тествате, за да сте сигурни, че работи. |
Причината е, че след оптимизирането, кодът най-често става по-голям, по-труден за четене и съответно по-труден за дебъгване в случай, че не работи правилно.
|
|
Бъдете внимателни, когато оптимизирате код. Не изпадайте в крайности и не правете ненужни оптимизации, които правят кода минимално по-бърз, но за сметка на това драстично влошават четливостта и затрудняват поддръжката на кода. |
![clip_image001[1]](https://introprogramming.info/wp-content/uploads/2011/07/clip_image001113.gif "clip_image001[1]"){kind=small}
Стъпка 2 – Намиране на следващото просто число
За намирането на следващото просто число можем да дефинираме метод, който приема като параметър дадено число, и връща като резултат първото, по-голямо от него, просто число. За проверката дали числото е просто ще използваме методa от предишната стъпка. Следва реализацията на метода:
|
private static int FindNextPrime(int startNumber) { int number = startNumber; while(!IsPrime(number)) { number++; } return number; } |
Отново трябва да изпробваме метода, подавайки му няколко числа и проверявайки дали резултатът е правилен.
Стъпка 3 – Отпечатване на матрицата
След като дефинирахме горните методи, вече сме готови да отпечатаме и цялата матрица:
|
private static void PrintMatrix(int dimension) { int lastPrime = 1; for (int row = 0; row < dimension; row++) { for (int col = 0; col < dimension; col++) { int nextPrime = FindNextPrime(lastPrime + 1); Console.Write("{0,4}", nextPrime); lastPrime = nextPrime; } Console.WriteLine(); } } |
Стъпка 4 – Вход от конзолата
Остава да добавим възможност за прочитане на N от конзолата:
|
static void Main() { int n = ReadInput(); PrintMatrix(n); }
private static int ReadInput() { Console.Write ("N = "); string input = Console.ReadLine(); int n = int.Parse(input); return n; } |
Тестване на решението
След като всичко е готово, можем да пристъпим към проверка на решението. За целта можем да намерим например първите 25 прости числа и да проверим изхода на програмата за стойности на N от 1 до 5. Не трябва да пропускаме случая за N=1, тъй като това е граничен случай и вероятността за допусната грешка при него е значително по-голяма.
В конкретния случай, при условие че сме тествали добре методите на всяка стъпка, можем да се ограничим с примерите от условието на задачата. Ето как изглежда изходът от програмата за стойности на N съответно 1, 2, 3 и 4:
|
2 2 3 2 3 5 2 3 5 7 5 7 7 11 13 11 13 17 19 17 19 23 23 29 31 37 41 43 47 53 |
Можем да се уверим, че решението на задачата работи сравнително бързо и за по-големи стойности на N. Примерно при N=200 не се усеща някакво забавяне.
Следва пълната реализация на решението:
|
PrimesMatrix.cs |
|
using System;
public class PrimesMatrix { static void Main() { int n = ReadInput(); PrintMatrix(n); }
private static int ReadInput() { Console.Write("N = "); string input = Console.ReadLine(); int n = int.Parse(input); return n; }
private static bool IsPrime(int number) { if (number == 2) { return true; } if (number % 2 == 0) { return false; }
int maxDivider = (int)Math.Sqrt(number); for (int divider = 3; divider <= maxDivider; divider += 2) { if (number % divider == 0) { return false; } } return true; }
private static int FindNextPrime(int startNumber) { int number = startNumber; while(!IsPrime(number)) { number++; } return number; }
private static void PrintMatrix(int dimension) { int lastPrime = 1; for (int row = 0; row < dimension; row++) { for (int col = 0; col < dimension; col++) { int nextPrime = FindNextPrime(lastPrime + 1); Console.Write("{0,4}", nextPrime); lastPrime = nextPrime; } Console.WriteLine(); } } } |
Дискусия за производителността
Трябва да отбележим, че посоченото решение не търси простите числа по най-ефективния начин. Въпреки това, с оглед яснотата на изложението и поради очаквания малък размер на матрицата, можем да използваме този алгоритъм без да имаме проблеми с производителността.
Ако трябва да подобрим производителността, можем да намерим първите N2 числа с "решето на Ератостен" (Sieve of Eratosthenes) без да проверяваме дали всяко число е просто до намиране на N2 прости числа.
Задача 3: Аритметичен израз
Напишете програма, която изчислява стойността на прост аритметичен израз, съставен от цели числа без знак и аритметичните операции "+" и "-". Между числата няма интервали.
Изразът се задава във формат:
|
<число><операция>...<число> |
Примерен вход:
|
1+2-7+2-1+28+2+3-37+22 |
Примерен изход:
|
15 |
Намиране на подходяща идея за решение
За решаване на задачата можем да използваме факта, че формата на израза е стриктен и ни гарантира, че имаме последователност от число, операция, отново число и т.н.
Така можем да извлечем всички числа участващи в израза, след това всички оператори и накрая да изчислим стойността на израза, комбинирайки числата с операторите.
Проверка на идеята
Наистина, ако вземем лист и химикал и изпробваме подхода с няколко израза, получаваме верен резултат. Първоначално резултатът е равен на първото число, а на всяка следващата стъпка добавяме или изваждаме следващото число в зависимост от текущия оператор.
Структури от данни и ефективност
Задачата е прекалено проста, за да използваме сложни структури от данни. Числата и знаците можем да пазим в масив. За проблеми с ефективността не може да говорим, тъй като всеки знак и всяко число се обработват точно по веднъж, т.е. имаме линейна сложност на алгоритъма.
Разбиване на задачата на подзадачи
След като сме се убедили, че идеята работи можем да пристъпим към разбиването на задачата на подзадачи. Първата подзадача, която ще трябва да решим, е извличането на числата от израза. Втората ще е извличането на операторите. Накрая ще трябва да изчислим стойността на целия израз, използвайки числата и операторите, които сме намерили.
Стъпка 1 – Извличане на числата
За извличане на числата е необходимо да разделим израза, като за разделители използваме операторите. Това можем да направим лесно чрез метода Split(…) на класа String. След това ще трябва да преобразуваме получения масив от символни низове в масив от цели числа:
|
private static int[] ExtractNumbers(string expression) { string[] splitResult = expression.Split('+', '-');
List<int> numbers = new List<int>(); foreach (string number in splitResult) { numbers.Add(int.Parse(number)); } return numbers.ToArray(); } |
За преобразуването на символните низове в цели числа използваме метода Parse(…) на класа Int32. Той приема като параметър символен низ и връща като резултат целочислената стойност, представена от него.
Защо използваме масив за съхранение на числата? Не можем ли да използваме например свързан списък или динамичен масив? Разбира се, че можем, но в случая е нужно единствено да съхраним числата и след това да ги обходим при изчисляването на резултата. Ето защо масивът ни е напълно достатъчен.
Преди да преминем към следващата стъпка проверяваме дали извличането на числата работи коректно:
|
static void Main() { int[] numbers = ExtractNumbers("1+2-7+2-1+28"); foreach (int x in numbers) { Console.Write("{0} ", x); } } |
Резултатът е точно такъв, какъвто трябва да бъде:
|
1 2 7 2 1 28 |
Проверяваме и граничния случай, когато изразът се състои само от едно число без оператори, и се уверяваме, че и той се обработва добре.
Стъпка 2 – Извличане на операторите
Извличането на операторите можем да направим, като последователно обходим низа и проверим всяка буквичка дали отговаря на операциите от условието:
|
private static char[] ExtractOperators(string expression) { string operatorCharacters = "+-"; List<char> operators = new List<char>(); foreach (char c in expression) { if(operatorCharacters.Contains(c)) { operators.Add(c); } } return operators.ToArray(); } |
Следва проверка дали методът работи коректно:
|
static void Main() { char[] operators = ExtractOperators("1+2-7+2-1+28"); foreach(char oper in operators) { Console.Write("{0} ", oper); } } |
Изходът от изпълнението на програмата е правилен:
|
+ - + - + |
Правим проверка и за граничния случай, когато изразът не съдържа оператори, а се състои само от едно число. В този случай получаваме празен низ, което е очакваното поведение.
Стъпка 3 – Изчисляване на стойността на израза
За изчисляване на стойността на израза можем да използваме факта, че числата винаги са с едно повече от операторите и с помощта на един цикъл да изчислим стойността на израза при условие, че са ни дадени списъците с числата и операторите:
|
private static int CalculateExpression(int[] numbers, char[] operators) { int result = numbers[0]; for (int i = 1; i < numbers.Length; i++) { char operation = operators[i - 1]; int nextNumber = numbers[i]; if (operation == '+') { result += nextNumber; } else if (operation == '-') { result -= nextNumber; } } return result; } |
Проверяваме работата на метода:
|
static void Main() { // Expression: 1 + 2 - 3 + 4 int[] numbers = new int[] { 1, 2, 3, 4 }; char[] operators = new char[] { '+', '-', '+' }; int result = CalculateExpression(numbers, operators); // Expected result is 4 Console.WriteLine(result); } |
Резултатът е коректен:
|
4 |
Стъпка 4 – Вход от конзолата
Ще трябва да дадем възможност на потребителя да въвежда израз:
|
private static string ReadExpression() { Console.WriteLine("Enter expression:"); string expression = Console.ReadLine(); return expression; } |
Стъпка 5 – Сглобяване на всички части в едно цяло
Остава ни само да накараме всичко да работи заедно:
|
static void Main() { string expression = ReadExpression();
int[] numbers = ExtractNumbers(expression); char[] operators = ExtractOperators(expression);
int result = CalculateExpression(numbers, operators); Console.WriteLine("{0} = {1}", expression, result); } |
Тестване на решението
Можем да използваме примера от условието на задачата при тестването на решението. Получаваме коректен резултат:
|
Enter expression: 1+2-7+2-1+28+2+3-37+22 1+2-7+2-1+28+2+3-37+22 = 15 |
Трябва да направим още няколко теста с различни примери, които да включват и случая, когато изразът се състои само от едно число, за да се уверим, че решението ни работи.
Можем да тестваме и празен низ. Не е много ясно дали това е коректен вход, но можем да го предвидим за всеки случай. Освен това не е ясно какво става, ако някой въведе интервали в израза, например вместо "2+3" въведе "2 + 3". Хубаво е да предвидим тези ситуации.
Друго, което забравихме да тестваме, е какво става при число, което не се събира в типа int. Какво ще стане, ако ни бъде подаден изразът "11111111111111111111111111111+222222222222222222222222222222"?
Дребни поправки и повторно тестване
Във всички случаи, когато изразът е невалиден, ще се получи някакво изключение (най-вероятно System.FormatException). Достатъчно е да прихванем изключенията и при настъпване на изключение да съобщим, че е въведен грешен израз. Следва пълната реализация на решението след тази корекция:
|
SimpleExpressionEvaluator.cs |
|
using System; using System.Collections.Generic; using System.Linq; using System.Text;
public class SimpleExpressionEvaluator { private static int[] ExtractNumbers(string expression) { string[] splitResult = expression.Split('+', '-'); List<int> numbers = new List<int>(); foreach (string number in splitResult) { numbers.Add(int.Parse(number)); } return numbers.ToArray(); }
private static char[] ExtractOperators(string expression) { string operationsCharacters = "+-"; List<char> operators = new List<char>(); foreach (char c in expression) { if (operationsCharacters.Contains(c)) { operators.Add(c); } } return operators.ToArray(); }
private static int CalculateExpression(int[] numbers, char[] operators) { int result = numbers[0]; for (int i = 1; i < numbers.Length; i++) { char operation = operators[i - 1]; int nextNumber = numbers[i]; if (operation == '+') { result += nextNumber; } else if (operation == '-') { result -= nextNumber; } } return result; }
private static string ReadExpression() { Console.WriteLine("Enter expression:"); string expression = Console.ReadLine(); return expression; }
static void Main() { try { string expression = ReadExpression();
int[] numbers = ExtractNumbers(expression); char[] operators = ExtractOperators(expression);
int result = CalculateExpression(numbers, operators); Console.WriteLine("{0} = {1}", expression, result); } catch (Exception ex) { Console.WriteLine("Invalid expression!"); } } } |
Упражнения
1. Решете задачата "броене на думи в текст", използвайки само един буфер за четене (StringBuilder). Промени ли се сложността на алгоритъмът ви?
2. Реализирайте по-ефективно решение на задачата "матрица с прости числа" като търсите простите числа с "решето на Ератостен": http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
3. Добавете поддръжка на операциите умножение и целочислено деление в задачата "аритметичен израз". Имайте предвид, че те са с по-висок приоритет от събирането и изваждането!
4. Добавете поддръжка на реални числа, не само цели.
5. Добавете поддръжка на скоби в задачата "аритметичен израз".
6. Напишете програма, която валидира аритметичен израз. Например "2*(2.25+5.25)-17/3" е валиден израз, докато "*232*-25+(33+а" е невалиден.
Решения и упътвания
1. Можете да четете входния файл символ по символ. Ако поредният символ е буква, го добавяте към буфера, а ако е разделител, анализирате буфера (той съдържа поредната дума) и след това зачиствате буфера. Когато свърши входния файл, трябва да анализирате последната дума, която е в буфера (ако файлът не завършва с разделител).
2. Помислете първо колко прости числа ви трябват. След това помислете до каква стойност трябва да пускате "решето на Ератостен", за да ви стигнат простите числа за запълване на матрицата. Можете опитно да измислите някаква формула.
3. Достатъчно е да изпълните първо всички умножения и деления, а след тях всички събирания. Помислихте ли за деление на нула?
4. Работата с реални числа можете да осигурите като разширите използването на символа "." и заместите int с double.
5. Можем да направим следното: намираме първата затваряща скоба и търсим наляво съответната й отваряща скоба. Това, което е в скобите, е аритметичен израз без скоби, за който вече имаме алгоритъм за изчисление на стойността му. Можем да го заместим със стойността му. Повтаряме това за следващите скоби докато скобите свършат. Накрая ще имаме израз без скоби.
Например, ако имаме "2*((3+5)*(4-7*2))", ще заместим "(3+5)" с 8, след това "(4-7*2)" с -10. Накрая ще заместим (8*-10) с -80 и ще сметнем 2*-80, за да получим резултата -160. Трябва да предвидим аритметични операции с отрицателни числа, т.е. да позволяваме числата да имат знак.
Съществува и друг алгоритъм. Използва се стек и преобразуване на израза до "обратен полски запис". Можете да потърсите в Интернет за фразата "postfix notation" и за "shunting yard algorithm".
6. Ако изчислявате израза с обратен полски запис, можете да допълните алгоритъма, така че да проверява за валидност на израза. Добавете следните правила: когато очаквате число, а се появи нещо друго, изразът е невалиден. Когато очаквате аритметична операция, а се появи нещо друго, изразът е невалиден. Когато скобите не си съответстват, ще препълните стека или ще останете накрая с недоизпразнен стек. Помислете за специални случаи, например "-1", "-(2+4)" и др.
Дискусионен форум
Коментирайте книгата и задачите в нея във: форума на софтуерната академия.
Коментирай
Трябва да сте влезнали, за да коментирате.