实验一：递归函数的设计与实现

实验一：递归函数的设计与实现

实验目的：掌握递归函数的设计与实现方法 实验原理: 递归函数的设计

实验步骤：编写程序实现教材P12例2-5 整数划分问题 问题描述：整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。

思路：递归函数的声明为 int split(int n, int m);其中n为要划分的正整数，m是划分中的最大加数(当m > n时，最大加数为n)，

1 当n = 1或m = 1时，split的值为1，可根据上例看出，只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1

可用程序表示为if(n == 1 || m == 1) return 1; 2 下面看一看m 和 n的关系。它们有三种关系 (1) m > n

在整数划分中实际上最大加数不能大于n，因此在这种情况可以等价为split(n, n);

可用程序表示为if(m > n) return split(n, n); (2) m = n

这种情况可用递归表示为split(n, m - 1) + 1，从以上例子中可以看出，就是最大加

数为6和小于6的划分之和

用程序表示为if(m == n) return (split(n, m - 1) + 1); (3) m < n

这是最一般的情况，在划分的大多数时都是这种情况。

从上例可以看出，设m = 4，那split(6, 4)的值是最大加数小于4划分数和整数2的划分数的和。

因此，split(n, m)可表示为split(n, m - 1) + split(n - m, m) 实验要求：（1）使用C++或TC2.0

（2）上机前要有源代码或流程图。

简易代码

#include #include int q(int n,int m) {

if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n

if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); }

int main() {

int n,m;

cout<<\请输入整数和最大加数：\ cin>>n>>m;

cout<<\正整数\共有\种不同的划分。\}

结果显示

稍复杂

#include

#include \用于system()函数*/ #include \#define NN 300

int y=0; /*用于记录存放的数据的个数*/ int length=0; /*用于存放标记-1的个数*/

int number[NN]; /*存放所有的划分出来的数以及换行符*/ /*函数q()用于计算给定整数的划分的个数*/ int q(int n,int m) { if((n<1)||(m<1))return 0; if((n==1)||(m==1))return 1; if(n

/*函数slipt()用于递归划分给定的整数*/ void slipt(int n,int m) { if((n==0)||(m==0)) return; /*如果被划分的数为0，或最大加数为0，则退出slipt()函数*/ if(m==1) /*如果最大加数为1，则存储n个1*/ for(int i=n;i>0;i--) number[y++]=1; /*将n个1存放汝number数组中*/ if(n==1) number[y++]=1; if(m>n&&n>1)slipt(n,n); /*如果最大加数大于被划分的数，则递归调用slipt(n,n)*/ if(m>1&&m<=n) /*如果最大加数大于0且不大于被划分的数，则进行以下工作(分两种情况)*/ { number[y++]=m; /*将本次最大加数存入数组number中*/ slipt(n-m,m); /*保持最大加数不变，被划分的数减小m，因为此时最大加数已作为一个加数因子*/ number[y++]=-1; /*插入标志-1*/ length++; /*记录标志-1的个数*/ slipt(n,m-1); /*保持被划分的数不变，最大加数减1，此时最大加数变为m-1*/ } }

//number2为存放数据的数组，n为待划分的整数，length为-1的个数，sum为存入number2中的数据的个数

void out_of_slipt(int * number2,int n,int length,int sum) {

int * c=(int *)malloc(sizeof(int)*(length+2)); /*动态申请一块内存空间作为存放两个相邻标志间的数的和*/ if (NULL==c){printf(\ /*判断申请是否成功*/ for(int i=0;i

//为被划分的数的数 for (int i6=0;i6n) { summ-=b[i6][j4]; xx--; for(int mx=1;mx<=sunm;mx++) { for (int jx=0;b[i6+mx][jx]!=0;jx++) { summ+=b[i6+mx][jx]; if(summ==n) { for(int mnm=0;mnm

// for(mnm=0;mnm<=jx;mnm++) // printf(\ printf(\ for(mnm=0;b[k2][mnm]!=0;mnm++) printf(\ printf(\ } else { summ-=b[i6+mx][jx]; } } } } } } i6=k2; //恢复本次下标 } free(c); for(int ff=0;ff

int main() { for (int r=0;r

printf(\有%d种划分!\\n\ printf(\种划分如下(每一行代表一个划分)：\\n\ slipt(integer,m); number[y]=-1; //存入最后一个标志-1 length+=1; out_of_slipt(number,integer,length,y); for(int k=0;k

结果显示

本文来源：https://www.bwwdw.com/article/p5v7.html