ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.12.2023
Просмотров: 323
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
#include
double f(double);
void bisecn0(double a, double b, double epsx, double epsy,
double &res,int &k, int &ier)
{double c, fa, fb, fc;
const int kmax=1000;
fa=f(a); fb=f(b);
if ( (fa*fb)<=0.0)
{ k=0; do { c=(a+b)*0.5; fc=f(c);
if ( fa*fc>0.0) { a=c; fa=fc;} else { b=c; fb=fc;} k+=1;
}
while ( (k<=kmax) && ( (fabs(b-a)>epsx) || ( fabs(fc)>epsy)) );
res=(a+b)*0.5;
if (k<=kmax) ier=0; else ier=1;
}
else ier=2;
}
#include
double f(double);
void bisecr0(double a,double b,double epsx,double epsy,
double &res,int &k,int &ier)
{ double c, fa, fb, fc; int kmax=1000;
fa=f(a);
fb=f(b);
if ( (fa*fb)<=0.0 )
{ res=(a+b)*0.5; c=res; fc=f(c);
if ( (fabs(b-a)
else { c=(a+b)*0.5; fc=f(c);
k=k+1;
if (f(a)*fc>0.0) bisecr0(c,b,epsx,epsy,res,k,ier);
else bisecr0(a,c,epsx,epsy,res,k,ier);
}
}
}
else ier=2;
}
g++
a=0.0000000000000e+00
b=1.0000000000000e+00
krep=1000000
----- epsx=1.0000000000000e-05 epsy=1.0000000000000e-05
res f(res)
k ier
Время
Функция
3.3333206176758e-01
-3.8146972656250e-06 17 0
1.760
bisecn0 3.3333206176758e-01
-3.8146972656250e-06 17 0
4.310
bisecr0
a=
0.0000000D+00
b=
0.1000000D+01
gfortran epsx=
0.1000000D-04 epsy=
0.1000000D-04
krep=
1000000
-------- res f(res)
iter ier
Время
Подпрограмма
0.33333206176757812D+00
-0.38D-05 17 0
1.895
bisecn0 0.33333206176757812D+00
-0.38D-05 17 0
5.354
bisecr0 80
2.7
Понятие о хвостовой рекурсии
Хвостовая рекурсия — особый вид рекурсивного описания функции,
когда рекурсивный вызов оказывается её последним действием. В этом случае рекурсию можно заменить на итерацию (т.е. на оператор цикла,
исключая временные затраты на рекурсивные вызовы и не используя стековую память для хранения адресов возврата), что автоматически реализуется во многих компиляторах, если при компиляции, указывают- ся соответствующие опции оптимизации. Продемонстрируем эффект использования хвостовой рекурсии на примере расчёта факториала.
2.7.1
CИ (компилятор gcc)
typedef double real;
#include "mytype.h"
real factorn(long int n)
//
Файл factorx.c
{ long int i; real p;
// Нерекурсивная функция расчета n!
p=1.0; for (i=1;i<=n;i++) p*=i;
// Находит n! посредством оператора return p; }
// цикла.
real factorr1(long int n)
// Рекурсивная функция расчета n!
{ if (n==0) return 1.0;
// по формуле f=n*f(n-1).
else return n*factorr1(n-1); }
real factorr2(long int n)
// Рекурсивная функция расчета n!
{ if (n==0) return 1.0;
// по формуле f=f(n-1)*n.
else return factorr2(n-1)*n; }
real ftimes(long int n, real res)
// ХВОСТОВАЯ РЕКУРСИЯ: Функция умножения
{ if (n==0) return res;
// второго аргумента на все натуральные else return ftimes(n-1,res*n); //
от 1
до значения первого.
}
real factorxx(long int n)
// Процедура вызова рекурсивной функции
{ return ftimes(n,1);
// с хвостовой рекурсией.
}
В файле factorx.c помещены описания пяти функций:
1. factorn — нерекурсивная;
2. factorr1 — рекурсивная ( по схеме n!=n*factorr1(n-1) );
3. factorr2 — рекурсивная ( по схеме n!=factorr2(n-1)*n );
4. ftimes — рекурсивная с хвостовой рекурсией;
5. factorx — функция вызова рекурсивной ftimes.
81
Каждая из них вызывается в главной программе по 10000000 раз для расчёта значений k! (k=50, 75, 100, 125, 150) с вычислением соответ- ствующих временных затрат.
#include
//
Файл timefact.c
#include
#include "mytype.h"
real factorn (long int); real factorr1(long int);
real factorr2(long int); real ftimes
(long int,real);
real factorxx(long int);
int main()
{ real fn, fr1, fr2, fr3, frx;
double t01,t12,t23,t34,t45;
double s01,s12,s23,s34,s45;
long int n=10000000, i, k, t0,t1,t2,t3,t4,t5;
s01=s12=s23=s34=s45=0;
printf(" Число нерекурсивных вызовов (n)=%ld\n",n);
printf("%25s %30s\n"," Форма описания функции:",
"Нерекурсивная
Рекурсивная");
printf("%73s\n","-1-
-2-
-3-
-4-");
for (k=50; k<=150; k+=25)
{
t0=clock(); for (i=1;i<=n;i++) fn=factorn (k);
t1=clock(); for (i=1;i<=n;i++) fr1=factorr1(k);
t2=clock(); for (i=1;i<=n;i++) fr2=factorr2(k);
t3=clock(); for (i=1;i<=n;i++) fr3=ftimes(k,1.0);
t4=clock(); for (i=1;i<=n;i++) frx=factorxx(k);
t5=clock();
t01=((double)(t1-t0))/CLOCKS_PER_SEC;
t12=((double)(t2-t1))/CLOCKS_PER_SEC;
t23=((double)(t3-t2))/CLOCKS_PER_SEC;
t34=((double)(t4-t3))/CLOCKS_PER_SEC;
t45=((double)(t5-t4))/CLOCKS_PER_SEC;
s01+=t01; s12+=t12; s23+=t23; s34+=t34; s45+=t45;
printf(" Время расчёта %5ld!: %10.2lf%10.2lf%10.2lf%10.2lf%10.2lf\n",
k,t01,t12,t23,t34,t45);
}
printf(" Итоги по колонкам
: %10.2lf
%8.2lf
%8.2lf
%8.2lf
%8.2lf\n",
s01, s12, s23, s34, s45);
printf(" Полное время
:%10.2lf\n", s01+s12+s23+s34+s45);
printf("\n
Значение
150!
=
%8.1le
%8.1le
%8.1le
%8.1le
%8.1le\n",
fn,fr1,fr2,fr3,frx);
return 0;
}
На следующей странице приведены результаты пропусков этой програм- мы при различных уровнях оптимизации.
82
Оптимизация -O0.
factorn factorr1
factorr2
ftimes factorrx
----------------
Время расчёта
50!:
2.62 2.94 3.09 8.60 8.74
Время расчёта
75!:
4.30 4.55 4.73 13.13 13.27
Время расчёта
100!:
5.70 6.12 6.29 17.41 17.56
Время расчёта
125!:
7.08 7.59 7.81 21.70 21.84
Время расчёта
150!:
8.48 9.10 9.41 25.99 26.12
Итоги по колонкам
:
28.18 30.30 31.33 86.83 87.53
Полное время
:
264.17
Оптимизация -O1.
factorn factorr1
factorr2
ftimes factorrx
----------------
Время расчёта
50!:
1.05 2.78 2.80 3.82 3.93
Время расчёта
75!:
2.04 4.46 4.46 5.88 5.99
Время расчёта
100!:
2.67 5.90 5.92 7.76 7.89
Время расчёта
125!:
3.29 7.24 7.24 9.65 9.78
Время расчёта
150!:
3.93 8.60 8.61 11.55 11.67
Итоги по колонкам
:
12.98 28.98 29.03 38.66 39.26
Полное время
:
148.91
Оптимизация: -O2.
factorn factorr1
factorr2
ftimes factorrx
-----------------
Время расчёта
50!:
1.04 2.85 2.85 1.00 0.99
Время расчёта
75!:
2.00 4.35 4.35 2.00 2.03
Время расчёта
100!:
2.62 5.74 5.74 2.64 2.65
Время расчёта
125!:
3.26 7.09 7.10 3.27 3.28
Время расчёта
150!:
3.89 8.53 8.51 3.90 3.91
Итоги по колонкам
:
12.81 28.56 28.55 12.81 12.86
Полное время
:
95.59
Оптимизация: -O3.
factorn factorr1
factorr2
ftimes factorrx
-----------------
Время расчёта
50!:
1.04 2.13 1.71 1.00 0.99
Время расчёта
75!:
2.00 3.15 2.63 2.01 2.02
Время расчёта
100!:
2.63 4.30 3.59 2.64 2.65
Время расчёта
125!:
3.26 5.27 4.47 3.26 3.28
Время расчёта
150!:
3.89 6.39 5.58 3.89 3.91
Итоги по колонкам
:
12.82 21.24 17.98 12.80 12.85
Полное время
:
77.69
Как видим, при опциях оптимизации -02 и -O3 время работы функции с хвостовой рекурсией практически совпадает со временем работы нере- курсивной.
83
2.7.2
ФОРТРАН-95 (компилятор gfortran)
Поместим ФОРТРАН-аналоги СИ-функций factorn, factorr1, factorr2,
ftimes и factorrx в модуль myfactor.f95:
module myfactor implicit none contains function factorn(n)
real
(8) factorn, p integer(8) n, i p=1d0; do i=1,n p=p*i enddo factorn=p end function factorn recursive real(8) function factorr1(n) result(w)
integer(8) n if (n.eq.0) then;
w=1d0
else;
w=n*factorr1(n-1)
endif end function factorr1
recursive real(8) function factorr2(n) result(w)
integer(8) n if (n.eq.0) then; w=1d0
else; w=factorr2(n-1)*n endif end function factorr2
recursive real(8) function ftimes(n,res) result(w)
integer(8) n real(8)res if (n.eq.0) then; w=res else; w=ftimes(n-1,res*n)
endif end function ftimes real(8) function factorxx(n) result(w)
integer(8) n w=ftimes(n,1d0)
end function factorxx end module myfactor
84
program timefact; use myfactor; implicit none
!
Файл timefact.f9
integer(8) :: n=10000000, i, k
!...................
real(8) fn, fr1, fr2, fr3, frx real t0,t1,t2,t3,t4,t5, t01,t12,t23,t34,t45
real s01,s12,s23,s34,s45
s01=0.0; s12=0.0; s23=0.0; s34=0.0; s45=0.0
write(*,*) ’ Число нерекурсивных вызовов (n)=’,n write(*,*) ’ Форма описания функции :
Нерекурсивная
Рекурсивная’
write(*,’(a75)’) ’-1-
-2-
-3-
-4-’
do k=50,150,25
call cpu_time(t0); do i=1,n; fn=factorn(k);
enddo call cpu_time(t1); do i=1,n; fr1=factorr1(k);
enddo call cpu_time(t2); do i=1,n; fr2=factorr2(k);
enddo call cpu_time(t3); do i=1,n; fr3=ftimes(k,1d0); enddo call cpu_time(t4); do i=1,n; frx=factorxx(k);
enddo call cpu_time(t5);
t01=t1-t0; t12=t2-t1; t23=t3-t2; t34=t4-t3; t45=t5-t4
s01=s01+t01; s12=s12+t12; s23=s23+t23; s34=s34+t34; s45=s45+t45
write(*,&
&
’(’’ Время расчёта ’’,i5,’’!....:’’,f10.2,f10.2,f10.2,f10.2,f10.2)’)&
&
k,t01,t12,t23,t34,t45
enddo write(*,’(" Итоги по колонкам
:",&
&
f10.2,2x,f8.2,2x,f8.2,2x,f8.2,2x,f8.2)’) s01, s12, s23, s34, s45
write(*,’(" Полное время
:",f10.2)’) s01+s12+s23+s34+s45
write(*,’(/"
Значение",i5,’’!
=
’’,1P,e8.1,2x,e8.1,2x,e8.1,&
&
2x,e8.2,2x,e8.1/)’)
k,fn,fr1,fr2, fr3, frx end
Оптимизация: -O3.
factorn factorr1
factorr2
ftimes factorrx
Время расчёта
50!....:
5.63 6.29 2.83 5.75 5.80
Время расчёта
75!....:
8.48 9.50 4.21 8.59 8.65
Время расчёта 100!....:
11.25 12.61 5.58 11.56 11.53
Время расчёта 125!....:
14.03 15.70 6.96 14.38 14.37
Время расчёта 150!....:
16.80 18.92 8.54 17.33 17.48
Итоги по колонкам
:
56.19 63.02 28.11 57.61 57.83
Полное время
:
262.77
Ключ оптимизации -O3 при использовании компилятора gfortran реа- лизует наиболее быстрый способ расчёта факториала на основе рекур- сивной функции factorr2, работающей по схеме: n!=(n-1)!*n (вдвое быстрее !!! чем нерекурсивная factorn). Использование хвостовой рекур- сии (хоть и сократило время расчёта до времени работы factorn), тем не менее, привело к более медленному алгоритму нежели схема factorr2,
которая в свою очередь оказалась вдвое медленней исполнимого CИ-кода с явным оформлением хвостовой рекурсии.
85
!
Файл timefact.f9
integer(8) :: n=10000000, i, k
!...................
real(8) fn, fr1, fr2, fr3, frx real t0,t1,t2,t3,t4,t5, t01,t12,t23,t34,t45
real s01,s12,s23,s34,s45
s01=0.0; s12=0.0; s23=0.0; s34=0.0; s45=0.0
write(*,*) ’ Число нерекурсивных вызовов (n)=’,n write(*,*) ’ Форма описания функции :
Нерекурсивная
Рекурсивная’
write(*,’(a75)’) ’-1-
-2-
-3-
-4-’
do k=50,150,25
call cpu_time(t0); do i=1,n; fn=factorn(k);
enddo call cpu_time(t1); do i=1,n; fr1=factorr1(k);
enddo call cpu_time(t2); do i=1,n; fr2=factorr2(k);
enddo call cpu_time(t3); do i=1,n; fr3=ftimes(k,1d0); enddo call cpu_time(t4); do i=1,n; frx=factorxx(k);
enddo call cpu_time(t5);
t01=t1-t0; t12=t2-t1; t23=t3-t2; t34=t4-t3; t45=t5-t4
s01=s01+t01; s12=s12+t12; s23=s23+t23; s34=s34+t34; s45=s45+t45
write(*,&
&
’(’’ Время расчёта ’’,i5,’’!....:’’,f10.2,f10.2,f10.2,f10.2,f10.2)’)&
&
k,t01,t12,t23,t34,t45
enddo write(*,’(" Итоги по колонкам
:",&
&
f10.2,2x,f8.2,2x,f8.2,2x,f8.2,2x,f8.2)’) s01, s12, s23, s34, s45
write(*,’(" Полное время
:",f10.2)’) s01+s12+s23+s34+s45
write(*,’(/"
Значение",i5,’’!
=
’’,1P,e8.1,2x,e8.1,2x,e8.1,&
&
2x,e8.2,2x,e8.1/)’)
k,fn,fr1,fr2, fr3, frx end
Оптимизация: -O3.
factorn factorr1
factorr2
ftimes factorrx
Время расчёта
50!....:
5.63 6.29 2.83 5.75 5.80
Время расчёта
75!....:
8.48 9.50 4.21 8.59 8.65
Время расчёта 100!....:
11.25 12.61 5.58 11.56 11.53
Время расчёта 125!....:
14.03 15.70 6.96 14.38 14.37
Время расчёта 150!....:
16.80 18.92 8.54 17.33 17.48
Итоги по колонкам
:
56.19 63.02 28.11 57.61 57.83
Полное время
:
262.77
Ключ оптимизации -O3 при использовании компилятора gfortran реа- лизует наиболее быстрый способ расчёта факториала на основе рекур- сивной функции factorr2, работающей по схеме: n!=(n-1)!*n (вдвое быстрее !!! чем нерекурсивная factorn). Использование хвостовой рекур- сии (хоть и сократило время расчёта до времени работы factorn), тем не менее, привело к более медленному алгоритму нежели схема factorr2,
которая в свою очередь оказалась вдвое медленней исполнимого CИ-кода с явным оформлением хвостовой рекурсии.
85
2.8
О чем узнали из второй главы? (2-ой семестр)
1. Рекурсия – способ определения какого-либо понятия через само это понятие.
2. Рекурсивная процедура – это процедура явно или неявно (т.е.
через посредника), обращающаяся сама к себе.
3. Всякий алгоритм может быть описан как в рекурсивной форме, так и в нерекурcивной. Способ выбирает программист.
4. В нерекурсивном алгоритме аналог рекурсии моделируется опера- тором цикла.
5. Старые версии ФОРТРАНа не допускали рекурсиных процедур.
6. Современный ФОРТРАН допускает рекурсивные процедуры, одна- ко, в отличие от СИ, ФОРТРАН-процедура по умолчанию считает- ся нерекурсивной. (рекурсивности описания ФОРТРАН-процедуры необходимо указать особо служебным словом recursive).
7. В С и С++ изначально предполагается возможность рекурсии.
8. При описании рекурсивной функции всегда должно быть задано условие прекращения ее рекурсивного вызова.
9. Глубина рекурсии – число промежуточных рекурсивных вызовов функции.
10. Запись рекурсивной функции обычно выглядит проще нерекурсив- ной. Однако время её работы может оказаться значительно больше
(из-за временных затрат на каждый рекурсивный вызов), а отладка
– сложнее. Поэтому при выборе рекурсивного описания функции выгодно уменьшать количество рекурсивных вызовов, запоминая
(если возможно) их результаты (например, в массиве).
11. Xвостовая рекурсия — описание рекурсивного алгоритма так, что его рекурсивный вызов оказывается последним выполняемым дей- ствием.
86
2.9
Второе домашнее задание (2-ой семестр)
Каждая программа, тестирующая процедуры, должна оценивать время работы соответственно обоих вариантов расчета (нерекурсивного и ре- курсивного), обеспечивая ввод исходных данных из файла и вывод ре- зультата в файл.
make-файл должен инициировать выполнение программы, используя утилиту time.
1. Разработать на ФОРТРАНе и СИ нерекурсивную и рекурсивную процедуры a) целочисленного деления одного целого числа на другое, моде- лируя операцию деления операциями вычитания;
b) нахождения остатка от целочисленного деления одного целого на другое, моделируя операцию нахождения остатка операция- ми вычитания;
c) перевода введенного целого в двоичную систему счисления d) возведения основания в неотрицательную целочисленную сте- пень, моделируя операцию возведения в степень операциями умножения.
e) перевода введенного неотрицательного меньшего единицы ве- щественного числа в двоичную систему счисления;
f) которые выясняют, является ли заданное натуральное простым;
2. Продемонстрировать на ФОРТРАНе и СИ работоспособность алго- ритма Ханойская башня (см. лекцию).
3. Продемонстрировать на ФОРТРАНе и СИ работоспособность всех лекционных алгоритмов, реализующих расчет чисел Фибоначчи.
4. Продемонстрировать на ФОРТРАНе и СИ работу лекционных ал- горитмов поиска изолированного корня уравнения f(x)=0 методом половинного деления.
5. Добавить к программе тестирования рекурсивной и нерекурсивной функций моделирования операции возведения в степень через по- средство операции умножения вызов соответствующей рекурсивной функции, использующей схему хвостовой рекурсии.
87
3
Немного о массивах, структурах и указателях
3.1
Массивы
В программировании одни простые переменные не всегда удобны. При необходимости сопоставить одному имени много значений, одновремен- но хранимых в оперативной памяти (например, матрицу) используют структуру данных массив – набор конечного количества нумерованных элементов одинакового типа. Массив называют одномерным (или вектором), если в его описании указано, что все элементы распределены вдоль одного измерения (указать элемент можно его порядковым номе- ром). Так положение точки задаётся вектором, содержащим три элемен- та (первый — абсцисса, второй — ордината, третий — апликата):
3.1.1
ФОРТРАН
program tvector; implicit none !
Файл tvector.f95
real a(3), c(3), d(3)
! Число в скобках - число элементов.
real b(3) / 1.0, 2.0, 3.0 /
! Старый способ инициализации вектора;
data c / 4.0, 5.0, 6.0 /
! ещё один старый способ инициализации;
data d / 3 * 8.0 /
! ещё один старый способ инициализации;
real, dimension (3) :: g=3*8.0 ! Описание массива возможное в ФОРТРАНе-90
integer i; real :: e(3)=(/ 7.0, 8.0, 9.0 /) ! Пример инициализации массива real, dimension (3) :: f=(/(5*i,i=3,1,-1)/) ! через его конструктор (/ /).
a=(/ 10, 11, 12 /)
! Справа неименованный массив!
write(*,*) ’ a=’,a; write(*,*) ’ b=’,b
! Фортран позволяет для вывода write(*,*) ’ c=’,c
! всего массива указать только write(*,*) (a(i),i=1,3); write(*,*) (b(i),i=1,3,2) ! его имя, хотя возможен write(*,*) (c(i),i=3,1,-1)
! и поэлементный вывод в виде write(*,*) ’ d=’,d;
! циклоподобного списка вывода.
write(*,*) ’ g=’,g
!
end a=
10.000000 11.000000 12.000000
! Результат b=
1.0000000 2.0000000 3.0000000
! программы tvector c=
4.0000000 5.0000000 6.0000000 10.000000 11.000000 12.000000 1.0000000 3.0000000 6.0000000 5.0000000 4.0000000
d=
8.0000000 8.0000000 8.0000000
! Сравните содержимое g=
24.000000 24.000000 24.000000
!
d и
g
В ФОРТРАНе описание массива допускает изменение нумерации (индек- сации) элементов. Например, real a(-1:1) или real b(11:13). Правда,
вряд ли подобное изменение удобно для описания положения точки.
88
3.1.2
CИ
#include
// СИ-пример аналогичного описания координат точки.
int main(void)
{ float a[3];
// Число в скобках - число элементов.
float b[3]={ 1, 2, 3 };
// Инициализация вектора при описании.
float e[]={4, 5, 6};
// В СИ число элементов может определиться int i;
// по числу инициализирующих значений.
a[0]=10.0; a[1]=11.0; a[2]=12.0;
printf(" a=%p\n",a);
printf(" b=%e %e %e\n",b[0],b[1],b[2]);
for (i=0;i<=2;i++)
{ printf("%e...",e[i]);}
printf("\n");
printf("Адрес a[0]=%p, а содежимое a[0]=%e \n",
a , *a);
printf("Адрес a[0]=%p, а содежимое a[0]=%e \n", &a[0], *a);
printf("Адрес a[1]=%p, а содежимое a[1]=%e \n", (a+1), *(a+1));
printf("Адрес a[1]=%p, а содежимое a[1]=%e \n", &a[1], *(a+1));
printf("Адрес a[2]=%p, а содежимое a[2]=%e \n", (a+2), *(a+2));
printf("Адрес a[2]=%p, а содежимое a[2]=%e \n", &a[2], *(a+2));
return 0;
}
1. СИ-индексация массива всегда начинается с нуля.
2. Имя СИ-массива есть указатель (адрес) его начального элемента.
По имени массива в сочетании с операцией разыменования выво- дится значение лишь начального элемента (в ФОРТРАНе — все).
3. Функция форматного вывода printf предоставляет для вывода ука- зателя спецификатор p.
4. Синтаксически доступ к содержимому нужного элемента массива можно оформить двояко: по традиции a[0], a[1], a[2] или через опе- рацию разыменования указателя *(a+i). Запись *(a+i), где i —
индекс элемента, означает:
1) извлечь адрес &a[0] начального элемента переменной a;
2) увеличить его на i*sizeof(тип_элемента), т.е. на число байт,
нужное для i элементов (c 0 по (i-1)), вычисляя адрес a[i]-го;
3) разыменовать указатель *(a+i), получая доступ к a[i].
5. Операция выделения элемента массива посредством заключения его индекса в квадратные скобки имеет более высокий приоритет неже- ли операция & (взятия адреса). Поэтому, например, при записи вы- ражения &a[0] можно a[0] не заключать в круглые скобки.
89
6.
a=0xbf99afd0
// Результат пропуска b=1.000000e+00 2.000000e+00 3.000000e+00
// СИ-программы из
4.000000e+00...5.000000e+00...6.000000e+00...
// этого пункта.
Адрес a[0]=0xbf99afd0, а содежимое a[0]=1.000000e+01 // printf по формату
Адрес a[0]=0xbf99afd0, а содежимое a[0]=1.000000e+01 // %p выводит значение
Адрес a[1]=0xbf99afd4, а содежимое a[1]=1.100000e+01 // указателя
Адрес a[1]=0xbf99afd4, а содежимое a[1]=1.100000e+01 // в шестнадцатеричном
Адрес a[2]=0xbf99afd8, а содежимое a[2]=1.200000e+01 // виде c префиксом 0x
Адрес a[2]=0xbf99afd8, а содежимое a[2]=1.200000e+01 //
3.2
Структуры
В программировании наряду с массивами (наборами элементов одинако- вого типа) широко востребован именованный тип данных, который ха- рактеризуется набором элементов разных типов.
Например, строка каталога звёзд содержит имя звезды, её координа- ты, звёздную величину, спектральный класс и т.д. Обработка каждой ха- рактеристики требует операций, соответствующих её типу данных, хотя для человека удобна возможность обозначить весь набор, относящийся к одной звезде, одним именем. В случае массива элементы однотипны и состоят из одинакового числа байтов (адрес элемента просто вычислить по его индексу). В случае разнородной информации размер памяти, от- водимой под элементы разных типов, может оказаться разным (расчёт адреса по номеру элемента будет не так прост как в случае массива).
Упорядочение элементов разных типов по номеру неудобно и для человека, т.к. обезличивает их смысловую нагрузку. Вместо числового индекса гораздо важнее видеть имя, указывающее назначение данного
(a.ra right ascention — прямое восхождение звезды; a.dec declination —
её склонение) и т.д. Подобный подход иногда предпочтительнее даже,
когда вполне могли бы обойтись и массивом. Например, при написании программы, работающей с координатами точки, удобнее иметь дело с обозначениями a.x, a.y и a.z вместо a(1), a(2) и a(3).
Языки программирования для организации именованной совокупно- сти возможно разнотипных элементов предоставляют синтаксическую конструкцию, которая называется в ФОРТРАНе — производным ти- пом (служебное слово type, в СИ/C++ — структурой (служебное сло- во struct). Эта конструкция определяет новое имя, которое “понимает- ся” программой как имя типа данных, а также имена и типы, входящих в него элементов. Последние часто называют полями структуры.
90
3.2.1
ФОРТРАН
В программе tstcoord0 описан тип coord, с полями x, y, z и инициали- зированы coord-переменные:
program tstcoor0; implicit none type coord
! В качестве имени нового типа --- слово coord.
real x, y, z
!
x, y, z - его поля типа real.
end type coord
! Завершение описания типа coord.
type cube
! cube - имя ещё одного типа.
v - имя его поля,
type (coord) v(8) ! являющегося массивом из 8 элементов, каждый из end type cube
! которых, в свою очередь есть структура с именем coord.
type (coord) :: a, b, c, w
! Описание четырёх переменных типа coord.
type (cube) ::
t
! Описание одной переменной типа cube.
integer j a=coord(1.0, 2.0, 3.0); b=coord(4.0, 5.0, 6.0)
! Присваивание значений c=coord(7.0, 8.0, 9.0)
! переменным типа coord write(*,*) ’ a: ’,a; write(*,*) ’ b: ’,b; write(*,*) ’ c: ’,c w=a; a=c; c=w write(*,*) ’ a: ’,a; write(*,*) ’ b: ’,b; write(*,*) ’ c: ’,c
!
и t=cube ((/ coord(4,4,4), coord(4,4,5), coord(4,5,5), coord(4,5,4),&
! типа coord(5,4,4), coord(5,4,5), coord(5,5,5), coord(5,5,4)/))
! cube write(*,’((a,i5,3e15.7))’) ’ t: ’,1,t%v(1), (’
’,j,t%v(j),j=2,4),&
&
(’
’,j,t%v(j),j=5,8)
end
В tstcoord0 помимо типа coord описан и тип cube c одним полем типа одномерного массива из восьми элементов типа coord. При инициали- зации значения полей типа coord, разделяются запятыми. Их список заключается в круглые скобки и предваряется именем типа. При иници- ализации поля v типа cube необходимо использовать конструктор мас- сива, заключая весь список значений типа coord в символы (/ и /).
a:
1.0000000 2.0000000 3.0000000
! Результат работы b:
4.0000000 5.0000000 6.0000000
! tstcoord0.
c:
7.0000000 8.0000000 9.0000000
a:
7.0000000 8.0000000 9.0000000
b:
4.0000000 5.0000000 6.0000000
c:
1.0000000 2.0000000 3.0000000
t:
1 0.4000000E+01 0.4000000E+01 0.4000000E+01 2
0.4000000E+01 0.4000000E+01 0.5000000E+01 3
0.4000000E+01 0.5000000E+01 0.5000000E+01 4
0.4000000E+01 0.5000000E+01 0.4000000E+01 5
0.5000000E+01 0.4000000E+01 0.4000000E+01 6
0.5000000E+01 0.4000000E+01 0.5000000E+01 7
0.5000000E+01 0.5000000E+01 0.5000000E+01 8
0.5000000E+01 0.5000000E+01 0.4000000E+01 91