КЕГЭ. Задача 12. Исполнитель «Редактор»

Условие

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл:

ПОКА условие
   последовательность команд
КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции Если:

ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
 КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Конкретизация условия для одной из задач этого типа:
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.

НАЧАЛО
 ПОКА нашлось (222) ИЛИ нашлось (888)
    ЕСЛИ нашлось (222)
       ТО заменить (222, 8)
       ИНАЧЕ заменить (888, 2)
    КОНЕЦ ЕСЛИ
 КОНЕЦ ПОКА
 КОНЕЦ

Решение

Несмотря на очевидную простоту, задача не решается тупым перебором за разумное время. Очевидно только, что в конкретном примере длина строки будет уменьшаться и поиск этой закономерности и был заложен авторами в суть этой задачи. Однако, наличие возможности реализовать Исполнитель в виде программы меняет способ ее решения. Нужно просто написать программу. Единственное, что требуется кроме общих навыков программирования в этом случае, это опыт работы со строками. Тогда могут быть использованы такие программы (Бейсик, Паскаль, С++, С#):

C# (Visual Studio 2019}

// 12 тема. Исполнитель Редактор Общее решение (менять константы только!) 
using System;
namespace ConsoleApp7
{
    class Program
    {
        const int N = 68;   // длина строки
        const string c = "8";   // из какой цифры состоит строка
        const string sts1 = "222";  // подстрока для 1 поиска
        const string sts2 = "888";  // подстрока для 1 поиска
        const string stc1 = "8";    // на что заменяется 1 подстрока
        const string stc2 = "2";    // на что заменяется 1 подстрока
        static string s;   //исходная строка из N символов
        //В строке s замена sts на stc
        static void Change(string sts, string stc) //в строке s замена sts на stc
        {
            int k = s.IndexOf(sts);
            s = s.Remove(k, 3);
            s = s.Insert(k, stc);
        }
        // Поиск s1 в строке s
        static bool Search(string s1)
        {
            string s2;
            int k;
            bool result = false;
            k = s.IndexOf(s1);
            if ((s.Length > 2) && (k >= 0))
            {
                s2 = s.Substring(k, 3);
                if (s2.Equals(s1))
                    result = true;
            }
            return result;
        }
        // программа
        static void Main()
        {
            // строка из N одинаковых цифр
            s = c;
            for (int i = 1; i < N; i++) 
                s += c;
            // вывод исходной строки
            Console.WriteLine(s); 
            // цикл Редактора                      
            while (Search(sts1) || Search(sts2))
            {
                if (Search(sts1)) // условие
                    Change(sts1, stc1);
                else
                    Change(sts2, stc2);
            }
            // вывод результата
            Console.WriteLine(s);           
        }
    }
}

Результат:
888888888888888888888888888888888888888888888888888888888888
28

C++ (Visual Studio 2019}

// 12 тема. Исполнитель Редактор. Общее решение. Только менять константы! 
#include 
using namespace std;

const int N = 68;   // длина строки
const string c = "8";   // из какой цифры состоит строка
const string sts1 = "222";  // подстрока для 1 поиска
const string sts2 = "888";  // подстрока для 1 поиска
const string stc1 = "8";    // на что заменяется 1 подстрока
const string stc2 = "2";    // на что заменяется 1 подстрока
static string s;   //исходная строка из N символов

//В строке s замена sts на stc
static void Change(string sts, string stc) //в строке s замена sts на stc
{
    int k = s.find(sts);
    s = s.erase(k, 3);
    s = s.insert(k, stc); 
}
// Поиск s1 в строке s
static bool Search(string s1)
{
    string s2;
    int k;
    bool result = false;
    k = s.find(s1);
    if ((s.size() > 2) && (k >= 0))
    {
        s2 = s.substr(k, 3);
        if (s2 == s1)
            result = true;
    }
    return result;
}
// программа
int main()
{
    // строка из N одинаковых цифр
    s = c;
    for (int i = 1; i < N; i++)
        s += c;
    // вывод исходной строки
    cout << s << endl;
    // цикл Редактора                      
    while (Search(sts1) || Search(sts2))
    {
        if (Search(sts1)) // условие
            Change(sts1, stc1);
        else
            Change(sts2, stc2);
    }
    // вывод результата
    cout << s << endl;
}

Ответ: тот же.

Паскаль (Pascal ABC)

// 12 тема. Исполнитель Редактор Общее решение (менять константы только!)
const 
  N=68; // длина строки
  c='8';  // из какой цифры состоит строка
  sts1='222'; // подстрока для 1 поиска
  sts2='888'; // подстрока для 1 поиска
  stc1='8'; // на что заменяется 1 подстрока
  stc2='2'; // на что заменяется 1 подстрока
var s: string; //исходная строка из N символов
procedure Change(sts:string; stc:string); //в строке s замена sts на stc
var k: integer;
begin
  k:=s.IndexOf(sts);
  s:=s.Remove(k,3);
  s:=s.Insert(k,stc);
end;
function Search(s1: string): boolean; // поиск s1 в строке s
var 
  s2: string; 
  k:integer;
begin
  result:=false;
  k:=s.IndexOf(s1);
  if (s.Length>2)  and (k >= 0) then
  begin
    s2:=s.Substring(k,3);
    if s2=s1 then
      result:=true;
  end;
end;
// программа
begin
  // строка из N одинаковых цифр
  s:=c;
  for i: integer :=2 to N do
    s:=s+c;
  writeln(s); // вывод
  // цикл
  while search(sts1) or search(sts2) do
  begin
    if search(sts1) // условие
      then 
        Change(sts1, stc1)
      else 
        Change(sts2, stc2);
  end;
  // вывод результата
  writeln(s);
end.

Ответ тот же.

Бейсик (Visual Studio 2019}

 12 тема. Исполнитель Редактор Общее решение (менять константы только!) 
Module Module1
    Dim N As Integer = 60 ' длина строки
    Dim c, sts1, sts2, stc1, stc2, s As String
    ' В строке s замена sts на stc
    Sub Change(sts As String, stc As String) ' в строке s замена sts на stc
        Dim k As Integer
        k = s.IndexOf(sts)
        s = s.Remove(k, 3)
        s = s.Insert(k, stc)
    End Sub
    ' Поиск s1 в строке s
    Function Search(s1 As String) As Boolean
        Dim s2 As String
        Dim k As Integer
        Dim result As Boolean
        result = False
        k = s.IndexOf(s1)
        If s.Length > 2 And k >= 0 Then
            s2 = s.Substring(k, 3)
            If (s2.Equals(s1)) Then
                result = True
            End If
        End If
        Search = result
    End Function
    ' Основная программа
    Sub Main()
        c = "8"         ' из какой цифры состоит строка
        sts1 = "222"    ' подстрока для 1 поиска
        sts2 = "888"    ' подстрока для 1 поиска
        stc1 = "8"      ' на что заменяется 1 подстрока
        stc2 = "2"      ' на что заменяется 1 подстрока
        ' строка из N одинаковых цифр
        s = c
        For i As Integer = 2 To N
            s = s + c
        Next i
        ' вывод исходной строки
        Console.WriteLine(s)
        ' цикл Редактора    
        While Search(sts1) Or Search(sts2)
            If Search(sts1) Then
                Change(sts1, stc1)
            Else
                Change(sts2, stc2)
            End If
        End While
        ' вывод результата
        Console.WriteLine(s)
        Console.ReadKey()
    End Sub
End Module

Ответ тот же.
Замечание. В VB оператор Print s не поддерживается, заменен на Console.WriteLine(s).

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Пролистать наверх