文档章节

递归的应用

Cynthia_x
 Cynthia_x
发布于 2016/11/21 18:34
字数 702
阅读 29
收藏 0

1. 设计一个算法并编程实现,将一个正整数划分成多个正整数的加和,并把所有的结果组合输出。

分  析: 正整数的划分就是把一个正整数n,写成多个大于等于1且小于等于其本身的整数的和,其中各加数所构成的集合为n的一个划分,这是一个典型的递归算法。即:

 一个正整数被划分成多个正整数,划分组合的成员个数最多是这个正整数的大小,最少是这个正整数本身。而且在递归的过程中还要传递上层的划分数字,要求划分的后一个数字大于等于前一个,使无序的划分方式变为有序,去掉重复项。

代码实现: 

#include <stdio.h>
int mark[10]; //定义全局变量 
int n;
void Divide(int now,int k,int pre){
   int i;
   if(now>n) return;
   if(now==n){
        for(i=0;i<k-1;i++)
          printf("%d+",mark[i]);
    printf("%d\n",mark[i]);
   }
   else{
     for(i=pre;i>0;i--){
        if(i<=pre){
           mark[k]=i;
           now+=i;
           Divide(now,k+1,i); //递归调用函数 
           now-=i;
        }
     }
   }

int main(void){
   scanf("%d",&n);
   Divide(0,0,n-1);
   return 0;
}

运行结果

 

2. 设计一个算法并编程实现,对一组数的全排列,并将所有的排列结果输出。

分 析 :   对于全排列问题,f(n)=n!(定义0!=1),其中需要用到函数的递归调用,在调用中,序列中的某两个元素需要不断地交换位置,在输出时调用一次,满足条件即可输出,是一种情况。一组数的全排列组合的个数为n!,通过先序递归将这一组数存入新的数组中,递归的过程中需要判断新放入的数在数组中是不是存在,如果存在,就不能被放入数组中,如果不存在,则可以放入数组,递归一次,在数组中放入一个数。递归四次则输出一次,输出完成后递归回退,进行穷举。R的全排列可归纳定义如下:

当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素;

当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),......,(rn)Perm(Rn)构成。

代码实现

#include <stdio.h>  
#define N 100
void swap(int *a, int *b){     //功能:交换两个数
    int m;     
     m = *a;     
    *a = *b;     
    *b = m;
}  
void perm(int arr[], int k, int m){     
    int i,n=0;     
    if(k > m){         
        for(i = 0; i <= m; i++)            
            printf("%d ", arr[i]);         
        printf("\n");         
        n++;     
    }     
    else{         
        for(i = k; i <= m; i++){            
            swap(&arr[k], &arr[i]);            
            perm(arr, k + 1, m);    //递归调用        
            swap(&arr[k], &arr[i]);         
        }     
    }
}
int main(void){     
    int n,i,k;
    int arr[N];
    printf("请输入有几个数:\t");
    scanf("%d",&n);
    for(i = 0; i < n; i++)  {
        scanf("%d", &arr[i]);
    }
    perm(arr, 0, n-1);         
    return 0;

运行结果

© 著作权归作者所有

共有 人打赏支持
Cynthia_x
粉丝 0
博文 8
码字总数 8751
作品 0
西安
前端工程师
递归六--判断一个数是偶数还是奇数 -java实现

交互递归: 到目前为止,看到的递归函数都是直接调用自己。虽然大多数的递归函数都符合这一形式,但其实递归的定义更为广泛,如果某个函数被细分成了几个子函数,那么可以在更深的嵌套层次上...

Amui
2015/10/02
6
0
人工智能3:神经网络发展分支介绍

前言:自己要开始学习神经网络,当然要先搞明白神经网络发展过程中出现的分支有哪些,这些分支经过理论上的论证,实际上的操作,不断的完善后发展成现如今的哪些神经网络,以及各自的用处在哪...

zzz_cming
01/21
0
0
try catch无法捕获 StackOverflowException

在以前版本的 .NET Framework 中,您的应用程序可以捕获 StackOverflowException 对象(例如,从无限递归恢复)。 但是,现在我们建议不要使用这种做法,原因是需要大量附加代码才能可靠地捕...

C_Sharp大大
2013/08/17
0
0
每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。 学习使用递归的关键在于:如何将问题分为基线条件和递归条...

爱吃西瓜的番茄酱
01/09
0
0
java中常见的递归使用场景

一、递归概述 程序调用自身的编程技巧称为递归.递归作为一种算法在程序设计语言中广泛应用。 递归需具备的条件: 子问题须与原始问题为同样的事,且更为简单; 不能无限制调用本身,须有个出...

lkee6760
2017/02/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

NIO与BIO的区别、NIO的运行原理和并发使用场景

NIO(Non-blocking I/O,在Java领域,也称为New I/O),是一种同步非阻塞的I/O模型,也是I/O多路复用的基础,已经被越来越多地应用到大型应用服务器,成为解决高并发与大量连接、I/O处理问题的...

Java干货分享
40分钟前
1
0
Makefile 学习 1 - 基于若干 Blog 的汇总

基于若干 Blog 汇总的 makefile 教程 陈皓 https://blog.csdn.net/haoel/article/details/2886 Makefile 基础知识 1. 什么是 Makefile? 规定软件工程的编译规则。一个工程中的源文件,其按类...

公孙衍
53分钟前
1
0
72.告警系统邮件引擎 运行告警系统

20.23/20.24/20.25 告警系统邮件引擎 20.26 运行告警系统 20.23/20.24/20.25 告警系统邮件引擎 邮件首先要有一个mail.py,以下。 因为我们之前zabbix的时候做过,就可以直接拷贝过来 mail.s...

王鑫linux
今天
1
0
09-利用思维导图梳理JavaSE-

09-利用思维导图梳理JavaSE-Java IO流 主要内容 1.Java IO概述 1.1.定义 1.2.输入流 - InputStream 1.3.输出流 - OutputStream 1.4.IO流的分类 1.5.字符流和字节流 2.InputStream类 2.1.File...

飞鱼说编程
今天
3
0
Spring Cloud 微服务的那点事

在详细的了解SpringCloud中所使用的各个组件之前,我们先了解下微服务框架的前世今生。 单体架构 在网站开发的前期,项目面临的流量相对较少,单一应用可以实现我们所需要的功能,从而减少开...

我是你大哥
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部