Редактор

      Комментарии к записи Редактор отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #3399

    Задача взята с сайта acmp.ru:

    Немногие знают, что первые версии текстового редактора из предыдущей задачи были написаны в России программистом Колей. Для этого он несколько месяцев почти не выходил из подвала, где стояли только диван и компьютер.

    Вот одна из проблем, с которыми столкнулся Коля в те времена. Во время работы пользователь набирает какой-то текст, а так же может его редактировать. При этом, даже если итоговый результат полностью помещается на экран, в процессе работы отдельные строки могут иметь слишком большую длину. Мы не будем просить вас повторить Колин подвиг и заново написать редактор. Определите, какой максимальной длины строка получалась в течение набора текста, если вам известно, какие клавиши и в каком порядке нажимал пользователь.

    Входные данные
    Во входном файле INPUT.TXT записана строка из различных символов — последовательность кнопок на клавиатуре, которые нажимал пользователь. Переводы строк заменены на символ ‘\’. Первые версии редактора поддерживали три управляющие команды, которые закодированы следующим образом:

    ‘< ' - удаление предыдущего символа (если курсор находится в начале строки, и эта строка не первая, то удаляется предшествующий перевод строки);

    ‘^’ — перемещение в конец предыдущей строки (игнорируется, если курсор находится на первой строке);

    ‘|’ — перемещение в конец следующей строки (игнорируется, если курсор находится на последней строке).

    Все остальные символы, содержащиеся в файле, имеют коды от 32 (пробел) и выше и должны пониматься как есть. Число нажатий клавиш не превосходит 105.

    Выходные данные
    В выходной файл OUTPUT.TXT выведите одно целое число — максимальную длину строки, которая была достигнута в течение работы редактора.

    Примеры

    INPUT.TXTOUTPUT.TXT
    1Hello, World???<<<!15
    2Hello, World?\This is^<!!!| a sample.17

    Разбор решения задачи

    Считывается содержимое входного файла input.txt в строковую переменную input. Объявляются переменные max равную 0 для нахождения самой длинной введенной строки и count равную 1 (так как одна строка однозначно будет введена) для подсчета количества введенных строк. В цикле перебирается каждый символ строки input и проверяется, равен ли он символу перевода каретки на новую строку ‘\’. Если равен – счетчик строк count увеличивается на 1. Затем объявляется массив countStr с длиной, равной count, в каждый элемент которого будет записываться длина строки. В цикле перебирается и обнуляется каждый элемент countStr. Объявляются 2 переменные i для перебора строки input и j для подсчета символов в каждой введенной строке. Далее начинается перебор каждого символа строки input. Выполняется поиск символов < , ^, | и \ :

    • Символ равен ‘< ': выполняется проверка, не является ли этот символ первым в строке и является ли предыдущий символ символом перевода каретки на новую строку. Если да, то это означает, что был удален предшествующий перевод строки, а значит все количество символов j, подсчитанное для данной строки countStr[j], прибавляется к количеству символов предыдущей строки countStr[j-1] и кол-во строк уменьшается на единицу. Иначе количество символов данной строки уменьшается на единицу.
    • Символ равен ‘^’: выполняется проверка, не является ли этот символ первым. Если он не первый, то произошло перемещение в конец предыдущей строки, и количество символов данной строки уменьшается на единицу, иначе игнорируется, так как курсор находится на первой строке.
    • Символ равен ‘|’: выполняется проверка, не является ли этот символ последним (меньше ли он count). Если не является, то количество символов данной строки увеличивается на единицу. Иначе игнорируется, так как курсор находится на последней строке.
    • Символ равен ‘\’: переменная j увеличивается на единицу, происходит переход на другую строку.
      Затем объявляется переменная max для поиска максимальной длины строки. В цикле перебирается каждый символ массива countStr, и если данный символ больше max, то его значение присваивается переменной max. В конце производится запись переменной max в выходной файл output.txt и исполнение программы заканчивается.
    • Этот алгоритм может быть представлен в виде следующей блок-схемы:

      Исходный код решения задачи на языке C#:

      using System; 
      using System.Collections.Generic; 
      using System.IO; 
      using System.Linq; 
      using System.Text; 
      using System.Threading.Tasks; 
      
      namespace ConsoleApplication2  { 
        class Program { 
          static void Main(string[] args) { 
            StreamReader sr = new StreamReader("input.txt"); 
            string input = sr.ReadToEnd(); 
            sr.Close(); 
      
            int max = 0; 
            int count = 1; 
            for (int z = 0; z < input.Length; z++) { 
              if (input[z] == '\') 
                count++; 
            } 
      
            var countStr = new int[count]; 
      
            for (int z = 0; z< count;z++) { 
              countStr[z] = 0; 
            } 
      
            int j = 0; 
            int i = 0; 
            while (i < input.Length) { 
              switch (input[i]) { 
              case '<': 
                if (i > 0 && input[i - 1] == '\\') { 
                  countStr[j - 1] = countStr[j - 1] + countStr[j]; 
                  count--; 
                } 
                else {
                  countStr[j]--; 
                }
                break; 
              case '^': 
                j = (j > 0) ? j - 1 : j; 
                break; 
              case '|': 
                j = (j < count) ? j + 1 : j; 
                break; 
              case '\': 
                j++; 
                break; 
              default: 
                countStr[j]++; 
                break; 
              } 
              i++; 
            } 
            max = countStr[0]; 
            for (int c = 0; c < count; c++) { 
              if (max < countStr[c]) 
                max = countStr[c]; 
            } 
            StreamWriter sw = new StreamWriter("output.txt"); 
            sw.WriteLine("{0}", max); 
            sw.Close(); 
          } 
        } 
      }

Для ответа в этой теме необходимо авторизоваться.