Что такое функция в алгоритмическом языке
Перейти к содержимому

Что такое функция в алгоритмическом языке

  • автор:

7.19. Что такое стандартная функция?

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

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

Таблица стандартных функций школьного алгоритмического языка

Название и математическое обозначение функции

Абсолютная величина (модуль)

Экспонента (степень числа е ~ 2.72)

Знак числа x ( — 1, если х 0)

Целая часть х (т.е. максимальное целое число,не превосходящее х)

Минимум из чисел х и y

Максимум из чисел х и y

Частное от деления целого х на целое y

Остаток от деления целого х на целое y

Случайное число в диапазоне от 0 до х — 1

Синус (угол в радианах)

Косинус (угол в радианах)

Тангенс (угол в радианах)

Котангенс (угол в радианах)

Арксинус (главное значение в радианах)

Арккосинус (главное значение в радианах)

Арктангенс (главное значение в радианах)

Арккотангенс (главное значение в радианах)

В качестве аргументов функций можно использовать константы, переменные и выражения. Например:

sin ( 3.05 ) min ( a, 5)

sin ( x ) min ( a, b )

sin ( 2 * y + t / 2 ) min ( a + b , a * b )

sin((exp(x) + 1) ** 2) min(min(a, b), min(c, d))

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

7.20. Как записываются арифметические выражения?

Арифметические выражения записываются по следующим правилам:

  • Нельзя опускать знак умножения между сомножителями и ставить рядом два знака операций.
  • Индексы элементов массивов записываются в квадратных (школьный АЯ, Pascal) или круглых (Basic) скобках.
  • Для обозначения переменных используются буквы латинского алфавита.
  • Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, потом умножение и деление и в последнюю очередь — сложение и вычитание.
  • Операции одного старшинства выполняются слева направо. Однако, в школьном АЯ есть одно исключение из этого правила: операции возведения в степень выполняются справа налево. Так, выражение 2**(3**2) в школьном АЯ вычисляется как 2**(3**2) = 512. В языке QBasic аналогичное выражение 2^3^2 вычисляется как (2^3)^2 = 64. А в языке Pascal вообще не предусмотрена операция возведения в степень, в Pascal x^y записывается как exp(y*ln(x)), а x^y^z как exp(exp(z*ln(y))*ln(x)).

Функции в языках объектно-ориентированного и алгоритмического программирования (9 класс)

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

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

Математические функции.
В языке Visual Basic 2005 математические функции реализуются с помощью методов: синус Math.Sin ( ), косинус Math.Cos ( ), квадратный корень Math.Sqrt ( ) и др.

В языке Gambas и языке OpenOffice.org Basic математические функции реализуются с помощью числовых функций: синус Sin ( ), косинус Cos ( ), квадратный корень Sqr ( ) и др .

Строковые функции.
В строковых функциях строками являются либо аргументы, либо возвращаемые функциями значения. В языке Visual Basic 2005 и языке OpenOffice.org Basic строковые функции оперируют данными в кодировке Unicode, а в языке Gambas — в кодировке ASCII.

Функция вырезания левой подстроки Left ( ).
В функции вырезания подстроки (части строки) Left (Строка, Длина) значением функции является левая подстрока. Подстрока начинается от крайнего левого символа аргумента Строка и имеет количество символов, равное значению числового аргумента Длина.

Функция вырезания правой подстроки Right ( ).
В функции вырезания подстроки Right (Строка, Длина) значением функции является правая подстрока. Подстрока начинается от крайнего правого символа аргумента Строка и имеет количество символов, равное значению числового аргумента Длина.

Функция вырезания произвольной подстроки Mid ( ).
В функции вырезания подстроки Mid (Строка, Позиция, Длина) значением функции является подстрока. Подстрока начинается с символа аргумента Строка, позиция которого задана числовым аргументом Позиция, и имеет количество символов, равное значению числового аргумента Длина.

Функция определения длины строки Len ( ).
В функции определения длины строки Len (Строка) аргументом является строка Строка, а возвращает функция числовое значение длины строки (количество символов в строке).

Функция Asc ( ).
Функция Asc (Строка) осуществляет преобразование строки в числовой код ее первого символа. Аргументом функции является строка, а значением — число.

Функция Chr ( ).
Функция Chr (Число) осуществляет преобразование числового кода в символ. Аргументом функции является число, а значением — символ.

Строковые функции и их значения

Функции ввода/вывода данных.
В Visual Basic 2005 и в языке OpenOffice.org Basic для ввода данных может использоваться функция InputBox ( ), которая позволяет вводить данные с помощью диалогового окна ввода.

Аргументами этой функции являются две строки: «Сообщение» и «Заголовок», а значением функции является строка, введенная пользователем в текстовое поле:
А = InputBox («Сообщение», «Заголовок»)

Если пользователь введет строку в текстовое поле и щелкнет по кнопке ОК, то значением функции станет строка, введенная пользователем в окно ввода функции текстовое поле. Если пользователь щелкнет по кнопке Отмена, то значением функции станет пустая строка » «.

Диалоговое окно InputBox

В языке Visual Basic 2005 и в языке OpenOffice.org Basic для вывода данных может использоваться функция MsgBox ( ). Эта функция позволяет выводить сообщения с помощью окна сообщений, на котором можно разместить определенный набор кнопок и информационный значок о типе сообщения:
MsgBox («Сообщение» [, ЧисКод1 +ЧисКод2] [,»Заголовок»])

Аргумент «Сообщение» выводится в окне сообщений, аргумент ЧисКод1 + ЧисКод2 определяет внешний вид окна, а строка «Заголовок» выводится в строке заголовка окна. Последние два аргумента не являются обязательными.

Необязательные части программного кода заключаются в квадратные скобки.

Например, для функции MsgBox («Сообщение» , 48 + 3, «Заголовок») будет выведено следующее окно сообщений.

Диалоговое окно MsgBox

Значение, возвращаемое функцией MsgBox ( ) , зависит от того, какая из кнопок на окне сообщений была нажата.

Значения функции MsgBox

Однако в языке OpenOffice.org Basic для вывода данных часто до сих пор используется оператор Print, который выводит строки или числовые выражения, разделенные запятой или точкой с запятой, в диалоговом окне.

В языках Visual Basic 2005 и Gambas для ввода и вывода данных чаще используются элементы управления графического интерфейса. Для ввода данных используется элемент управления текстовое поле TextBox, а для вывода данных — элемент управления метка Label1.

Функции даты и времени.
В языках Visual Basic 2005 и Gambas и в языке OpenOffice.org Basic существуют функции даты и времени. Для определенности рассмотрим функции даты и времени, принятые в языке Visual Basic 2005.

Функция Today возвращает значение текущей даты, которое можно присвоить переменным типа Date. Значение даты представляется в виде тройки чисел #Число/Месяц/Год#, разделенных знаком «/» .

Функция Timeofday возвращает значение текущего времени типа String, которое можно вывести на надпись. Значение времени представляется в виде тройки чисел #Часы: Минуты: Секунды#, разделенных знаком «:».

Функция Now одновременно возвращает значение текущей даты и текущего времени.

Функция DateDiff (Dateinterval.Day, Dat1, Dat2) возвращает разность значений аргументов Dat1 , Dat2, равную количеству дней между датами. Первый аргумент Dateinterval.Day задает единицу измерения времени.

Контрольные вопросы:

  1. Какой тип данных могут иметь аргументы и возвращаемые значения математических функций?
  2. Какой тип данных могут иметь аргументы и возвращаемые значения строковых функций?
  3. Какой тип данных могут иметь аргументы и возвращаемые значения функций ввода и вывода?
  4. Какой тип данных могут иметь аргументы и возвращаемые значения функций даты и времени?

Об объектах, описываемых формулами в алгоритмическом языке Текст научной статьи по специальности «Математика»

Предлагаются определение операции с передаваемой переменной ( F-операции ) и определение суперпозиции таких операций. Определяется процесс вычисления суперпозиции , в котором допустимо промежуточное преобразование переменных. Строится синтаксис текстовых описаний суперпозиций и осуществляется расширение простейшего языка описания алгоритмов с использованием F-операций .

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Фрумкин А. М.

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

Текст научной работы на тему «Об объектах, описываемых формулами в алгоритмическом языке»

ОБ ОБЪЕКТАХ, ОПИСЫВАЕМЫХ ФОРМУЛАМИ В АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ

© 2015 А. М. Фрумкин

ст. науч. сотрудник кафедры математического анализа и прикладной математики, канд. техн. наук, e-mail: frumkinamamail. ru

Курский государственный университет

Предлагаются определение операции с передаваемой переменной (F-операции) и определение суперпозиции таких операций. Определяется процесс вычисления суперпозиции, в котором допустимо промежуточное преобразование переменных. Строится синтаксис текстовых описаний суперпозиций и осуществляется расширение простейшего языка описания алгоритмов с использованием F-операций.

Ключевые слова: F-операция, операция присваивания, суперпозиция, функция подстановки, дерево суперпозиции, правильная нумерация, вычисление суперпозиции, выражение.

Ранее автором статьи [Фрумкин 2014] было предложено определение формального языка как математической структуры, включающей в качестве компонентов множество описываемых объектов и семантическое отображение. Был дан вариант определения вычислительного алгоритма как композиции вычислительных операций и вариант простейшего языка для описания алгоритмов. Возможности рассматриваемого языка оказались ограниченными. Например, в нем отсутствовали формулы как инструмент описания композиций операций и, соответственно, операторы присваивания. Для того чтобы ввести в язык формулы, необходимо, чтобы на нем можно было описывать операции, ссылки на которые изображаются так же, как функции в математике. Это операции с выделенной переменной, значение которой функционально зависит от остальных. В такой форме операция определяется в большинстве языков высокого уровня. Это «процедура-функция» в языке «Паскаль» [Фаронов 1998], «функция» в языках C\C++ [Павловская 2013], «функция» в языке «Matlab» [Дьяконов 1999] и т.д. При этом в каждом языке понятие «функция» имеет свои смысловые особенности.

В данной статье в терминологии работы [Фрумкин 2014] дается формальное определение F-операции — аналога понятия процедуры-функции и исследуются возможные интерпретации суперпозиции F-операций. Таким образом, статья продолжает исследование процесса построения алгоритмического языка.

1. Обобщение определения ссылки на операцию

Определение 1. Пусть p=(Q,T,f) — вычислительная операция. Переменную aeQ назовем независимой или входной переменной операции p, если значение этой переменной после выполнения операции всегда совпадает с ее значением до выполнения операции.

Формально: V xeDm(f)eQAT [f(x)]a=xa. Переменную aeQ назовем строго зависимой или выходной переменной операции p, если значение этой переменной после выполнения операции не зависит от ее значения до выполнения операции.

[ х^((а,и)>еБш(0 л х^ еБшф ] ^ [Г(хи)]а = [Г(хи)]а. Переменную аеО назовем обычной, если множество содержит более одного элемента.

Утв. 1. Обычная переменная не может быть одновременно и входной и выходной.

^ Пусть переменная а одновременно входная и выходная. Пусть хе(0\)ЛТ, иеТ(а), уеТ(а) и и^у. Так как переменная выходная, то [Г(х^)]а = [Г(х^)]а. Так как переменная входная, то [Г(х^)]а=[х^]а=и и [Дх^)]а=[х^]а=у, то есть и=у, ■. ►

Определение 2. Пусть (О,Т) и (Л,8) — области переменных, Л и О -непересекающиеся множества: ЛпО=0. Функцию назовем подстановкой

переменных, если УаеО Т(а)=Б(^(а)).

Функция подстановки переменных не обязательно инъективна. Пусть р=(О,Т,Г) -операция и множество О упорядочено. Используя отношение порядка на О, определим вычислительную операцию (Н^^), определенную операцией р и функцией подстановки Положим Н=^(О) и 0=БН — сужение Б на Н.

Область определения g Бш(§)= < х е HЛQ: еDш(f)>. Для вычисления значения g на наборе xеDш(g) определим набор у= и вычислим z=f(y). Для каждой переменной РеН найдем а=шт Положим ир=2а. В результате получим набор значений иеНЛБ, который и будем считать значением функции g.

2. Операции с передаваемой переменной Определение 3. Операцией с передаваемой переменной (Б-операцией) назовем кортеж (О,Т,£,л:), в котором О — конечное множество внутренних переменных, л:1О -передаваемая (внешняя) переменная, Т — семейство множеств (типов) с областью индексов О^, Г Dm(f)e ОЛТ^(О^)ЛТ.

Функцию Го: хе Dш(f)^f(x)Q назовем внутренним преобразованием Б-операции. Функцию Г1=)ЛТ: хОе Dш(f) л у= Г(хО)и > назовем полным преобразованием Б-операции.

Б-операцию назовем простой, если все переменные аеО являются входными относительно операции (О^,Т,Г1), или, иными словами, если £ — тождественное отображение на своей области определения. Простая Б-операция определяет внешнюю функцию, то есть функцию, которая набору значений внутренних переменных ставит в соответствие значение передаваемой переменной.

Определение 4. Операцией присваивания, порожденной Б-операцией (О,Т,£,л:) и переменной а называется операция (Л,Б^) с компонентами:

Л=Ои, Б=Т^ и g=< (х,у): хеЛЛБ л xQеDш(f) л у=<(Р,1): (реО\л 1= [Г(хп)]р ) V (р=а л 1= [АМ]*) > >. В определении функции g набор хО обозначает сужение х на множество переменных О. Определение применимо как для случая а1О, так и для случая аеО. В последнем случае в процессе вычисления функции g значение а, вычисленное с помощью функции заменяется на значение внешней переменной л, вычисленное с помощью функции Г Из определения следует, что а является выходной переменной операции присваивания. 3. Композиции суперпозиции для операций с передаваемой переменной Б-операции можно использовать для того, чтобы ввести в алгоритмический язык формулы (алгебраические выражения) и сформулировать правила их интерпретации. Рассмотрим пример формулы:

В ней A обозначает операцию или F-операцию, B и C обозначают некоторые F-операции, x, у, z обозначают переменные. Множества переменных, участвующих в определении операций A, B, C, в формуле никак не обозначены, потому что переменные x, у, z «подставлены» на место этих переменных. Место подстановки определяют позиции между запятыми. Более того, на место двух переменных, участвующих в определении операции A, подставлены обозначения F-операций B и C. Это означает, что при вычислении по формуле мы должны сначала вычислить B(x,y) и С(у^) и затем подставить результирующие значения их внешней переменной л в формулу для А. Но в общем случае переменная х может измениться при вычислении В(х,у), а переменная у -при вычислении С(у^). Поэтому результат зависит от порядка вычислений. Далее рассматривается модель, согласно которой может интерпретироваться формула общего вида, и выбирается один из вариантов вычисления согласно данной модели.

Определение 5. Пусть (Л,Б) — область переменных, Р — множество уже определенных F-операций. Суперпозицией F-операций над областью переменных (Л,Б) назовем кортеж ^^^,ш,£,г), в котором F — конечное непустое множество позиций F-операций, V — конечное непустое множество позиций переменных, FnV=0, —

семейство F-операций, ш^^-Л — семейство переменных, P=FoV — функция

Функция g каждой позиции pеF автоматически ставит в соответствие все атрибуты F-операции g(p): О, Т, Г, л. При описании свойств функции подстановки придадим каждому символу функциональный смысл, то есть будем считать, что мы задали семейства О, Т, Г, л с одной и той же областью индексов F. Функция подстановки обладает следующими свойствами.

1) Для каждой позиции pеF и аеОр если £(p,а)еF, то Т£(р,а)(л£(р,а))=Тр(а), а если ^(р,а)е^ то Б(ш(£(р,а)))=Тр(а). Это свойство назовем свойством согласованности типов.

2) Существует единственная позиция геР, которая не является образом подстановки.

3) Функция £ инъективна: VpеF (аеОрлРеОрла^Р)^£(р,а)^£(р,Р); Vp,qеF р^ ^ V аеОр VpGОq £(р,а)^ £(^р).

4) Маршрутом подстановки £ длины п назовем последовательность р:[1..п]^Р, обладающую свойством V те[1..п-1] pmеFл Зае Орт ■ рт+1=£(рт,а). У функции подстановки отсутствуют циклические маршруты, то есть маршруты, в которых повторяются позиции.

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

Утв. 2. Пусть — суперпозиция. Определим отношения

1) оба отношения являются функциями;

2) тройка (Р,г^) является деревом [Новиков 2011], то есть Бт(^=Р\ и VqеDm(h) ЗnеN : ^(ф=г;

3) множество V есть множество терминальных узлов дерева.

^ Пусть (р^) е h л(р^) еhлq^s.

Тогда ЗaеОq, РеО./ р=£^,а), р=£^,Р). Так как £ инъективна, из q^s следует, что р^р, ■. Следовательно, h — функция.

Пусть (р,а)е9л (р,Р)е9. Тогда найдутся £(дьа)=рл£(дьР)=р. Так как £ -инъективна, то я^гл а=р. Таким образом, (р,а)е9л (р,Р)е9 ^а=Р, то есть 9 является функцией.

Из определения функции И следует, что область определения И совпадает с образом функции подстановки, то есть по свойству 2) функции £, От(Ь)=Р\. Возьмем любую позицию де Бт(Ь). Пусть для некоторого п>1 Ьп(д)=8. Если б^г, то 8еБт(Ь) и найдется 1еР: 1= Ип1(д). Если не найдется такого п, что Ип(д)=г, то последовательность Ип(д) — бесконечна. Но тогда в ней обязательно встретится повторяющийся элемент, то есть у функции £ найдется циклический маршрут, И. Следовательно, найдется такое натуральное п, что Ип(д)=г, то есть (Р,г,И) — дерево.

Если позиция ре У, то на ней не определена функция £, то есть р — терминальная позиция. Обратно, если р — терминальная позиция, то на ней не определена функция £, то есть реУ. ►

Определение 6. Дерево, определенное в последнем утверждении, назовем деревом суперпозиции. Для реБ наследников р, принадлежащих Б, назовем Б-наследниками, а наследников р, принадлежащих У, назовем У-наследниками. Для реР\ позицию И(р) будем называть родительской позицией позиции р, а переменную 9(р) — родительской переменной позиции р.

В определении суперпозиции участвуют множество переменных ш(У)^Л и семейство множеств переменных Ор, реБ. Переменные из множеств Ор будем называть формальными. Переменные из множества ю(У) будем называть фактическими. Определим Б-операцию с множеством переменных ю(У), задаваемую суперпозицией, описав процесс ее вычисления. При этом формальные переменные будем использовать для «хранения» промежуточных результатов.

Если (Б,§,У,ш,£,г) — суперпозиция, то для каждой позиции реБ множество Ор делится на два непересекающихся подмножества:

множество У-переменных Бр= и множество Б-переменных Ур=.

Определение 7. Элементарной операцией вычисления суперпозиции (Б,§,У,ш,£,г) в позиции реБ\ назовем операцию (Е^^) со следующими компонентами.

Множество переменных Е включает родительскую переменную 9(р), множество подставляемых переменных [шо£(р,-)](Др) (образ множества У-переменных) и множество Б-переменных Ур, то есть Б=^ [шо£(р,-)](Др)о> Ур.

Семейство типов Q определяется теми типами переменных из Е, которые определены моделью суперпозиции.

Вычислительное преобразование w осуществляется в следующей последовательности. Пусть хеЕ^. Сначала каждой переменной аеДр ставим в соответствие значение переменной шо£(р,а)е[шо£(р,-)](Др). В результате получаем набор значений переменных уеОрЛТр. Затем осуществляем вычисление ъ=Гр(у)е(Оро>)лтр. Далее для каждой переменной Ре[шо£(р/)](Др) найдем а=тт и положим ир=ъа. В результате получим набор значений ие[шо£(р,-)](Др)л8. Дополним этот набор сужением функции ъ на множество Б-переменных Ур и парой (9(р),г^). В результате получим набор значений w(x)е EЛQ.

Определение 8. Элементарной операцией вычисления суперпозиции (Б,§,У,ш,£,г) в позиции р=г назовем операцию с передаваемой переменной (Е^^,л:г), компоненты кортежа которой определяются так. Множество переменных Е=[шо£(г,-)](Дг)о> Уг. Семейство типов Q определяется теми типами переменных из Е, которые определены моделью суперпозиции.

При вычислении w(x) для xeEAQ сначала каждой переменной аеЛр ставим в соответствие значение переменной шо^(р,а)е[шо^(р,-)](Лр). В результате получаем набор значений переменных yeQrATr. Затем осуществляем вычисление z=fr(y)e(Qr^)ATr. Далее для каждой переменной Ре[шо^(р,-)](Лр) найдем а=шт и положим up=za. В результате получим набор значений ие[шо^(р,-)](Лр)А8. Дополним этот набор u сужением функции z на множество Yr^). В результате получим набор значений w(x)e (E^)AQ.

Для того чтобы описать последовательность вычислений, добавим в каждый из типов формальных переменных элемент е. Готическая буква «е» здесь означает «етр1у», то есть «пустой». Если набор значений xeQ^Tf, таков, что для какой-то переменной a xa=e, то xIDmfj,). Будем считать, что до начала вычисления суперпозиции заданы начальные значения переменных из ra(V), а все формальные переменные имеют значение е.

Определение 9. Пусть в множестве F n элементов и р:[1..п]оБ — нумерация множества F. Набор значений переменных xera(V)AS назовем допустимым для данной нумерации, если можно последовательно выполнить элементарное вычисление в позициях р1з р2, . рп.

Утв. 3. Для того чтобы набор xgq(V)aS был допустим для нумерации, необходимо, чтобы согласно данной нумерации каждой позиции предшествовали все ее F-наследники.

^ Любая формальная переменная aeQq может изменить свое исходное значение е только в случае, если выполнена элементарная операция в позиции ^(q,a). Если позиция ^(q,a) расположена в последовательности р после q, то при достижении в процессе вычисления позиции q окажется, что значение переменной a равно е. ^

Определение 10. Если согласно нумерации F-позиций суперпозиции каждой позиции предшествуют все ее F-наследники, то данную нумерацию назовем правильной.

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

^ Пусть нумерация правильная. Пусть q и s — две F-позиции, причем q -потомок s. Если q — наследник (непосредственный потомок) s, то, в силу правильности нумерации, s располагается после q. Если q не является наследником s, то воспользуемся индукцией по расстоянию от q до s. Позиция h(q) располагается после q в силу правильности нумерации, а s располагается после h(q) по предположению индукции. Следовательно, s располагается после q.

Обратно, если каждая позиция располагается после всех своих потомков, то, в частности, каждая позиция располагается после своих F-наследников. ^

Утв. 5. Если нумерация F-позиций является правильной, то первая позиция не имеет F-наследников, а последняя позиция является корневой.

^ Если бы первая позиция имела F-наследника, то этот наследник должен был бы располагаться перед первой позицией, И. Вторая часть утверждения является прямым следствием предыдущего утверждения. ^

Определение 11. F-операцией, порожденной суперпозицией (F,g,V,Q,^,r), и правильной нумерацией p:[1..n]oF множества F назовем кортеж (ra(V), Sro(V), w, л:г) в котором функция преобразования w определяется так. Dm(w) — множество допустимых для нумерации р наборов значений xgq(V)aS. Для допустимого набора значений x результатом преобразования является набор значений ye(ra(V)^)AS и значение

переменной л:г, полученное после выполнения всех элементарных процедур в позициях Pl, P2, . Pn.

Утв. 6. Пусть (Р^^,ш,Ъ,г) — суперпозиция и p:[1..n]oF — правильная нумерация. Возьмем позицию qeF\. Обозначим через F’ множество F-позиций, достижимых из позиции q, через V’ множество V-позиций, достижимых из позиции q, Пусть P’= V’, g’, ш’,Ъ’ — сужения функций g,ш,Ъ на множества F’, V’, F’®Q соответственно. Тогда — суперпозиция и нумерация множества F’, порожденная p, является

^ Так как Ъ’ есть сужение Ъ, то Ъ’ инъективна и обладает свойствами согласованности типов. Кроме того, не существует циклических маршрутов относительно Ъ’. Позиция q не является образом функции Ъ’. В противном случае существовал бы циклический маршрут. Таким образом, все свойства функции Ъ повторяются для функции Ъ’ , и q есть корневая позиция.

Утв. 7. Если все F-оперaции в суперпозиции просты, то любая правильная нумерация порождает одну и ту же простую F-оперaцию.

^ Воспользуемся индукцией по высоте дерева суперпозиции. Пусть утверждение верно для деревьев высоты, не большей п>2. Рассмотрим суперпозицию высоты п+1.

Корневая F-оперaция простая. Ее передаваемое значение определяется значениями ее V- и F-переменных и она не изменит значений переменных. Все F-поддеревья корня задают суперпозиции высоты, не превышающей п. Правильная нумерация позиций исходной суперпозиции определяет правильные нумерации поддеревьев. Поэтому по предположению индукции при любой нумерации значения одноименных F-переменных для коневой функции будут одинаковы. Но и значения V-переменных одинаковы и равны исходным значениям, потому что ни одна F-оперaция поддерева их не изменила. Следовательно, преобразуемый набор переменных коневой функции не зависит от нумерации. ^

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

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

4. Синтаксис выражений Синтаксические конструкции, описывающие суперпозиции в формальном языке, называют выражениями. Опишем грамматику [Ахо, Ульман 1978] выражений, которая может быть использована для усовершенствования языка из статьи [Фрумкин 2014]. Будем использовать метасимволы, определенные в упомянутой статье. Частным случаем

суперпозиции будем считать константы и переменные. Простейшая грамматика строится с помощью следующих предложений. ::= | | $ ::= ()$

Более сложная грамматика выражений, содержит обозначения алгебраических операций. С точки зрения построения алгоритмического языка алгебраические операции — это некоторые выделенные простые F-операции, для обозначения которых предусмотрены специальные символы сложения, вычитания, умножения, деления и т.д. ::= | $ ::= | ^суперпозици^ () $

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

5. Расширение алгоритмического языка с использованием выражений

Объектами, описываемыми усовершенствованным алгоритмическим языком, являются композиции операций и F-операций, которые определяют как эквивалентные операции, так и F-операции. Если в усовершенствованном языке используются различные типы данных, то заголовок процедуры, посвященной F-операции, отличается от заголовка процедуры, посвященной обычной операции, описанием типа внешней переменной. Но в нашем простейшем языке используется только один тип (целые числа), поэтому заголовок процедуры, посвященной F-операции, будет совпадать с заголовком процедуры, посвященной обычной операции. Описания операций и F-операций будут отличаться не заголовками, а наличием некоторой конструкции внутри текста. Можно предложить два варианта такой конструкции — конструкцию «return», возвращающую значение внешней переменной, или конструкцию присваивания внешней переменной ее значения. В последнем варианте фиксированное имя внешней переменной становится зарезервированным словом, таким же как «if», «while» и др. Выберем второй вариант и для обозначения внешней переменной выберем слово «passed» ( передаваемая ).

Новая версия языка отличается от версии [Фрумкин 2014] следующими особенностями:

1) в описателях if-композиций и while-композиций кроме имени управляющей переменной можно указать выражение, описывающее суперпозицию с результирующей F-операцией;

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

Далее приводится часть грамматики, связанная описанными изменениями. ::= if # (< выражение >^) # #end | if # # # else #end $

::= passed = ;$ ::= =; $ К данному набору правил добавляется более сложный вариант грамматика выражений с обозначениями алгебраических операций из предыдущего пункта.

Определение переменной — это частный случай присваивания, поэтому в новой версии языка не нужно правило:

::= =< целое число>; Элементарная операция копирования также описывается как операция присваивания. Нет упоминания ссылки, потому что понятие выражения обобщает ссылку. Элементарные операции арифметических действий описываются с помощью алгебраических выражений со стандартными обозначениями этих операций: «+», «-», «*», «/».

Приведем примеры описаний простейших алгоритмов на модифицированном

Factorial (x) % вычисление факториала положительного числа x passed=1; m=1;

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

IsSimple(x) % простое ли положительное число x ? y=2; passed=1;

Приведем также пример, иллюстрирующий рассуждения из п. 3. Рассмотрим четыре вычислительных процедуры. A(x,y,z)passed=x+y+z; end B(x) x=x+2; passed =1; end C(x,y) x=x+1; passed=1; end D(x) x=xA2; passed=1; end Проанализируем процесс вычисления выражения A(x,B(x),C(x,D(x))). Согласно стандартной нумерации позиций (стандартному обходу дерева суперпозиции) процедуры выполняются в последовательности: D, B, C, A. При начальном значении x=2 результатом выполнения суперпозиции будет число 9. Если же принять другой допустимый обход, например B, D, C, A, то результатом будет число 19.

АхоА., УльманДж. Теория синтаксического анализа, перевода и компиляции. Т. 1 Синтаксический анализ. М.: Мир, 1978. 612 с.

Дьяконов В.П., Абраменкова И.В. MATLAB 5.0/5.3. Система символьной математики. М.: Нолидж, 1999. 640 с.

Новиков Ф.А. Дискретная математика. СПб.: Питер, 2011. 384 с.

Павловская Т.А. C/C++. Программирование на языке высокого уровня. СПб.: Питер, 2013. 461 с.

Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М.: Нолидж, 1998. 516 с.

Программирование на алгоритмическом языке

Информатика, информационные технологии

Занятие 1 -2Выражения. Виды операций. Стандартные функции.

Задание 1. Записать выражения

X4
Log2x/5
|a+bx|
E|x-y|

Задание2 . Записать в общепринятом виде

(-d+sqrt(sqr(d)-4*a*b))/(2*a)
Arctan(y2-a)/2*abs(x4-ln(5)*y5)/exp(-1)

Задание 3. Вычислить выражение

Задание4. Указать порядок операций

A and b or not c and d

Задание5 .Записать выражение

X принадлежит отрезку [2,5] или [-1,1]

Задание 6. Каково назначение функций?

FloatToStrF(n, f , k,m)
FloatToStr (n)
StrToInt (s)
StrToFloat (s)
Round (n)
Trunc (n)
Frac(n)
Int (n)
Chr(n)
IntToStr (k)
Ехр(n)
Ln(n)
Rardom(n)
Аbs (n)

ПРИЛОЖЕНИЕ 3. Математические формулы

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

Функция Соотношение Соотношение на языке ObjectPascal
Ln(x)/Ln(a)
Exp(a*Ln(x))
Sin(x)/Cos(x)
Cos(x)/Sin(x)
ArcTan(Sqrt(x/(1-sqr(x))))
Pi/2- ArcTan(Sqrt(x/(1-sqr(x))))
Pi/2-ArcTan(x)
(Exp(x)-Exp(-x))/2
(Exp(x)+Exp(-x))/2
1/Sin(x)
1/Cos(x)

Занятие1 . Операторы условного и безусловного перехода

Задание1. Указать ошибки

Else begin x:=0; y:=y+1 end;

Задание 2 Есть ли в программе пустой оператор?

Begin a:=true; ; b:=b or a end;

Beginif x=0 then goto 1; y:=x; 1: end

Задание 3. Записать на языке выражение , соответствующее рисунку (см. номер варианта)

Задание 4 . Рассмотреть программу вычисления стоимости междугородного телефонного разговора.

Как известно, стоимость междугородного разговора по телефону в выходные дни ниже, чем в обычные. Программа, текст которой приведен в листинге 2.1, запрашивает длительность разговора и день недели, а затем вычисляет стоимость разговора. Если день недели — суббота или воскресенье, то стоимость уменьшается на величину скидки. Цена минуты разговора и величина скидки задаются в тексте программы как константы. Вид диалогового окна программы приведен на рис. 2.4.

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

Рис. 2.4.Диалоговое окно программы Стоимость разговора

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

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

Статьи к прочтению:
  • Программирование обработки по заданному контуру в коде iso-7
  • Программирование плк ge fanuc семейства versamax. разработка системы автоматического регулирования температуры печи.

Язык программирования Кумир. Урок 1

Похожие статьи:
  • Понятие языка программирования. классификация языков программирования. Физические принципы работы электронных устройств ЭВМ таковы, что компьютер может воспринимать команды, состоящие только из единиц и нулей, т. е. машинный…
  • Характеристика языка программирования паскаль Одним из наиболее популярных языков программирования является язык Паскаль. Первая версия языка программирования Паскаль была разработана на кафедре…

Добавить комментарий

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