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

Решение

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

rec( ) = число цифр после данного символа, если символ – не цифра, и

rec( ) = 1 + число цифр после данного символа, если символ – цифра.

Текст рекурсивной функции и вызывающей ее программы:

#include <stdio.h>

#include <ctype.h>

int rec( FILE *f) // возвpащает число цифp в файле f

{

int c = fgetc(f);

if (feof(f)==0)

{

if (isdigit(c)) return rec(f) + 1; // если c - цифра

else return rec(f);

} else return 0; }

main()

{

FILE *fp = fopen("tp05.c","r");   // открывает файл,

printf ("\n %d", rec( fp )); // содержащий данный текст

fclose(fp);

}

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

5

Пример 6

Вывести на экран в обратном порядке текст, записанный в текстовом файле.

Решение

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

Текст подпрограммы и вызывающей ее программы, решающих поставленную задачу, будет следующими:

#include <stdio.h>

#include <conio.h>

FILE *fp;

void print(void)

{

char c;               // локальная переменная

if (fscanf(fp,"%c",&c) == EOF) return;

print();        // 'c' запоминается в стек

printf("%c",c);       // вывод символа из системного стека

}

main()

{

clrscr();       // очистить экран

fp = fopen("ovp2.txt","rt"); //открыть текстовый файл на чтение

print();  // вызов подпрограммы

}

Для входного файла:

123456

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

654321

Пример 7

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

Решение

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

#include <stdio.h>

#include <conio.h>

void   pn( FILE *f )

{

int n;

if( fscanf(f, “%d”, &n) == EOF ) return;

if( n > 0 ) printf(“%d”, n);

pn( f );

if( n < 0 ) printf(“%d”, n);

}

main( )

{

FILE *fp = fopen(“integer.txt”, “r”);

clrscr();

pn( fp );   getch(); }

Если файл integer.txt состоит из чисел

10        20        –2        0          –1        –12      34,

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

10     20    34    –12   –1    -2

Задание 2

Разработать алгоритм и написать программу, которая дает ответ на вопрос.

Варианты заданий

В вариантах 1 – 6 заданы n городов, между которыми определены рейсы самолетов. Матрица n ´ n состоит из чисел a_ij = 1, если существует рейс самолета из i в j, и 0 – в противном случае.

1.  Найти все города, в которые можно попасть из города p самолетом.

2.  Заданы два города – p и q. Можно ли попасть из p в q?

3.  Изолированными странами называются группы городов, такие, что между городами различных групп не существует летных сообщений. Найти число изолированных стран.

4.  Найти по крайней мере один маршрут между заданными городами p и q.

5.  Для заданной вершины p найти маршруты в другие города, хотя бы один маршрут для каждого города.

6.  Найти маршрут из p в q и вывести посещаемые города в обратном направлении.

В вариантах 7 – 14 заданы n человек и два массива натуральных чисел mother[n] и father[n], такие, что mother[i] – номер матери i-го человека, а father[i] – номер его отца, для каждого i, удовлетворяющего неравенствам              0 £ i £ n-1.

7.  Найти всех предков человека с номером p.

8.  Найти всех потомков человека с номером p.

9.  Найти всех родственников человека с номером p.