Рекурсивные алгоритмы. Разложение натурального числа на слагаемые и множители.
статья по информатике и икт (10, 11 класс)

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

Разложение натурального числа на слагаемые и множители.

Слово “рекурсия” происходит от латинского слова “recursio” – возвращение.

Рекурсия — определение, описание, изображение объекта или процесса внутри самого этого объекта или процесса, т.е. когда объект является частью самого себя.

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

Рекурсия в программировании — это способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма обращается сама к себе напрямую (прямая рекурсия) или через другие функции (косвенная рекурсия).

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

В этой статье программы представлены на языке С++.

Пример 1. Рекурсивная функция для расчета факториала заданного числа n:

n!=1⋅2⋅…⋅n, причем 0!=1 и 1!=1.

Кроме того, выполняется следующее соотношение:

n!=n⋅(n-1)!

Используя это соотношение, можно составить рекурсивную функцию для вычисления факториала:

long int F(int n)
{
   if (n > 1)  F=n * F(n – 1);
   else F=1;
}

Пример 2. Вычисление n-го члена последовательности чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21 и т.д.

#include

using namespace std;

int  fibonachi(int n)

{

  if (n>1)return(fibonachi(n-1)+fibonachi(n-2));

  else return(n);

 }

int main( )

{ int n,p;

  cin>>n;

  p=fibonachi(n);

  cout<<"p="<

}

Разложение числа на слагаемые

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

Решение.

Будем раскладывать число N на два слагаемых. Затем второе из полученных слагаемых снова будем раскладывать на 2 слагаемых и т.д., т.е. можно использовать рекурсию.

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

Обозначим: n1 - первое слагаемое в разложении.

Таким образом, на каждом шаге будем получать сумму двух слагаемых n1 и N-n1. Вновь полученное число N-n1 снова раскладывать на 2 слагаемых и т.д. Все слагаемые будем записывать в массив. Для этого нам понадобится массив a[N] из N элементов, поскольку самое длинное представление – это сумма N единиц.

Первый вызов подпрограммы надо выполнить при n1=1 (т.е. первое слагаемое будет равно 1), первое слагаемое в разложении хранится в массиве под номером 0 (т.е. pos=0). Поэтому первый вызов подпрограммы R(N, 1, 0).

Для поиска первого слагаемого в разложении (обозначим его n1) будем проверять все числа, начиная с 1 до N/2. Например, для числа 7 достаточно проверить в качестве первого слагаемого числа 1, 2, 3; для числа 10 – числа от 1 до 5).

После выбора первого слагаемого надо решить задачу разложения на слагаемые числа, равного N=N-n1. Параметрами создаваемой рекурсивной функции (ее имя — R) будут:

n – число, раскладываемое на слагаемые (не только заданное);

n1 – первое слагаемое числа n;

a[50] – массив, в котором хранятся слагаемые разложения (50 – максимальное с запасом кол-во возможных слагаемых в разложении).

Первый вызов подпрограммы надо выполнить при n1=1 (т.е. первое слагаемое будет равно 1), первое слагаемое в разложении хранится в массиве под номером 0 (т.е. pos=0). Поэтому первый вызов подпрограммы R(0, N, 1).

В подпрограмме в качестве первого слагаемого разложения будем  перебирать числа от n1 до n/2 в цикле c параметром i:

1) очередное число i надо сохранить в массиве a[50]  под номером pos, т.е. a[pos]=i;

2) снова обратиться к подпрограмме R. При очередном вызове подпрограммы надо увеличить номер в массиве на 1 (т.е. pos=pos+1), уменьшить раскладываемое на слагаемые число на i (т.е. n=n-i) и в качестве первого слагаемого нового числа снова выбрать число i, т.е. R(pos+1,n-i,i).

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

#include

using namespace std;

int a[50]; //глобальный массив для хранения слагаемых разложения

void R(int pos, long int n, int n1)

     {int i;

        for (i=n1 ; i<=n/2;i++)

              {a[pos]=i;

               R(pos+1,n-i,i);

               }

       for (i=0;i<=pos-1;i++)

            cout<< a[i]<<"+";

       cout<

       cout<

     }

int main(void)

{

 long int N;

 cin>>N;

 R(0,N,1);

 }

Например, число n=7.

Цикл

      for (i=n1 ; i<=n/2; i++)

будет работать при i=1,  i=2 и i=3. При каждом i , будет выполняться рекурсивный вызов подпрограммы:

Надо распечатать элементы массива a[…] , начиная с 0-го по 1 (т.к. pos-1=1). Будет напечатано: 1+1+1+1+1+1+

Надо еще напечатать число 1 (т.е. последнее полученное значение числа n) и перейти на новую строку.

Задача 2. Вывести на экран все варианты разложения заданного натурального числа N на нечетные слагаемые. 

Решение. Алгоритм несущественно отличается от предыдущего: слагаемые должны быть нечетными.  Очередное разложение закончено, если полученное значение числа n является нечетным; в этом случае его надо распечатать.

#include

using namespace std;

int a[50];

void R(int pos,long n, int n1)

     { int i;

       for (i=n1;i<=n/2;i++)

           if (i%2!=0)

               {a[pos]=i;

                R(pos+1,n-i,a[pos]);

               }

       if (n%2!=0)

          {for (i=0;i<=pos-1;i++)

               cout<< a[i]<<"+";

             cout<

           cout<

          }

     }

int main( )

{

 long int N;

 cin>>N;

 R(0,N,1);

 }

Замечание. Для разложения числа на четные слагаемые надо изменить выделенные строки на if (i%2==0) и на if (n%2==0). При первом вызове первое слагаемое равно 2, т.е. R(0,N,2). Эта задача имеет решение, если N – четное число.

Задача 3. Вывести на экран все варианты разложения заданного натурального числа N на простые слагаемые.

Решение. Алгоритм отличается от предыдущего тем, что вместо проверки на нечетность будем проверять, является ли слагаемое простым числом. Это будет проверяться в подпрограмме simple.

#include

using namespace std;

int a[50];

bool simple(int a)

{ int k=0;

  for (int i=2; i<=a; i++)

      if (a%i==0)k++;

  if(k==1)return true;else return false;

}

void R(int pos,long n, int n1)

     { int i;

       for (i=n1;i<=n/2;i++)

           if (simple(i))

               {a[pos]=i;

                R(pos+1,n-i,a[pos]);

               }

       if (simple(n))

          {for (i=0;i<=pos-1;i++)

               cout<< a[i]<<"+";

             cout<

           cout<

          }

     }

int main( )

{

 long int N;

 cout<<"N=";

 cin>>N;

 R(0,N,1);

 }

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

Задача 4. Вывести на экран все варианты разложения заданного натурального числа N на различные слагаемые в порядке возрастания (слагаемые не могут повторяться).

Решение. Алгоритм несущественно отличается от предыдущих: чтобы следующее слагаемое в разложении было больше предыдущего, подпрограмму надо вызывать с параметрами  R(pos+1,n-i,i+1).  Чтобы для четных чисел не было разложения на два одинаковых слагаемых, первое слагаемое разложения должно меняться от 1 до (n-1)/2 (например, для чисел 7 и 8 в качестве первого слагаемого могут быть числа 1,2,3).

#include

using namespace std;

int a[50];

void R(int pos,long n, int n1)

{     int i;

      for (i=n1 ; i<=(n-1)/2;i++)

              {a[pos]=i;

               R(pos+1,n-i,i+1);

               }

      for (i=0;i<=pos-1;i++)

               cout<

      cout<

 cout<

 }

int main( )

{

 long N;

 cin>>N;

 R(0,N,1);

 }

Задача 4. Вывести на экран все варианты разложения заданного натурального числа N на различные нечетные слагаемые в порядке возрастания (слагаемые не могут повторяться).

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

#include

using namespace std;

int a[50];

void R(int pos,long n, int n1)

{int i;

 for (i=n1 ; i<=(n-1)/2;i++)

      if (i%2!=0)

         {a[pos]=i;

          R(pos+1,n-i,i+1);

         }

 if (n%2!=0)

 {for (i=0;i<=pos-1;i++)

           cout<

      cout<

  cout<

 }

      }

      int main( )

      {

 long N;

 cin>>N;

 R(0,N,1);

}

Замечание. Для разложения числа на различные четные слагаемые надо изменить выделенные строки на if (i%2==0) и на if (n%2==0). При первом вызове первое слагаемое равно 2, т.е. R(0,N,2). Эта задача имеет решение, если N – четное число.

Задача 5. Вывести на экран все варианты разложения заданного натурального числа N на k слагаемых (слагаемые могут повторяться). Порядок слагаемых учитывается, т.е. разложения отличающиеся порядком слагаемых учитываются. Напечатать количество таких разложений.

Решение. Будем раскладывать число N на два слагаемых. Затем второе из полученных слагаемых снова будем раскладывать на 2 слагаемых и т.д., т.е. можно использовать рекурсию.

Задача 7. Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа N на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, 9 = 1 + 2 + 2 + 4 является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше, не является интересным, а разбиение 9 = 1 + 3 + 5 — является.

Помогите Мише вывести все интересные разбиения числа n на слагаемые.

Решение.

Будем раскладывать число N на два слагаемых. Затем второе из полученных слагаемых снова будем раскладывать на 2 слагаемых и т.д., т.е. можно использовать рекурсию.

Для поиска первого слагаемого в разложении (обозначим его n1) будем проверять все числа, начиная с 1 до N/2-1 (т.к. разность между слагаемыми должна быть ≥2). Например, для числа 7 достаточно проверить в качестве первого слагаемого числа 1, 2; для числа 10 – числа от 1 до 4).

После выбора первого слагаемого надо решить задачу разложения на слагаемые числа, равного N=N-n1. Параметрами создаваемой рекурсивной функции (ее имя — R) будут:

n – число, раскладываемое на слагаемые (не только заданное);

n1 – первое слагаемое числа n;

a[50] – массив, в котором хранятся слагаемые разложения (50 – максимальное с запасом кол-во возможных слагаемых в разложении).

Первый вызов подпрограммы надо выполнить при n1=1 (т.е. первое слагаемое будет равно 1), первое слагаемое в разложении хранится в массиве под номером 0 (т.е. pos=0). Поэтому первый вызов подпрограммы R(0, N, 1).

В подпрограмме в качестве первого слагаемого разложения будем  перебирать числа от n1 до n/2-1 в цикле c параметром i:

1) очередное число i надо сохранить в массиве a[50]  под номером pos, т.е. a[pos]=i;

2) снова обратиться к подпрограмме R. При очередном вызове подпрограммы надо увеличить номер в массиве на 1 (т.е. pos=pos+1), уменьшить раскладываемое на слагаемые число на i (т.е. n=n-i) и в качестве первого слагаемого нового числа выбрать число i+2, т.е. R(pos+1,n-i,i+2).

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

#include

using namespace std;

int a[50];//глобальный массив для хранения множителей разложения

long int N;//глобальная переменная, равная исходному числу

void R(int pos,long n, int n1)

     {int i;

      for (i=n1;i<=n/2-1;i++)

              {a[pos]=i;

               R(pos+1,n-i,i+2);

               }

       cout<< N <<"=";

       for (i=0;i<=pos-1;i++)

               cout<

       cout<

     }

int main( )

{

 cout<<"N=";

 cin>>N;

 R(0,N,1);

}

Разложение числа на множители

Задача. Вывести на экран все варианты разложения заданного натурального числа n на множители (порядок следования множителей не учитывается).

Алгоритм:

Решение будем получать в виде элементов массива, аналогичного следующему (для n = 12):

2*2*3

2*6

…

Будем раскладывать число n на два множителя. Затем второй из полученных множителей снова будем раскладывать на 2 множителя и т.д., т.е. можно использовать рекурсию.

Для поиска первого множителя в разложении будем проверять все числа, начиная с двойки до  Например, для числа 36 достаточно проверить в качестве первого множителя числа 2, 3, …,6; для числа 30 – числа от 2 до 5). Т.е. для числа n необходимо проверить, являются ли его множителями числа: n1, n1 + 1,…,.

Если среди них окажется множитель, то сохраним его в массиве, а затем решим задачу разложения на множители числа, равного частному от деления n на этот множитель.

Параметрами создаваемой рекурсивной функции (ее имя — R) будут:

n – число, разлагаемое на множители (не только заданное);

n1 – первый возможный множитель числа n;

a[50] – массив, в котором хранятся множители разложения (50 – максимальное с запасом кол-во возможных множителей в разложении).

Первый вызов подпрограммы надо выполнить при n1=2 (т.е. в качестве первого множителя будем проверять число 2), первый множитель в разложении хранится в массиве под номером 0 (т.е. pos=0). Поэтому первый вызов R(0, n, 2).

В подпрограмме будем проверять делимость n на числа от n1 до в цикле c параметром i. Если очередное число i является множителем числа n, то:

1) надо сохранить его в массиве a[50]  под номером pos, т.е. a[pos]=i;

2) снова обратиться к подпрограмме R. При очередном вызове подпрограммы надо увеличить номер в массиве на 1 (т.е. pos=pos+1), уменьшить раскладываемое на множители число в i раз (т.е.  n=n/i) и в качестве первого делителя нового числа проверять число i, т.е. R(pos+1,n/i,i).

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

#include

using namespace std;

int a[50];//глобальный массив для хранения множителей разложения

void R(int pos, long int n, int n1)

     {int i;

      for (i=n1 ; i*i<=n; i++)

           if (n%i==0)  //если i - множитель числа n

              {a[pos]=i;

               R(pos+1,n/i,i);

               }

      for (i=0;i<=pos-1;i++)

      cout<

      cout<

 cout<

     }

int main( )

{

 long intN;

 cin>>N;

 R(0,N,2);

}

Например, число n=12.

Цикл

      for (i=n1 ; i*i<=n; i++)

будет работать при i=2 и i=3. При каждом i , будет выполняться рекурсивный вызов подпрограммы:

При первом вызове подпрограммы n1=2. Число 2 является делителем числа 12, поэтому  a[0]=2. Затем снова вызывается подпрограмма, но уже для числа 6, pos=1 и в качестве первого проверяемого делителя - снова число 2. Для числа 6 число 2 снова является делителем, поэтому a[1]=2. Затем снова вызывается подпрограмма, но уже для числа 3, pos=2 и в качестве первого проверяемого делителя снова число 2. Т.к. i меняется от n1 до , то для числа 3 в качестве i будет проверяться только 2. Т.к. 3 на 2 не делится, то первое разложение для числа 12 закончено.

Надо распечатать элементы массива a[…] , начиная с 0-го по 1 (т.к. pos-1=1). Будет напечатано: 2*2*

Надо еще напечатать число 3 (т.е. последнее полученное значение числа n) и перейти на новую строку.