Рекурсивные алгоритмы. Разложение натурального числа на слагаемые и множители.
статья по информатике и икт (10, 11 класс)
В этой статье предложены решения задач на разложение натурального числа на слагаемые и множители, удовлетворяющие различным условиям. Статья содержит программы на языке программирования С++.
Скачать:
Вложение | Размер |
---|---|
![]() | 111.19 КБ |
Предварительный просмотр:
Рекурсивные алгоритмы.
Разложение натурального числа на слагаемые и множители.
Слово “рекурсия” происходит от латинского слова “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< } 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< } } 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 слагаемых и т.д., т.е. можно использовать рекурсию. #include using namespace std; int a[50]; int c,k; void R(int pos, int n) { int i; for (i=1 ; i {a[pos]=i; R(pos+1,n-i); } if (pos==k-1) {for (i=0;i<=pos-1;i++) cout<< a[i] <<"+"; cout< c++; } } int main( ) { int N; cout<<"N="; cin>>N; cout<<"k="; cin>>k; R(0,N); cout<<"c="< } Задача 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< } int main( ) { cout<<"N="; cin>>N; R(0,N,1); } Разложение числа на множители Задача. Вывести на экран все варианты разложения заданного натурального числа n на множители (порядок следования множителей не учитывается). Алгоритм: Решение будем получать в виде элементов массива, аналогичного следующему (для n = 12): 2*2*3 2*6 … Будем раскладывать число n на два множителя. Затем второй из полученных множителей снова будем раскладывать на 2 множителя и т.д., т.е. можно использовать рекурсию. Для поиска первого множителя в разложении будем проверять все числа, начиная с двойки до Если среди них окажется множитель, то сохраним его в массиве, а затем решим задачу разложения на множители числа, равного частному от деления n на этот множитель. Параметрами создаваемой рекурсивной функции (ее имя — R) будут: n – число, разлагаемое на множители (не только заданное); n1 – первый возможный множитель числа n; a[50] – массив, в котором хранятся множители разложения (50 – максимальное с запасом кол-во возможных множителей в разложении). Первый вызов подпрограммы надо выполнить при n1=2 (т.е. в качестве первого множителя будем проверять число 2), первый множитель в разложении хранится в массиве под номером 0 (т.е. pos=0). Поэтому первый вызов R(0, n, 2). В подпрограмме будем проверять делимость n на числа от n1 до 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< } 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 до Надо распечатать элементы массива a[…] , начиная с 0-го по 1 (т.к. pos-1=1). Будет напечатано: 2*2* Надо еще напечатать число 3 (т.е. последнее полученное значение числа n) и перейти на новую строку. Например, для числа 36 достаточно проверить в качестве первого множителя числа 2, 3, …,6; для числа 30 – числа от 2 до 5). Т.е. для числа n необходимо проверить, являются ли его множителями числа: n1, n1 + 1,…,
.
в цикле c параметром i. Если очередное число i является множителем числа n, то:
, то для числа 3 в качестве i будет проверяться только 2. Т.к. 3 на 2 не делится, то первое разложение для числа 12 закончено.
По теме: методические разработки, презентации и конспекты
Понятие рекурсии. Построение рекурсивных алгоритмов в среде исполнителя
Открытый урок по теме "Алгоритмизация" для 9-х классов. К описанию урока приложена презентация с примерами результатов работы рекурсивных алгоритмов в среде "kTurtle" и подробное описание хода урока (...
![](/sites/default/files/pictures/2013/01/23/picture-73532-1358966471.jpg)
Презентация для подготовки к ЕГЭ по информатике по теме "Рекурсивные алгоритмы"
Презентация на тему "Рекурсивные алгоритмы" создана для подготовки обучающихся к ЕГЭ по информатике и ИКТ. В работе рассмотрено определение рекурсии, приведены примеры рекурсивно-определенных графичес...
![](/sites/default/files/pictures/2015/07/27/picture-650824-1438020270.jpg)
Конспект урока в модульной технологии (3Х30) для 5-класса, обучающихся по учебнику С.М.Никольского "Разложение натуральный чисел на простые множители"
Данный модульный – урок (3 Х 30) адресован для учителей математики, работающих в 5 классе по учебнику С.М.Никольского для объяснения темы « Разложение натурального числа на простые множители». Урок ра...
![](/sites/default/files/pictures/2015/01/15/picture-565185-1421325781.jpg)
Обобщающий урок для 6 класса по теме "Разложение натуральных чисел на простые множители и нахождение НОД"
Урок проводится в виде математической игры "Авторалли"...
Рекурсивные алгоритмы
Презентации рассмотрен вопросы, связанные с изучением рекурсивных алгоритмов: что такое рекурсия, где в жизни встречается рекурсия, как используется, особенности рекурсивных алгоритмов....
Разложение натуральных чисел на множители
Конспект урока по алгебре, 7 класс, УМК Никольский...