Рекурсивный алгоритм. Определение рекурсивной функцию int Lat, возвращающую количество латинских букв в текстовом файле, страница 3

else printf("Unsolvable\n"); getch();

if (knapsack(8+8+12,0))printf("\n");

else printf("Unsolvable\n"); getch();

getch();

}

Программа выведет

unsolvable

12 8 8

Пример 2

Задана непрерывная на отрезке [a, b] функция f(x), значения которой в точках a и b имеют противоположные знаки, т.е. f(a) * f(b) < 0. Найти решение уравнения f(x) = 0, с точностью до ε > 0, если функция f определена как подпрограмма.

Решение

Корень уравнения f(x) = 0 будем искать с помощью деления отрезка пополам. Если f(a) и f((a + b) / 2) имеют противоположные знаки, то корень находится в интервале [a, (a + b) / 2], в противном случае – в интервале [(a + b) / 2, b]. Если длина интервала меньше ε, то решение x = (a + b) / 2 будет отличаться от корня не больше, чем на ε. Построим алгоритм:

1)  Разделить отрезок пополам, x = (a + b) / 2.

2)  Если f(x) = 0, то x – корень уравнения.

3)  Иначе, если f(a) и f(x) имеют разные знаки, применить данную процедуру с шага 1 к отрезку [a, x], а в противном случае – к отрезку [x, b].

Аргументами рекурсивной подпрограммы будут указатель на функцию f и числа a, b, ε. Присоединяя к подпрограмме тестовый пример, получим следующий окончательный текст.

#include <stdio.h>

#include <conio.h>

#include <math.h>

double root(double (*f)(double),double a,double b,double eps);

double f(double x);

void main()

{

clrscr();

printf("%20.19f", root(f,1,4,0.000000000000001));

}

double root(double (*f)(double),double a,double b,double eps)

{

double x =(b+a)/2;

if(f(a)==0) return a;

if(f(b)==0) return b;

if( (b-a)<eps ) return x;

if(f(x)==0) return x;

else if(f(x)*f(a) < 0) return root(f,a,x,eps);

else return root(f,x,b,eps);

}

double f(double x)

{

return sin(x);

}

Программа выведет:

3.1415926535897935600

Пример 3

Дан массив целых чисел. Найти минимум его элементов с помощью рекурсивной функции min1(k), возвращающей минимум последних элементов, начиная с k-го.

Решение

Пусть x[0], x[1], …, x[n-1] – заданный массив целых чисел. Тогда функция min1(k), возвращающая минимум элементов x[k], x[k+1], …, x[n-1], будет удовлетворять соотношению

min1(k) = min( x[k], min1(k+1)).

Добавляя равенство min1(n-1) = x[n-1], напишем текст функции и тестирующей программы:

#include <stdio.h>

#include <conio.h>

int x[] = {1, 2, 1, 3, 12, 2};

int min1(int k)

{

int s;

if( k == sizeof(x)/2 – 1)         // если k = n - 1

return x[sizeof(x)/2 – 1];

else

{

s = min1(k+1);

if( x[k] < s ) return x[k];    // возврат минимума чисел

else return s;           // min1(k+1) и x[k]

} }

void main()

{   printf(“\n min = %d”, min1(0)); } // вывод минимума элементов массива

Программа выведет:

min = 1

Пример 4

Дана текстовая строка char *s. Проверить, симметрична ли часть строки s от s[i] до s[j],  i ≤ j.

Решение

Пусть sym(i, j) – функция, принимающая значение 1, если часть строки от s[i] до s[j] симметрична, и 0 – если нет. Тогда при i < j имеет место соотношение    sym(i, j) = sym(i+1, j-1). Отсюда

sym(i, j) = sym(i+1, j-1) = sym(i+2, j-2) = …

Ясно, что sym(i, j) = 1, ибо строка из одного символа симметрична, и               sym(i, i-1) = 1, поскольку строка от s[i] до s[i-1] пуста. Отсюда sym(i, j) = 1, при i ≥ j.

Напишем рекурсивную подпрограмму, использующую эти соотношения. Учитывая, что длина строки вычисляется с помощью функции strlen(), получим следующий текст:

#include <stdio.h>

#include <string.h>

int sym(char *s, int i, int j)

{

if (i>=j) return 1;   // если подстрока пуста

// или содержит 1 символ

if (s[i]==s[j]) return sym(s,i+1,j-1);

else return 0;  // если s[i] != s[j], то несимметрична

}

// тестовая программа

main()

{

char *str="ababa";    // входная последовательность символов

if(sym(str,0,strlen(str)-1)) printf("\nСтрока симметрична\n");

else printf("\nСтрока несимметрична\n");

}

Программа выведет:

Строка симметрична

Пример 5

Вычислить количество цифр в текстовом файле.