WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 17 |

Пример: вычисление многочлена по его коэффициентам.

Пусть требуется вычислить многочлены P3(x) 4x3 2x2 1, P5 (x) x5 x4 x3 x2 x 7, P9 (x) x9 2x7 3x6 x5 x2 (1) в точке x=0.6.

Ввиду важности вычисления многочленов составим функцию, осуществляющую вычисление многочлена степени n Pn (x) C0 C1x C2 x2 Cn xn по его коэффициентам Ci. Для эффективного вычисления многочлена используем так называемую схему Горнера (которую на самом деле за 100 лет до Горнера описал Ньютон). Эта схема состоит в том, что многочлен переписывается в следующей форме:

Pn(x) (...((0 x Cn ) x Cn1) x C1) x C.

При таком порядке вычислений для получения значения Pn(x) требуется лишь n умножений и n сложений.

Коэффициенты многочленов будем хранить в массиве с.

Для вычисления многочленов (1) напишем программу, в которой схема Горнера реализована в функции pol().

#include const n = 10;

double pol (int n, double c[ ], double x){ double p=0;

for (int i = n; i >= 0; i – –) p = p*x + c[i];

return p;} void main(){ double x=0.6, p, c[n] = {1, 0, 2, 4};

p=pol(3, c, x);

cout<<”x= ”<

c[0]=7;

c[1]=c[2]=c[3]=c[4]=c[5]=1;

p=pol(5, c, x);

cout<<”x= ”<

c[0]=2; c[2]=1; c[5]=1; c[6]=3; c[7]=2; c[9]=1;

c[1]=[3]=c[4]=c[8]=0;

cout<<”x= ”<

} 16.3. Передача многомерных массивов Если функции передаётся двумерный массив, то описание соответствующего аргумента функции должно содержать количество столбцов; количество строк – несущественно, поскольку фактически передаётся указатель.

Рассмотрим пример функции, перемножающей матрицы А и В;

результат – С.

Размер матриц – не более 10.

const nmax = 10;

void product (int a[ ][nmax], int b[ ][nmax], int c[ ][nmax], int m, int n, int k){ /* m – число строк в матрице a;

n – число строк в матрице b (должно быть равно числу столбцов в матрице a);

k – число столбцов в матрице b.

*/ for (int i=0; i

for (int l=0; l

} } Если заданы, например, квадратные матрицы A и B размером 5 5, то получить их произведение C можно так:

product (A, B, C, 5, 5, 5);

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

Напишем функцию, транспонирующую квадратную матрицу произвольной размерности n.

void trans ( int n, double *p[ ] ) {double x;

for (int i=0; i

double ptr[ ]={(double*)&A[0], (double*)&A[1], (double*)&A[2], (double*)&A[3]};

int n=4;

trans (n, ptr);

for (int i=0; i

for (int j; j cout<<\n”;

} } В функции main матрица представлена двумерным массивом double A[4][4]. Такой массив нельзя непосредственно использовать в качестве фактического параметра, соответствующего формальному double *p[]. Поэтому вводится дополнительный вспомогательный массив указателей double *ptr[]. В качестве начальных значений элементам этого массива присваиваются адреса строк матрицы, преобразованные к типу double*.

Многомерный массив с переменными размерами может быть динамически сформирован внутри функции. В вызываемую функцию его можно передать как указатель на одномерный массив указателей на одномерные массивы с элементами известной размерности и заданного типа.

В качестве примера приведем функцию, формирующую единичную матрицу порядка n.

int** singl (int n){ int **p=new int*[n];

/* Тип int* [n] – массив указателей на целые.

Операция new возвращает указатель на выделенную память под этот массив и тип переменной p есть int**. Таким образом, р есть массив указателей на строки целых будущей матрицы.

*/ if (p = = NULL){ cout<<”Динамический массив не создан!\n”;

exit(1);

} // цикл создания одномерных массивов – строк матрицы:

for (int i=0; i

if( !p[i] ){cout<<”Не создана динамическая строка!\n”; exit(1);} for (int j=0; j

} return p;

} void main(){ int n;

cout<<”\n Задайте порядок матрицы: ”;

cin>>n;

int** matr; //Указатель для формируемой матрицы matr = singl(n);

for (int i=0; i

cout.width(2);

cout<

for (int j=0; j

cout<

} } for(i=0; i

delete matr;

} В этой программе обращение к функции cout.width(k) устанавливает ширину поля следующего вывода в k позиций, что позволяет выровнять вид полученной матрицы.

16.4. Указатели на функции Указатель на функцию определим следующим образом:

Тип_функции (*имя_указателя) (список параметров);

Например, int (*fptr) (double);

Здесь определяется fptr как указатель на функцию с одним аргументом типа double, которая возвращает значение int. Имя функции без следующих за ним ( ) – это указатель на функцию, который содержит адрес начала кода этой функции.

Пример:

void f1(void){ cout<<”\n Выполняется f1().”;



} void f2(void){ cout<<”\n Выполняется f2().”;} void main(){ void (*ptr)(void);

ptr = f2;

(*ptr)(); //вызов функции f2();

ptr = f1;

(*ptr)(); //вызов f1();

ptr(); //альтернативная запись! } Результат:

Выполняется f2().

Выполняется f1().

Выполняется f1().

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

Проиллюстрируем это при решении следующей задачи.

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

// Файл TRAP.CPP double trap(double a, double b, int n, double (*func)(double)){ double x, h = (b-a)/n, i = ((*func) (a) + (*func) (b))/2;

for (x = a; n >1; n – –) i + = (*func)(( x+=h );

return h*i; } //Файл INTEGRAL.CPP #include #include #include #include “trap.cpp“ double f1(double x){ return x*x+sin(3+x);} double f2(double x){ return x/(x*x+1)+exp(-2*x*x);} void main( ){ double a=1, b=3;

double i = trap(a, b, 50, f1);

cout <<”интеграл от первой функции = ”<

i = trap(a, b, 50, f2);

cout <<”интеграл от второй функции = ”<

} Отметим, что в теле функции trap можно также писать обращения func(a), func(b) и т.д.

16.5. Ссылки Тип “ссылка на тип” определяется так: тип&, например:

int& или double& Ссылочные типы устанавливают псевдонимы объектов. Ссылка обязательно должна быть инициализирована. После инициализации использование ссылки дает тот же результат, что и прямое использование переименованного объекта.

Рассмотрим инициализацию ссылки:

int i=0;

int& iref = i;

Здесь создана новая переменная типа ссылка на int с именем iref.

Физически iref – это постоянный указатель на int и, следовательно, значение ссылки после инициализации не может быть изменено. Инициализирующим значением в нашем случае является адрес переменной i, т.е. при инициализации ссылка ведёт себя как указатель.

При использовании ссылка ведёт себя не как указатель, а как переменная, адресом которой она инициализирована:

iref ++; // то же, что и i++;

int *ip=&iref; // то же, что и ip=&i.

Итак, iref стало другим именем, псевдонимом переменной i.

Ссылку можно определить так:

ссылка есть такой постоянный указатель на объект, к которому всегда при его использовании неявно применяется операция разрешения указателя *.

Если тип инициализированной ссылки не совпадает с типом объекта, создаётся новый анонимный объект, для которого ссылка является псевдонимом. Инициализатор преобразуется и его значение используется для установки значения анонимного объекта.

double d=0.0;

int& ir = d; // Создан анонимный объект типа int;

ir = 3.0; // d – не меняется! Здесь создаётся анонимная переменная типа int, которая инициализируется значением, полученным в результате преобразования значения типа double к типу int. Затем ссылка инициализируется значением адреса этой переменной.

Анонимный объект создаётся также, когда инициализатор не является объектом, например, является константой:

int& ir = 3; // Анонимный объект получил значение 3.

Здесь сначала создается анонимный объект типа int и он инициализируется значением 3. После этого создаётся ссылка ir и инициализируется адресом анонимного объекта. Теперь ir – его псевдоним и оператор ir = 8;

устанавливает новое значение этого анонимного объекта.

16.6. Ссылки в качестве параметров функций Ссылки часто используются в качестве формальных параметров функций. Механизм передачи параметров в функции с помощью ссылок называют в программировании передачей аргументов по ссылке. С помощью ссылок можно добиться изменения значений фактических параметров из вызывающей программы (без применения указателей).

void swap (int & x, int & y){ int t = x;

x = y;

y = t;

} Теперь обращение в вызывающей функции имеет вид:

int a = 3, b = 7;

swap (a, b);

Здесь создаются локальные относительно функции swap() переменные x и y ссылочного типа, которые являются псевдонимами переменных a и b и инициализирующиеся переменными a, b. После этого все действия с x и y эквивалентны действиям с a и b, что приводит к изменению значений a и b.

Заметим, что в последнем примере можно обратиться к функции swap() и с аргументами, отличными по типу от int, и даже с аргументами, не являющимися объектами:

float a = 5, b = 2.7;

swap (a, b);

swap (3, a+b);

Однако в этих случаях функция swap() фактически никакого действия со своими аргументами не выполняет. Создаются временные объекты типа int, которые инициализируются значениями, полученными в результате преобразования a, b, a+b к типу int; затем ссылки x и y инициализируются значениями адресов этих анонимных объектов;

анонимные объекты и будут изменены. Фактические параметры же останутся неизменными.

Компилятор выдаст предупреждение, что он вынужден завести временные переменные, и будет работать с ними.

16.7. Рекурсивные функции Ситуацию, когда функция тем или иным образом вызывает саму себя, называют рекурсией. Рекурсия, когда функция обращается сама к себе непосредственно, называется прямой; в противном случае она называется косвенной.

Все функции языка С++ (кроме функции main) могут быть использованы для построения рекурсии.

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





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

Если попытаться отследить по тексту программы процесс выполнения рекурсивной функции, то мы придем к такой ситуации: войдя в рекурсивную функцию, мы “движемся” по ее тексту до тех пор, пока не встретим ее вызова, после чего мы опять начнем выполнять ту же самую функцию сначала. При этом следует отметить самое важное свойство рекурсивной функции – ее первый вызов еще не закончился. Чисто внешне создается впечатление, что текст функции воспроизводится (копируется) всякий раз, когда функция сама себя вызывает. На самом деле этот эффект воспроизводится в компьютере. Однако копируется при этом не весь текст функции (не вся функция), а только ее части, связанные с данными (формальные, фактические параметры, локальные переменные и точка возврата). Алгоритм (операторы, выражения) рекурсивной функции не меняется, поэтому он присутствует в памяти компьютера в единственном экземпляре.

Пример1. Вычислить n! Определение факториала рекурсивно:

0!=1; n!=(n-1)!*n при n=1,2,3, … В соответствии с этим определение фкнкции, вычисляющей факториал, можно записать следующим образом;

long fact (int n){ if ( n<1 ) return 1;

else return n*fact(n-1);

} Если, например, в main написать long result=fact(3), то последовательность вызовов можно показать так:

main( ) result=fact(3) (1) fact(n =3) return3*fact(n-1) (2) fact(n=2) return2*fact(n-1) (3) fact(1) return Пример 2. По заданному целому числу распечатать символьную строку цифр, изображающую это число:

void cnum(int n){int a=10;

if(n = = 0) return;

else {cnum(n/a); cout <

Косвенная рекурсия является одним из тех случаев, когда нельзя определить функцию до использования её имени в программе.

Пусть функция f1() вызывает f2(), которая, в свою очередь, обращается к f1(). Пусть первая из них определена ранее второй. Для того чтобы иметь возможность обратиться к функции f2() из f1(), мы должны поместить объявление имени f2 раньше определения обеих этих функций:

void f2();

void f1(){ … if (…);

f2();

…} void f2(){ … f1();

…} 16.8. Аргументы по умолчанию Удобным свойством С++ является наличие предопределённых инициализаторов аргументов. Значения аргументов по умолчанию можно задать в объявлении функции, при этом они подставляются автоматически в вызов функции, содержащий меньшее число аргументов, чем объявлено. Например, следующая функция объявлена с тремя аргументами, два из которых инициализированы:

error (char* msg, int level = 0, int kill = 0);

Эта функция может быть вызвана с одним, двумя или тремя аргументами:

error (“Ошибка!”); // Вызывается error (“ошибка”, 0, 0);

error (“Ошибка!”, 1); // вызывается error (“ошибка”, 1, 0);

error (“Ошибка!”, 3, 1); // значения аргументов по умолчанию // не используются.

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

Если аргумент по умолчанию уже определён в одном объявлении, он не может быть переопределён в другом. Аргументы по умолчанию должны быть объявлены при первом объявлении имени функции и не обязаны быть константами:

int i=8;

void func (int = i);

Заметим, что если инициализация аргументов произведена в прототипе функции, в определении функции задавать инициализацию аргументов не надо.

16.9. Переопределение функций В С++ можно переопределять имена функций и использовать одно и то же имя для нескольких функций с различным типом или числом аргументов.

Пусть объявлены следующие функции:

int func(int, int);

int func(char, double);

int func(long, double);

int func(float, …); // Функция с неопределенным числом аргументов.

int func(char*, int);

Рассмотрим, что будет происходить при вызове функции с именем func с некоторым списком аргументов.

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

char string[ ]=”Строка – это массив символов”;

int i=func (string, 13); // func (char*, int);

int j=func(1995L, 36.6); // func(long, double);

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

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

Пусть обращение к функции выглядит так:

float a=36.6;

j=func(‘a’, a);

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 17 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.