Лекции, страница 6

Задача сводится к нахождению корня функции y = x2-aна отрезке [0,b], где b = max(1,a). На этом отрезке функция имеет ровно один корень, поcколькуона монотонно возрастает и на концах отрезка принимает значения разных знаков (или нулевоезначение при a = 0 или a = 1).Идея алгоритма состоит в том, что отрезок делится пополам и выбирается та половина, накоторой функция принимает значения разных знаков.

Эта операция повторяется до тех пор,пока длина отрезка не станет меньше, чем ε. Концы текущего отрезка содержатся в переменныхx0, x1. В данном случае функция монотонно возрастает при x 0. Инвариантом цикла являетсяутверждение о том, что функция принимает отрицательное или нулевое значение в точке x0 иположительное или нулевое значение в точке x1. Цикл рано или поздно завершается, посколькупосле каждого выполнения тела цикла длина отрезка [x0,x1] уменьшается в два раза.Приведем полный текст программы:#include <stdio.h> // Описания стандартного ввода-выводаint main()doubledoubledoubledouble{a;// Число, из которого извлекается кореньx, x0, x1;// [x0, x1] - текущий отрезокy;// Значение ф-ции в точке xeps = 0.000001; // Точность вычисления корняprintf("Введите число a:\n");scanf("%lf", &a);if (a < 0.0) {printf("Число должно быть неотрицательным.\n");return 1; // Возвращаем код}//некорректного завершения//x0x1ifЗадаем концы отрезка= 0.0;= a;(a < 1.0) {x1 = 1.0;}// Утверждение: x0 * x0 - a <= 0,//x1 * x1 - a >= 0while (x1 - x0 > eps) {// Инвариант: x0 * x0 //x1 * x1 x = (x0 + x1) / 2.0; //y = x * x - a;//a <= 0,a >= 0середина отрезка [x0,x1]значение ф-ции в точке xif (y >= 0.0) {x1 = x; // выбираем левую половину отрезка}else {x0 = x; // выбираем правую половину отрезка}}18// Утверждение:////x = (x0 + x1) /x0 *x1 *x1 2.0;x0x1x0//- a <= 0,- a >= 0,<= epsКорень := середина отрезка// Печатаем ответprintf("Квадратный корень = %lf\n", x);}return 0; // Возвращаем код успешного завершенияВыход из цикла break, переход на конец цикла continueЕсли необходимо прервать выполнение цикла, следует использовать операторbreak;Оператор break применяется внутри тела цикла, заключенного в фигурные скобки.Пример: требуется найти корень целочисленной функции f(x), определенной дляцелочисленных аргументов.int f(int x);// Описание прототипа функции.

. .int x;. . .// Ищем корень функции f(x)x = 0;while (1) {if (f(x) == 0) {break; // Нашли корень}// Переходим к следующему целому значению x//в порядке 0, -1, 1, -2, 2, -3, 3, ...if (x >= 0) {x = (-x - 1);}else {x = (-x);}}// Утверждение: f(x) == 0Здесь используется бесконечный цикл "while (1)". Выход из цикла осуществляется с помощьюоператора "break".Иногда требуется пропустить выполнение тела цикла при каких-либо значениях изменяющихсяв цикле переменных, переходя к следующему набору значений и очередной итерации. Дляэтого используется операторcontinue;Оператор continue, так же, как и break, используется лишь в том случае, когда тело цикласостоит более чем из одного оператора и заключено в фигурные скобки.

Его следует пониматькак переход на фигурную скобку, закрывающую тело цикла.Цикл forПопулярный в других языках программирования параметрический цикл в языке Си реализуется с помощью циклаfor. Он выглядит следующим образом:for (инициализация; условие продолжения; итератор)тело цикла;Инициализация выполняется один раз перед первой проверкой условия продолжения ипервым выполнением тела цикла.

Условие продолжения проверяется перед каждымвыполнением тела цикла. Если условие истинно, то выполняется тело цикла, иначе циклзавершается. Итератор выполняется после каждого выполнения тела цикла (перед следующейпроверкой условия продолжения).Поскольку условие продолжения проверяется перед выполнением тела цикла, цикл forявляется, подобно циклу while, циклом с предусловием. Если условие продолжения невыполняется изначально, то тело цикла не выполняется ни разу.Рассмотрим пример суммирования массива с использованием цикла for:19double a[100]; // Массив a содержит не более 100 эл-товint n;// Реальная длина массива a (n <= 100)double sum;// Переменная для суммы эл-тов массиваint i;// Переменная цикла.

. .sum = 0.0;for (i = 0; i < n; ++i) {sum += a[i]; // Увеличиваем сумму на a[i]}Здесь целочисленная переменная i используется в качестве переменной цикла. В оператореинициализации переменной i присваивается значение 0. Условием продолжения цикла являетсяусловие i<n. Итератор ++i увеличивает переменную i на единицу. Таким образом, переменная iпоследовательно принимает значения 0, 1, 2,..., n-1. Для каждого значения i выполняется телоцикла.ЗАДАНИЯ1. Напишите функцию, реверсируюшую строку (переставляющуюсимволы в строке в обратном порядке).2.

Вычислить y=x1+x1x2+x1x2x3+:+ x1x2 *** xm,где m - либо номер первого отрицательного элемента массива x,либо общее количество элементов n в массиве x.3. Напишите программу, печатающую таблицу умножения для чисел от 0 до 9 в десятичнойсистеме счисления.20Представление программы в виде функцийПрототипы функцийФункция - это самостоятельная единица программы, созданная для решения конкретной задачи.

Функция вязыке С играет ту же роль, что и подпрограммы или процедуры в других языках. Функциями удобно пользоваться,например, если необходимо обработать один и тот же код программы. Как и переменные, функции надо объявлять(declare). Функцию необходимо объявить до её использования.Каждая функция языка С имеет имя и список аргументов (формальных параметров). Функции могутвозвращать значение.

Это значение может быть использовано далее в программе. Так как функция может вернутькакое-нибудь значение, то обязательно нужно указать тип данных возвращаемого значения. Если тип не указан, топо умолчанию предполагается, что функция возвращает целое значение (типа int). После имени функции принятоставить круглые скобки (это касается вызова функции её объявления и описания). В этих скобках перечисляютсяпараметры функции, если они есть. Если у функции нет параметров, то при объявлении и при описании функциивместо <список параметров> надо поставить void - пусто.Объявление (прототип) функции имеет вид:тип <имя функции>(список параметров);Обратите внимание на то, что при описании функции после заголовка функции тип <имя функции>(списокпараметров) точка с запятой не ставится, а при объявлении функции точка с запятой ставится.

Прототип функциисообщает информацию об имени функции, типе возвращаемого значения, количестве и типах ее аргументов.Пример:int gcd(int x, int y);Описан прототип функции gcd, возвращающей целое значение, с двумя целыми аргументами.Имена аргументов x и y здесь являются лишь комментариями, не несущими никакойинформации для компилятора. Их можно опускать, например, описаниеint gcd(int, int);является вполне допустимым.Вызов функции делается следующим образом:<имя функции>(параметры);или<переменная>=<имя функции>(параметры);int n=0;n = gcd(10,20);При вызове функции так же ставиться точка с запятой.Формальный аргумент - переменная в вызываемой программе, а фактический аргумент - конкретноезначение, присвоенное этой переменной вызывающей программой.

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

Например:print_num(i,j){int i,j;printf("значение i=%d. Значение j=%d.", i,j);}Обращение в программе к данной функции будет таковым:print_num(6,19);В языке Си функциям передаются значения фактических параметров. При вызове функциизначения параметров копируются в аппаратный стек. Следует четко понимать, что изменениеформальных параметров в теле функции не приводит к изменению переменных вызывающейпрограммы, передаваемых функции при ее вызове, - ведь функция работает не с самими этимипеременными, а с копиями их значений. Если необходимо, чтобы функция могла изменитьзначения переменных вызывающей программы, надо передавать ей указатели на этипеременные.