Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.)

Жанр: Информационные системы и технологии

Просмотров: 1394


Задача 11: в строке все слова, которые начинаются и заканчиваются одной буквой, выделить квадратными скобками.

Пример: из строки «шалаш широкий и просторный» должно получиться

«[шалаш] широкий [и] просторный».

Размышления:

1.  Очевидно, что      задача представима  в          виде    следующей последовательности действий:

1.1.      Ввод данных

1.2.      Обработка данных

1.3.      Вывод результата

2.  Так  же  логично  предположить,  что  пользователь  вводит  строку  с клавиатуры. Т. е. в качестве входных данных у нас есть строка.

3.  Из предыдущего примера ясно, что, если мы научимся находить начало слова и его длину, это решит проблему нахождения слова.

3.1.      Операции  нахождения  начала  и  длины  слова  так  же  полностью

аналогичны тем, которые были в предыдущем примере.

3.2.      Теперь  мы  умеем  находить  слово  (потому  что  умеем  находить начало слова и его длину). Поэтому вернемся к изначальному заданию:

выделить слова, которые начинаются и заканчиваются одной и той же буквой. Очевидно, что выделение слова происходит по условию. Возникает вопрос – как реализовать это условие? Если у нас есть слово в

виде строки, то первый символ в нем имеет индекс 0, а последний – Length - 1. Поэтому в виде кода условие необходимости выделения слова будет выглядеть следующим образом:

public static bool needMarkWord(string word) {

if (word[0] == word[word.Length - 1]) {

return true;

} else {

return false;

}

}

3.3.      Как видно из этого кода, нам нужно получить слово в виде строки.

Получение слова из строки полностью аналогично примеру из предыдущей задачи.

3.4.      Что бы верно реализовать алгоритм, вспомним, что по сути строка

является одномерным массивом символов. Поэтому вставка в нее ведет к изменению индексации (в случае выделения слова вставляются  квадратные  скобки).  Поэтому  очевидно,  что  в результате обработки строки строка будет изменяться. И для обработки строки необходима только сама строка. Поэтому в функции обработки будет только один строковый параметр с ключевым словом ref.

3.5.      Псевдокодовый         алгоритм        решения          задачи будет   выглядеть следующим образом:

Для каждого символа строки

НачалоЦикла

Если текущийСимвол – начало слова, то

НачалоЕсли

Объявить длину слова

Найти длину слова, которое начинается в текущем символе Объявить переменную, в которой будет храниться текущее слово Получить слово в виде строки.

Если слово необходимо выделить, то

НачалоЕсли Удалить слово Выделить слово

Вставить выделенное слово на позицию старого Увеличить текущую позицию на длину выделенного слова ОкончаниеЕсли

ОкончаниеЕсли

ОкончаниеЦикла

 

3.6.      Обратите внимание на увеличение позиции после вставки слова.

Это      принципиально         важно.            Для      того,    что      бы       это продемонстрировать, рассмотрим предложение «я». Первая буква (с

индексом 0) является началом слова, которое надо выделить. После выделения получится «[я]». При этом позиция текущего символа была  равна  0.  После  выделения  мы  переместимся  на  символ  с

индексом 1. «я» является словом, которое надо выделить, поэтому после выделения получится «[[я]]». Как видно, без увеличения текущей позиции в данном случае алгоритм «зациклится».

3.7. Оптимизации кода так же аналогичны оптимизациям в предыдущей

задаче. Приведем полный код решения:

using System;

 

namespace ConsoleApplication17 {

class Program {

public static bool needMarkWord(string word) {

if (word[0] == word[word.Length - 1]) {

return true;

} else {

return false;

}

}

 

private static bool isSeparator(char c) {

string oneCharStr = "" + c;

return " .,?!".Contains(oneCharStr);

}

 

public static bool isBeginOfWord(string str, int index) {

if (isSeparator(str[index])) {

return false;

}

if (index == 0) {

return true;

}

if (isSeparator(str[index - 1])) {

return true;

} else {

return false;

}

}

 

public static int getWordLength(string str, int index) {

int res = 0;

for (int i = index; i < str.Length; i++) {

if (isSeparator(str[i])) {

break;

}

res = res + 1;

}

return res;

}

 

public static void processString(ref string str) {

for (int i = 0; i < str.Length; i++) {

if (isBeginOfWord(str, i) == false) {

continue;

}

int len = getWordLength(str, i);

string word = str.Substring(i, len);

if (needMarkWord(word)) {

str = str.Remove(i, len); word = "[" + word + "]"; str = str.Insert(i, word); i = i + 2 + len;

} else {

i = i + len;

}

}

}

 

static void Main(string[] args) {

string inputStr = Console.ReadLine(); Console.WriteLine("Строка  до   обработки: " + inputStr); processString(ref inputStr);

Console.WriteLine("Строка  после  обработки: " + inputStr);

Console.ReadKey();

}

}

}

Задача 12 (1 способ решения): Из файла удалить слова-полиндромы.

Размышления о ходе решения задачи.

1.  Для того, что бы можно было обрабатывать файл, необходимо знать его имя. Пусть в этой задаче пользователь вводит имя файла с клавиатуры.

2.  Логично предположить, что результат обработки файла надо записать в

другой  файл,  имя  которого  так  же  неизвестно.  Поэтому  попросим пользователя ввести и имя выходного файла.

3.  Для обработки файла входной файл необходимо открыть на чтение, а выходной файл – на запись. При этом каждая из этих операций может

дать  ошибку  (например,  пользователь  ввел  неверное  имя  файла).

Следовательно, надо предусмотреть такую возможность.

4.  С    файлами         можно работать         2          способами      –          через   функции

File.ReadAllLines, File.WriteAllLines и через потоки.

5.  В этом способе решения мы воспользуемся методами ReadAllLines и

WriteAllLines. Они возвращают (записывают) все содержимое файла.

Как следствие, возникает ограничение по использованию – ими можно пользоваться, если файл может целиком уместиться в оперативной памяти компьютера. Будем считать, что это условие выполняется. Так же следует отметить, что для использования этих методов надо подключить using File.IO в программе.

6.  Текстовый файл – множество строк. Значит задача обработки файла сводится к задаче обработки каждой строки в нем. Т. е. в псевдокоде

алгоритм обработки будет выглядеть следующим образом:

Получить все строки входного файла в массив

Создать массив для обработанных строк, размер которого равен изначальному

Для каждой строки файла

НачалоЦикла

Обработать текущую строку и результат записать в результирующий массив.

ОкончаниеЦикла

7.  Задача обработки одной строки рассматривалась в предыдущих задачах.

Единственное отличие – условие удаления слова. Сказать, что слово является полиндромом, мы можем только после просмотра всего слова. Если во время просмотра слова буквы не совпадут, то это слово не является полиндромом. В начале мы должны сравнить первую и последнюю букву, потом вторую и предпоследнюю и т. д. Приведем код класса для обработки одной строки.

class StringWorker {

 

public string str;

 

public bool needDelWord(string word) {

//убираем  чувствительность к  регистру

for (int i = 0; i < word.Length;i++ ) {

if (word[i] != word[word.Length - 1 - i]) {

return false;

}

}

return true;

}

 

private bool isSeparator(char c) {

string oneCharStr = "" + c;

return " .,?!".Contains(oneCharStr);

}

 

public int getWordLength(int index) {

int res = 0;

for (int i = index; i < str.Length; i++) {

if (isSeparator(str[i])) {

break;

}

res = res + 1;

}

return res;

}

 

public void processString() {

for (int i = 0; i < str.Length; i++) {

if (isSeparator(str[i])) {

continue;

}

int len = getWordLength(i);

string word = str.Substring(i, len);

if (needDelWord(word)) {

str = str.Remove(i, len);

} else {

i = i + len;

}

}

}

}

 

8.  Тогда алгоритм обработки файла будет очень простым. Для того, чтобы обработать строку, мы должны создать экземпляр StringWorker и с его помощью обработать одну строку. И так для каждой строки.

public void processFile(string inFileName, string outFileName) {

string[] content = File.ReadAllLines(inFileName); string[] processLines = new string[content.Length]; for (int i = 0; i < content.Length;i++ ) {

StringWorker worker = new StringWorker(); worker.str = content[i]; worker.processString();

processLines[i] = worker.str;

}

File.WriteAllLines(outFileName, processLines);

}

9.  Но  следует  учитывать,  что       в  ReadAllLines  и  WriteAllLines  могут возникнуть ошибки. Поэтому надо все обрамить в try … catch.

И создать еще один класс, который будет отвечать за обработку файла.

public class FileWorker {

 

public void processFile(string inFileName, string outFileName) {

try {

string[] content = File.ReadAllLines(inFileName); string[] processLines = new string[content.Length]; for (int i = 0; i < content.Length; i++) {

StringWorker worker = new StringWorker();

worker.str = content[i]; worker.processString(); processLines[i] = worker.str;

}

File.WriteAllLines(outFileName, processLines);

} catch {

Console.WriteLine("Возникла ошибка  при   обработке");

}

}

}

10. И приведем весь код программы целиком.

using System;

using System.IO;

 

namespace ConsoleApplication17 {

class Program {

static void Main() {

Console.WriteLine("введите  имя   входного файла: ");

string inFileName = Console.ReadLine(); Console.WriteLine("введите  имя   выходного  файла: "); string outFileName = Console.ReadLine();

FileWorker fileWorker = new FileWorker();

fileWorker.processFile(inFileName, outFileName);

}

}

public class StringWorker {

public string str;

public bool needDelWord(string word) {

//убираем  чувствительность к  регистру

for (int i = 0; i < word.Length; i++) {

if (word[i] != word[word.Length - 1 - i]) {

return false;

}

}

return true;

}

private bool isSeparator(char c) {

string oneCharStr = "" + c;

return " .,?!".Contains(oneCharStr);

}

public int getWordLength(int index) {

int res = 0;

for (int i = index; i < str.Length; i++) {

if (isSeparator(str[i])) {

break;

}

res = res + 1;

}

return res;

}

public void processString() {

for (int i = 0; i < str.Length; i++) {

if (isSeparator(str[i])) {

continue;

}

int len = getWordLength(i);

string word = str.Substring(i, len);

if (needDelWord(word)) {

str = str.Remove(i, len);

} else {

i = i + len;

}

}

}

 

}

 

public class FileWorker {

 

public void processFile(string inFileName, string outFileName)

{

try {

string[] content = File.ReadAllLines(inFileName); string[] processLines = new string[content.Length]; for (int i = 0; i < content.Length; i++) {

StringWorker worker = new StringWorker();

worker.str = content[i]; worker.processString(); processLines[i] = worker.str;

}

File.WriteAllLines(outFileName, processLines);

} catch {

Console.WriteLine("Возникла ошибка  при   обработке");

}

}

}

}