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

res = insert( res, x );

return res;

}

}

main( )

{

clrscr();

s1 = insert( s1, 1 );

s1 = insert( s1, 2 );

s1 = insert( s1, 3 );

display( s1 );

s2 = insert( s2, 8 );

s2 = insert( s2, 9 );

puts(“\n”);

display( s2 );

puts(“\n”);

display( s3 = concat( s1, s2 ));

getch();

puts(“\n”);

display( reverse( s3 ));

}

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

1      2      3

8      9

1      2      3      8      9

9      8      3      2      1

Пример 4

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

Решение

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

Вместе с подпрограммой добавления элемента к списку и подпрограммой вывода элементов списка, написанных рекурсивно, наша подпрограмма сложения будет иметь следующий текст:

// сложение длинных целых чисел,

// заданных в виде списков цифр

#include <stdio.h>

#include <string.h>

#include <alloc.h>

#include <conio.h>

typedef struct nd

{

int info;

struct nd *next;

} NODE;

NODE *s1 = 0, *s2 = 0, *s3 =0;

NODE   *insert( NODE *root, int x )

{

if (root==0)

{

root = (NODE *) malloc (sizeof(NODE));

root->info = x;

root->next = 0;

} else

root->next = insert ( root-> next, x );

return root;

}

void display( NODE *p )

{

if ( p != 0 )

{

display ( p->next );

printf("%-7d", p->info);

}

}

NODE *add( NODE *s, NODE *t )

{

int x, c=0 ; NODE* res=0 ;

while ((s!=0) || (t!=0))

{

if (s == 0) x = t->info + c;

else if (t==0) x = s->info +c ;

else x = s->info+t->info+c ;

if (x > 9){ x-=10; c=1;}

else c=0;

res = insert( res,x );

if(s!=0) s = s->next;

if(t!=0) t = t->next;

}

if (c == 1) res = insert( res, 1 );

return res;

}

main()

{

clrscr() ;

s1 = insert ( s1, 1);

s1 = insert ( s1, 2);

s1 = insert ( s1, 3);

display (s1);

s2 = insert ( s2, 9);

s2 = insert ( s2, 9);

puts("\n");

display (s2);

puts("\n");

display( add(s1,s2));

getch();

}

В главной программе складываются числа 321 и 99. Будет выведено:

3      2      1

9      9

4      2      0

Вопросы и задачи на зачет

Вопросы

1.  Этапы построения алгоритма.

2.  Структурное программирование.

3.  Предусловие, постусловие и инварианты.

4.  Правила верификации программ.

5.  Рекурсивные подпрограммы.

6.  Представление итераций рекурсией.

7.  Косвенная рекурсия, пример использования.

8.  Синтаксический анализ и вычисление методом рекурсивного спуска.

9.  Рекурсивный обход вершин графа.

10.  Метод динамического программирования.

11.  Алгоритм Дейкстры поиска кратчайшего пути.

12.  Временная сложность алгоритма.

13.  Жадные алгоритмы.

14.  Теория матроидов.

15.  Алгоритм Прима.

16.  Алгоритм Крускала.

17.  Структуры данных, списки.

18.  Стек и преобразование рекурсивных подпрограмм.

19.  Организация динамического стека.

20.  Применение стека для вычисления арифметических выражений.

21.  Организация очереди и дека.

22.  Обход вершин графа в глубину и в ширину.

23.  Односвязный и двухсвязный циклические списки.

24.  Деревья, представление неупорядоченных деревьев.

25.  Обходы упорядоченного дерева.

26.  Дерево поиска.

27.  Представление упорядоченного дерева с помощью дерева поиска.

Задачи

1.  Написать программу, выводящую на экран разложения заданного числа N в виде суммы положительных натуральных чисел m₁ > m₂ > … > m_k.

2.  Написать программу, находящую решение задачи о Ханойских башнях. Оценить её временную сложность.

3.  Задача о минимальном числе монет, разменивающих заданную сумму.

4.  Написать рекурсивную подпрограмму для вычисления суммы чисел, содержащихся в файле.