Файл: Соловейчик, Р. Э. Программирование на АЛГОЛ-60 учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 104
Скачиваний: 1
80
имеет следующий вид:
procedure |
RK (x . y . h . f ) : |
value; |
*.h? |
real |
||||
real' |
procedure |
f |
1 |
|
|
|
|
|
begin |
re a l S1, |
|
IS2, |
k3, |
S4 | |
|
|
|
|
SI » a h |
|
* |
(* .y ) ; . |
|
|
||
|
S2 |
* а Ь |
^ |
f |
(x ♦ h/2, у ♦ S1/2 ) ; |
|||
|
S3 |
s =■ h |
* f |
(* ♦ Ь/2, у t |
S2/2 |
) t |
||
|
S+ s а Ь |
^ f (x + h, у ♦ S 4 ) } |
|
|||||
7 * ». у ♦ (k l 4 2 * k? * 2 4 S3 * k4
and
x,h,
) / 6
Эта процедура выполняет только одноразовую операцию, т.е. вычисляет одну новую точку интегральной кривой, а нуж ное число ил должно задаваться программой, которая обращает ся к этой цроцедуре. Кроме того, подчеркнем, что формальный параметр t здесь специфицирован как процедура-функция.
Предположим, что нужно проинтегрировать уравнение
у ' = ( f 3 + |2 )* + i 56 * * -(x+ 7 )_
Это может быть достигнуто использованием приводимой програм-
“ И |
begin |
re a l |
x ,y ,h ,x f i r s t , |
x |
la s t |
|
|
|
|
|
re a l |
procedure |
d e riv |
(x , y ) |
; |
|
|
|
|
d e riv t= (x t3 / 5 * y t2 / 2 )t(l/ 3 )+ I.6 3 * |
e x p (-x -y ); |
|||||
|
|
ЗВ0Д (x f ir s t , h ,x la s t , y ) ; |
|
|||||
|
' |
fo r xj=. x f i r s t |
step |
h |
u n til |
x la s t |
do |
|
|
|
begin |
RE (x ,y ,h ,d e r iv |
|
) » |
|
|
|
|
дечать |
(x t fa, у |
) |
|
|
|
|
|
|
end |
|
|
|
|
|
|
|
end
81
Остановимся более подробно на работе этой программы. Процедура RK считается записанной вместо многоточия. Стоящее на первом месте в программе описание процедуры-функ ции не вызывает никакого действия, оно просто задает струк туру процедуры-функции. Далее производится ввод начального значения аргумента, приращение аргумента, т.е. шага таблицы, конечного значения аргумента и начального значения функции.
Затем стоит оператор цикла по |
х. от его начального |
значе |
||||||
ния г first |
с шагом |
ь |
до его конечного |
значения, |
||||
уменьшенного на величину шага, т.е. до |
* lsst-h |
. На |
||||||
конец, происходит обращение к процедуре |
RK |
, применительно |
||||||
к данному уравнению, т.е. при данных |
х, |
у, Ь |
и конкретном |
|||||
виде дифференциального уравнения, т.е. процедуры-функции |
||||||||
derlv |
. В результате выполнения процедуры |
НК |
печата |
|||||
ются наращенное значение аргумента, т.е. х t |
h — , и |
соответ |
||||||
ствующее значение • у |
. Сама процедура |
RK |
при этом вызы |
|||||
вает |
процедуру-функцию |
derlv |
и |
вычисляет новое значение |
||||
у |
. После |
этого управление передается на основную програм |
||||||
му. |
|
|
|
|
|
|
|
|
На этом заканчиваем изложение программирования на язы ке АЛГОЛ-60 и надеемся, что оно окажется достаточным для пер воначального знакомства с предметом и для возможности нача ла самостоятельной работы по программированию на этом языке. Для более детального изучения можно рекомендовать книгу М.И.Агеева "Основы алгоритмического языка АЛГОЛ-60" (М., изд. Вычислительного центра АН СССР,1965) или "Алгоритмический
язык АЛГОЛ-60" (М., "Мир", 1965).
Перейдем теперь к приложению языка АЛГОЛ-60 к ряду спе циальных вопросов, имеющих'применение прежде всего в эконо мике.
. Определение быстрейшего пути
Задача подобного рода возникает в шахтах при разработ ке планов аварийного вывода людей.
В качестве входных данных к этой задаче должна быть дана матрица размером n х n t содержащая времена прямой
связи точки i с точкой i , обозначаемые в дальнейшем
в [i.jJ . Если прямой связи между этими точками нет, то время берется равным очень большой величине, обозначаемой М (напри мер, М = Ю ^ м и н ) . Отметим, что ®[i,j] не равно и, следовательно, рассматриваемая матрица не может считаться сим метричной хотя бы из-за подземной орографии.
Приведем программу, решающую поставленную задачу,
procedure shortest path (a) dature eults |
(в) |
; |
|||||||
value |
n* |
integer nj |
array я j |
|
|
||||
begin reel inf, |
s ? integer |
i,J,k |
j |
|
|
||||
inf |
i * |
И |
• |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
for |
1 i • ( |
step |
1 |
until n |
do |
|
|||
for |
|
» |
1 step |
•)- until |
n do |
|
|||
if * |
[j,i] < |
inf then |
|
|
|||||
|
for |
k: =» i |
step 1 |
until |
n |
dn |
|||
|
if m |
£i, kj < |
inf |
then |
|
|
|||
|
begin |
si з в [j,ij ♦ в £±,icj j |
|||||||
|
|
|
|
if s<^ |
■ £j,kj then m JTj,kJi3 e |
||||
|
end |
|
|
|
|
|
|
|
|
end
После выполнения этой процедуры получим новую матрицу,
содержащую величины в [i»jj |
, но теперь эти величины будут |
|||
давать нам не время прямой связи точки i |
с точкой |
j , а |
||
время ныискорейшей связи точки |
i |
с точкой j |
|
|
Поясним конструкцию этой процедуры на конкретном примере, . |
||||
Допустим имеется семь точек под номерами I, |
2, 3, 4, 5, |
6 , |
||
и 7 , а наличие между ними прямых связей изображено в следую |
||||
щей таблице, дающей длительность |
этих связей. |
|
||
83 --
|
1 |
2 |
3 |
4 |
5 |
8 |
7 |
1 |
0 |
м |
м |
м |
м |
м |
м |
2 |
м |
о |
м |
м |
м |
м |
м |
“ S--- |
м |
2 |
0 |
м |
м |
м |
М |
|
|
|
|
|
i |
|
м |
4 |
3 |
м |
м |
0 |
м |
м |
|
3 |
10 |
м |
м |
в |
0 |
м |
м |
в |
м |
м |
м |
2 |
м |
й |
м |
7 |
м |
в |
3 |
м |
м |
5 |
0 |
Так как длительность связей всегда не отрицательна, то элемен
ты, |
стоящие на главной диагонали, имеют наименьшее значение, |
||||||
и, следовательно, они останутся неизменными при дальнейших |
|||||||
преобразованиях матрицы. |
|
|
|
|
|||
|
Рассмотрим следующий частный |
случай. Пусть в [ 1 > |
м |
||||
и m |
|
[i,k] К. М |
* тогда вводим величину s |
, так что |
|
||
six |
m |
t m [ ± , |
k} |
. и если |
m £ j , k ] > a |
то в jj ,k j |
s»e. . |
|
Поясним геометрию этой конструкции |
|
|
||||
|
|
|
i |
к |
|
|
|
Здесь |
прямоугольником обозначена величина в |
• Треуголь |
ником, |
расположенным в той же строке,что и црямоугольник, |
|
|
|
84 |
|
|
|
|
обозначена величина m £j,ij |
, а треугольником, |
расположенным |
||||
в том же столбце, что и прямоугольник, |
- величина |
а [ i >k] . |
||||
Обе величины, стоящие в треугольниках, |
должны быть меньше М, |
|||||
и если сумма этих величин меньше величины, |
стоящей в прямо |
|||||
угольнике, то эта сумма присваивается |
m £j,kj |
- В |
результа |
|||
те этого присвоения величина |
и [$•*} |
теряет смысл прямей свя |
||||
зи между точками j, к |
; она приобретает теперь |
смысл наиско |
||||
рейшего перемещения из |
точки |
з в точку |
к . |
|
|
|
Наряду с приведенной схемой возможна и другая,
кi
но она ничем существенным не отличается от цриведенной выше. Все, сказанное выше, позволяет.сформулировать своеобразное пра
вило прямоугольника. |
|
|
Выбираем меньший, чем М, |
элемент в |
g-й строке матрицы |
и меньший, чем М, элемент в |
i-м столбце |
(причем в обоих |
случаях выбранные элементы не могут быть расположены на глав ной диагонали). Затем строим прямоугольник со сторонами, нап равленными по строкам и столбцам матрицы, двумя вершинами ко торого являются выбранные элементы, одна вершина расположена на главной диагонали и одна вершина в некотором элементе рас сматриваемой матрицы. Если значение этого элемента матрицы больше сумма значений элементов в двух других вершинах, не