Разработка программ рекурсивной структуры

Имени Н.Э. Баумана

(национальный исследовательский университет)»

(МГТУ им. Н.Э. Баумана)

 

 

Т.Н. Ничушкина

 

 

Разработка программ рекурсивной структуры

 

 

Учебное пособие по курсу «Информатика»

 

 

Москва

(С) 2018 МГТУ им. Н.Э. БАУМАНА

 

                               

 

УДК 004.432

 

Рецензент: доцент кафедры ИУ1  к.т.н. Задорожная Н.М.

                                                   

Т.Н. Ничушкина

Разработка программ рекурсивной структуры. Учебное пособие  по дисциплине «Информатика» - М.: МГТУ имени Н.Э. Баумана, 2017. 33 с.

 

Учебное пособие содержат теоретические сведения по  разработке рекурсивных программ в языке С++. Приведены примеры рекурсивных алгоритмов и программ.

 Для студентов МГТУ имени Н.Э. Баумана, обучающихся по программе бакалавриата по направлению «Математика и компьютерные науки»

Рекомендовано Учебно-методической комиссией НУК «Информатика и системы управления» МГТУ им. Н.Э. Баумана

                                 Ничушкина Татьяна Николаевна

 

 

Разработка программ рекурсивной структуры.

Учебное пособие  по дисциплине «Информатика»

© Т.Н. Ничушкина, 2018

© МГТУ имени Н.Э. Баумана, 2018

 

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ_ 4

ВВЕДЕНИЕ_ 7

Глава 1. Рекурсия. Основные положения_ 8

1.1. Рекурсивные алгоритмы.. 8

1.2. Рекурсивные процедуры и функции. Взаиморекурсия. 10

1.3. Фрейм активации. 11

1.4 Линейная и древовидная рекурсии. 16

1.5 Примеры рекурсивных программ.. 19

1.6 Задания для самопроверки. 26

Глава 2. Полный и ограниченный перебор. Использование рекурсии при программировании ограниченного перебора_ 27

2.1. Понятие полного перебора. Основные приемы его осуществления 27

2.2. Использование рекурсии при реализации ограниченного перебора 35

2.3 Задания для самопроверки. 41

3 Использование рекурсии при обработке бинарных деревьев_ 41

3.1 Понятие бинарного дерева. 41

3.2 Использование рекурсивных алгоритмов обработки бинарных деревьев. 43

3.3 Задания для самопроверки. 53

4 Контрольные вопросы_ 54

ЗАКЛЮЧЕНИЕ_ 55

СПИСОК ЛИТЕРАТУРЫ_ 56

 

ПРЕДИСЛОВИЕ

Учебное пособие предназначено для углубления знаний, полученных при освоении лекционного материала и семинарских занятий, а также самостоятельного изучения студентами темы «Рекурсия» по дисциплине «Информатика», входящей в основную образовательную программу подготовки бакалавров для студентов, обучающихся по направлению «Математика и компьютерные науки» 02.03.01.

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

После изучения этой темы дисциплины студенты овладеют:

· базовыми знаниями теории рекурсивных алгоритмов, необходимыми для разработки математических моделей объектов и формализации задач разработки сложных программ;

· практическими навыками разработки рекурсивных алгоритмов;

· приемами тестирования и отладки программ рекурсивной структуры.

Планируемые результаты обучения

  Студент должен знать:

- виды задач с рекурсивной структурой;

- способы разработки задач с применением рекурсивных алгоритмов;

- область применения рекурсивных алгоритмов;

      – способы оценки необходимости применения рекурсивного алгоритма.

       Студент должен уметь:

- выполнять анализ задачи и обосновывать необходимость применения рекурсивных алгоритмов для ее решения;

- разрабатывать алгоритм решения задачи;

- выбирать способ реализации рекурсивного алгоритма на языке С++;

- программировать и отлаживать рекурсивные программы.

Студент должен иметь навыки:

    – анализа предметных областей решаемых задач;

– анализа содержательной и получения формальной постановки задач;

– анализа и применения методов решения задач рекурсивной структуры.

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

ВВЕДЕНИЕ

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

 Рекурсия— это одна из жемчужин теории алгоритмов. Она является важнейшим приемом, который широко используется в различных разделах информатики и вычислительной техники.

Так, например, на рекурсии построен язык «Пролог», который используется в системах искусственного интеллекта. Рекурсия применяется в языках параллельного и динамического программирования. Возможности разработки рекурсивных алгоритмов заложены в современных универсальных языках программирования, таких, как Паскаль и С++.

Кроме того, в теории структур данных широкий класс структур относят к рекурсивным, как по описанию, так и по обработке. Например, списки и деревья.

Все это делает изучение рекурсивных алгоритмов и структур очень важным для понимания многих дисциплин профессионального цикла студентами, обучающимися по направлениям «Математика и компьютерные науки» и «Информатика и вычислительная техника».

Предлагаемое учебное пособие предназначено для студентов первого курса кафедры ФН-11, изучающих дисциплину «Информатика». Однако, они могут быть полезны при проведении семинаров, лабораторных работ и домашних заданий по теме «Рекурсия» студентам и преподавателям смежных специальностей.

 

Рекурсивные алгоритмы

Строгое определение некоторых понятий может опираться на то же понятие. Существует доступная математическая форма определений, согласно которой определяемое понятие используется как заголовок определения и как его элемент. Эта форма называется рекурсивной или индуктивной.  

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

Пример 1. Определение отношения "Кубик А находится в башне над кубиком В."

   Рисунок 1 – Схема размещения кубиков в башне

1. Если кубик А лежит непосредственно на кубике В, то кубик А находится в

башне над кубиком В.   

2. Если кубик А лежит непосредственно на кубике С и этот кубик находится в

 башне над кубиком В, то кубик А находится в башне над кубиком В.

Первое утверждение носит название базисного. Базисное утверждение нерекурсивно.

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

При этом базисное утверждение определяет один или более случаев, удовлетворяющих определению, а рекурсивное утверждение показывает, как надо применять определение, чтобы проверить, удовлетворяют ли ему другие случаи.

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

а) Проверяем первое утверждение "Синий кубик находится в башне над зеленым, если он лежит на зеленым". Оно ложно, следовательно, переходим к проверке второго.

б) Второе утверждение "Синий кубик находится в башне над зеленым, если синий кубик лежит на красном, а красный находится в башне над зеленым" требует доказательства того, что красный кубик находится в башне над зеленым. А это значит, что надо вновь применить правило 1 и проверить, находится ли красный кубик непосредственно на зеленом. Поскольку это положение истинно, значит истинно и то, что синий кубик находится в башне над зеленым.  

Пример 2. Рекурсивное определение понятия "нечетное число".

Базисное утверждение: Число 1 является нечетным.

Рекурсивное утверждение: Если i является нечетным числом, то нечетными являются и числа i-2 и i+2.

Определить, являются ли числа 7 и -7 нечетными.

а) 7-2 -> 5     5-2 -> 3       3-2 -> 1 1 - нечетное число, следовательно, число 7 - нечетное.

б) -7+2 -> -5 -5+2 -> -3     -3+2 -> -1 -1+2 -> 1 - нечетное число, следовательно, число -7 - нечетное.

Очень важной областью применения рекурсии является синтаксис языков программирования.

Пример 3. Определение целой константы.

Базисное утверждение: Числа от 0 до 9 являются целыми константами. 

Рекурсивное утверждение: Добавление десятичной цифры к записи целой константы образует новую целую константу.

Соответствующая форма Бэкуса-Наура записывается следующим образом:

<цифра>:: = 0|1|2|3|4|5|6|7|8|9 - базис

<целая константа>:: =<цифра>|<целая константа> - рекурсивная часть

Таким образом, мощность рекурсии заключается в том, что она позволяет определить бесконечное множество объектов с помощью конечного количества высказываний.

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

 

          1.2. Рекурсивные процедуры и функции. Взаиморекурсия

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

Различают следующие виды рекурсии:

Прямая или явная рекурсия характеризуется существованием в теле процедуры оператора обращения к самой себе.

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

Для описания на языках программирования С и С++ прямой рекурсии никаких дополнительных операторов не требуется. При описании неявной рекурсии возникает проблема: при определении первой из нескольких взаиморекурсивных процедур или функций возникает необходимость обращения к подпрограмме, которая еще не определена, что в языке С++ недопустимо. В этом случае используется  прототип функции, которая позволяет выполнять предописание:

1) сначала задаются прототипы подпрограмм с параметрами;

2) затем описываются тела этих подпрограмм (причем параметры второй раз можно уже не описывать).

Например, описание взаиморекурсивных процедур A и B можно выполнить следующим образом:                                                           

Рисунок 2 – Пример взаиморекурсии

void A (int j);

Void B (int j)

  {...

A (j);

...

}

Void A(int j)

{ ….

B(j);

…..

}

В соответствие с правилами языков С и С++, прототипы взаиморекурсивных подпрограмм могут быть размещены в заголовочных файлах и храниться отдельно от текстов самих подпрограмм.

Фрейм активации

Каждое обращение к процедуре вызывает независимую активацию этой процедуры. С процедурой принято связывать некоторое множество локальных объектов (переменных, констант, типов и процедур), которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Совокупность данных, необходимых для одной активации называется фреймом активации.

Фрейм активации содержит независимые копии всех локальных переменных и формальных параметров процедуры, в которых оставляют "следы" операторы текущей активации.

Если процедура обращается к себе несколько раз, образуется несколько одновременно существующих активаций и, соответственно, несколько фреймов активации. Обычно все фреймы являются различными экземплярами одной и той же структуры и размещаются в стеке. При некотором количестве вызовов возможно переполнение стека. На размер фрейма активации влияет способ передачи параметров в процедуру: при использовании параметров-переменных фрейм содержит адреса данных (по 4 байта на каждый параметр), а при использовании параметров-значений - сами данные, которые могут занимать достаточно много места (например, массивы).

Размер фрейма активации можно примерно определить следующим образом:

V= <размер области параметров>+4(адрес возврата)+2..8(для сохранения содержимого регистров)+<размер области локальных переменных>+<размер строки результата, если это функция, возвращающая результат - строку>

Пример 4. Вычисление наибольшего общего делителя двух чисел (алгоритм Евклида).

Базисное утверждение: Если два числа равны, то их наибольший общий делитель  равен этим числам.

Рекурсивное утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел.

Таким образом, редуцирование происходит при замене большего из чисел на их разность.

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

 

 

Рисунок 3 – Схема алгоритма подпрограммы- процедуры нахождения наибольшего общего делителя двух чисел                                                                          

 

Текст программы:

 

#include "stdafx.h"

#include <stdio.h>

void nod(int a,int b,int &r)

{

if(a==b) r=a;

else

{

if (a>b)nod(a-b,b,r);

else nod(a,b-a,r);

}

}

int main(int argc, char* argv[])

{

int a,b,r;

puts("input two integer value ");

scanf("%d %d",&a,&b);

nod(a,b,r);

     printf("\n nod %7d %7d = %7d\n",a,b,r);

  return 0;

}

При выполнении программы  будет использоваться стек, в который будут записываться фреймы активации каждого вызова. Например, для а=12 и b=8 стек будет выглядеть следующим образом (запись в стек идет словами, то есть по 2 байта,, однако, на адреса отводится в стеке 4 байта – два слова, как и изображено на рисунке):

 

Рисунок 4 – Структура фрейма активации

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

#include "stdafx.h"

#include <stdio.h>

int nod(int a,int b)

{

if(a==b) return a;

else

{

 if (a>b) return nod(a-b,b);

      else  return nod(a,b-a);

}

}

int main(int argc, char* argv[])

{

  int a,b;

puts("input two integer value ");

scanf("%d %d",&a,&b);

printf("\n nod %7d %7d = %7d\n",a,b,nod(a,b));

return 0;

}

Как показывает опыт разработки и использования рекурсивных подпрограмм, объем используемой стековой памяти зависит как от размера фрейма активации, так и от количества вызовов рекурсивной подпрограммы. Поэтому, чтобы избежать переполнения стека, необходимо прикинуть возможный размер фрейма активации и хотя бы приблизительно подсчитать ожидаемое количество возможных активаций.

 

Int fib(int n)

{

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

else

{ return fib(n-1)+ fib(n-2);}

}

int main(int argc, char* argv[])

{ int n;

puts("input n value Fibonnachi");

scanf("%d",&n);

 printf("\n %7d Fibonachi =",n);

 printf("%10d\n",fib(n));

return 0;

}

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

Примеры рекурсивных программ

Как показывает опыт, практически любой итерационный цикл можно реализовать в виде рекурсивной подпрограммы. При этом, один вызов подпрограммы выполняет операторы одной итерации цикла. Именно эта особенность рекурсии позволяет довольно быстро научиться создавать рекурсивные подпрограммы. Далее рассмотрим несколько примеров применения рекурсии при разработке программ, для которых ранее, на лекциях и семинарах, использовались итерационные циклы.

 

Пример 7. Определение корней уравнения y=x²-2 на заданном отрезке методом половинного деления.

Для простоты будем считать, что отрезок задается таким образом, что корень на нем есть (иначе основная программа должна содержать проверку наличия корня).

Метод половинного деления для непрерывных функций заключается в следующем:

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

  Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

Рисунок 7 – Схема алгоритма рекурсивной программы-процедуры вычисления корня функции на отрезке

Текст программы:

# include " stdafx. h "

# include < stdio. h >

# include < math. h >

void root (float a, float b, float eps, float & r)

{

float x,f;

x=(a+b)/2;

f=x*x-1;

  if (fabs(f)>=eps)

     if ((a*a-1)*f>0)

                 root(x,b,eps,r);

     else

              root(a,x,eps,r);

else

     r = x;

}

 

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

Пример 8. Проверка чередования букв и цифр в заданной строке (первый символ - обязательно буква).

 Базисные утверждения: Строка допустима, если она пустая.

                                          Строка не допустима, если обнаружен не допустимый символ.

Рекурсивное утверждение: Если текущий символ строки допустим, то допустимость строки определяется оставшейся частью строки.

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

 Текст программы:

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

bool f_char(char st[]);

bool f_value(char st[])

{ if(strlen(st)==0)

return true;

else

{

     if((st[0]<='9')&&(st[0]>='0'))

     {

             int l=strlen(st);char s[40];

     strncpy(s,&st[1],l-1);s[l-1]='\0';

     return f_char(s);

     }

     else return false;

}

}

bool f_char(char st[])

{

if(strlen(st)==0)

  return true;

    else

   {

     if((st[0]<='Z')&&(st[0]>='A'))

     {

                int l=strlen(st);char s[40];

        strncpy(s,&st[1],l-1);s[l-1]='\0';

           return f_value(s);

     }

     else return false;

}

}

int main(int argc, char* argv[])

{  

char s[40];

puts("input string char and value");

 scanf("%s",s);

if (f_char(s))

       printf("\n TRUE\n");

else   

    printf("\n FALSE\n");

return 0;

}

Данная программа разработана не совсем удачно, так как размер фрейма активации достаточно большой. Это объясняется тем, что используется вспомогательный локальный параметр - строка, размер которой 40 байт. Так как она создается в стеке, то каждая активация использует эти дополнительные байты. И чем больше строка, тем больше памяти в стеке будет использовано. Например, если длина строки 10 символов, то количество активаций будет 11, а значит, фрейм активации будет не меньше 440 байт.   Для уменьшения размера фрейма следует подумать об изменении способа передачи параметра. Действительно, если гарантировать, что исходная строка изменяться не будет, то ее можно передавать по указателю. Переход к следующему символу можно осуществить, используя дополнительный указатель (4 байта в основной программе) и адресную арифметику. Размер фрейма активации при этом сократится и будет составлять»10байт.

Текст программы:

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

bool f_char(char * st);

bool f_value(char * st)

{

if(strlen(st)==0)

    return true;

else

{

     if((st[0]<='9')&&(st[0]>='0'))

              return f_char(++st);

     else

                   return false;

   }

}

bool f_char(char * st)

{

 if(strlen(st)==0)

return true;

else

{

     if((st[0]<='Z')&&(st[0]>='A'))

              return f_value(++st);

     else return false;

}

}

int main(int argc, char* argv[])

{ char s[80],*ptr;

puts("input string char and value");

      scanf("%s",s);

      ptr=s;

      if (f_char(ptr))

       printf("\n TRUE\n");

      else printf("\n FALSE\n");

     return 0;

}

 

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

Пример 9. Из заданного массива, завершающегося нулем, распечатать сначала положительные значения, а затем - отрицательные в любом порядке.

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

называемый "рекурсивный возврат" для вывода оставшихся элементов. Структура рекурсивной подпрограммы в общем случае имеет вид, представленный на рисунке 8.

Рисунок 8 – Схема алгоритма подпрограммы с операторами после рекурсивного вызова

Операторы, которые на схеме помечены как "операторы после вызова" будут выполняться после возврата управления из рекурсивно вызванной подпрограммы. Если попытаться изобразить последовательность действий,

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

 

                                    

Рисунок 9 – Схема последовательности обработки операторов рекурсивной подпрограммы

Таким образом, сначала выполняются операторы до вызова всех активаций. Затем, при достижении условия выхода, выполняется нерекурсивная часть. И только потом, в порядке, обратном порядку вызова, операторы, записанные после рекурсивного вызова (!!!). Используя это свойство, построим обработку следующим образом: в области до вызова запрограммируем печать положительных чисел, в области после вызова - печать отрицательных чисел, а нерекурсивная часть будет содержать вывод звездочек.

Тескт программы:

# include " stdafx. h "

# include < stdio. h >

// рекурсивная подпрограмма

void print (int x [], int i)

{

if (x [ i ]==0) puts ("***********");

else

{

if (x [ i ]>0) printf ("%4 d \ n ", x [ i ]);

   print (x, i +1);

if (x [ i ]<0) printf ("%4 d \ n ", x [ i ]);

}

}

Примечание. Обратите внимание, что значение i при каждом вызове свое, и оно не меняется все время обработки данного вызова: одно и то же, как до вызова, так и после него.

Задания для самопроверки

Задание 1. Разработайте рекурсивную подпрограмму, формирующую следующую последовательность строк:

A

BB

CCC

DDDD

EEEEE

FFFFFF и т. д.

Всего 26 строк.

Разработайте тестирующую программу.

Задание 2. Разработайте рекурсивную подпрограмму вычисления биномиальных коэффициентов:

             ì 0, если m>n³0;

с{m,n} = í 1, если (m=0 и n>0) или (m=n=0);

             î c{m-1,n-1} + C{m,n-1} в остальных случаях.

Задание 3. Разработайте рекурсивную подпрограмму быстрой сортировки элементов массива (сортировка Хоора [3, 5]). Быстрая сортировка выполняется следующим образом. Выбирают любой, например, первый элемент массива, и затем элементы переставляют так, чтобы слева располагались элементы меньше выбранного, а справа – больше. Для этого массив просматривают с двух сторон и меняют местами элементы, стоящие не в своей части массива. Тем самым выбранный элемент оказывается на своем месте. После этого описанный алгоритм применяют к левой и правой частям образовавшихся подмассивов. Процесс продолжается, пока очередной подмассив не окажется состоящим из одного элемента.

 

 Глава 2. Полный и ограниченный перебор. Использование рекурсии при программировании ограниченного перебора

 

Все-цикл

Для генерации вариантов используют либо вложенные циклы, применение которых существенно уменьшают универсальность программы, либо программно-реализуемый счетчик, который в каждом разряде считает от минимального до максимального значений элементов в данной позиции. Каждое состояние такого счетчика соответствует одному варианту. Для генерации следующего варианта в младший разряд счетчика добавляют 1 и "протряхивают" межразрядные переносы.

В качестве примера рассмотрим классическую "задачу о сдаче".

Пример 10. Разработать программу выдачи сдачи минимальным количеством монет при ограниченном количестве монет каждого достоинства в кассе.

Попытка использовать известный алгоритм, при котором сдача выдается, начиная с монет большего достоинства, и включает максимальное возможное количество монет каждого достоинства, в этом случае не дает оптимального решения. Например, если необходимо выдать сдачу 47 копеек, и в кассе имеется достаточное количество монет достоинством 1,2,3, 5,10,15,20 копеек, то алгоритм работает: 47=20*2+5*1+2*1 - 4 монеты. Но при отсутствии в кассе 5 копеечных монет вариант 47=15*3+2*1 (4 монеты) лучше варианта 47=20*2+3*2+1*1 (5 монет). При таких условиях для решения этой задачи используется метод перебора вариантов и программируемый счетчик.

Текст программы

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

#include <locale.h>

#include <conio.h>

const int n=8;

int q[]={0,0,0,0,0,0,0,0}; // программный счетчик

int p[]={50,20,15,10,5,3,2,1}; // номиналы монет

int s[8]; //количество монет каждого достоинства

int s1[8];     // количество монет каждого достоинства с учетом сдачи

int qn[8]; // найденная комбинация, позволяющая выдать сдачу

int e,en,k,kn,mink,i;

long komb;

int imin(int a,int b)

{

if(a>b) return b;

else return a;

}

Void main()

{

setlocale(0,"russian");

puts("Введите количество монет каждого достоинства в кассе");

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

{

printf("%5d коп. - ",p[i]);

scanf("%d",&s[i]);

}

puts("Введите размер сдачи");

scanf("%d",&e);

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

   s1[i]=imin(s[i],e/p[i]);

mink=e+1;

while(q[0]<=s1[0])

{

     q[n-1]+=1;

     for (k = n -1; k >0; k --) // протряхивание счетчика

     if(q[k]>s1[k])

     {

              q[k]=0;

               q[k-1]+=1;

               }

     en=0;kn=0;

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

     {

              en=en+q[i]*p[i];

       kn+=q[i];

              }

     komb++;

            if((en==e)&&(kn<mink))

              {

                        mink=kn;

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

                 qn[i]=q[i];

              }

}

if(mink!=e+1)

{  

  puts(" В сдаче:");

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

    if(qn[i]!=0)

     printf(" Монет %5d коп. - %5d штук \n",p[i],qn[i]);

}

 else puts("Сдачу выдать невозможно");

 printf("Количество рассмотренных вариантов=%5d\n",komb);

getch();

}

 

Пример 11. Написать программу, которая генерирует следующие комбинации: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211,..., 3333.

 В процессе решения этой задачи, необходимо программно реализовать 4-разрядный счетчик, который в каждом разряде будет считать от 1 до 3.

#include "stdafx.h"

#include <stdio.h>

short int a [4]={1,1,1,1}; // исходное значение счетчика

  void main()

{ int i;

while (a[0]<4) //условие "сброса" счетчика

   {

     for(i=0;i<4;i++)

     printf("%2d",a[i]);

     printf("\n"); //вывод комбинации

       a[3]=a[3]+1; // добавление 1 в последний разряд

      for(i=3;i>0;i--) // анализ и осуществление переносов

       if (a[i]>3)

     {

            a[i]=1;

     a[i-1]=a[i-1]+1;

     }

}

}

Этот прием можно использовать и для решения других задач данного класса.

Еще одна задача полного перебора – это задача о ферзях.

Пример 12. Задача о расстановке ферзей.       

Разработка программы решения начинается с выявления некоторых деталей.

1. Определим форму представления данных задачи. С первого взгляда кажется, что доска должна представляться матрицей, а местоположение ферзей - индексами в матрице. Однако при некотором размышлении можно заметить, что доска может быть представлена вектором, в котором индекс соответствует номеру столбца доски, а значение - номеру строки. Представление данных задачи в виде вектора приведено на рисунке 10.

              Матрица                     Вектор

               Рисунок 10 – Представление доски вектором

2. Определим, что для векторного представления означает "бьет". Ферзь "бьет" другую фигуру, если она расположена на той же диагонали, вертикали или горизонтали, т.е. если

                  Pole [ j ]= Pole [ i ] – одна горизонталь;

                  | Pole [ j ]- Pole [ i ] | = | j - i | – одна диагональ

Равенство по вертикали исключается тем, что в одной ячейке массива может

располагаться только одно значение.

Вариант программы полного перебора рассматриваемых вариантов полностью выглядит следующим образом:

#include "stdafx.h"

#include <stdio.h>

#include <math.h>

bool new _ r (int n, int pole []) // проверка варианта на условие   ферзь "не бьет"

{ bool r=true;

for(int i=0;i<n-1;i++)

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

     if((pole[i]==pole[j])||(abs(pole[j]-pole[i])==abs(j-i)))

      {r=false;return r;}

     return r;

}

bool variant (int m, int pole []) // генерация варианта

{

     int i;

pole[m-1]=pole[m-1]+1;

     for(i=m-1;i>0;i--)

              if(pole[i]>m)

              {

                        pole[i]=1;

                        pole[i-1]=pole[i-1]+1;

              }

              if (pole[0]<=m) return true;

              else return false;

}

int main(int argc, char* argv[])

{

  int pole[10],m,i;

  puts("Input N");

scanf("%d",&m);

for(i=0;i<m;i++)

pole[i]=1;

      while (variant (m, pole)) // пока есть варианты

{

     if (new _ r (m, pole)) // проверка варианта на условие    ферзь "не бьет"

     {

                for (i =0; i < m; i ++) // печать подходящего варианта