Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Переменная называется индуктивной, если она при выполнении цикла принимает значения, образующие арифметическую прогрессию.
Любой из следующих двух случаев является достаточным для того, чтобы переменная была индуктивной:
1. В теле цикла лишь в одном операторе присваивания эта переменная встречается в качестве генератора, это вхождение в теле цикла встречается раньше использований и в этом операторе данная переменная линейно выражается через счетчик цикла.
2. В теле цикла данная переменная рекуррентно перевычисляется, причем рекуррентная зависимость имеет вид A=A+Const, где A – индуктивная переменная, а Const – заранее известное число.
Пример 122. В рассматриваемом цикле переменные INC и I2 являются индуктивными.
INC=N
DO 99 I=1,N
I2=2*I-1
X(INC)=Y(I)+Z(I2)
INC=INC-1
T(INC)=A(I)
99 CONTINUE
Если индуктивные переменные встречаются в индексных выражениях переменных, то они затрудняют вычисление информационных зависимостей. Для вычисления информационных зависимостей индуктивную переменную можно выразить через счетчик цикла и всюду по тексту заменить эту переменную ее значением. Приведенный выше цикл преобразится к виду
DO 99 I=1,N
X(N-I+1)=Y(I)+Z(2*I-1)
T(N-I)=0
99 CONTINUE
INC=1
I2=2*N-1
Конец примера.
Для выражения индуктивных переменных через счетчик цикла надо использовать тот факт, что I-ый член арифметической прогрессии равен первому члену плюс разность прогрессии, умноженная на (I-1). Рассмотрим получение этих формул для обоих видов индуктивных переменных.
1. В теле цикла лишь в одном операторе присваивания эта переменная встречается в качестве генератора и линейно выражается через счетчик цикла. Тогда выполняется преобразование подстановка. Заметим, что всякое использование индуктивной переменной, которое встречается ниже по тексту генератора, заменяется просто правой частью этого оператора присваивания.
Если индуктивная переменная рекуррентно перевычисляется, то ее вхождения могут встречаться до генератора и после, и такие вхождения будут по-разному выражаться через счетчик цикла (они заменяются на (I-1)-ый и I-ый члены арифметической прогрессии соответственно).
Пример 123.
K=3
J=N
do 99 I=1,N
B(I)=(A(J)+A(K))/2
K=K+1
J=I
99 CONTINUE
В этом цикле переменная K является индуктивной, а переменная J - охватывающая. Этот цикл эквивалентен следующему.
K=3
J=N
B(1)=(A(J)+A(K))/2
K=K+1
J=1
DO 99 I=2,N
B(I)=(A(J)+A(K))/2
K=K+1
J=I
99 CONTINUE
Конец примера.
Переменная называется охватывающей, если при выполнении цикла все ее значения, кроме, возможно, первого, образуют арифметическую прогрессию. Индуктивная переменная является частным случаем охватывающей. Охватывающая переменная не всегда является индуктивной. Например, если в первом случае разрешить появление этой переменной в качестве использования раньше, чем, в качестве генератора.
Пример 124.
J=N
do 99 I=1,N
B(I)=(A(J)+A(I))/2
J=I
C(I)=(A(J)+A(I))/2
99 CONTINUE
Если отщепить от цикла первую итерацию, то охватывающая переменная становится индуктивной.
Конец примера.
Преобразование циклов, содержащих охватывающие переменные, состоит в следующем:
1. Отделяем от цикла первую итерацию. Для остальных итераций охватывающая переменная принимает значения, образующие арифметическую прогрессию.
2. В оставшейся части цикла заменяем охватывающую переменную выражениями, содержащими счетчики цикла: при этом необходимо учитывать, что вхождения охватывающей переменной, которые встречаются до генератора и после имеют разные значения.
Рассмотренный выше цикл с охватывающей переменной может быть преобразован к следующему фрагменту программы
J=N
if (N>=1) then
B(1)=(A(J)+A(1))/2
C(1)=(A(1)+A(1))/2
do 99 I=1,N
B(I)=(A(I-1)+A(I))/2
99 C(I)=(A(I)+A(I))/2
end if
J=N
Кроме индуктивных и охватывающих переменных в теле цикла могут встречаться и другие переменные, меняющие свое значение в процессе выполнения цикла.
Пример 125. Следующая программа реализует алгоритм параллельной прогонки. Переменная L меняет свои значения в процессе выполнения внешнего цикла. Она не является индуктивной или охватывающей, поскольку значения этой переменной образуют геометрическую прогрессию.
do 99 K=1,log(N) %%N=2**M
L=2**(K-1)
do 99 J=L+1,N
H(J)= H(J)-A(J)*H(J-L)
A(J)=A(J)*A(J-L)
99 CONTINUE
Конец примера.
Пример 126.
do 99 I=1,N
K=2*K
L=2*L+I
KK=K+1
J=L-K
C(I)=A(J)+B(KK).
99 CONTINUE
В этом примере переменные K, L, KK, J по-разному меняют свои значения в процессе выполнения цикла, но ни одна из них не является индуктивной или охватывающей переменной.
Конец примера.
Дополнительные примеры.
Пример 127. Рассматриваемый цикл содержит охватывающую переменную
DO 99 I=1,N
Y(I) = W(I2+3)
I2=2*I-1
X(I)=Y(I)+Z(I2)
99 CONTINUE
равносилен следующему
Y(1) = W(I2+3)
I2=1
X(1)=Y(1)+Z(1)
DO 99 I=1,N
Y(I) = W((2*(I-1)-1)+3)
I2=2*I-1
X(I)=Y(I)+Z(2*I-1)
99 CONTINUE
Конец примера.
Дата: 2018-12-21, просмотров: 554.