文档章节

递归的应用

Cynthia_x
 Cynthia_x
发布于 2016/11/21 18:34
字数 702
阅读 28
收藏 0
点赞 0
评论 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
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
每天学习一点儿算法--递归

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

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

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

lkee6760
2017/02/02
0
0
JavaScript专题之递归

JavaScript 专题系列第十八篇,讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例: 示意图(图片来自 wwww.penjee.com): 斐波那契数列 在《JavaScript专...

冴羽
2017/09/13
0
0
Python基础之函数

Python基础之函数 一、函数基础 1、函数概念: 函数是指将一组语句的集合通过一个名字(函数名)封装起来,要想执行这个函数,只需调用其函数名即可 2、函数的作用 (1)减少重复代码 (2)使程...

Dayi_123
2017/04/20
0
0
vue组件递归——级联菜单的实现

最近做项目经常会用到一些UI库,比如、等,这些能够快速构建应用的库真的十分方便。比如的级联菜单很是好用,但是在使用的同时不免起了一些疑惑,它是怎么做到多级联动,依我所知,如果一个数...

ALOLONGHUN
01/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

shell中的函数、shell中的数组、告警系统需求分析

shell中的函数 格式: 格式: function f_name() { command } 函数必须要放在最前面 示例1(用来打印参数) 示例2(用于定义加法) 示例3(用于显示IP) shell中的数组 shell中的数组1 定义数...

Zhouliang6
今天
2
0
用 Scikit-Learn 和 Pandas 学习线性回归

      对于想深入了解线性回归的童鞋,这里给出一个完整的例子,详细学完这个例子,对用scikit-learn来运行线性回归,评估模型不会有什么问题了。 1. 获取数据,定义问题     没有...

wangxuwei
今天
1
0
MAC安装MAVEN

一:下载maven压缩包(Zip或tar可选),解压压缩包 二:打开终端输入:vim ~/.bash_profile(如果找不到该文件新建一个:touch ./bash_profile) 三:输入i 四:输入maven环境变量配置 MAVEN_HO...

WALK_MAN
今天
0
0
33.iptables备份与恢复 firewalld的9个zone以及操作 service的操作

10.19 iptables规则备份和恢复 10.20 firewalld的9个zone 10.21 firewalld关于zone的操作 10.22 firewalld关于service的操作 10.19 iptables规则备份和恢复: ~1. 保存和备份iptables规则 ~2...

王鑫linux
今天
2
0
大数据教程(2.11):keeperalived+nginx高可用集群搭建教程

上一章节博主为大家介绍了目前大型互联网项目的系统架构体系,相信大家应该注意到其中很重要的一块知识nginx技术,在本节博主将为大家分享nginx的相关技术以及配置过程。 一、nginx相关概念 ...

em_aaron
今天
1
0
Apache Directory Studio连接Weblogic内置LDAP

OBIEE默认使用Weblogic内置LDAP管理用户及组。 要整理已存在的用户及组,此前办法是导出安全数据,文本编辑器打开认证文件,使用正则表达式获取用户及组的信息。 后来想到直接用Apache Dire...

wffger
今天
2
0
HFS

FS,它是一种上传文件的软件。 专为个人用户所设计的 HTTP 档案系统 - Http File Server,如果您觉得架设 FTP Server 太麻烦,那么这个软件可以提供您更方便的档案传输系统,下载后无须安装,...

garkey
今天
1
0
Java IO类库之BufferedInputStream

一、BufferedInputStream介绍 /** * A <code>BufferedInputStream</code> adds * functionality to another input stream-namely, * the ability to buffer the input and to * sup......

老韭菜
今天
0
0
STM 32 窗口看门狗

http://bbs.elecfans.com/jishu_805708_1_1.html https://blog.csdn.net/a1985831055/article/details/77404131...

whoisliang
昨天
1
0
Dubbo解析(六)-服务调用

当dubbo消费方和提供方都发布和引用完成后,第四步就是消费方调用提供方。 还是以dubbo的DemoService举例 -- 提供方<dubbo:application name="demo-provider"/><dubbo:registry address="z...

青离
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部