Салават 2008

Данное руководство призвано оказать помощь при выполнении лабораторных работ по курсу “Информатика” студентами очной и очно-зачной форм обучения.

В методическом указании рассматриваются вопросы,связанные с построением алгоритмом решения задач №1-7 курса “Информатика”,приводятся примеры практической реализации на языке Бейсик.

Автор: доцент,кандидат физико-математических наук

Кузьминых Павел Владимирович.

Общие положения.

Список лабораторных работ по курсу

“ Информатика “

Часть I. Программирование на ЭВМ.

1. Простейшие вычисления на ПЭВМ.Программирование арифметических выражений.

2. Программирование арифмерических циклов.

3. Программирование разветвляющихся вычислительных процессов.

4. Суммирование рядов на ЭВМ.

5. Программирование матричных операций.

6. Построение графиков функций, заданных параметрически.

7. Построение движущихся графических объектов.

По результатам выполнения лабораторной работы оформляется отчет. Каждый отчет начинается с титульного листа. Описательная часть отчета содержит:

· задание

· блок-схему вычислительного процесса

· текст программы

· результаты расчета

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

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

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

Программирование арифметических выражений.

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

Ниже приведена таблица арифметических функций.

Наименование	Обознач. /Обращение
Модуль числа	Abs x	ABS(X)
Экспонента числа	ex	EXP(X)
Натуральный логарифм	Ln x	LOG(X)
Корень квадратный	Ö x	SQR(X)
Арктангенс угла	Arctg x	ATN(X)
Косинус угла	Cos x	COS(X)
Синус угла	Sin x	SIN(X)
Тангенс	Tg x	TAN(X)

Другие математические функции записываются через вышеперечисленные. Так для вычисления логарифма числа по основанию A применяется формула приведения

Ln x

Log_A x= -----

Ln A

Для тригонометрических функций угловая мера берется в радианах.

Не лишним кажется и напоминание о порядке выполнения математических операций при вычислении выражений.

1. В математических выражениях внутри скобок или между скобками действия выполняются в следующей последовательности (приоритет операций):

· вначале вычисляются значения функций

· проводятся операции возведения в степень

· выполняются операции умножения и деления

· в последнюю очередь выполняются операции сложения и вычитания.

Операции оного приоритете выполняются слева направо.

2. При записи дробей используется линейная форма записи.

3. Нельзя опускать знак умножения.

4. Нельзя использовать два знака математических операций подряд.

Рассмотрим пример решения лабораторной работе № 1.

Задание: вычислить значение функции,заданной по формуле

ax³+sin(bx)+0.1

y=------------------

Ln a + |x+c|-1,

где

x=e^c-0.5+5Tg(a-b), c=log₅(a+0.6), a=2.05,b=1.3

Вначале приведем словесное описание алгоритма решения задачи.[П.В.2]

· задаются значения переменных a и b

· вычисляется значение переменных с и х по формуле

· вычисляется по формуле значение искомой функции

· печатается полученный результат.

Приведем вариант программы на языке Qbasic

a=2.05:b=1.3

c=log(a+0.6)/log(5)

x=exp(c-0.5)+5*tan(a-b)

y=(a*x^3+sin(b*x)+.1)/(log(a)+abs(x+c)-1)

Print “y=“;y

Программирование арифмерических циклов.

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

Так в частности, в задании к данной лабораторной работе предлагается рассчитать и напечатать таблицу значений функции.

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

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

Формат оператора For - Next:

For <параметр цикла>=<начальное значение> To <конечное значение> Step <щаг по параметру>

ТЕЛО ЦИКЛА

Next <параметр цикла>

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

Кроме оператора For -Next для программной реализации можно применить и другие операторы цикла языка Бэйсик. Для нижеприведенных операторов цикла в рамках решаемой задачи приходится предусматривать самостоятельное изменение переменной расчета на величину заданного шага и контроль диапазона.

Формат оператора While - Wend:

While <условие>

ТЕЛО ЦИКЛА

Wend.

Оператор While - Wend повторяет выполнение тела цикла до тех пор, пока выполняется <условие>. При нарушении условия действие оператора завершается и программа продолжает свою работу с оператора, записанным за Wend.

Абсолютно идентичен выше приведенному и оператор Do Loop с предусловием типа While.

Формат оператора:

Do While <условие>

ТЕЛО ЦИКЛА

Loop

По своему действию очень близок к этому оператору и оператор Do-Loop с предусловие Until. Разница заключается в том, что после ключевого слова Until записывается не условие продолжения цикла (как в случае While), а условие его окончания.

Другая форма оператора Do - Loop - оператор с постусловием.Формат этого оператора:

Do

ТЕЛО ЦИКЛА

Loop While <условие>.

Вместо ключевого слова While можно использовать Until. В этом случае <условие > определяет условие выхода из цикла Do -Loop.

Различие двух этих модификаций (с пред- и пост-условиями) оператора Do - Loop заключается в следующем. Так если условие повторения цикла не выполняется в самом начале, то оператор Do - Loop с предусловие не выполнит тело цикла ни разу. Оператор с постусловием выполнит тело цикла один раз, так как условие повторения выполнения цикла проверяется в этом случае после выполнения последнего оператора тела.

Задание: рассчитать и напечатать таблицу значений функции

y = |x+2| + lnx,для хÎ [0.1,2.2],Dx=0.2

Алгоритм решения задачи предусматривает лишь размешение в теле цикла операторов вычисления функции и печати полученных результатов.

Для программной реализации можно использовать любой из вышерассмотренных операторов цикла. Приведем для примера использование операторов For-Next,While -Wend и Do - Loop с постусловием.

Вариант 1

for x=0.1 to 2.2 step.2

y=abs(x+2)+log(x)

print using “ ##.## ###.####”;x,y

next x

Вариант 2

x=0.1

while x<=2.2

y=abs(x+2)+log(x)

print using “ ##.## ###.####”;x,y

x=x+0.2

wend

Вариант 3

x=0.1

do

y=abs(x+2)+log(x)

print using “ ##.## ###.####”;x,y

x=x+0.2

loop while x<=2.2

Вариант 4

x=0.1

do

y=abs(x+2)+log(x)

print using “ ##.## ###.####”;x,y

x=x+0.2

loop until x>2.2

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

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

Продемонстрируем вложенные циклы на примере вычисления элементов квадратной матрицы.

Необходимо вычислить и напечатать элементы квадратной матрицы размером N*N,заданных по формуле

a_i,j=i³-³Öj, i=1,...,N j=1,...,N

Первый индекс матрицы (i) обозначает номер строки, второй -номер столбца.

Для вычисления элементов иатрицы необходимо организовать цикл по всем строкам (i от 1 до N). Для каждой текущей строки нужно пройти по всем столбцам (j от 1 до N). Для каждого текущего i и j рассчитать и напечатать элемент матрицы.

Input “N=“;N

For i=1 To N:For j=1 To N

a(i,j)=i^3-j^(1/3)

Print “a”;i;j”=“;a(i,j)

Next j:Next i

Отметим, что внутренний цикл (по J) закрывается ранее внешнего (по i).

Программирование разветвляющихся вычислительных процессов.

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

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

Условные операторы языка Бэйсик имеют две модификации: одностроковый оператор IF - Then - Else и многостроковый If - EndIf. Различие заключается в следующем:

одностроковый оператор If-Then-Else должен записываться в одну строку

многостроковый оператор IF-EndIf может содержать несколько строк.

Формат оператора If-Then-Else

If <условие> Then <операторы> Else<операторы>.

При выполнении заказанного условия выполняются операторы, расположенные между ключевыми словами Then и Else, либо от Then до конца строки при отсутствии Else. После выполнения действий управление передается оператору, следующему за If.

При невыполнении условия выполняются операторы, следующие за Else,при отсутствии Else действие оператора If игнорируется.

Одностроковый оператор IF-Then-Else удобно использовать при небольшом числе проверок условий и небольшой длине <операторов>. В противном случае запись оператора может быть слишком громоздкой и не наглядной.

При значительном количестве проверок условий и самое главное большом числе действий при выполении или невыполнении анализируемого условия следует прибегать к многостроковому оператору If-EndIf.

Формат многострокового оператора:

If <условие 1> Then

<операторы>

ElseIf <условие 2> Then

<операторы>

.

.

.

Else

<операторы>

Endif

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

· при выполнении <условие 1> выполняются операторы, стоящие за первым Then.После их выполнения управление передается оператору, следующему за EndIf.При невыполнении первого условия анализируюется <условие 2>

· при выполнении второго условия выполняются действия, стоящие за вторым Then.После их выполнения управление передается оператору, следующему за Endif

· При невыполнении очередного условия последовательно анализируются последующие. При невыполнении ни одного из заказанных условий выполняются действия, стоящие за Else.

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

Однако для организации сложных и многочисленных проверок удобнее использовать оператор выбора Select Case.

Формат оператора

Select Case <выражение выбора>

Case <список выражений 1>

<операторы>

Case <список выражений 2>

<операторы>

.

.

.

Case Else

<операторы>

End Select

Здесь: <выражение выбора>-любое числовое или символьное выражение;

<список выражений>- анализируемое значение.

Элементы списка выражений должны иметь одну из следующих форм:

· выражение, выражение...

· выражение To выражение

· Is выражение со знаком операции

· выражение- любое числовое или символьное выражение, совпадающее с типом выражения выбора.

Если <выражение выбора >отвечает условиям списка выражений данного блока Case, выполняются операторы из этого блока. После этого управление передается оператору, следующему за End Select.

Задание: вычислить значение функции

ì tg(a+x³), x>2.35 где x=ln(z/a+1)-e^z

y=í |ax+Öz|/3, 0£x£2.35 z=tg(ae^1.5)

î sin³z⁵, x<0 a=0.7

Алгоритм решения задачи:

· задаем значение переменной а

· вычисляем значения z и x

· если значение х больше 2.25 - вычисляем y по первой из формул

· для значения х из диапазона от 0 до 2.25 вычисляем y по второй формуле

· в противном случае вычисляем y по третьей формуле

· полученный результат печатаем.

Приведем два варианта программной реализации поставленной задачи: с помощью оператора If - Then - Else и Select Case.

Вариант 1

a=0.7

z=Tan(a*exp(1.5))

x=log(z/a+1)-exp(z)

if x>2.35 Then y=tan(a+x^3) Else if x>=0 Then y=Abs(a*x+sqr(z))/3 Else y=Sin(z^5)^3

Print “x=“;x,”y=“;y

Вариант 2

a=0.7

z=Tan(a*exp(1.5))

x=Log(z/a+1)-Exp(z)

Select Case x

Case Is >2.35

y=tan(a+x^3)

Case 0 To 2.35

y=Abs(a*x+sqr(z))/3

Case Else

y=Sin(z^5)^3

End Select

Print “x=“;x,”y=“;y

Вычисление сумм на ЭВМ.

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

· задается начальное значение переменной,хранящей сумму

· организуется цикл суммирования по параметру суммирования от начального до конечного с шагом 1

· в цикле переменная, хранящая сумму, увеличивает свое значение на текущий элемент суммы

Продемонстрируем процесс вычисление суммы на примере:

- вычислить сумму числовой последовательности, заданной в виде

S=1-x+x²-x³+...+(-1)ⁿxⁿ , где x и N считаются заданными.

Для программирования процесса суммирования представим последовательность в стандартном виде.

_N

S=1+å (-1)ⁱxⁱ

ⁱ⁼¹

В нашем случае, начальное значение переменной, хранящей сумму, следует взять равной 1. Параметр суммирования (I) должен пробегать значение от 1 до N с шагом 1. Текущий элемент суммы следует брать в виде (-1)ⁱxⁱ

Фрагмент программы, реализующий процесс вычисления суммы ряда, показан ниже:

S=1

For i=1 To N

S=S+(-1)^i*x^i

Next i

После завершения цикла переменная S будет хранить текущее значение суммы элементов последовательности.

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

_N

x_i= å a_i,j *a_j,i

^j=1

В этом случае, начальное значение переменной суммирования x_i рано 0, параметр суммирования (j) пробегает значение от 0 до N,текущий член суммы равен a_i,j *a_j,i.

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

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

При вычислении бесконечной последовательности с заданным числом ее членов N, процесс суммирования рассматривался выше.

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

Для получения результата с нужной точностью можно использовать другой алгоритм суммирования:

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

При таком подходе нельзя использовать для процесса суммирования цикл For -Next, т.к. не определена верхняя граница предела суммирования.

Для программирования этапа накопления суммы по этому алгоритму можно использовать цикл Do - Loop с пост условием. Приведем фрагмент вычисления ряда

_¥

S=1+å (-1)ⁱxⁱ

ⁱ⁼¹

на языке Qbasic (значения X и точность E считаются заданными):

S=1:i=0

Do

i=i+1

a=(1-)^i*x^i

S=S+a

Loop While Abs(a)>Eps

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

· с заданным числом членов (N=10)

· с заданной точностью (Eps=10^-5)

Например,

y=-----, S=1-x+x²-x³+...+(-1)ⁿxⁿ+...

1-x для xÎ[0,0.9] Dx=0.1

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

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

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

Вычисление произведений на ЭВМ.

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

Для вычисления произведения применяется следующий алгоритм:

· задается начальное значение переменной,хранящей произведение,равное 1

· организуется цикл вычисления произведения по параметру от начального до конечного с шагом 1

· в цикле переменная, хранящая произведение, умножается на текущий элемент.

Продемонстрируем процесс вычисление произведения на примере:

вычислить значение функции Y как произведение элементов одномерного массива

_N

Y = P x_i,

ⁱ⁼¹

элементы одномерного массива считаются заданными.

Фрагмент программы, реализующий решение данной задачи:

Y=1

For i=1 To N

Y=Y*X(i)

Next i

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

Однако, если нужно найти факториал некоторого числа К, вычисляемого по формуле

_К

К!=П i

ⁱ⁼¹

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

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

_N

S=å (-1)ⁱxⁱ/i!

ⁱ⁼¹

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

I!=I*(I-1)!.

Каждое последующее значение факториала вычисляется как значение факториала предыдущего числа, умноженное на текущее значение I. Такой подход позволяет уменьшить объем вычислений и зачастую упростить алгоритм. При вычислении факториала вводится переменная, хранящая требуемый результат. Задается начальное значение этой переменной равной 1 (как известно 0!=1).Каждое вычисляемое значение факториала заносится в ту же переменную.

Для рассмативаемого ряда, процессс вычисления суммы может быть реализован в виде следующего фрагмента:

S=0:P=1

For i=1 To N

P=I*P

S=S+x^i/P

Next i

Однако подобный подход приемлем лишь для вычисление факториалов для небольших значений I (i!<10³⁸).Для вычислений больших значений факториалов можно использовать вещественные переменные с двойной точностью либо дополнительные математические приемы.

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

(2*I)!, то для реализации подобного подхода необходимо связать значение факториала не с предыдущим, а с пред-предыдущим. Для вычисления второго члена последовательности необходимо использовать значение 4!, связав его со значением 2!, участвовавшего при расчете 1-ого члена ряда. В этом случае рекуррентная формула приобретает вид

(2I)!=2*I*(2I-1)*(2I-2)!

Соответственно изменится формула расчета факториала в вышеприведенном фрагменте программы.

Получение рекуррентных формул.

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

Рекуррентная формула позволяет связать каждый последующий член последовательности с предыдущим.

Для заданного в виде

S=a₀+a₁+a₂+...+a_N+...

ряда рекуррентная формула связывает a₁ с a₀ , a₂ с a₁ и т.д., или

a_i=B*a_i-1

Получим рекуррентную формулу для вычисления ряда, вида

_¥

S=å (-1)ⁱx²ⁱ/(2i)!

ⁱ⁼¹

Значение (i-1)-ого члена последовательности получается путем замены значения I на I-1 в общем члене ряда:

a_i-1=(-1)^i-1x^(2i-2)/(2i-2)!

Для нахождения коэффициента В в общей формуле рекуррентной последовательности выделим из a_i члены, подобные a_i-1

(-1)ⁱ=(-1)^i-1(-1)

x²ⁱ=x^2i-2x²

(2i)!=2i*(2i-1)*(2i-2)!

Подставим в a_i полученные выражения и сгруппируем их

(-1)x² (-1)^i-1 x^2i-2 -x²

a_i=-------- * ---------- = --------- a_i-1 =B*a_i-1

2i(2i-1) (2i-2)! 2i(2i-1)

Полученное значение В можно использовать в программе. Процесс программирования мало чем отличается от выше описанных примеров. Единственно, что нужно не забыть -это определить начальное значение последовательности a₀, который является стартующим. В рассматриваемом случае a₀=1.

Фрагмент программы, реализующих вычисление ряда с заданным числом членов, показан ниже:

a=1:S=0

For i=1 To N

a=-x^2/2/i/(2*i-1)*a

S=S+a

Next i

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

Нахождение максимума и минимума.

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

Для поиска минимального элемента одномерной последовательности (вектора) применяется следующих алгоритм:

· в качестве минимального берется значение первого элемента массива

· начиная со второго элемента и до последнего проверяется условие:

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

В качестве примера покажем фрагмент программы поиска минимального значения одномерного массива X

Min=x(1)

For i=2 To N

If x(i)<Min Then Min=x(i)

Next i

Сортировка одномерного массива.

Третья подзадача 5-ой лабораторной работы предлагает произвести упорядочивание одномерной последовательности.

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

Задача сортировки массивов является достаточно массовой при решении практических задач на ЭВМ, потому для ее решения разработан ряд алгоритмов.

Рассмотрим два из них: всплытие пузырька и сортировка по Шеллу.

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

Приведем фрагмент программы, сортирующий одномерный массив Х по возрастанию.

For i=1 to N-1 ‘цикл N-1 проходов

For j=1 to N-1 ‘ цикл одного прохода

if x(j+1)<x(j) Then Swap x(j),x(j+1)

Next j,i

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

Кроме сортировки путем всплытия пузырька,в практике программирования часто применяют сортировку по Шеллу. Смысл сортировки по возрастанию состоит в следующем. Начиная с первого и до последнего элементов массива определяется наименьший. Первый и найденный элемент меняются местами. Далее, начиная со второго и до последнего находят наименьший из оставшихся. Второй и найденный элементы меняются местами и т.д. Процедуру поиска минимального элемента и перестановку с текушим повторяют N-1 раз.

Приведем фрагмент программы,сортирующий одномерный массив Х по возрастанию по Шеллу.

For i=1 to N-1 ‘цикл N-1 проходов

k=i:y=x(i)

For j=i+1 to N ‘ цикл поиска min и номера эл. if x(j)<y Then y=x(j):k=j

Next j

Swap x(i),x(k)

Next i

Описанные выше приемы сортировки приемлемы не только для упорядочивания одномерного массива, но и для сортировки строк/столбцов/диагоналей матрицы. Так если требуется привести к нужному виду первую строку матрицы, следует в приведенных алгоритмах заменить Х(*) на А(1,*), здесь * заменяет индекс массива (i или j или k...).

При сортировке последнего столбца матрицы следует в формулах использовать значения A(*,N). При сортировке элементов главной диагонали следует учитывать, что эти элементы фактически образуют одномерный массив A(I,I), и поэтому к ним можно применить ту же процедуру сортировки.

Построение графиков функций.

При использовании графических возможностей языка Basic в начале программы необходимо задать вид графического экрана. По умолчанию после запуска программы устанавливается текстовый режим отображения, поэтому без заказа графического экрана первый же графический оператор вызовет сообщение об ошибке. Задание типа экрана производится с помощь оператора Screen < тип экрана > (укороченный формат). В качестве целого значения, определяющего вид экрана можно использовать:

· 0-текстовый режим.Число строк и столбцов определяется оператором Width (по умолчанию 25 строк 80 колонок),8 фоновых и 32 основных цветов.

· 7- графический режим. Разрешение 320*200 пикселей, 16 цветов. Для вывода текста 25 строк, 40 столбцов. Коэффициент нелинейности = 5/6

· 8- графический режим. Разрешение 640*200 пискелей,16 цветов. Текст выводится в 25 строк, 80 колонок. Коэффициент нелинейности = 5/12

· 9- графический режим. Разрешение 640*350 пикселей, 16 цветов. Текст выводится в 25 или 43 строк и 80 колонок. Коэффициент нелинейности =35/48

· 11 и 12- графический режимы. Разрешение 640*480 пикселей 256 цветов для 2 палитр. Текст выводится в 30 или 60 строк и 80 колонок. Коэффициент нелинейности =1

Для позиционирования графических точек используется оператор Pset, установка указателя вывода текста производится оператором Loсate.

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

Дадим краткий перечень графических операторов, позволяющих решать задачи лабораторных работ №№6-7.

· Cls - очистка экрана.

· Color <основные символы>,<фон><рамка> - задание цветов. В качестве цвета фона выступают значения от 0 до 7, цвет основных символов - от 0 до 31, рамка - от 0 до 15. Расшифровка цветов:

0-черный 8-серый

1-синий 9-ярко-синий

2-зеленый 10-ярко-зеленый

3-голубой 11-ярко-голубой

4-красный 12-ярко-красный

5-лиловый 13-ярко-лиловый

6-коричневый 14-желтый

7-белый 15-ярко-белый

Цвета от 16 до 31 являются мигающими по отношению к основной гамме.

· Pset (x,y),<цвет>- вывод точки с координатами x,y заданного цвета. Если после Pset стоит ключевое слово Step- x и y определяют не абсолютные координаты, а смещение относительно последней графической точки.

· Line (x_н,y_н)-(x_к,y_к),<цвет>,BF,<стиль>- построение линии или прямоугольника. Начало линии (верхний левый угол прямоугольника)-(x_н,y_н),конец линии (нижний правый угол прямоугольника)- (x_к,y_к). При наличии необязательного параметра В изображается прямоугольник (при отсутствии -линия),если после В стоит F- прямоугольник закрашивается. Стиль- 16-ти битовая маска, задающая вид линии. Если бит=0,точка не рисуется,1- рисуется. При наличии ключевого слова Step после Line, координаты определяют смещения по отношению к последней построенной точке.

· Circle (x,y),<радиус>,<цвет>,<нач.дуги>, <конец дуги>,<коэффициент эллипсности>- рисует окружность, дугу,сектор,эллипс. Параметры x и y определяют координаты центра, необязательные параметры нач.дуги и конец дуги определяют угловые координаты строимой дуги. При отсутствии этих параметров строится окружность. Отрицательные значения этих параметров указывают на построение не дуги, а сектора, причем значения углов берутся по модулю. При наличии последнего параметра вместо окружности строится эллипс.При построении эллипса необходимо учитывать коэффициент нелинейности. Так при попытке построения эллипса с коэффициентом эллипсности =1 (окружность) для экранов с 7 по 9 будет построена не окружность, а эллипс.

· Paint (x,y,),<цвет краски>,<цвет границы> - заливает ограниченную <цвет границы> область краской, заданного цвета. Если точка принадлежит внутренней области- заливается внутренняя часть, в противном случает заливается внешняя область. Отметим,что при наличии хотя бы одной точки разрыва на границе заливаемой области, краска разливается на весь экран.

· Draw <Символьное выражение> - обеспечивает выполнение графической программы. Символьное выражение содержит графические команды. Каждая графическая команда содержит буквенное обозначение и стоящее за ним числовое значение. Графические команды:

Un -вверх на n точек

Dn - вниз на n точек

Ln - влево на n точек

Rn - вправо на n точек

En - под углом 45° на n точек

Fn - под углом 135° на n точек

Gn - под углом 225° на n точек

Hn - под углом 315° на n точек

TAn- поворот всего изображения на n градусов

Cn- установка цвета n

При наличии перед символом графической команды префикса В производится действие без рисования.

· Window Screen (x_н,y_н)-(x_к,y_к) - задает размеры текущего окна вывода. При задании размеров окна координаты всех строимых точек определяются как относительные к данному окну. Наличие ключевого слова Screen преобразует направление вертикальной графической координаты в декартову.

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

Для примера построим окружность, заданную в полярных координатах:

y=R*sin f

x=R*cos f

угол f изменяется от 0 до 2p.

Для реализации выберем 8-ой тип экрана.

Screen 8

R=70:Pi=4*Atn(1)

For f=0 to 2*Pi Step Pi/200

x=320+R*Sin(f)

y=100-R*Cos(f)*5/12

Pset(x,y),4

Next f

Здесь, при расчете графических координат точек x и y учтено смещение центра координат, обратное направление координаты y и геометрическая нелинейность 8-ого типа экрана. Окружность строится цветом 4 (красный).

Построение движущихся графических объектов.

Язык Basic позволяет проводить построение несложных перемещающихся графических объектов. Для построения сложных динамических картин в реальном времени следует применять дополнительные приемы программирования либо другие программные средства.

В простейшем случае процесс построение динамических объектов заключается в следующем:

- строится текущее графическое изображение или фрагменты объекта.

- изображение фиксируется на незначительное время.

- построенное изображение или его фрагменты стираются.

- процесс построения объекта или его фрагментов повторяется со смещением от предыдущего.

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

Рассмотрим в качестве примера вращение вокруг некоторой точки. Процесс вращения проще описывать с помощью полярных координат: радиуса и угла поворота. Расстояние до точки (радиус) для недеформируемых тел является величиной неизменной, значение угла поворота изменяется от 0 до 2p для описания полного оборота.

Для построения вращения линии вокруг одного из ее концов используем следующий алгоритм:

- определяем тип графического экрана и исходные данные для построения

- организуем цикл по углу поворота

- в теле цикла вычисляем новое местоположение движущегося конца линии

- вычерчиваем линию

- задерживаем изображение на экране

- стираем линию

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

Вариант программы на языке Basic:

Screen 12

R=100:pi=4*Atn(1)

For f=0 To 2*Pi Step Pi/36

x=320+R*Cos(f)

y=240-r*Sin(f)

Line (320,240)-(x,y),4

For i=1 to 500: Next i

Line (320,240)-(x,y),0

Next f

В данном варианте программы для организации задержки использован оператор пустого цикла. Количество повторений (500) определяет временную задержку и зависит от типа ЭВМ. В данном случае использование оператора приостанова Sleep не приемлемо, т.к. этот оператор приостанавливает выполнение программы на целое число секунд.

Для построения вращения более сложных геометрических объектов(треугольников, прямоугольников и т.д.) можно применить следующий прием. Выбирается базовая линия (например, одна из сторон треугольника). Эта линия вращается аналогично рассмотренному ранее примеру. Углы и расстояния между вершинами треугольника остаются неизменными. Поэтому, если в равностороннем треугольнике базовая сторона повернулась на угол f, тогда другая сторона треугольника повернется на угол f+p/3. В теле цикла вращения вычисляются новые координаты вершин треугольника,строятся три линии, определяющие новое местоположение треугольника, изображение выдерживается на экране, производится стирание изображения путем проведения этих же линий цветом фона. При построении вращения прямоугольника можно использовать этот же прием с тем условием, что число вершин равно 4. Кроме того для описания вращения прямоугольника можно использовать оператор Draw с вращением системы координат и попеременной сменой цветов.

Содержание

Общие положения..................3

Программирование арифметических

выражений....................... 4

Программирование арифмерических циклов........................... 6

Программирование разветвляющихся вычислительных процессов......... 10

Вычисление сумм на ЭВМ........... 14

Вычисление произведений на ЭВМ... 17

Получение рекуррентных формул.... 19

Нахождение максимума и минимума.. 22

Сортировка одномерного массива... 23

Построение графиков функций..... 26

Построение движущихся графических объектов......................... 30

[П.В.1]

[П.В.2]