шпоры4 (1079655), страница 2

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

Текст из файла (страница 2)

Общий формат функции operator таков.

тип имя_класса::operator значение_оператора(список_аргументов)

{операция_над_классом}

class Drobi

{public:

double drob;

Drobi operator*(Drobi d1);};

Drobi Drobi::operator*(Drobi d1)

{ Drobi d2;

d2.drob=drob*d1.drob;

return d2;}

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

41-42. Структуры рекурсивных алгоритмов

Применение рекурсивных алгоритмов

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

int factorial (int N)

{if (N= =0) return 1; return N*factorial(N-1); }

Функция вычисляет функцию N!? используя стандартное рекурсивное определение. Она возвращает правильное значение, когда вызывается с неотрицательным и достаточно малым аргументом N, чтобы N! Можно было представить типом int. Программа эквивалентна простому циклу:

for (t=1, i=1; i<=N; i++) t*=i;

Программа иллюстрирует базовые особенности рекурсивной программы: она вызывает саму себя и содержит условие завершения, при выполнении которого непосредственно вычисляет свое результирующее значение. Чтобы убедиться в правильности работы программы, можно применить метод математической индукции: 1) программа вычисляет 0! (исходное значение), 2) если допустить, что программа вычисляет k! для k<N (индуктивное предположение), то она вычисляет и N!.

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

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

1. Функции – друзья класса

В C++ существует возможность разрешить доступ к закрытым членам класса функциям, которые не являются членами этого класса. Для этого достаточно объявить эти функции дружественными(или друзьями) по отношению к рассматриваемому классу. Чтобы сделать функцию другом класса, необходимо включить ее прототип в public раздел объявления класса и предварить прототип ключевым словом friend.

Функция может быть другом нескольких классов.

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

#include <iostream>

using namespace std;

class myclass

{int a,b;

public:

myclass(int i, int j) {a=i;b=j;}

friend int sum(myclass x);};

int sum(myclass x)

{return x.a+x.b;}

int main()

{myclass n(3,4);

cout<<sum(n);

return 0;}

Объявление, определение и использование функций-друзей

Есть два вида определяющих операций класса, задающих его интерфейс:

• функции-члены класса (методы)

• функции-друзья класса

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

Объявление друзей (файл mystring.h)

const int max_string_length = 128;

class String

{public:

void set_to(char*);

int length();

int read(); // чтение из stdin

void print(); // вывод в stdout

String substring(int start, int len);

// возвращает подстроку не изменяя оригинала

friend String concat(String*, String*);

friend String concat(String*, char*);

friend String concat(char*, String*);

private:

char text[max_string_length + 1];};

// объект типа String – это последовательность из не более чем max_string_length символов, оканчивающаяся символом NULL

Программирование друзей (файл mystring.cpp)

String concat(String* s1, String* s2) {

if (s1->length()+s2->length()>max_string_length){

fprintf(stderr,

"string too large: \"%s %s\".\n",

s1->text, s2->text);

exit(1);}

String both;

strcpy(both.text, s1->text);

strcat(both.text, s2->text);

return both;}

String concat(String* s1, char* s2) {

if (s1->length()+strlen(s2)>max_string_length) {

fprintf(stderr,

"string too large: \"%s %s\".\n",

s1->text, s2);

exit(1);}

String both;

strcpy(both.text, s1->text);

strcat(both.text, s2);

return both;}

String concat(char* s1, String* s2) {

if (strlen(s1)+s2->length()>max_string_length) {

fprintf(stderr,

"string too large: \"%s %s\".\n",

s1, s2->text);

exit(1);}

String both;

strcpy(both.text, s1);

strcat(both.text, s2->text);

return both;}

Вызов друзей (файл main.cpp)

#include "mystring.h"

#include <conio.h>

#include <stdio.h>

int main(int argc, char* argv[])

{ String firstname, lastname, name, output;

firstname.set_to("Bilbo");

lastname.set_to("Baggins");

name = concat(&firstname, " ");

name = concat(&name, &lastname);

output = concat("Name is: ", &name);

output.print();

getch();

return 0;}

42. смотри 15 вопрос

1. Функции потокового ввода и вывода объектов

Принципиальным для понимания C++ системы ввода-вывода является то, что она опирается на понятие потока. Поток-это последовательный логический интерфейс, который связан с физическим файлом.В C++ содержится ряд встроенных потоков(cin-стандартный входной, cout-стандартный выходной,cerr и clog-вывод информации об ошибках),которые автоматически открываются, как только программа начинает выполняться.В C++ также предусмотрены двухбайтовые (16-битовые) символьные версии стандартных потоков, именуемые wcin, xcout, wcerr, wclog. Они предназначены для поддержки языков, для предоставления которых требуются большие символьные наборы.В C++ система ввода-вывода использует заголовок <iostream>. Система ввода-вывода построена на двух связанных, но различных иерархиях шаблонных классов. Первая выведена из класса низкоуровневого ввода-вывода basic_streambuf, вторая из класса высокоуровневого ввода-вывода basic_ios.В C++ для выполнения операций ввода-вывода классовых данных предусмотрен способ перегрузки операторов ввода-вывода. Оператор << выводит информацию в поток, а оператор >> вводит информацию из потока. Оператор << называется оператором вывода или вставки, поскольку он вставляет символы в поток, а оператор >> называется оператормо ввода или извлечения, поскольку он извлекает символы из потока.Рассмотрим на примере создание оператора вывода для класса three_d.

Class three_d

{public:

int x,y;

three_d(int a,int b) {x=a; y=b;} };

Чтобы создать операторную функцию вывода для объектов типа three_d, необходимо перегрузить оператор <<.

Отображение коодинат x,y;

ostream &operator<<(ostream &stream, three_d obj)

{stream<<obj.x<<”,”;

stream<<obj.y<<”\n”;

return stream;}

Данная функция возвращает ссылку на объект типа ostream. Это позволяет несколько операторов вывода объединить в одном выражении. Также эта функция имеет два параметра. Первый представляет собой ссылку на поток, вторым является объект, который стоит в правой части оператора <<.

Вывод организуется строкой. three_d a(1,2),b(3,4); cout<<a<<b;

Рассмотрим на примере создание оператора ввода для класса three_d. Чтобы создать операторную функцию ввода для объектов типа three_d, необходимо перегрузить оператор >>.

istream &operator<<(istream &stream, three_d &obj)

{stream>>obj.x;

stream>>obj.y;

return stream;}

43. Оценка сложности рекурсивных алгоритмов

Сложность рекурсивных вычислений. При относительной простоте написания, у рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро.

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

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

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

Например, пусть мы пытаемся вычислить числа Фибоначчи по рекурсивной схеме

F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 1; F(1) = 1;

с помощью указанной выше рекурсивной подпрограммы-функции F(n). Требующееся при вычислении значения F(N) по такой схеме количество рекурсивных вызовов может быть получено из решения рекуррентного выражения

T_N = T_N-1 + T_N-2, при N >= 1; T₀ = 1; T₁ = 1

T_N приблизительно равно Ф^N , где Ф »1.618 - золотая пропорция («золотое сечение»), т.е. приведенная выше программа потребует экспоненциальных временных затрат на вычисления.

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

общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид: fA(n)= a * fA( n/b )+d(n)+U(n) (9.1), где:

d(n) – трудоемкость алгоритма деления задачи на подзадачи,
U(n) – трудоемкость алгоритма объединения полученных решений. Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману:

Характеристики

Список файлов лабораторной работы