Основы программирования

Арифметический цикл


В рассмотренных выше программах в цикле перебираются элементы массива с индексом i, где i пробегает значения от 0 до n-1 (в последней программе - от 0 до n, поскольку многочлен n-й степени имеет n+1 коэффициент). Для удобства записи таких циклов большинство языков программирования предоставляет конструкцию арифметического цикла. В нем используется так называемая переменная цикла, т.е. целочисленная переменная, которая последовательно принимает значения в указанных пределах. Для каждого значения переменной цикла выполняется тело цикла, в котором эта переменная может использоваться.

цикл для i от a до b | . . . | тело цикла | . . . конец цикла

Здесь переменная цикла i последовательно принимает значения от a до b с шагом 1, где a и b - некоторые целочисленные выражения. Таким образом, всего тело цикла выполняется b-a+1 раз. Если b меньше, чем a, то цикл не выполняется ни разу. Возможна также конструкция арифметического цикла с шагом s, отличным от единицы:

цикл для i от a до b шаг s | . . . | тело цикла | . . . конец цикла

Переменная цикла последовательно принимает значения a, a+s, a+2s, ... до тех пор, пока ее значение содержится в отрезке [a,b]. Для каждого значения переменной цикла выполняется тело цикла. Шаг может быть и отрицательным, в этом случае b должно быть не больше, чем a, иначе цикл не выполняется ни разу.

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

цикл для i от a до b | . . . | тело цикла | . . . конец цикла

эквивалентна конструкции

i := a цикл пока i <= b | . . . | тело цикла | . . . | i := i + 1 конец цикла

Однако традиционно арифметический цикл включается в большинство языков высокого уровня. С использованием арифметического цикла схема Горнера переписывается следующим образом:

вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t) | дано: n -- степень многочлена | a[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | цикл для i от 0 до n | | p := p * t + a[i]; // Вычисление нового значения | | // при добавлении коэффициента | конец цикла | ответ := p; конец алгоритма

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

вещ алгоритм схема Горнера2(вх: цел n, вещ b[n+1], вещ t) | дано: n -- степень многочлена | b[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | цикл для i от n до 0 шаг -1 | | p := p * t + b[i]; // Вычисление нового значения | | // при добавлении коэффициента | конец цикла | ответ := p конец алгоритма



Содержание раздела