|
Programming Taskbook |
|
|
||
|
Электронный задачник по программированию |
||||
|
© М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024 |
|
|
Вычисление дактилограмм в методе Карпа–Рабина: Match73 (язык C#)В качестве последнего примера, связанного с группой заданий Match, рассмотрим задание, относящееся к получисленным алгоритмам поиска подстрок, т. е. к алгоритмам, в которых поиск подстрок сводится не к сравнению символов, а к вычислению вспомогательных числовых величин и последующему анализу этих величин (см. Match61–80). Match73°. Дана строка S, состоящая из символов «0» и «1», и число q. Через Hq(S) обозначается число, равное Н(S) mod q, где число H(S) определено в Match70, а «mod» обозначает операцию взятия остатка от деления нацело. Значение Hq(S) лежит в диапазоне от 0 до q − 1 и называется дактилограммой строки S. Найти Нq(S), используя вариант схемы Горнера, в котором ни один результат умножения не превосходит 2·q: Hq(S) = ((…(((d(S[1])·2 mod q + d(S[2]))·2 mod q + d(S[3]))·2 mod q + d(S[4]))…)·2 mod q + d(S[|S|])) mod q. Вывести промежуточные результаты вычислений, полученные перед каждой операцией умножения на 2, а также найденное значение Hq(S). Решение этой задачи приведем на языке C# — одном из базовых языков платформы .NET (наряду с Visual Basic .NET). В настоящее время языки платформы .NET получают все более широкое распространение благодаря реализованной в них современной объектной модели и богатому набору стандартных библиотек, доступных для использования в любом языке .NET. Задачник поддерживает как язык C#, так и язык Visual Basic .NET; при этом задания доступны для выполнения в любой из программных сред Microsoft Visual Studio. Отметим, что к языкам платформы .NET можно отнести и язык PascalABC.NET, в программную среду которого также интегрирован электронный задачник (см. примечание в конце описания выполнения задания Match4). Для выполнения задания на языке C# надо настроить программный модуль PT4Load на одну из сред, поддерживающих этот язык, выбрав в контекстном меню окна модуля PT4Load один из пунктов с текстом «C#». Если, например, выбрать пункт «Microsoft Visual C# .NET 2008» (при этом в заголовке окна модуля появится текст «[VCSNET3]»), то заготовка для выбранного задания будет создана для среды Visual Studio .NET 2008. Как и для языка C++, проект для языка C# состоит из нескольких файлов. Файлом, в котором требуется запрограммировать решение, является файл с расширением .cs и именем, совпадающим с именем задания. В нашем случае этот файл будет иметь имя Match73.cs. Именно этот файл будет загружен в редактор среды Visual Studio .NET. Приведем содержимое данного файла: using System;
using PT4;
namespace PT4Tasks
{
public class MyTask: PT
{
public static void Solve()
{
Task("Match73");
}
}
}
Сравнительно большие размеры программы-заготовки для решения задачи на языке C# объясняются тем обстоятельством, что в языке C# нельзя использовать «обычные» процедуры и функции; все подпрограммы должны оформляться как методы некоторого класса. Поэтому в программе определяется класс MyTask, содержащий описание функции Solve, в которой должно размещаться решение задачи (напомним, что функция с тем же именем используется и в проектах-заготовках для языка C++ — см. решение задачи Match24). В начале функции Solve вызывается метод Task, инициализирующий задание с указанным именем; этот метод класс MyTask наследует от своего предка — класса PT, который реализован в специальной библиотеке задачника pt4net.dll, автоматически подключаемой к созданному проекту. Класс MyTask помещается в пространство имен PT4Tasks; директивы using позволяют обращаться к классам, описанным с пространствах имен System и PT4, без явного указания этих пространств имен. Подчеркнем, что данные директивы не обеспечивают подключения к программе соответствующих библиотек (для подключения требуются другие действия, которые автоматически выполняются в ходе создания проекта-заготовки). Стартовой функцией, с которой начинается выполнение программы на языке C#, является функция Main, однако ее описание в файле Match73.cs отсутствует. Функция Main описана в другом файле проекта-заготовки, имеющем имя pt4main.cs; в этот файл не требуется вносить никаких изменений. Для запуска программы на выполнение достаточно нажать клавишу [F5]. В результате на экране появится окно задачника с информацией о выбранном задании:
Для ввода исходных данных в программу, выполняющую задание на языке C#, надо использовать одну из функций ввода. Эти функции не имеют параметров и возвращают очередной элемент исходных данных в качестве своего значения. Для ввода данных различных типов предусмотрены различные функции: GetInt для ввода целых чисел, GetChar для ввода символов, GetString для ввода строк (исходные данные других типов в заданиях групп Match и Align не используются). Для вывода результатов предусмотрена универсальная функция Put, в которой можно указывать любое количество результирующих данных любого типа. Все эти функции реализованы в классе PT — предке класса MyTask. Для работы со строками в стандартной библиотеке платформы .NET предусмотрен специальный класс System.String (в языке C# имеется краткое имя-синоним для этого класса: string). При выполнении заданий групп Match достаточно использовать свойство Length этого класса, возвращающее длину строки (для обращения к свойствам используется точечная нотация, например, s.Length), и свойство-индексатор [], позволяющее обратиться к символу строки по его индексу, например, s[5] (индексирование, как и в C++, выполняется от 0). Операция взятия остатка от целочисленного деления, которая в формулировке задания обозначается словом «mod», в языке C# (как и в других языках с C-подобным синтаксисом) обозначается символом % (процент). Требуемая в задании реализация схемы Горнера является достаточно простой; следует лишь учесть дополнительное условие задания: надо выводить промежуточные результаты вычислений перед каждой операцией умножения на 2. Кроме того, в данной схеме требуется преобразовывать символы «0» и «1» в соответствующие им числовые значения. Для этого проще всего использовать тот факт, что цифровые символы располагаются в кодовой таблице символов подряд, и поэтому для получения числового значения символа достаточно из его кода вычесть код символа «0» (в языке C# для получения кода символа c достаточно выполнить операцию приведения типа: (int)c). С учетом сделанных замечаний, получаем следующее решение задачи: using System;
using PT4;
namespace PT4Tasks
{
public class MyTask: PT
{
public static void Solve()
{
Task("Match73");
string s = GetString();
int q = GetInt(), res = (int)s[0] - (int)'0';
for (int i = 1; i < s.Length; i++)
{
Put(res);
res = res * 2 % q + (int)s[i] - (int)'0';
}
Put(res % q);
}
}
}
После пяти тестовых запусков данного варианта решения будет выведено сообщение о том, что задание выполнено:
|
|
|
Разработка сайта: |
Последнее обновление: |