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

Задание 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. Полный и ограниченный перебор. Использование рекурсии при программировании ограниченного перебора

 

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

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

К задачам, при решении которых используется перебор, относятся также задачи из области искусственного интеллекта, решения которых ищутся методом "проб и ошибок". Например, задача о расстановке n ферзей на доске n*n таким образом, чтобы они не били друг друга. К этой же группе относятся задачи, в которых требуется получить все возможные перестановки каких-то элементов, например, все перестановки букв от A до F.

Существует две стратегии решения задач данного типа. При первой - мы генерируем вариант, а затем определяем его пригодность. При второй - вариант генерируется по одному элементу, и проверка пригодности осуществляется после добавления каждого элемента. Поскольку вычислительная сложность задач данного типа - nⁿ, то есть при увеличении размерности задачи время вычислений возрастает как nⁿ, вторая стратегия предпочтительней.

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

цикл-пока еще есть варианты

генерировать вариант

 если вариант удовлетворяет условию,

        то обработать набор

все-если

Все-цикл

Для генерации вариантов используют либо вложенные циклы, применение которых существенно уменьшают универсальность программы, либо программно-реализуемый счетчик, который в каждом разряде считает от минимального до максимального значений элементов в данной позиции. Каждое состояние такого счетчика соответствует одному варианту. Для генерации следующего варианта в младший разряд счетчика добавляют 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++) // печать подходящего варианта

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

                printf("\n");

          }

}

     return 0;

}

Недостаток примененного метода, как уже говорилось, заключается в m^m-ой зависимости времени выполнения от значения m.