Лекция 1.5 Процедуры и функции – методы класса

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

Процедуры и функции – методы класса

Долгое время процедуры и функции играли не только функциональную, но и архитектурную роль. Весьма популярным при построении программных систем был метод функциональной декомпозиции «сверху вниз», и сегодня еще играющий важную роль. Вся программа рассматривалась, как некоторая главная функция. В процессе проектирования программы происходила декомпозиция главной функции на подфункции, решающие частные задачи. Этот процесс декомпозиции продолжался до тех пор, пока не приходили к достаточно простым функциям, реализация которых не требовала декомпозиции и могла быть описана базовыми конструкциями языка программирования.

с появлением ООП архитектурная роль функциональных модулей отошла на второй план. Для ОО-языков, к которым относится и язык C#, роль архитектурного модуля играет класс. Программная система строится из модулей, роль которых играют классы, но каждый из этих модулей имеют содержательную начинку, задавая некоторую абстракцию данных.

Процедуры и функции связываются теперь с классом, они обеспечивают требуемую функциональность класса и называются методами класса. Поскольку класс в объектно-ориентированном программировании рассматривается как некоторый тип данных, то главную роль в классе начинают играть его данные – поля класса, задающие свойства объектов класса. Методы класса  «служат» данным, занимаясь их обработкой. Помните, в C# процедуры и функции существуют только как методы некоторого класса, они не существуют вне класса.

В данном контексте понятие класс распространяется и на все его частные случаи – структуры, интерфейсы, делегаты.

В языке C# нет специальных ключевых слов – method, procedure, function, но сами понятия конечно же присутствуют. Синтаксис объявления метода позволяет однозначно определить, чем является метод – процедурой или функцией.

Прежнюю роль библиотек процедур и функций теперь играют библиотеки классов. Библиотека классов FCL, доступная в языке C#, существенно расширяет возможности языка. Знание классов этой библиотеки, методов этих классов совершенно необходимо для практического программирования на C#, использование всей его мощи.

Процедуры и функции. Отличия

Функция отличается от процедуры двумя особенностями:

  • всегда вычисляет некоторое значение, возвращаемое в качестве результата функции;
  • вызывается в выражениях.

Процедура C# имеет свои особенности:

  • возвращает формальный результат void, указывающий на отсутствие результата, возвращаемого при вызове процедуры;
  • вызов процедуры является оператором языка;
  • имеет входные и выходные аргументы, причем выходных аргументов – ее результатов – может быть достаточно много.

Хорошо известно, что одновременное существование в языке процедур и функций в каком-то смысле избыточно. Добавив еще один выходной аргумент любую функцию можно записать в виде процедуры. Справедливо и обратное. Если допускать функции с побочным эффектом, то любую процедуру можно записать в виде функции. В языке С – дедушке C# – так и сделали, оставив только функции. Однако значительно удобнее иметь обе формы реализации метода –  процедуры и функции. Обычно метод предпочитают реализовать в виде функции тогда, когда он имеет один выходной аргумент, рассматриваемый как результат вычисления значения функции. Возможность вызова функций в выражениях также влияет на выбор в пользу реализации метода в виде функции. В других случаях метод реализуют в виде процедуры.

Описание методов (процедур и функций). Синтаксис

Синтаксически в описании метода различают две части – описание заголовка и описание тела метода:

заголовок_метода

тело_метода

Рассмотрим синтаксис заголовка метода:

[атрибуты][модификаторы]{void| тип_результата_функции} имя_метода([список_формальных_аргументов])

Имя метода и список формальных аргументов составляют сигнатуру метода. Заметьте, в сигнатуру не входят имена формальных аргументов, здесь важны типы аргументов. В сигнатуру не входит и тип возвращаемого результата.

Квадратные скобки (метасимволы синтаксической формулы) показывают, что атрибуты и модификаторы могут быть опущены при описании метода. Подробное их рассмотрение будет дано в лекциях, посвященных описанию классов. Сейчас же упомяну только об одном из модификаторов – модификаторе доступа. У него четыре возможных значения, из которых пока рассмотрим только два – public и private. Модификатор public показывает, что метод открыт и доступен для вызова клиентами и потомками класса. Модификатор private говорит, что метод предназначен для внутреннего использования в классе и доступен для вызова только в теле методов самого класса. Заметьте, если  модификатор доступа опущен, то по умолчанию предполагается, что он имеет значение private и метод является закрытым для клиентов и потомков класса.

Обязательным при описании заголовка является указание типа результата, имени метода и круглых скобок, наличие которых необходимо и в том случае, если сам список формальных аргументов отсутствует. Формально тип результата метода указывается всегда, но значение void однозначно определяет, что метод реализуется процедурой. Тип результата, отличный от void, указывает на функцию. Вот несколько простейших примеров описания методов:

void A() {…};

int B(){…);

public void C(){…};

Методы A и B являются закрытыми, а метод С – открыт. Методы A и С реализованы процедурами, а метод B – функцией, возвращающей целое значение.

Список формальных аргументов

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

Рассмотрим теперь синтаксис объявления одного формального аргумента:

[ref|out|params]тип_аргумента имя_аргумента

Обязательным является указание типа и имени аргумента. Заметьте, никаких ограничений на тип аргумента не накладывается. Он может быть любым скалярным типом, массивом, классом, структурой, интерфейсом, перечислением, функциональным типом.

Несмотря на фиксированное число формальных аргументов, есть возможность при вызове метода передавать ему произвольное число фактических аргументов. Для реализации этой возможности в списке формальных аргументов необходимо задать ключевое слово params. Оно может появляться в объявлении лишь для последнего аргумента списка, объявляемого как массив произвольного типа. При вызове метода этому формальному аргументу соответствует произвольное число фактических аргументов.

Содержательно, все аргументы метода разделяются на три группы: входные, выходные и обновляемые. Аргументы первой группы передают информацию методу, их значения в теле метода только читаются. Аргументы второй группы представляют собой результаты метода, они получают значения в ходе работы метода. Аргументы третьей группы выполняют обе функции. Их значения используются в ходе вычислений и обновляются в результате работы метода. Выходные аргументы всегда должны сопровождаться ключевым словом out, обновляемые – ref. Что же касается входных аргументов, то, как правило, они задаются без ключевого слова, хотя иногда их полезно объявлять с параметром ref, о чем подробнее скажу чуть позже. Заметьте, если аргумент объявлен как выходной с ключевым словом out, то в теле метода обязательно должен присутствовать оператор присваивания, задающий значение этому аргументу. В противном случае возникает ошибка еще на этапе компиляции.

Для иллюстрации давайте рассмотрим группу методов класса Testing из проекта ProcAndFun, сопровождающего эту лекцию:

/// <summary>

/// Группа перегруженных методов Cube()

/// первый аргумент — результат

/// представляет сумму кубов

/// произвольного числа оставшихся аргументов

/// Аргументы могут быть разного типа.

/// </summary>

void Cube(out long p2, int p1)

{

p2 = (long)Math.Pow(p1, 3);

Console.WriteLine(«Метод A-1″);

}

void Cube(out long p2, params int[] p)

{

p2 = 0; for (int i = 0; i < p.Length; i++)

p2 += (long)Math.Pow(p[i], 3);

Console.WriteLine(«Метод A-2″);

}

void Cube(out double p2, double p1)

{

p2 = Math.Pow(p1, 3);

Console.WriteLine(«Метод A-3″);

}

void Cube(out double p2, params double[] p)

{

p2 = 0; for (int i = 0; i < p.Length; i++)

p2 += Math.Pow(p[i], 3);

Console.WriteLine(«Метод A-4″);

}

/// <summary>

/// Функция с побочным эффектом

/// </summary>

/// <param name=»a»>Увеличивается на 1</param>

/// <returns>значение a на входе</returns>

int F(ref int a)

{

return (a++);

}

Четыре перегруженных метода с именем Cube и метод F будут использоваться при объяснении перегрузки и побочного эффекта. Сейчас проанализируем только их заголовки. Все методы закрыты, поскольку объявлены без модификатора доступа. Перегруженные методы с именем Cube являются процедурами, метод F – функцией. Все четыре перегруженных метода имеют разную сигнатуру. Хотя имена и число аргументов у всех методов одинаковы, но типы и ключевые слова, предшествующие аргументам, различны. Первый аргумент у всех четырех перегруженных методов является выходным и сопровождается ключевым словом out, в теле метода этому аргументу присваивается значение. Аргумент функции F является обновляемым, он снабжен ключевым словом ref,  в теле функции используется его значение для получения результата функции, но и само значение аргумента изменяется в теле функции. Два метода из группы перегруженных методов используют ключевое слово params для своего последнего аргумента. Позже мы увидим, что при вызове этих методов этому аргументу будет соответствовать несколько фактических аргументов, число которых может быть произвольным.

Тело метода

Синтаксически тело метода является блоком, представляющим последовательность операторов и описаний переменных, заключенную в фигурные скобки. Если речь идет о теле функции, то в блоке должен быть хотя бы один оператор, возвращающий значение функции в форме return <выражение>.

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

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

Вызов метода. Синтаксис

Как уже отмечалось, метод может вызываться в выражениях или быть вызван как оператор тела блока. В качестве оператора может использоваться любой метод – как процедура, так и функция. Конечно, функцию разумно вызывать как оператор только, если она обладает побочным эффектом. В последнем случае она вызывается ради своего побочного эффекта, а возвращаемое значение никак не используется. Любое выражение с побочным эффектом может выступать в роли оператора, классическим примером является оператор x++;.

Если же попытаться вызвать процедуру в выражении, то это приведет к ошибке еще на этапе компиляции. Возвращаемое процедурой значение void не совместимо с выражениями. Так что  в выражениях могут быть вызваны только функции.

Сам вызов метода, независимо от того, процедура это или функция, имеет один и тот же синтаксис:

имя_метода([список_фактических_аргументов])

Если это оператор, то вызов завершается точкой с запятой.

Формальный аргумент, задаваемый при описании метода, синтаксически является  идентификатором – именем аргумента. Фактический аргумент – представляет собой «выражение», значительно более сложную синтаксическую конструкцию. Вот точный синтаксис фактического аргумента:

[ref|out]выражение

О соответствии списков формальных и фактических аргументов

Между списком формальных и списком фактических аргументов должно выполняться определенное соответствие по числу, порядку следования, типу и статусу аргументов. Если в первом списке n формальных аргументов, то фактических аргументов должно быть не меньше n (соответствие по числу). Каждому i-му формальному аргументу (для всех i от 1 до n-1) ставится в соответствие i-й фактический аргумент. Последнему формальному аргументу при условии, что он объявлен с ключевым словом params, ставятся в соответствие все оставшиеся фактические аргументы (соответствие по порядку). Если формальный аргумент объявлен с ключевым словом ref или out, то фактический аргумент должен сопровождаться таким же ключевым словом в точке вызова (соответствие по статусу).

Появление ключевых слов при вызове методов – это особенность языка C#, отличающая его от большинства других языков. Такой синтаксис следует приветствовать, поскольку он направлен на повышение надежности программной системы, напоминания программисту о том, что данный фактический аргумент является выходным и значение его наверняка изменится после вызова метода. Однако из-за непривычности синтаксиса при вызове методов эти слова часто забывают писать, что приводит к появлению синтаксических ошибок.

Если T – тип формального аргумента, то выражение, задающее фактический аргумент, должно быть согласовано по типу с типом T. Это означает, что вычисленный  тип выражения совпадает c типом T или допускает неявное преобразование к типу T, или является потомком типа T (соответствие по типу).

Если формальный аргумент является выходным – объявлен с ключевым словом ref или out, то соответствующий фактический аргумент не может быть сложным выражением, поскольку используется в левой части оператора присваивания, так что он должен быть именем, которому можно присвоить значение.

Вызов метода. Семантика

Что происходит в момент вызова метода? Выполнение начинается с вычисления фактических аргументов, которые, как мы знаем, являются выражениями. Вычисление этих выражений может приводить в свою очередь к вызову других методов. Так что первый этап может быть довольно сложным и требовать больших временных затрат. В чисто функциональном программировании все вычисление по программе сводится к вызову одной функции, фактические аргументы которой содержат вызовы функций, фактические аргументы которых содержат вызовы функций, и так далее и так далее. И на языке C# можно организовать вычисления подобным образом.

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

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

Каково следствие семантики вызова по значению? Если вы забыли указать ключевое слово ref или out для аргумента, фактически являющегося выходным, то к нему будет применяться вызов по значению. Даже если в теле метода происходит изменение значения этого аргумента, то оно действует только на время выполнения тела метода. Как только метод заканчивает свою работу (завершается блок) все локальные переменные (в том числе созданные для замены формальных аргументов) оканчивают свое существование, так что изменения не затронут фактических аргументов, и они сохранят свое значение, бывшее у них до вызова. Отсюда вывод: все выходные аргументы значимых типов, значения которых предполагается изменить в процессе работы, должны иметь ключевое слово ref или out.

Говоря о семантике вызова по ссылке и по значению, следует сделать важное уточнение. В объектном программировании, каковым является и программирование на C#, основную роль играют ссылочные типы – мы работаем с классами и объектами. Когда методу передается объект ссылочного типа, то все поля этого объекта могут в методе меняться самым беззастенчивым образом. И это несмотря на то, что объект формально не является выходным, не имеет ключевых слов ref или out, использует семантику вызова по значению. Сама ссылка на объект при этом, как и положено, остается неизменной, но состояние объекта, его поля могут полностью обновиться. Такая ситуация типична и представляет один из основных способов изменения состояния объектов. Именно поэтому ref или out не столь часто появляются при описании аргументов метода.

Что нужно знать о методах?

Знания формального синтаксиса и семантики недостаточно, чтобы эффективно работать с методами. Рассмотрим сейчас несколько важных вопросов, касающихся различных сторон работы с методами класса.

Почему у методов мало аргументов?

Методы класса имеют значительно меньше аргументов, чем процедуры и функции в классическом процедурном стиле программирования, когда не используется концепция классов. За счет чего происходит уменьшение числа аргументов у методов? Ведь аргументы играют важную роль – они передают информацию методу, нужную ему для работы, и возвращают информацию – результаты работы метода – программе, вызвавшей метод.

Все дело в том, что методы класса – это не просто набор процедур и функций, это методы, обслуживающие данные класса. Все поля класса доступны любому методу по определению. Нужно четко понимать, что в момент выполнения программной системы работа идет с объектами – экземплярами класса. Из полей соответствующего объекта – цели вызова – извлекается информация, нужная методу в процессе работы, а работа метода чаще всего сводится к обновлению значений полей этого объекта. Поэтому понятно, что методу не нужно через входные аргументы передавать информацию, содержащуюся в полях. Если в результате работы метода обновляется значение некоторого поля, то, опять-таки не нужен никакой выходной аргумент.

Поля класса или функции без аргументов?

Поля хранят информацию о состоянии объектов класса. Состояние объекта динамически изменяется в ходе вычислений – обновляются значения полей. Часто возникающая дилемма при проектировании класса: что лучше – создать ли поле, хранящее информацию, или создать функцию без аргументов, вычисляющую значение этого поля всякий раз, когда это значение понадобится. Решение дилеммы – это вечный для программистов выбор между памятью и временем, Если предпочесть поле, то это приводит к дополнительным расходам памяти. Они могут быть значительными, когда создается большое число объектов, ведь поле должен иметь каждый объект. Если предпочесть функцию, то это потребует временных затрат на вычисление значения, они могут быть значительными, если функция вызывается многократно, а ее вычисление требует значительно больших затрат в сравнении с выбором текущего значения поля.

Если бы синтаксис описания метода допускал отсутствие скобок у функции (метода), в случае, когда список аргументов отсутствует, то клиент класса мог бы и не знать, обращается он к полю или к методу. Такой синтаксис принят, например, в языке Eiffel. Преимущество такого подхода в том, что изменение реализации никак не сказывается на клиентах класса. В языке C# это не так. Когда мы хотим получить длину строки, то пишем s.Length, точно зная, что Length – это поле, а не метод класса string. Если бы по каким-либо причинам разработчики класса string решили изменить реализацию и заменить поле Length соответствующей функцией, то ее вызов имел бы вид s.Length().

Пример: Две версии класса Account

Продемонстрируем рассмотренные выше вопросы на примере проектирования классов Account и Account1, описывающих такую абстракцию данных, как банковский счет. Определим на этих данных две основные операции – занесение денег на счет и снятие денег. В первом варианте – классе Account – будем активно использовать поля класса. Помимо двух основных полей credit и debit, хранящих приход и расход счета, введем поле balance, задающее текущее состояние счета и два поля, связанных с последней выполняемой операцией. Поле sum будет хранить сумму денег текущей операции, а поле result – результат выполнения операции. Увеличение числа полей класса приведет, как следствие, к уменьшению числа аргументов у методов класса. Вот описание нашего класса:

/// <summary>

/// Класс Account определяет банковский счет.

/// простейший вариант с возможностью трех операций:

/// положить деньги на счет, снять со счета, узнать баланс.

/// Вариант с полями

/// </summary>

public class Account

{

//закрытые поля класса

int debit=0, credit=0, balance =0;

int sum =0, result=0;

/// <summary>

/// Зачисление на счет с проверкой

/// </summary>

/// <param name=»sum»>зачисляемая сумма</param>

public void putMoney(int sum)

{

this.sum = sum;

if (sum >0)

{

credit += sum; balance = credit — debit; result =1;

}

else result = -1;

Mes();

}//putMoney

/// <summary>

/// Снятие со счета с проверкой

/// </summary>

/// <param name=»sum»> снимаемая сумма</param>

public void getMoney(int sum)

{

this.sum = sum;

if(sum <= balance)

{

debit += sum; balance = credit — debit; result =2;

}

else result = -2;

Mes();

}//getMoney

/// <summary>

/// Уведомление о выполнении операции

/// </summary>

void Mes()

{

switch (result)

{

case 1:

Console.WriteLine(«Операция зачисления денег прошла успешно!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance);

break;

case 2:

Console.WriteLine(«Операция снятия денег прошла успешно!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance);

break;

case -1:

Console.WriteLine(«Операция зачисления денег не выполнена!»);

Console.WriteLine(«Сумма должна быть больше нуля!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance);

break;

case -2:

Console.WriteLine(«Операция снятия денег не выполнена!»);

Console.WriteLine(«Сумма должна быть не больше баланса!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance);

break;

default:

Console.WriteLine(«Неизвестная операция!»);

break;

}

}

}//Account

Как можно видеть, только у методов getMoney и putMoney имеется один входной аргумент. Это тот аргумент, который нужен по сути дела, поскольку только клиент может решить какую сумму он хочет снять или положить на счет. Других аргументов у методов класса нет, вся информация передается через поля класса. Уменьшение числа аргументов приводит к повышению эффективности работы с методами, так как исчезают затраты на передачу фактических аргументов. Но за все надо платить. В данном случае усложняются сами операции работы со вкладом, поскольку нужно в момент выполнения операции обновлять значения многих полей класса. Закрытый метод Mes вызывается после выполнения каждой операции, сообщая о том, как прошла операция и информируя клиента о текущем состоянии его баланса.

А теперь спроектируем аналогичный класс Account1, отличающийся только тем, что у него будет меньше полей. Вместо поля balance  в классе появится соответствующая функция с этим же именем, вместо полей sum и result появятся аргументы у методов, обеспечивающие необходимую передачу информации. Вот как выглядит этот класс:

/// <summary>

/// Класс Account1 определяет банковский счет.

/// Вариант с аргументами и функциями

/// </summary>

public class Account1

{

//закрытые поля класса

int debit=0, credit=0;

/// <summary>

/// Зачисление на счет с проверкой

/// </summary>

/// <param name=»sum»>зачисляемая сумма</param>

public void putMoney(int sum)

{

int res =1;

if (sum >0)credit += sum;

else res = -1;

Mes(res,sum);

}//putMoney

/// <summary>

/// Снятие со счета с проверкой

/// </summary>

/// <param name=»sum»> снимаемая сумма</param>

public void getMoney(int sum)

{

int res=2;

if(sum <= balance())debit += sum;

else res = -2;

balance();

Mes(res, sum);

}//getMoney

/// <summary>

/// вычисление баланса

/// </summary>

/// <returns>текущий баланс</returns>

int balance()

{

return(credit — debit);

}

/// <summary>

/// Уведомление о выполнении операции

/// </summary>

void Mes(int result, int sum)

{

switch (result)

{

case 1:

Console.WriteLine(«Операция зачисления денег прошла успешно!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance());

break;

case 2:

Console.WriteLine(«Операция снятия денег прошла успешно!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance());

break;

case -1:

Console.WriteLine(«Операция зачисления денег не выполнена!»);

Console.WriteLine(«Сумма должна быть больше нуля!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance());

break;

case -2:

Console.WriteLine(«Операция снятия денег не выполнена!»);

Console.WriteLine(«Сумма должна быть не больше баланса!»);

Console.WriteLine(«Cумма={0}, Ваш текущий баланс={1}»,

sum,balance());

break;

default:

Console.WriteLine(«Неизвестная операция!»);

break;

}

}

}//Account1

Сравнивая этот класс с классом Account, можно видеть, что число полей сократилось с 5 до двух, упростились основные методы getMoney и putMoney. Но в качестве платы у класса появился дополнительный метод balance(),  у метода Mes теперь появились два аргумента. Какой класс лучше? Однозначно сказать нельзя, все зависит от контекста, приоритетов, заданных при создании конкретной системы.

Приведу процедуру класса Testing, тестирующую работу с классами Account и Account1:

public void TestAccounts()

{

Account myAccount = new Account();

myAccount.putMoney(6000);

myAccount.getMoney(2500);

myAccount.putMoney(1000);

myAccount.getMoney(4000);

myAccount.getMoney(1000);

//Аналогичная работа с классом Account1

Console.WriteLine(«Новый класс и новый счет!»);

Account1 myAccount1 = new Account1();

myAccount1.putMoney(6000);

myAccount1.getMoney(2500);

myAccount1.putMoney(1000);

myAccount1.getMoney(4000);

myAccount1.getMoney(1000);

}

На рис. 1_5.1 показаны результаты работы этой процедуры.

Рис. 1_5.1. Тестирование классов Account и Account1

Функции с побочным эффектом

Функция называется функцией с побочным эффектом, если помимо результата, вычисляемого функцией и возвращаемого ей в операторе return, она имеет выходные аргументы с ключевыми словами ref и out. В языках C/C++ функции с побочным эффектом применяются сплошь и рядом. Хороший стиль ОО-программирования не рекомендует использование таких функций. Выражения, использующие функции с побочным эффектом, могут потерять свои прекрасные свойства, присущие им в математике. Если F(a) – функция с побочным эффектом, то a + F(a) может быть не равно F(a) + a, так что теряется коммутативность операции сложения.

Примером такой функции является функция F, приведенная выше. Вот тест, демонстрирующий потерю коммутативности сложения при работе с этой функцией:

/// <summary>

/// тестирование побочного эффекта

/// </summary>

public void TestSideEffect()

{

int a = 0, b=0, c=0;

a = 1; b = a + F(ref a);

a = 1; c = F(ref a) + a;

Console.WriteLine(«a={0}, b={1}, c={2}»,a, b, c);

}

 

На рис. 1_5.2 показаны результаты работы этого метода.

Рис. 1_5.2. Демонстрация вызова функции с побочным эффектом

Обратите внимание на полезность указания ключевого слова ref в момент вызова. Его появление хоть как-то оправдывает некоммутативность сложения.

Напомню, что и выражения с побочным эффектом также приводят к потере коммутативности сложения и умножения. Выражение x + ++x не эквивалентно выражению ++x + x.

Методы. Перегрузка

Должно ли быть уникальным имя метода в классе? Нет, это не требуется. Более того, проектирование методов с одним и тем же именем является частью стиля программирования на С++  и стиля C#. Существование в классе методов с одним и тем же именем называется перегрузкой, а сами одноименные методы называются перегруженными.

Перегрузка методов полезна, когда требуется решать подобные задачи с разным набором аргументов. Типичный пример – это нахождение площади треугольника. Площадь можно вычислить по трем сторонам, по двум углам и стороне, по двум сторонам и углу между ними и при многих других наборах аргументов. СчиПродемонстрируем рассмотренные выше вопросы на примере проектирования классов Account и Account1, описывающих такую абстракцию данных, как банковский счет. Определим на этих данных две основные операции – занесение денег на счет и снятие денег. В первом варианте – классе Account – будем активно использовать поля класса. Помимо двух основных полей credit и debit, хранящих приход и расход счета, введем поле balance, задающее текущее состояние счета и два поля, связанных с последней выполняемой операцией. Поле sum будет хранить сумму денег текущей операции, а поле result – результат выполнения операции. Увеличение числа полей класса приведет, как следствие, к уменьшению числа аргументов у методов класса. Вот описание нашего класса:тается удобным во всех случаях иметь для метода одно имя, например Square, и всегда, когда нужно вычислить площадь, не задумываясь вызывать метод Square, передавая ему известные в данный момент аргументы.

Пример этот может быть не совсем удачен, поскольку при перегрузке сигнатуры реализаций должны отличаться, а для вычисления площади передаются три аргумента, вообще говоря, одного типа. Так что в этом случае придется использовать искусственные приемы, например, объявляя стороны треугольника типа float, а углы типа – double.

Перегрузка характерна и для знаков операций. В зависимости от типов аргументов один и тот же знак может выполнять фактически разные операции. Классическим примером является знак операции сложения +, который играет роль операции сложения не только для арифметических данных разных типов, но и выполняет конкатенацию строк.

Перегрузка требует уточнения семантики вызова метода. Когда встречается вызов не перегруженного метода, то имя метода в вызове однозначно определяет, тело какого метода должно выполняться в точке вызова. Когда же метод перегружен, то знания имени недостаточно – оно не уникально. Уникальной характеристикой перегруженных методов является их сигнатура. Перегруженные методы, имея одинаковое имя, должны отличаться либо числом аргументов, либо их типами, либо ключевыми словами (заметьте, с точки зрения сигнатуры ключевые слова ref и out не отличаются). Уникальность сигнатуры позволяет вызвать требуемый перегруженный метод.

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

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

Есть ситуации, где перегрузка полезна, недаром она широко используется при построении библиотеки FCL. Возьмем, например класс Convert, у которого 16 методов с разными именами, зависящими от целевого типа преобразования. Каждый из этих 16 методов перегружен и в свою очередь имеет примерно 16 реализаций в зависимости от типа источника. Согласитесь, что-то неразумное было бы иметь в классе Convert 256 методов вместо 16 перегруженных методов. Впрочем, также неразумно было бы иметь один перегруженный метод, имеющий  256 реализаций. Перегрузка – это инструмент, которым следует пользоваться с осторожностью и обоснованно.

В заключение этой темы, посмотрим, как проводилось тестирование работы с перегруженными методами:

/// <summary>

/// Тестирование перегруженных методов Cube()

/// </summary>

public void TestLoadMethods()

{

long u = 0; double v = 0;

Cube(out u, 7); Cube(out v, 7.5);

Console.WriteLine(«u= {0}, v= {1}», u, v);

Cube(out v, 7);

Console.WriteLine(«v = {0}», v);

Cube(out u, 7, 11, 13);

Cube(out v, 7.5, Math.Sin(11.5) + Math.Cos(13.5), 15.5);

Console.WriteLine(«u= {0}, v= {1}», u, v);

}//TestLoadMethods

На рис. 1_5.3 показаны результаты этого тестирования.

Рис. 1_5.3 Тестирование перегрузки методов

Архитектура проекта

Как обычно для поддержки примеров этой главы создано Решение с именем Ch5, содержащее консольный проект ProcAndFun. Помимо автоматически созданного класса Program в проект добавлены три класса – Testing, Account, Account1. В Main процедуре класса Program создается объект testObject класса Testing, вызывающий методы этого класса. Каждый из методов представляет собой тест, позволяющий на примере пояснить излагаемый материал.

Задачи и алгоритмы

Слово, число, рисунок, нота,– величайшие изобретения человечества. Для программистов это информационные объекты, с которыми нужно уметь оперировать.

Числа

Алгоритмы и задачи, рассматриваемые в этой главе, можно использовать на начальном этапе обучения программированию при изучении простейшего вида модульности – процедур и функций.

Многие задачи этой главы являются хорошими примерами при изучении темы классов. У класса двойственная природа – с одной стороны это модуль, с другой – тип данных. Рациональные числа, комплексные числа, простые числа, являются естественными примерами классов, поскольку интуитивно понятно, какой тип данных они задают.

Цифры. Системы счисления

Для записи чисел привычным способом, знакомым еще с первых классов школы, является их запись в позиционной системе счисления. Напомним некоторые факты. В позиционной системе счисления всегда есть цифра 1. Считается, что единицу создал бог, а остальные цифры придуманы человеком. Если так, то наиболее замечательной из человеческих придумок в этой области является введение цифры 0. Цифры позиционной системы упорядочены и каждая получатся из предыдущей прибавлением единицы. Число различных цифр в позиционной системе счисления задает основание системы счисления – p. В привычной для нас десятичной системе счисления p = 10 и цифрами являются знакомые всем символы: 0, 1, 2, … 9. В двоичной системе счисления цифр всего две – 0 и 1 и p = 2. В шестнадцатеричной системе счисления p =16 и привычных символов для обозначения цифр не хватает, так что дополнительно используются большие буквы латинского алфавита: 0, 1, 2, … 9, A, B, C, D, E, F, где A задает 10, а F – цифру 15. Поскольку в любой позиционной системе счисления цифры задают числа от 0 до p-1, то для числа p уже нет специального символа. Как следствие, в любой позиционной системе счисления основание системы счисления представляется числом 10, так что справедливы следующие соотношения: 2(10) = 10(2); 16(10) = 10(16); p(10) = 10(p). Здесь и в дальнейшем при записи числа при необходимости будем указывать в круглых скобках и систему счисления. В обыденной жизни непреложным фактом является утверждение «2*2=4». Мы понимаем, что столь же верным является утверждение «2*2 = 11» (в троичной системе счисления), или, если хотите «2*2 = 10», – все зависит от системы счисления, в которой ведутся вычисления.

Еще Эйлер занимался записью чисел в различных системах счисления. В его записных книжках можно найти запись числа π в двоичной системе счисления и запись чисел в системе с основанием 24, цифры которой он обозначал буквами латиницы.

Целые числа в позиционных системах счисления записываются в виде последовательности подряд идущих цифр: N=cncn-1…c0.Эта запись стала настолько естественной, что иногда теряется ее исконный смысл: N = cn10n + cn-110n-1 + … + c1101 + c0100, при котором цифры в записи числа представляют собой коэффициенты разложения числа N по степеням основания, так что вклад каждой цифры в число определяется как самой цифрой, так и ее позицией k и равен ck10k. По причине того, что вклад каждой цифры в число зависит от ее позиции, система счисления и называется позиционной.

Запись чисел в позиционной системе легко обобщается и на числа с дробной частью:
N=cncn-1…c0,d1…dm, где дробная часть отделяется от целой символом запятой или точки. И в этом случае остается справедливым разложение числа N по степеням основания, в котором цифры дробной части задают коэффициенты для отрицательных степеней основания:
N = cn10n + cn-110n-1 + … + c1101 + c0100 + d110-1 + d210-2 + … + dm10-m           (1)

Понимание соотношения (1) достаточно для решения большинства задач, рассматриваемых в этом разделе, являющихся частными случаями следующей задачи: дано представление числа в системе с основанием p, требуется найти его представление в системе с основанием q. (Пример: найти запись числа N=2BA37,5F(16) в троичной системе счисления).

Рассмотрим возможную схему решения подобных задач. Зная основание системы счисления p и цифры в записи числа в этой системе счисления, нетрудно вычислить значение числа N в десятичной системе счисления. Для этого достаточно воспользоваться соотношением (1), в котором значения цифр и основание системы счисления – p задаются в десятичной системе и в ней же ведутся вычисления. Например:

N=2BA37,5F(16) = 2*164 + 11*163 +10*162 + 3*161 +7 + 5*16-1 + 15*16-2

Сложнее, но достаточно просто решается и обратная задача. Зная значение числа N в десятичной системе, нетрудно получить цифры, задающие его запись в системе с основанием q. Представим число N в виде суммы целой и дробной частей N= C+D. Рассмотрим схему получения цифр отдельно для целой части C и дробной – D. Пусть в системе с основанием q число C представимо в виде C = cncn-1…c0. Тогда нетрудно получить его последнюю цифру c0 и число M = cncn-1…c1, полученное отбрасыванием последней цифры в записи числа C. Для этого достаточно воспользоваться операциями деления нацело и получения остатка при делении нацело: c0 = C%p; M = C/p;

Применяя этот прием n раз, получим все цифры в записи числа C. Заметьте, имеет место соотношение: N= (N/p)*p + N%p, где в соответствии с языком C# операция / означает деление нацело, а % – остаток от деления нацело. Чтобы получить все цифры и сохранить их в массиве, достаточно эту схему вставить в соответствующий цикл, что схематично можно представить следующим почти программным текстом:

M=C; i=0;

while(M!=0)

{

c=M%p; M=M/p; Ar[i] =c; i++;

}

Для получения цифр дробной части применяется та же схема, но с некоторой модификацией. Если цифры целой части вычисляются, начиная с последней, младшей цифры числа, то цифры дробной части вычисляются, начиная с первой цифры после запятой. Для ее получения достаточно имеющуюся дробь умножить на основание системы счисления и в полученном результате взять целую часть. Для получения последующих цифр этот процесс следует применять к числу M, представляющему дробь, из которой удалена первая цифра:
d1 =[D*p]; m={d*p}. Здесь [x] и {x} означают соответственно взятие целой и дробной части числа x. Хотя напрямую этих операций нет в языке C#, но их достаточно просто выразить имеющимися средствами этого языка.

Чтобы перейти от системы счисления p к системе счисления q, всегда ли следует использовать десятичную систему в качестве промежуточной: p→ 10 → q? Нет, не всегда. В ряде случаев удобнее использовать прием, основанный на следующем утверждении:

Если основания систем счисления связаны соотношением p = qk, то для перехода от записи числа в системе с основанием p к записи числа в системе с основанием q достаточно каждую цифру системы p представить группой из k цифр системы q.

Для обратного перехода из q в p достаточно сгруппировать цифры системы q и каждую группу из k цифр заменить одной цифрой системы p. Доказательство этих утверждений оставляю читателю.

Для программистов особую важность представляют три системы счисления – двоичная, восьмеричная и шестнадцатеричная. Основания этих систем счисления связаны упомянутым соотношением: 16 = 24; 8 = 23. Рассмотрим число N, записанное в шестнадцатеричной системе N = 2A,3E(16). Чтобы получить его запись в двоичной системе, каждую цифру запишем в двоичной системе, представив ее группой из четырех двоичных цифр. Нетрудно видеть, что N = 00101010,00111110(2). Незначащие нули слева и справа могут быть отброшены, так что окончательно имеем: N = 101010,0011111(2). Переведем это число в восьмеричную систему. Для этого достаточно провести группирование по три цифры влево и вправо от запятой соответственно для целой и дробной части, так что получим: N = 52,174(8).

Римская система счисления

Еще сегодня для записи целых чисел, в особенности дат, используется римская система счисления. Эта система записи чисел не является позиционной. В ее основе лежит понятие человеческих рук с их пятью и десятью пальцами. Поэтому в этой системе есть цифры 1, 5 и 10, записываемые с помощью символов I, V, X. Помимо этого есть еще четыре цифры – 50, 100, 500, 1000, задаваемые символами L, C, D, M. В этой системе нет цифры 0 и она не является позиционной.  С помощью цифр римской системы обычно записывают целые числа, не превышающие 4000. Запись числа представляет собой последовательность подряд идущих цифр, а значением числа является сумма цифр в его записи. Например число III означает I + I + I = 3. В записи числа старшие цифры предшествуют младшим, например CVI = C+V+I = 100+5+1=106. Из этого правила есть одно исключение. Младшая цифра может предшествовать старшей цифре и тогда вместо сложения применяется вычитание, например CIX = C+X-I = 100+10-1=109.

Задачи

  1. Дано целое число N = cn-1…c0, где ci – это цифры. Получить n – число цифр в записи числа и целочисленный массив DigitsN такой, что DigitsN[i] = ci.
  2. Дано целое число N = cn-1…c0, где ci – это цифры. Получить строку strN, задающую запись числа N.
    Указание: конечно, можно воспользоваться стандартным методом ToString, но в задаче требуется дать собственную реализацию этого метода.
  3. Дано дробное число N = 0.dm-1…d0, где di – это цифры. Получить m – число цифр в записи числа и целочисленный массив FractN такой, что FractN[i] = di.
  4. Дано дробное число N = 0. dm-1…d0, где di – это цифры. Получить строку strN, задающую запись числа N.
    Указание: конечно, можно воспользоваться стандартным методом ToString, но в задаче требуется дать собственную реализацию этого метода.
  5. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры. Получить n и m – число цифр в записи целой и дробной части числа и целочисленный массив DigitsN из n+m элементов такой, что первые его n элементов содержат цифры целой части, а последние m элементов – дробной.
  6. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры. Получить строку strN, задающую запись числа N.
  7. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в двоичную систему счисления N = bk-1…b0, получить k – число цифр и целочисленный массив DigitsN такой, что DigitsN[i] = bi, где bi – это цифры в записи числа N в двоичной системе счисления.
    Пример: N = 17(10) = 10001(2)
  8. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в троичную систему счисления N = bk-1…b0, получить k – число цифр и целочисленный массив DigitsN такой, что DigitsN[i] = bi, где bi – это цифры в записи числа N в троичной системе счисления.
    Пример: N = 17(10) = 122(3)
  9. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в четверичную систему счисления N = bk-1…b0, получить k – число цифр и целочисленный массив DigitsN такой, что DigitsN[i] = bi, где bi – это цифры в записи числа N в четверичной системе счисления.
    Пример: N = 17(10) = 101(4)
  10. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в восьмеричную систему счисления N = bk-1…b0, получить k – число цифр и целочисленный массив DigitsN такой, что DigitsN[i] = bi, где bi – это цифры в записи числа N в восьмеричной системе счисления.
    Пример: N = 17(10) = 21(8)
  11. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в шестнадцатеричную систему счисления N = bk-1…b0, получить k – число цифр и целочисленный массив DigitsN такой, что DigitsN[i] = bi, где bi – это цифры в записи числа N в шестнадцатеричной системе счисления.
    Пример: N = 17(10) = 11(16)
  12. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в двоичную систему счисления N = bk-1…b0. Получить строку strN, задающую запись числа N.
    Пример: N = 17(10) = 10001(2)
  13. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в троичную систему счисления N = bk-1…b0. Получить строку strN, задающую запись числа N.
    Пример: N = 17(10) = 122(3)
  14. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в четверичную систему счисления N = bk-1…b0. Получить строку strN, задающую запись числа N.
    Пример: N = 17(10) = 101(4)
  15. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в восьмеричную систему счисления N = bk-1…b0. Получить строку strN, задающую запись числа N.
    Пример: N = 17(10) = 21(8)
  16. Дано целое число N = cn-1…c0, где ci – это цифры десятичной системы счисления. Перевести число N в шестнадцатеричную систему счисления N = bk-1…b0. Получить строку strN, задающую запись числа N.
    Пример: N = 17(10) = 11(16)
  17. Дано дробное число N = 0.dm-1…d0, где di – это цифры десятичной системы счисления. Перевести число N в двоичную систему счисления N = 0.bk-1…b0, вычислив k цифр в его записи, сохраняя их в целочисленном массиве DigitsN таком, что DigitsN[i] = bi, где bi – это цифры в записи числа N в двоичной системе счисления.
    Пример: N = 0.17(10) = 0.001010111(2) при k=9.
  18. Дано дробное число N = 0.dm-1…d0, где di – это цифры десятичной системы счисления. Перевести число N в троичную систему счисления N = bk-1…b0, вычислив k цифр в его записи, сохраняя их в целочисленном массиве DigitsN таком, что DigitsN[i] = bi, где bi – это цифры в записи числа N в троичной системе счисления.
    Пример: N = 0.17(10) = 0.01112(3) при k=5.
  19. Дано дробное число N = 0.dm-1…d0, где di – это цифры десятичной системы счисления. Перевести число N в четверичную систему счисления N = bk-1…b0, вычислив k цифр в его записи, сохраняя их в целочисленном массиве DigitsN таком, что DigitsN[i] = bi, где bi – это цифры в записи числа N в четверичной системе счисления.
    Пример: N = 0.17(10) = 0.02232(4) при k=5.
  20. Дано дробное число N = 0.dm-1…d0, где di – это цифры десятичной системы счисления. Перевести число N в восьмеричную систему счисления N = bk-1…b0, вычислив k цифр в его записи, сохраняя их в целочисленном массиве DigitsN таком, что DigitsN[i] = bi, где bi – это цифры в записи числа N в восьмеричной системе счисления.
    Пример: N = 0.17(10) = 0.127(8) при k=3.
  21. Дано дробное число N = 0.dm-1…d0, где di – это цифры десятичной системы счисления. Перевести число N в шестнадцатеричную систему счисления N = bk-1…b0, вычислив k цифр в его записи, сохраняя их в целочисленном массиве DigitsN таком, что DigitsN[i] = bi, где bi – это цифры в записи числа N в шестнадцатеричной системе счисления.
    Пример: N = 0.17(10) = 0.1B(16) при k=5.
  22. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Перевести число N в двоичную систему счисления с заданной точностью, вычислив k цифр дробной части числа. Получить строку strN, задающую запись числа N в этой системе счисления.
    Пример: N = 17.17(10) = 10001. 001010111 (2)
  23. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Перевести число N в троичную систему счисления с заданной точностью, вычислив k цифр дробной части числа. Получить строку strN, задающую запись числа N в этой системе счисления.
    Пример: N = 17.17(10) = 122. 01112 (3)
  24. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Перевести число N в четверичную систему счисления с заданной точностью, вычислив k цифр дробной части числа. Получить строку strN, задающую запись числа N в этой системе счисления.
    Пример: N = 17.17(10) = 101. 02232 (4)
  25. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Перевести число N в восьмеричную систему счисления с заданной точностью, вычислив k цифр дробной части числа. Получить строку strN, задающую запись числа N в этой системе счисления.
    Пример: N = 17.17(10) = 21. 127 (8)
  26. Дано вещественное число с целой и дробной частью N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Перевести число N в шестнадцатеричную систему счисления с заданной точностью, вычислив k цифр дробной части числа. Получить строку strN, задающую запись числа N в этой системе счисления.
    Пример: N = 17.17(10) = 11. 1B (16)
  27. Дана строка, задающая представление целого числа N = cn-1…c0, где ci – это цифры десятичной системы счисления. Получить число N.
    Эту задачу можно сформулировать и так: задайте собственную реализацию метода ToInt32 класса Convert.
  28. Дана строка, задающая представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры десятичной системы счисления. Получить число N.
    Эту задачу можно сформулировать и так: задайте собственную реализацию метода ToDouble класса Convert.
  29. Дана строка, задающая в двоичной системе счисления представление целого числа N = cn-1…c0, где ci – это цифры двоичной системы счисления. Получить число N.
    Эту задачу можно рассматривать, как расширение класса Convert: добавление метода FromBinaryToInt32.
  30. Дана строка, задающая в двоичной системе счисления представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры двоичной системы счисления. Получить число N.
    Эту задачу можно рассматривать, как расширение класса Convert: добавление метода FromBinaryToDouble.
  31. Дана строка, задающая в шестнадцатеричной системе счисления представление целого числа N = cn-1…c0, где ci – это цифры шестнадцатеричной системы счисления. Получить число N.
    Эту задачу можно рассматривать, как расширение класса Convert: добавление метода FromHexToInt32.
  32. Дана строка, задающая в двоичной системе счисления представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры двоичной системы счисления. Получить число N.
    Эту задачу можно рассматривать, как расширение класса Convert: добавление метода FromHexToDouble.
  33. Дана строка, задающая в двоичной системе счисления представление целого числа N = cn-1…c0, где ci – это цифры двоичной системы счисления. Получить строки str4N, str8N, str16N, задающие представление числа N в системах счисления: четверичной, восьмеричной, шестнадцатеричной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  34. Дана строка, задающая в двоичной системе счисления представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры двоичной системы счисления. Получить строки str4N, str8N, str16N, задающие представление числа N в системах счисления: четверичной, восьмеричной, шестнадцатеричной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  35. Дана строка, задающая в восьмеричной системе счисления представление целого числа N = cn-1…c0, где ci – это цифры восьмеричной системы счисления. Получить строки str4N, str2N, str16N, задающие представление числа N в системах счисления: четверичной, двоичной, шестнадцатеричной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  36. Дана строка, задающая в восьмеричной системе счисления представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры восьмеричной системы счисления. Получить строки str4N, str2N, str16N, задающие представление числа N в системах счисления: четверичной, двоичной, шестнадцатеричной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  37. Дана строка, задающая в шестнадцатеричной системе счисления представление целого числа N = cn-1…c0, где ci – это цифры шестнадцатеричной системы счисления. Получить строки str4N, str8N, str2N, задающие представление числа N в системах счисления: четверичной, восьмеричной, двоичной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  38. Дана строка, задающая в шестнадцатеричной системе счисления представление вещественного числа с целой и дробной частью: N = cn-1…c0.dm-1…d0, где ci, dj – это цифры шестнадцатеричной системы счисления. Получить строки str4N, str8N, str2N, задающие представление числа N в системах счисления: четверичной, восьмеричной, двоичной.
    Указание. Используйте группирование цифр при переводе из одной системы счисления в другую.
  39. (*) Заданы p и q – основания двух систем счисления, strN – строка, задающая представление вещественного числа N в системе с основанием p. Получить строку, задающую представление числа N в системе с основанием q, возможно с некоторой точностью, заданной параметром k – числом цифр дробной части числа N при его записи в системе с основанием q.
  40. (*) Дано число N и основание системы счисления p. Получить ci – коэффициенты разложения числа N по степеням основания с заданной точностью Eps.
    Указание: В данной задаче предполагается, что N, p, ci являются вещественными числами и для ci выполняется условие (ci < p). Пример: N=30; p=2,5; c3 = 1; c2 = 1,5; c1 = 2; c0 = 0;
  41. Дано основание системы счисления p и ci – коэффициенты разложения числа N по степеням основания. Получить число N.
    Указание: В данной задаче предполагается, что N, p, ci являются вещественными числами и для ci выполняется условие (ci < p). Пример: p=2,5; c3 = 1; c2 = 1,5; c1 = 2; c0 = 0;
  42. (*) Дана строка strRome, задающая представление целого числа N, меньшего 4000, в непозиционной римской системе счисления. Получить число N.
    Пример: N= MMIV = 2004
  43. (*) Дано целое число N, меньшее 4000. Получить строку strRome, задающую представление числа в непозиционной римской системе счисления.
    Пример: N=2005 =MMV

Именованные числа

С давних пор числа применяются для измерения физических величин ­– длин, площадей, объемов. Как правило, при этом использовалась системы, вовсе не основанные на десятичной системе, а связанные с реально применяемыми мерами – бочонками, мешками и прочей применяемой тарой. Метрическая система мер, основанная на десятичной системе счисления, завоевала свои позиции лишь в последние два столетия, и мы стали применять километры и килограммы, килоджоули и килогерцы. Но рецидивы все еще дают себя знать, и примером тому является программисты, которые сравнительно недавно ввели систему мер для измерения объема информации. У нас байт равен 8 битам, а килобайт равен не 1000 байтов, как мог бы ожидать человек, далекий от программирования, а — 1024 байта. И связано это с любовью компьютеров к двоичной системе счисления, в которой 1 байт = 1000(2) битов, а 1 Кб = 10000000000(2) байтов.

Задачи

  1. Задано число T (температура) и единица измерения (C – градусы по Цельсию, F – по Фаренгейту, R – по Реомюру, K – по Кельвину). Определить значения температуры в других шкалах, используя следующие соотношения:Пример: -40 (С) = -40 (F) = -32 (R) = 233,2 (K)
  2. Дано число N, задающее расстояние, измеренное с точностью до долей миллиметра. Получите строку, задающее расстояние с использованием старинной китайской системы, в которой справедливы следующие соотношения:
  3. Дано число N, задающее расстояние, измеренное с точностью до долей миллиметра. Получите строку, задающее расстояние с использованием старинной древнерусской системы, в которой справедливы следующие соотношения:
  4. Дано число N, задающее расстояние, измеренное с точностью до долей миллиметра. Получите строку, задающее расстояние с использованием английской системы мер длины, в которой справедливы следующие соотношения:
  5. Дано вещественное число N, задающее объем хранимых данных в терабайтах. Выразите значение N в гигабайтах, мегабайтах, килобайтах, байтах, битах.

Классификация чисел

Целые положительные числа – N = {1, 2, 3, … } – составляют множество натуральных чисел. Зачастую и 0 считают натуральным числом.

Множество целых чисел Z включает в себя все натуральные числа, число 0 и все натуральные числа, взятые со знаком минус: Z = {0, 1, -1, 2, -2, …}.

Каждое рациональное число x можно задать парой целых чисел (m, n), где m является числителем, n – знаменателем числа: x = m/n. Эквивалентным представлением рационального числа является его задание в виде числа, записанного в позиционной десятичной системе счисления, где дробная часть числа может быть конечной или бесконечной периодической дробью. Например, число x = 1/3 = 0,(3) представляется бесконечной периодической дробью.

Числа, задаваемые бесконечными непериодическими дробями, называются иррациональными числами. Таковыми являются, например все числа вида √p, где p – простое число. Иррациональными являются известные всем числа π и e.

Объединение множеств целых, рациональных и иррациональных чисел составляет множество вещественных чисел. Геометрическим образом множества вещественных чисел является прямая линия – вещественная ось, где каждой точке оси соответствует некоторое вещественное число, так что вещественные числа плотно и непрерывно заполняют всю вещественную ось.

Плоскость представляет геометрический образ множества комплексных чисел, где вводятся уже две оси – вещественная и мнимая. Каждое комплексное число, задаваемое парой вещественных чисел, представимо в виде: x = a+b*i, где a и b – вещественные числа, которые можно рассматривать, как декартовы координаты числа на плоскости.

Делители и множители

Рассмотрим сейчас классификацию, которая делит множество натуральных чисел на два подмножества – простых и составных чисел. В основе этой классификации лежит понятие делимости натуральных чисел. Если n делится нацело на d, то говорят, что d «делит» n,что записывают в виде: d | n. Заметьте, это определение, возможно, не соответствует интуитивному пониманию: d «делит» n, если n делится на d, а не наоборот. Число d называется делителем числа n. У каждого числа n есть два тривиальных делителя – 1 и n. Делители, отличные от тривиальных, называются множителями числа n. Число n называется простым, если у него нет делителей, отличных от тривиальных. Простые числа делятся только на 1 и сами на себя. Числа, у которых есть множители, называются составными. Число 1 является особым числом, поскольку не относится ни к простым, ни к составным числам. Отрицательные числа также не относятся ни к простым, ни к составным, но всегда можно рассматривать модуль числа и относить его к простым или составным числам.

Любое составное число N можно представить в виде произведения его множителей: N = q1 * q2 * … * qk. Это представление не единственно, например 96 = 8*12 = 2*3*16. Однако для каждого составного числа N существует единственное представление в виде произведения степеней простых чисел: N = p1r1 * p2r2 * … * pkrk, где pi – простые числа и pk < pk+1. Это представление называется разложением числа N на простые множители. Например 96 = 25 * 31.

Если d | m и d | n, то d является общим делителем чисел m и n. Среди всех общих делителей можно выделить наибольший общий делитель, обозначаемый как НОД(m, n). Если НОД(m, n) = 1, то числа m и n называются взаимно простыми. Простые числа взаимно просты, так что НОД(q, p) =1, если q и p – простые числа.

Если m | A и n | A, то A является общим кратным чисел m и n. Среди всех общих кратных можно выделить наименьшее общее кратное, обозначаемое как НОК(m, n). Если НОК(m, n) = m*n, то числа m и n являются взаимно простыми. НОК(q, p) =q*p, если q и p – простые числа.

Если через Pm и Qn обозначить множества всех простых множителей чисел m и n, то

 

Если получено разложение чисел m и n на простые множители, то, используя приведенные соотношения, нетрудно вычислить НОД(m,n) и НОК(m,n). Существуют и более эффективные алгоритмы, не требующие разложения числа на множители.

Алгоритм Эвклида

Эффективный алгоритм вычисления НОД(m,n) предложен еще Эвклидом. Он основывается на следующих свойствах НОД(m,n), доказательство которых предоставляется читателю:

 

Если m > n, то по третьему свойству его можно уменьшить на величину n. Если же m < n, то по второму свойству аргументы можно поменять местами и вновь придти к ранее рассмотренному случаю. Когда же в результате этих преобразований значения аргументов сравняются, то решение будет найдено. Поэтому можно предложить следующую схему:

while(m != n)

{

if(m < n) swap(m,n);

m = m — n;

}

return(m);

Здесь процедура swap выполняет обмен значениями аргументов.

Если немного подумать, то становится ясно, что вовсе не обязательно обмениваться значениями, – достаточно на каждом шаге цикла изменять аргумент с максимальным значением. В результате приходим к схеме:

while(m != n)

{

if(m > n) m = m — n;

else n = n – m;

}

return(m);

Если еще немного подумать, то можно улучшить и эту схему, перейдя к циклу с тождественно истинным условием:

while(true)

{

if(m > n) m = m — n;

else if (n > m) n = n – m;

else return(m);

}

Последняя схема хороша тем, что в ней отчетливо видна необходимость доказательства завершаемости этого цикла. Доказать завершаемость цикла нетрудно, используя понятие варианта цикла. Для данного цикла вариантом может служить целочисленная функция – max(m,n), которая уменьшается на каждом шаге, оставаясь всегда положительной.

Достоинством данной версии алгоритма Эвклида является и то, что на каждом шаге используется элементарная и быстрая операция над целыми числами – вычитание. Если допустить операцию вычисления остатка при делении нацело, то число шагов цикла можно существенно уменьшить. Справедливо следующее свойство:

 

Это приводит к следующей схеме:

int temp;

if(n>m) temp = m; m = n; n = temp; //swap(m,n)

while(m != n)

{

temp = m; m = n; n = temp%n;

}

Если немного подумать, то становится ясно, что вовсе не обязательно выполнять проверку перед началом цикла. Это приводит к более простой схеме вычисления НОД, применяемой обычно на практике:

int temp;

while(m != n)

{

temp = m; m = n; n = temp%n;

}

Для вычисления НОК(m, n) можно воспользоваться следующим соотношением:

 

А можно ли вычислить НОК(m, n), не используя операций умножения и деления? Оказывается можно одновременно с вычислением НОД(m,n) вычислять и НОК(m,n). Вот соответствующая схема:

int x = v = m, y = u = n;

while(x != y)

{

if(x > y){  x = x — y; v = v + u;}

else {y = y – x; u = u + v;}

}

НОД = (x + y)/2; НОК = (u+v)/2;

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

 

Это соотношение выполняется после инициализации переменных до начала выполнения цикла. По завершении цикла, когда x и y становятся равными НОД, из истинности инварианта следует корректность схемы. Нетрудно проверить, что операторы тела цикла оставляют утверждение истинным. Детали доказательства оставляются читателям.

Понятие НОД и НОК можно расширить, определив их для всех целых чисел. Справедливы следующие соотношения:

 

Расширенный алгоритм Эвклида

Иногда полезно представлять НОД(m,n) в виде линейной комбинации m и n:

 

В частности вычисление коэффициентов a и b необходимо в алгоритме RSA – шифрования с открытым ключом. Приведу схему алгоритма, позволяющую вычислить тройку – d, a, b – наибольший общий делитель и коэффициенты разложения. Алгоритм удобно реализовать в виде рекурсивной процедуры

ExtendedEuclid(int m, int n, ref int d, ref int a, ref int b),

которая по заданным входным аргументам m и n вычисляет значения аргументов d, a, b. Нерекурсивная ветвь этой процедуры соответствует случаю n = 0, возвращая в качестве результата значения: d = m, a = 1, b = 0. Рекурсивная ветвь вызывает

ExtendedEuclid(n, m % n, ref d, ref a, ref b)

и затем изменяет полученные в результате вызова значения a и b следующим образом:

 

Доказательство корректности этого алгоритма построить нетрудно. Для нерекурсивной ветви корректность очевидна, а для рекурсивной ветви нетрудно показать, что из истинности результата, возвращаемого при рекурсивном вызове, следует его истинность для входных аргументов после пересчета значений a и b.

Как работает эта процедура? Вначале происходит рекурсивный спуск, пока n не станет равно нулю.

В этот момент впервые будет вычислено значение d и значения параметров a и b. После этого начнется подъем и будут перевычисляться параметры a и b.

Задачи

  1. Даны m и n – натуральные числа. Вычислите НОД(m, n). При вычислениях не используйте операций умножения и деления.
  2. Даны m и n – натуральные числа. Вычислите НОК(m, n).
  3. Даны m и n – натуральные числа. Вычислите НОК(m, n). При вычислениях не используйте операций умножения и деления.
  4. Даны m и n – целые числа. Вычислите НОД(m, n). При вычислениях не используйте операций умножения и деления.
  5. Даны m и n – целые числа. Вычислите НОК(m, n). При вычислениях не используйте операций умножения и деления.
  6. Даны m и n – целые числа. Вычислите НОД(m, n). При вычислениях используйте операцию взятия остатка от деления нацело.
  7. Даны m и n – целые числа. Вычислите НОК(m, n). При вычислениях используйте операцию взятия остатка от деления нацело.
  8. Даны m и n – целые числа. Вычислите тройку чисел – (d, a, b), используя расширенный алгоритм Эвклида.
  9. Даны m и n – натуральные числа. Представьте НОД(m, n) в виде линейной комбинации m и n.
  10. Даны m и n – целые числа. Представьте НОД(m, n) в виде линейной комбинации m и n.
  11. Даны m и n – целые числа. Проверьте, являются ли числа m и n взаимно простыми.

Простые числа

Среди четных чисел есть только одно простое число – это 2. Простых нечетных чисел сколь угодно много. Нетрудно доказать, что число N = (p1 * p2 * … * pk) +1, где pi – подряд идущие простые числа, является простым. Так что, если построено k простых чисел, то можно построить еще одно простое число p, большее pk. Отсюда следует, что множество простых чисел неограниченно. Пример: число N = 2*3*5*7 + 1 = 211 является простым числом.

Решето Эратосфена

Как определить, что число N является простым? Если допустима операция N % m, дающая остаток от деления числа N на число m, то простейший алгоритм состоит в проверке того, что остаток не равен нулю при делении числа N на все числа m, меньшие N. Очевидным улучшением этого алгоритма является сокращение диапазона проверки – достаточно рассматривать числа m в диапазоне [2, √N].

Еще в 3-м веке до н.э. греческий математик Эратосфен предложил алгоритм нахождения простых чисел в диапазоне [3, N], не требующий операций деления. Этот алгоритм получил название «Решето Эратосфена». В компьютерном варианте идею этого алгоритма можно описать следующим образом. Построим массив Numbers, элементы которого содержат подряд идущие нечетные числа, начиная с 3. Вначале все числа этого массива считаются невычеркнутыми. Занесем первое невычеркнутое число из этого массива в массив SimpleNumbers – и это будет первое нечетное простое число (3). Затем выполним просеивание, проходя по массиву Numbers с шагом, равным найденному простому числу, вычеркивая все попадающиеся при этом проходе числа. При первом проходе будет вычеркнуто число 3 и все числа, кратные 3. На следующем проходе в таблицу простых чисел будет занесено следующее простое число 5, а из массива Numbers будут вычеркнуты числа, кратные 5. Процесс повторяется, пока не будут вычеркнуты все числа в массиве Numbers. В результате массив SimpleNumbers будет содержать таблицу первых простых чисел, меньших N.

Этот алгоритм хорош для нахождения сравнительно небольших простых чисел. Но если потребуется найти простое число с двадцатью значащими цифрами, то памяти компьютера уже не хватит для хранения соответствующих массивов. Замечу, что в современных алгоритмах шифрования используются простые числа, содержащие несколько сотен цифр.

Плотность простых чисел

Мы показали, что число простых чисел неограниченно. Понятно, что их меньше, чем нечетных чисел, но насколько меньше? Какова плотность простых чисел? Пусть π(n) – это функция, возвращающая число простых чисел, меньших n. Точно задать эту функцию не удается, но для нее есть хорошая оценка. Справедлива следующая теорема:

 

Функция π(n) асимптотически сверху приближается к своему пределу, так что оценка дает слегка заниженные значения. Эту оценку можно использовать в алгоритме решета Эратосфена для выбора размерности массива SimpleNumbers, когда задана размерность массива Numbers, и, наоборот, при заданной размерности таблицы простых чисел можно выбрать подходящую размерность для массива Numbers.

Табличный алгоритм определения простоты чисел

Если хранить таблицу простых чисел SimpleNumbers, в которой наибольшее простое число равно M, то достаточно просто определить является ли число N, меньшее M2, простым. Если N меньше M, то достаточно проверить, находится ли число N в таблице SimpleNumbers. Если N больше M, то достаточно проверить, делится ли число N на числа из таблицы SimpleNumbers, не превосходящие значения √N. Понятно, что если у числа N нет простых множителей, меньших √N, то число N является простым.

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

Тривиальный алгоритм

Если N – нечетное число, то проверить, что оно является простым, можно на основе определения простоты числа. При этом не требуется никакой памяти для хранения таблиц чисел, но, как всегда, выигрывая в памяти, проигрываем во времени. Действительно, достаточно проверить, делится ли нацело число N на подряд идущие нечетные числа в диапазоне [3, √N]. Если у числа N есть хоть один множитель, то оно составное, иначе – простое.

Все рассмотренные алгоритмы перестают эффективно работать, когда числа выходят за пределы разрядной сетки компьютера, отведенной для представления чисел, так что если возникает необходимость работы с целыми числами, выходящими за пределы диапазона System.Int64, то задача определения простоты такого числа становится совсем не простой. Существуют некоторые рецепты, позволяющие определить, что число является составным. Вспомним хотя бы известные со школьных времен алгоритмы. Если последняя цифра числа делится на 2, то и число делится на 2. Если две последние цифры числа делятся на 4, то и число делится на 4. Если сумма цифр делится на 3 (на 9), то и число делится на 3 (на 9). Если последняя цифра рана 0 или 5, то число делится на 5. Математики затратили много усилий, доказывая, что то или иное число является (или не является) простым числом. Сейчас есть особые приемы, позволяющие доказать, что числа некоторого вида являются простыми. Наиболее подходящими кандидатами на простоту являются числа вида 2p -1, где p – это простое число. Например, доказано, что число 219937 — 1, имеющее более 6000 цифр, является простым, но нельзя сказать, какие простые числа являются ближайшими соседями этого числа.

Задачи

  1. Дано целое N. Используя алгоритм решета Эратосфена, найдите все простые числа, меньшие N.
  2. Дано целое N. Используя алгоритм решета Эратосфена, найдите N первых простых чисел.
  3. Дана таблица, содержащая N первых простых чисел. По заданному n < N вычислите разность между функцией π(n) и ее оценкой – n/ln(n).
  4. Дана таблица, содержащая N первых простых чисел. Используя табличный алгоритм, вычислите все простые числа в диапазоне [M+1, M*M], где M – наибольшее простое число, хранимое в таблице.
  5. Дано целое N. Постройте таблицу, содержащую N первых нечетных простых чисел. Используйте табличный алгоритм с постепенным заполнением таблицы, начиная со случая, когда в ней хранится только одно простое число 3.
  6. Дано число N. Определите, является ли оно простым, используя тривиальный алгоритм.

Дано число N. Определите его первый простой множитель, если он существует.

Проекты

  1. Построить класс «Температура», позволяющий задавать температуру в разных единицах измерения. Построить Windows проект, поддерживающий интерфейс для работы с классом.
  2. Построить класс «Расстояния», позволяющий использовать разные системы мер. Построить Windows проект, поддерживающий интерфейс для работы с классом.
  3. Построить класс «Простые числа». Построить Windows проект, поддерживающий интерфейс для работы с классом.
  4. Построить класс «Системы счисления». Построить Windows калькулятор, поддерживающий вычисления в заданной системе счисления.
  5. Построить класс «Рациональные числа». Построить Windows калькулятор, поддерживающий вычисления с этими числами.
  6. Построить класс «Комплексные числа». Построить Windows калькулятор, поддерживающий вычисления с этими числами.

Скачать лекцию 1.5