Материал: lectures_3

k =1

Решение Для упрощения процесса разработки алгоритма, который необходимо

организовать, перепишем исходное выражение для вычисления суммы в следующем виде:

n

s = åak , где

k =1

k*k

a k = Õj

j =k

Из соотношений, приведенных выше, следует, что для вычисления искомой суммы s необходимо организовать два циклических вычислительных процесса. Первый из них предназначен для накопления суммы s, а второй – для вычисления очередного слагаемого ak этой суммы.

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

Из соображений, изложенных выше, следует, что для реализации рассматриваемых циклических процессов необходимо организовать вложенные циклы. Программа, предназначенная для решения рассматриваемой задачи, приведена ниже.

#include<stdio.h>

#include<conio.h>

int main(void)

{

int k, j, n; long s, p; printf(“n=”); scanf(“%d”,&n);

66

printf(“Сумма = %d\n”, s) getch();

return 0;

}

34. Понятие о варианте и инварианте цикла

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

Вариант цикла — неотрицательное выражение, результат вычисления которого уменьшается на каждом шаге цикла.

Инвариант цикла — это логическое высказывание (утверждение), истинность которого должна быть обеспечена в следующих точках цикла:

∙вначале работы цикла (после выполнения его инициализации),

∙в конце каждого шага (перед очередным тестированием условия,

проверяемого в цикле).

Выполнение этих двух условий должно гарантировать выполнение инварианта после окончания работы цикла.

Вариант и инвариант цикла принято оформлять в виде комментариев в тексте программы, предшествующем циклу.

Назначение рассматриваемых понятий является:

∙Помочь программисту организовать цикл.

∙Повысить читабельность программного кода.

∙Помочь программисту убедиться в правильности работы цикла. Пример 1. Вычисление суммы квадратов натуральных чисел. Постановка задачи. Вычислить сумму квадратов первых n напуральных

чисел.

Алгоритм решения этой задачи приведен в п. 1. 26 первой части пособия. Напишем вариант и инвариант цикла для программы, выполняющей необходимые вычисления.

Вариантом цикла в рассматриваемом примере может служить выражение n – i + 1, а инвариантом цикла — утверждение: просуммированы квадраты всех натуральных чисел из диапазона [1, i - 1]. На каждом шаге цикла его вариант цикла численно равен количеству чисел, квадраты которых следует суммировать, а инвариант содержит оценку диапазона чисел, для которых такое суммирование уже выполнено.

Напишем программу, снабдив ее комментариями, содержащими вариант и инвариант цикла. Кроме того, в программе помощью комментариев будут отмечены точки, в которых должна иметь место истинность инварианта цикла. При использовании для организации цикла инструкции for такие

67

точки должны находиться внутри заголовка цикла. Первая из точек должна находиться после выражения инициализации, а вторая после выражения, определяющего продвижение цикла.

#include<stdio.h> int main(void)

{

int i, n, s; printf(“n=”); scanf(“%d”, &n);

/* Вариант : n – i + 1 */

/*

Инвариант цикла : Просуммированы все числа из диапазона

[1, i - 1]

getch(); return 0;

}

Проанализируем работу цикла, воспользовавшись понятиями варианта и инварианта. Для определенности будем полагать, что переменная “n” после выполнения операции ввода имеет значение, равное 3.

После инициализации цикла искомая сумма, представленная переменной s, обнуляется, а счетчик цикла (переменная i) оказывается равным 1. Выбранные инициализирующие значения переменных i и s обеспечивают истинность инварианта после выполнения выражения инициализации (i = 1) инструкции for. Действительно, для i == 1 диапазон чисел ([1, i - 1]), квадраты которых просуммированы, оказывается пустым. То положение, что сумма s пустого диапазона равна нулю, обеспечивает истинность инварианта цикла в рассматриваемой точке цикла. Вариант цикла (n – i + 1) в этой точке оказывается равным 3.

На каждом шаге цикла его вариант уменьшается на 1 и на 1 увеличивается диапазон просуммированных квадратов чисел. После окончания работы цикла параметр цикла i == n + 1. С учетом этого вариант цикла в этой точке будет равен нулю, истинность инварианта цикла будет свидетельствовать о том, что все квадраты чисел из заданного по условию задачи диапазона [1, 3] просуммированы.

Предположим теперь, что при программировании цикла была допущена ошибка, состоящая в том, что в заголовке цикла (инструкции for) в качестве

68

логического выражения вместо правильного отношения i <= n было написано i < n. В этом случае после окончания работы цикла параметр цикла окажется равным n. С учетом этого вариант цикла в этой точке будет равен единице, истинность инварианта цикла будет свидетельствовать о том, что просуммированы квадраты чисел только из диапазона [1, 2]. Это позволяет сделать вывод о том, что квадрат одного числа остался не учтенным. Это позволит устранить допущенную ошибку в организации цикла.

Пример 2. Возведение в целочисленную степень.

Постановка задачи. Пусть требуется вычислить значение выражения a n , не прибегая к использованию стандартной функции pow(). Будем считать основание степени a вещественным, а показатель n – неотрицательным целым числом.

Рассмотрим три различных варианта рещения рассматриваемой задачи. Каждый из вариантов решения будет иметь свой инвариант цикла. Дадим вначале общую характеристику предлагаемых решений.

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

Первый вариант решения. Наиболее очевидное решение может быть получено с учетом следующего соотношения

n

a n = ∏a

i =1

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

вычислений.

// Инвариант p == ai

p = 1.0;

for(int i = 0 /* Инв */; i != n; i++ /* Инв */) p *= a;

Второй вариант решения. Для нахождения искомого результата воспользуемся следующей идеей. Заменим вычисление исходного выражения a n многократным (циклическим) вычислением выражения p * a k . В цикле необходимо уменьшать значение показателя k на 1 и увеличивать значение множителя p. Для обеспечения корректности такой замены достаточно при организации цикла потребовать выполнения следующего инварианта цикла: p * == a n . Цикл должен закончить свою работу в момент, когда переменная k станет равной нулю. Тогда переменная p будет содержать искомый результат вычислений. Ниже приводится фрагмент программы, реализующий вычисление

69

int k = n; // Инв.

while(k != 0)

{

p *= a;

k--; // Инв.

}

Третий вариант решения.

// Инвариант p * b == a n p = 1.0;

int k = n; double b = a; while(k != 0)

{

if(k % 2 == 1)

{

p *= b; k--;

}else

{

b *= b; k /= 2;

}

}

35. Объявления и определения (расширенное рассмотрение)

Объявления и определения уже обсуждались в первой части настоящего пособия в пункте 1.12. Рассмотрение этого вопроса ограничивалось наиболее простыми вариантами их применений, в которых объявлялись простые переменные встроенных типов. Во второй части пособия должны изучаться более сложные программные элементы (функции, указатели, массивы). В связи с этим представляется целесообразным вновь вернуться к рассмотрению этого вопроса.

В общем случае объявление программного элемента состоит из двух структурных частей:

∙последовательности спецификаторов.

∙списка описателей; элементы списка отделяются запятыми Вначале объявления должна записываться последовательность

спецификаторов, а затем список объявителей. Число объявителей в списке определяется числом, объявляемых имен. Объявляемое имя в качестве необязательного компонента может иметь список инициализаторов.

35.1.Спецификаторы объявления

Можно выделить следующие три категории спецификаторов:

70