Урок 2. АЛГОРИТМИЗАЦИЯ

Содержание

Теоретические положения.
Алгоритмизация  - общие положения.
1. Алгоритмизация на основе векторного исчисления.
2. Алгоритмизация как геометрическое место точек (ГМТ).
3. Алгоритмизация, удовлетворяющая условию максимума/минимума.
4. Алгоритмизация на основе случайных чисел.
Пример. По методу случайных чисел вычислить десять точек на прямой р1-р2.
5. Алгоритмизация на основе макрокоманд.
Упражнение 1. Вычислить середину отрезка между точками р1 и р2.
Упражнение 2. В МК date.mac задать две точки р51 и р52, соединить их отрезком с помощью МК otrezok.mac.
Упражнение 3. На отрезке прямой, используя уравнение:  p=(1.-s)*p51+s*p52  вычислить десять точек р1-р10, изобразив их через базовую МК okr.mac.  Данные в date.mac.
Упражнение 4. Организовать расчет точек и их изображение на прямой в цикле.
Упражнение 5. Организовать расчет точек на прямой в зависимости от расстояния от начала
Упражнение 6.  Создать МК изображения кривых, заданных параметрически.
Упражнение 7.  По 4-м точкам задать косую плоскость в виде сетки прямых и точек.
Упражнение 8. В прямоугольнике задать серию окружностей, выбирая их центры (координаты) по методу случайных чисел, предварительно сформировав МК tnn.mac.
Упражнение 9 (самостоятельно).  Задать сферу в виде параллелей и точек на ней.


Теоретические положения:

Алгоритмизация - это поиск правил, по которым можно: 1) вычислять точки на линии или поверхности, 2) двигаться по кривой или поверхности с заданной скоростью, 3) вычислять минимальное или максимальное значение, 4) находить геометрическое место точек (ГМТ), 4) выбирать случайное число и по нему выполнять то или иное действие и т. п.

Алгоритм может быть задан: алгебраическим или векторным уравнением,  условиями на мах/min, ГМТ, генератором случайных чисел, программой, макрокомандой.



1. Алгоритмизация на основе векторного исчисления.

Величины, значения которых определяются размером и направлением в пространстве, называются векторами. Геометрически вектор - это направленный отрезок в пространстве, определяемый начальной точкой p0 и конечной p1.

Длина вектора называется его модулем. Единичный вектор - это вектор длина которого равна единице (вектор разделенный на его длину). Модуль вектора вычисляется по правилу: s=|p| = sqrt (x*x + y*y + z*z). Точка (двойка, тройка и т.д. ее составляющих) - есть фактически вектор, поэтому точки как и в векторном исчислении можно складывать, умножать их на вещественное число, делить и т.п.

Так, вычисление середины (т. p)  отрезка прямой р1-р2 будет:
p=p1+ (p2-р1)/2.       (1)

Уравнение (1) в свою очередь можно обобщить и вычислять не только середину, а любую точку в зависимости от безразмерного параметра s:
p=(1.-s)*p1+s*p2  при     0 <=s <=1
где входными данными будут точки р1 и р2 начала и конца отрезка и s изменяется в диапазоне от 0 до 1;
выходными - точка р.

Задание отрезка прямой через точку р1(х1, y1), его длину s и направление единичный вектор (р99).
p= p1+s*p99          (2)
где р99 - единичный вектор определяемый как отношение вектора к его длине: р99=р2-р1/|р2-р1|

В системе “Вектор” можно работать как непосредственно с векторами так и его компонентами. Так уравнение (2) можно задать:
x=x1+s*x99
y=y1+s*y99

Или, например, окружность радиуса s и центром в точке р1:
x=x1+s1*sin(s),
y=y1+s1*cos(s)
где s - угол (в радианах), изменяющийся от 0 до 2p.

Модуль вектора (длина вектора, отрезка) определяется:
s=|p2-p1|, или:
s= $sqrt((x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2)) как гипотенуза прямоугольного треугольника один катет которого являются разность абсцисс (координат х) начала и конца отрезка, а вторым разность ординат (координат y) начала и конца отрезка). В трехмерном случае добавляется разность координат по z.



2. Алгоритмизация как геометрическое место точек (ГМТ), например, все точки должны находиться на таком-то расстоянии от одной или нескольких точек.
 
 

2.1. Для прямой все ее точки p должны находиться на одинаковом (s1 и s2) расстоянии от двух заданных p1 и  p2: s1=s2  или  |p-p1|=|p-p2|. 
 

 
 

2.2.  Для окружности как места точек р, равноудаленных (расстояние s)  от точки р1: s=|p-p1|.  

 
 

2.3.  Для эллипса: s1+s2=c  или |p1-p|+|p2-p| =c 
 

 
 

2.4.  Для параболы: s1=s2 или |p1-p|=|p2-p|   (x2=c)  

 
 

2.5.  Для гиперболы: s2-s1=c  или |p1-p|-|p2-p| =c  

 
 

2.6.  Для дуги окужности, проходящей через две точки и заданный радиус: |p1-p|=|p2-p| = с (компромисс)

 
 

2.7.  Для дуги окужности, проходящей через три  точки |p1-p|=|p2-p| = |p3-p| (тоже компромисс)

 



3. Алгоритмизация, удовлетворяющая условию максимума/минимума (например, все точки(или точка) должны находиться на min/max расстоянии от заданной.

3.1. Минимальное расстояние s1 от точки p3 до отрезка p1-p2
 s1=|p3-p|-> min,     где р =(1.-s)*p1 +s*p2.

4. Алгоритмизация на основе случайных чисел.

Пример. На основе случайного выбора безразмерного параметра s, вычислить десять точек на прямой р1-р2.

<tsluhd.mac>
: p1=80.,50. p2=240.,110.
otrezok: p101=p1 p102=p2
tsluh: n1=1

<tsluh.mac>
n1 > 10 ? exit
_Случайное_число_(в_n191)_от_ 00000 00011
s1=n191
s=s1/10.
p=(1.-s)*p1+s*p2
okr: p100=p s100=5.
tsluh: n1=n1+1



5. Алгоритмизация на основе макрокоманд
 
 
Упражнение 1. Вычислить середину отрезка между точками р1 и р2 
 
Решение

1) В командной строке (ctrl+c) задаем точки и параметр s:
 : р1=50.,40. р2=180., 190. s=0.5

2)  В командной же строке вычисляем искомую точку:
p=(1.-s)*p1+s*p2
Результат внизу экрана.


Упражнение 2. В МК date.mac задать две точки р51 и р52, соединить их отрезком с помощью МК otrezok.mac.

date.mac  - МК задания исходных данных
: p51=10.,5.,20. p52=80.,70.,60. $ заданы две точки в регистрах p51 и p52
otrezok: p101=p51 p102=p52     $  соединяем две точки через МК otrezok.mac


Упражнение 3. На отрезке прямой, используя уравнение:  p=(1.-s)*p51+s*p52  вычислить десять точек р1-р10, изобразив их через базовую МК okr.mac.  Данные в date.mac.

ur2z1.mac  МК расчета точек на прямой по формуле: p=(1.-s)*p1+s*p2
date                                   $ данные в соответствующей МК
p25=p51+(p52-p51)/2.     $ расчет середины отрезка
okr: p100=p25 s100=10.  $ в середине отрезка построить окружность
s=0.1                                 $ переменный параметр s
p1=(1.-s)*p51 + s*p52     $ более универсальная формула расчета точек
s=0.2
p2=(1.-s)*p51+s*p52       $ вычисление второй точки при s=0.1 и т.д.
okr:p100=p1 s100=3.0     $ построение окружностей в каждой точке
okr: p100=p2                    $ радиус второй раз можно не задавать (значение 3.0 уже там).



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

ur2z2d.mac - МК задания данных для вычисления точек на прямой
:p1=20.,15. p2=120.,130.      $ сами точки
otrezok: p101=p1 p102=p2   $ строим отрезок
ur2z2i: s=0.                        $ обращения к МК построения точек на прямой

ur2z2i.mac исполнительная МК вычисления точек на прямой в цикле
s > 1.0 ? exit                       $ условие выхода из МК
p=(1.-s)*p1+s*p2 $ вычисение точек
okr: p100=p s100=3.0 $ в точке строим окружность
ur2z2i: s=s+0.05 $ рекурсия и увеличение s  на шаг 0.05



 
 
Упражнение 5. Организовать расчет точек на прямой в зависимости от расстояния от начала
 
$ ur2z3d.mac данные к расчету точек по формуле: p=p1+s*p99
:p1=20.,15. p2=220.,130.
otrezok: p101=p1 p102=p2
s1=$sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) $ расчет длины отрезка
p99=(p2-p1)/s1 $ единичный вектор
ur2z3i: s=0. $    обращения к циклу расчетов
$ ur2z3i.mac расчет точек на прямой в зависимости от расстояния от начала
s > s1 ? exit    $ условие выхода
p=p1+s*p99  $ расчет точек
okr: p100=p s100=3.0 $ точки изображаем окружностями
ur2z3i: s=s+15.0  $ рекурсия с шагом 15.0


 
 
 
Упражнение 6. Создать МК изображения кривых (в частности, окружности), заданных параметрически. 
Схема решение:
1)  задать исходные данные: центр, радиус, другие параметры
2)  организовать цикл: условия выхода, рекурсивное обращение МК самой на себя, шаг.
3)  в цикле организовать расчет точек по той или иной формуле
4)  используя МК построения отрезка с условием перезадания конца в начало, для каждой кривой обеспечить график их построения.
5)  в последней строчке МК обеспечить рекурсивное обращение МК к самой себе с изменяющимся углом s (s=s+шаг) в радианах от нуля до 6.28.

ur2z4d.mac  - МК данных и задания начальных точек построения графиков окружности, кардиоиды и т.д.
: p2=100.,100. p3=p2  p4=p2
ur2z4: s=0.    $  обращение к МК построения окружности, кардиоиды и т.д.

ur2z4.mac  МК расчета точек окружности, кардиоиды и т.д. и их графики
s > 2.*3.149 ? exit  $ условие выхода из МК

$ Задание окружности
x = 100.0 + 30.0*cos(s)  $ абсцисса точек на окружности
y = 100.0 + 30.0*$sin(s) $ ордината
otrezok: p101=p2 p102=p $ соединяем текущую точку с предыдущей
p2=p102   $ помещаем конец текущего отрезка в начало следующего

$  Кардиоиды
x = 100.0 + 50.0* cos(s)*(1.+cos(s))
y = 100.0 + 50.0* $sin(s)*(1.+cos(s))
otrezok: p101=p3 p102=p
p3=p102

$ Эпициклоиды (вид кривой зависит от s1/s2)
$ Если s1/s2 = 1 - кардиоида и т.д. см. справочник Бронштейна м Семендяева
$ : s1=5.0 s2=5.0   - кардиоида
: s1=5.0 s2=15.0        $ число s1 в s2 дает число выступов
x=100.0 +(s1+s2)*cos(s)-s1*cos((s1+s2)*s/s1)
y=100.0+ (s1+s2)*$sin(s)-s1*$sin((s1+s2)*s/s1)
otrezok: p101=p4 p102=p
p4=p102
ur2z4: s=s+0.1

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



 
Упражнение 7. Задать косую плоскость в виде сетки прямых и точек 
ur2z5d.mac  - задание исходных данных
print$on  $ включить печать
: p1=30.,120.,50. p2=130., 110.,60.
: p3= 40.,10.,10.  p4=120.,20.,0.
ur2z5i: s1=0.  $ обращение к циклу

ur2z5i.mac - МК первого цикла изменения параметра s1
s1 > 1.0 ? exit    $ условие выхода
p13 = (1.-s1)*p1+s1*p3 $ вычисление точек на левой стороне
p24 = (1.-s1)*p2+s1*p4 $  вычисление точек на правой стороне
otrezok: p101=p13 p102=p24 $ соединяем p13 с p24  отрезками прямых
ur2z5i2: s2=0. $ идем на цикл вычисления точек на каждой прямой
ur2z5i: s1=s1+0.1  $ рекурсия (вызов МК самой себя)

ur2z5i2.mac - МК внутреннего цикла расчета точек на косой плоскости
s2 > 1.0001 ? exit   $ условие выхода
p=(1.-s2)*p13 + s2*p24 $ расчет точек на прямой у косой плоскости
okr: p100=p s100=3.0 $ каждую точку отображаем окружностью
ur2z5i2: s2=s2+0.1 $ рекурсивный вызов МК самой себя



Упражнение 8. Задание окружностей в прямоугольнике по методу случайных чисел предварительно сформировав МК tnn.mac.

testnn.mac - имя МК
n1 > 50 ? exit                    $ условие выхода
tnn: n101=50  n102=150   $- выбор числа в диапазоне 50-150
x=n191 $ присваиваем число абсциссе центра окружности
tnn: n101=50 n102=150    $- выбор случайного числа в диапазоне 50-150
y=n191 $ присваиваем число ординате центра окружности
okr: р100=р  s100=5.0     $- построение окружности с центром в р100
testnn: n1=n1+1                $ - идем на рекурсивный цикл



 
Упражнение 9. Задать сферу в виде параллелей и точек на ней. 
ur2z6d.mac  - МК данных для построения сферы
print$on $ включить печать
: p1=50.,40.,40. s11=30. $ центр и радиус сферы
ur2z6i: s1=0. s2=0. p3=p1 $ обращение к вычислению точек на сфере

ur2z6i.mac - МК внешнего цикла (как бы перебор параллелей) сферы
s1 > 6.29 ? exit    $ условие выхода на 360 градусов
ur2z6i2: s2=0. p3=p1 $ к циклу расчета точек на параллелях
ur2z6i: s1=s1+0.5    $  рекурсия с шагом 0.5 радиан

ur2z6i2.mac  - вторая рекурсия расчета точек на параллелях сферы
s2 > 6.29 ? exit $  условие выхода
x=x1+s11*cos(s1)*$sin(s2) $ расчет абсциссы точек сферы
y=y1+s11*$sin(s1)*$sin(s2) $ ординаты
z=z1+s11*cos(s2) $ аппликаты
okr : p100=p s100=2.0 $  расчетные точки отображаем окружностями
otrezok: p101=p3 p102=p  $ соединяем текущую току с предыдущей - строим параллели
p3=p102   $ конец текущего отрезка помещаем в начало следующего
ur2z6i2: s2=s2+0.5 $ рекурсия с шагом 0.5 радиана


tnn.mac - МК вычисления случайного числа  (текст МК)
_Случайное_число_(в_n191)_от_ n101  n102

или
tnn.mac - МК вычисления случайного числа  (текст МК)
22 n101 n102
exit

Обращение:
tnn: n101=<первое целое число>  n102 = <второе целое число>
Выходные данные в n191 - случайное число