24. Оптимизация программного кода. Шаблоны функций. Один из способов сделать код программы проще использовать шаблоны функций. С помощью шаблона функции можно определить алгоритм, который будет применяться к данным различных типов, а конкретный тип данных передается функции в виде параметра на этапе компиляции. Компилятор автоматически генерирует правильный код, соответствующий переданному типу. Таким образом, создается функция, которая автоматически перегружает сама себя и при этом не содержит накладных расходов, связанных с параметризацией. Формирование шаблона Template <class Type> заголовок { /*тело функции*/ } Пример: /*обменная (пузырьковая) сортировка*/ Template <class Type> Void Sort (Type *a,int n){ for (int i=0;i<n-1;i++) for (int j=0;j<n-i-1;j++) if (a[j]>a[j+1]){ Type x=a[j]; a[j]=a[j+1];

a[j+1]=x;}} void main(){ int a[10]={4,5,2,3,8,9,1,5,67,0}; float b[5]={4.3, 6.12, 0.001, 32.98, 1.78}; Sort <int>(a,10); Sort<float>(b,5);}

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

Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

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

Примеры

Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.

Факториал целого неотрицательного числа n (обозначается ) определяется как

при и при

Числа Фибоначчи определяются с помощью рекуррентного соотношения:

Первое и второе числа Фибоначчи равны 1

Для , число Фибоначчи равно сумме -го и -го чисел Фибоначчи

Практически все геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского).

Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

Факториал:

#include <iostream>

using namespace std;

 

long double fact(int N)

{

if(N < 0) // если пользователь ввел отрицательное число

return 0; // возвращаем ноль

if (N == 0) // если пользователь ввел ноль,

return 1; // возвращаем факториал от нуля - не удивляетесь, но это 1 =)

else // Во всех остальных случаях

return N * fact(N - 1); // делаем рекурсию.

}

 

int main()

{

int N;

setlocale(0,""); // Включаем кириллицу

cout << "Введите число для вычисления факториала: ";

cin >> N;

cout << "Факториал для числа " << N << " = " << fact(N) << endl << endl; // fact(N) - функция для вычисления факториала.

return 0;

}

Ханойская башня:

#include <iostream>

 using namespace std;

 

void hanoi_towers(int quantity, int from, int to, int buf_peg)   //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)

{                                               //buf_peg - промежуточный колышек(1-3)

        if (quantity != 0)

        {

                hanoi_towers(quantity-1, from, buf_peg, to);

 

 cout << from << " -> " << to << endl;

 

 hanoi_towers(quantity-1, buf_peg, to, from);

        }

}

 

int main()

{

        setlocale(LC_ALL,"rus");

        int start_peg, destination_peg, buffer_peg, plate_quantity;

        cout << "Номер первого столбика:" << endl;

        cin  >> start_peg;

        cout << "Номер конечного столбика:" << endl;

        cin  >> destination_peg;

        cout << "Номер промежуточного столбика:" << endl;

        cin  >> buffer_peg;

        cout << "Количество дисков:" << endl;

        cin  >> plate_quantity;

 

        hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);

return 0;

}

Вычислить сумму ряда:

#include <iostream>

#include <cmath>

 

inline double func(int p){

    double c = cos(static_cast<double>(p));

    return c*c/static_cast<double>(3*p-3);

}

 

double sum(int n){

    return ( n < 3 ) ? 0.0 : ( n == 3 ) ? func(n) : func(n) + sum(n - 1);

}

 

int main(){

    int n;

    std::cout << "n = ";

    std::cin >> n;

    std::cout << "r = " << sum(n) << std::endl;

    return 0;

}

Вычисленние n-члена числа Фиббоначчи:

#include <iostream>

typedef _int64 int;

int mem[20]={0};

int fib (int n)

{

    if (n==1 || n==2) return 1;

    if (mem[n]!=0) return mem[n];

    else

    {

        mem[n]=fib(n-2)+fib(n-1);

        return mem[n];

    }}int main()

{

    int n;

    std:: cin >> n;

    std:: cout << fib(n) << "\n";

    system ("pause");

    return 0;

}

Перегрузка функций: правила и примеры:

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

#include <iostream.h>

int add_values(int a,int b)

{    return(a + b); )

int add_values (int a, int b, int c)

(    return(a + b + c); )

void main(void)

{    cout << "200 + 801 = " << add_values(200, 801) << endl;    cout << "100 + 201 + 700 = " << add_values(100, 201, 700) << endl; }

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

Подобным образом следующая программа MSG_OVR.CPP перегружает функциюshow_message. Первая функция с именем show_message выводит стандартное сообщение, параметры ей не передаются. Вторая выводит передаваемое ей сообщение, а третья выводит два сообщения:

#include <iostream.h>

void show_message(void)

{    cout << "Стандартное сообщение: " << "Учимся программировать на C++" << endl; }

void show_message(char *message)

{    cout << message << endl; }

void show_message(char *first, char *second)

{    cout << first << endl;    cout << second << endl; }

void main(void)

{    show_message();    show_message("Учимся программировать на языке C++!");    show_message("B C++ нет предрассудков!","Перегрузка - это круто!") ; }