66

AnsiToOem("\n введи a,b,c,d,f,g,h ",str); cout<<str; cin>>a>>b>>c>>d>>f>>g>>h;

s1=streug(a,b,h); s2=streug(h,c,g); s3=streug(g,d,f); s5=s1+s2+s3; cout<<"\n"; cout<<s5<<"\n";

return 0;}

float streug(float x,float y,float z)

//ф-я для вычисления площади 3-ника по его сторонам

{float p,s;

p=(x+y+z)/2; s=sqrt(p*(p-x)*(p-y)*(p-z)); return (s); }

Если провести расчеты по этой программе с такими данными: a = 1,5; b = 1; c = 2; d = 2,5; f = 1; g = 2,5; h = 2, то получим площадь

5-угольника = 3,90 (примерно).

9.2.Рекурсия

ВC++ допустима рекурсия – обращение функции к самой себе. Проиллюстрируем использование рекурсии на примере.

Пример 9.2. Рассчитать число сочетаний из N элементов по M:

По такой формуле можно рассчитать, например, каким числом способов можно рассадить учеников класса(скажем, N = 30) по двое (M = 2).

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

// число сочетаний из N по M #include <iostream> #include <cmath>

#include <windows.h> using namespace std; int n,m; double c; float fact(int n); int main()

{char str[256], str1[256]; AnsiToOem("\n введи N и M ", str); cout<<str; cin>>n>>m; c=floor(fact(n)/(fact(m)*fact(n-m)) );

AnsiToOem("\n число сочетаний из ", str); AnsiToOem(" по ", str1);

67

cout<<str<<n<<str1<<m<<" = "<<c<<"\n"; return (0); }

float fact(int n)

{if (n==0) return(1);else return (n*fact(n-1));}

Как видно, внутри функции fact имеется обращение к ней же, но со значением параметра, меньшим на 1. Поэтому, если, например, задать n = 5, то внутри функции произойдет обращение к ней же, но с n = 4, затем с n = 3, n = 2, n = 1, n = 0. Для n = 0 функция примет значение 1 и процесс пойдет в обратную сторону, последовательно выполняя умножение на 1, на 2, на 3, 4, 5. В результате и получим значение 5! .

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

целое число, то для его окончательного вычисления применили функцию округления вещественного до целогоfloor (она выдает наибольшее целое, не превосходящее данное число). Заметим, кстати, что для правильного округления вещественного числаx нужно указывать floor(x+0.5)

Если запустить программу и задатьn = 9, m = 5, то получим в ответе 126.

Пример 9.3. Провести сортировку одномерного массива последовательным поиском максимума и перестановкой его в конец, причем применить рекурсивную процедуру сортировки.

#include <iostream> #include <windows.h> using namespace std;

const int n=5; float a[n+1];

int fmax(float a[], int nach, int kon); void sort (float a[], int nach, int kon); int main()

{int i; char str[256]; AnsiToOem("\n введи a[", str); for (i=1; i<=n; i++)

{cout<<str<<i<<"] "; cin>>a[i];} sort (a,1,n);

for (i=1; i<=n; i++)

{cout<<" a["<<i<<"]="<<a[i];} cout<<"\n"; return(0);}

int fmax(float a[], int nach, int kon)

69

C00

C10 C11

C20 C21 C22 C30 C31 C32 C33

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

#include <cmath> #include <iomanip> #include <windows.h> using namespace std; int n,m,r,i,j; double c;

float fact(int n); int soch(int n,int m); int main()

{char str[256];

AnsiToOem("\n введи размер треугольника Паскаля", str); cout<<str; cin>>r;

for (i=0;i<=r;i++) {cout<<"\n";

for (j=0;j<=i;j++) {c=soch(i,j);cout<<setw(r*(r-i+j+1))<<c;}; cout<<"\n"; }

return (0);} float fact(int n)

{if (n==0) return(1); else return (n*fact(n-1)); } int soch(int n,int m)

{int c= floor(fact(n)/(fact(m)*fact(n-m)) ); return(c);}

Вданном примере нам потребовался форматированный вывод. Для его организации вC++ применяются так называемые манипуляторы (для их использования нужно подключить заголовочный

файл iomanip). Конкретно мы использовали манипулятор setw(int) – который задает ширину поля(количество позиций, отведенных для вывода переменной) с выравниванием по правому краю.

Если запустить данную программу и задать размер треугольника равным 3, то получим (рис. 8.22):