C# 递归算法详解

目录
  • 1）1、1、2、3、5、8.......用递归算法求第30位数的值？
  • 2）编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）斐波那契数列为：0、1、1、2、3、……，
  • 3）求1+2+3+4+5+....+n的值
  • 4）有两个整数型数组，从小到大排列，编写一个算法将其合并到一个数组中，并从小到大排列
  • 总结

1）1、1、2、3、5、8.......用递归算法求第30位数的值？

首先我们能够发现从第3位数起后一位数等于前两位数值之和，即：x=（x-1）+（x-2），x>2;

这里须要不断的相加，第一时刻就会想到循环处理，我们尝试用数组去装载这些数值，即：

int[] a=new int[30];
 a[0]=1;
 a[1]=1;
 for(int i=2;i<30;i++)
{
    a[i]=a[i-1]+a[i-2];
}

求a[29]的值即为第30位数的值，递归该怎样处理呢？相同定义函数

fun(n)
{
    return fun(n-1)+fun(n-2)//n为第几位数，第n位数返回值等于第n-1位数的值与第n-2位数的值之和
}

仅仅有当n>2为这样的情况，就能够做个推断

fun(n)
{
     if(n==1 || n==2)
          return 1;
     else
          return fun(n-1)+fun(n-2);
}

求fun(30);

2）编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）斐波那契数列为：0、1、1、2、3、……，

即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （当n>1时）

写成递归函数有：

int fib(int n)
{
　 if (n==0) return 0;
　 if (n==1) return 1;
　 if (n>1) return fib(n-1)+fib(n-2);
}

递归算法的运行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。

比如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能马上得到结果1和0。在递推阶段，必需要有终止递归的

情况。比如在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，比如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。

在编写递归函数时要注意，函数中的局部变量和參数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的參数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的參数和局部变量。

因为递归引起一系列的函数调用，而且可能会有一系列的反复计算，递归算法的运行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编敲代码。比如上例计算斐波那契数列的第n项的函数fib(n)应採用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。

3）求1+2+3+4+5+....+n的值

Fun(n)=n+Fun(n-1)
n=1时为1
Fun(n)
{
     if(n==1)
       return 1;
     else
      return n+Fun(n-1);
}

4）有两个整数型数组，从小到大排列，编写一个算法将其合并到一个数组中，并从小到大排列

public void Fun()
    {
        int[] a = { 1, 3, 5, 7, 9, 10 };
        int[] b = { 2, 4, 6, 8, 11, 12, 15 };
        int[] c = new int[a.Length + b.Length];
        ArrayList al=new ArrayList();
        int i=0;
        int j=0;
        while (i <= a.Length - 1 && j <= b.Length - 1)
        {  //循环比較把小的放到前面
            if (a[i] < b[j])
            {
                al.Add(a[i++]);
            }
            else
            {
                al.Add(b[j++]);
            }
        }
        //两个数组的长度不一样，必有个数组没比較完
        while (i <= a.Length - 1)//加入a中剩下的
        {
            al.Add(a[i++]);
        }
        while (j <= b.Length - 1)//加入b中剩下的
        {
            al.Add(b[j++]);
        }
        for (int ii = 0; ii <= c.Length-1 ; ii++)
        {
            c[ii] = (int)al[ii];
        }
    }

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C#递归算法寻找数组中第K大的数

    1.概述 国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景 在向量V[first,last)中查找出第K大元素的值 3.分析 如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失

  • C#递归算法之归并排序

    C#递归算法之归并排序

    归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表 首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25  和

  • C#递归算法之快速排序

    C#递归算法之快速排序

    上两片第归算法学习: 1)递归算法之分而治之策略 2)递归算法之归并排序 上一篇学习中介绍了了递归算法在排序中的一个应用:归并排序,在排序算法中还有一种算法用到了递归,那就是快速排序,快速排序也是一种利用了分而治之策略的算法,它由C.A.R发明,它依据中心元素的值,利用一系列递归调用将数据表划分成越来越小的子表.在每一步调用中,经过多次的交换,最终为中心元素找到最终的位置.与归并算法不同,快速排序是就地排序,而归并排序需要把元素在临时向量中拷贝,下面通过对以下向量进行排序来理解和加深快速排序算法

  • 经典实例讲解C#递归算法

    一 .递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法. 递归算法是一种直接或者间接地调用自身算法的过程.在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解. 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身. (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口. (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序. (4) 在递归调用的过程当中

  • C#递归算法之分而治之策略

    C#递归算法之分而治之策略

    1.分而治之的概念   分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决 2.分而治之的优点和缺点 分而治之算法通常包括一个或者多个递归方法的调用,当这些调用将数据分隔成为独立的集合从而处理较小集合的时候,分而治之的策略将会有很高的效率,而在数据进行分解的时候,分而治之的策略可能会产生大量的重复计算,从而导致性能的降低. 3.画标尺程序的分析讲解 画标

  • C#递归算法之打靶算法分析

    C#递归算法之打靶算法分析

    问题: 一个设计运动员打靶,靶一共10环,连开10环打中90环的可能性有多少?请用第归算法实现? 分析: 1)每次打靶可能的得分范围是什么? 靶有10个环,那么当打中时,分数可为1-10,如果未打中得分为0,所以每次打靶得分的范围为0-10,共有11中可能 2)计算有多少种可能最直接的方法: 打10次靶,分别记录这10次打靶过程,用循环来完成 for(int i1=0;i1<=10;i++) { for(int i2=0;i2<=10;i2++) { for(int i3=0;i3<=1

  • Java递归算法详解(动力节点整理)

    Java递归算法详解(动力节点整理)

    递归算法是一种直接或者间接调用自身函数或者方法的算法.Java递归算法是基于Java语言实现的递归算法.递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解.递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解.    递归算法解决问题的特点: 1)递归就是方法里调用自身.  2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口.  3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序.  4)在递

  • C# 递归算法详解

    目录 1)1.1.2.3.5.8.......用递归算法求第30位数的值? 2)编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)斐波那契数列为:0.1.1.2.3.--, 3)求1+2+3+4+5+....+n的值 4)有两个整数型数组,从小到大排列,编写一个算法将其合并到一个数组中,并从小到大排列 总结 1)1.1.2.3.5.8.......用递归算法求第30位数的值? 首先我们能够发现从第3位数起后一位数等于前两位数值之和,即:x=(x-1)+(x-2),x>2; 这里须

  • python装饰器与递归算法详解

    1.python装饰器 刚刚接触python的装饰器,简直懵逼了,直接不懂什么意思啊有木有,自己都忘了走了多少遍Debug,查了多少遍资料,猜有点点开始明白了.总结了一下解释得比较好的,通俗易懂的来说明一下: 小P闲来无事,随便翻看自己以前写的一些函数,忽然对一个最最最基础的函数起了兴趣: def sum1(): sum = 1 + 2 print(sum) sum1() 此时小P想看看这个函数执行用了多长时间,所以写了几句代码插进去了: import time def sum1(): star

  • Java的递归算法详解

    Java的递归算法详解

    目录 一.介绍 1.介绍 2.案例 二.迷宫问题 三.八皇后问题 四.汉诺塔问题 1.问题 2.思想 3.代码 总结 一.介绍 1.介绍 递归:递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁. 迭代和递归区别:迭代使用的是循环结构,递归使用的选择结构.使用递归能使程序的结构更清晰.更简洁.更容易让人理解,从而减少读懂代码的时间.其时间复杂度就是递归的次数. 但大量的递归调用会建立函数的副本,会消耗大量的时间和内存,而迭代则不需要此种付出

  • Python实例详解递归算法

    Python实例详解递归算法

    递归是一种较为抽象的数学逻辑,可以简单的理解为「程序调用自身的算法」. 维基百科对递归的解释是: 递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法.递归一词还较常用于描述以自相似方法重复事物的过程. 例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的.也可以理解为自我复制的过程. "递"是传递的意思,"归"是归还的意思,先把一个方法一层层传递下去,然后传递到最后一层再把结果归还回来. 比

  • 例题详解Java dfs与记忆化搜索和分治递归算法的使用

    例题详解Java dfs与记忆化搜索和分治递归算法的使用

    目录 一.dfs(深度优先搜索) 1.图的dfs 2.树的dfs 二.记忆化搜索 1.普通递归:O(2^n) 2.记忆化搜索: O(n) 三.分治 四.算法题 1.dia和威严 示例 2.小红点点点 示例1 3.kotori和素因子 示例1 示例2 4.kotori和糖果 示例 一.dfs(深度优先搜索) 1.图的dfs /** * 深度优先搜索 * * @param node * @param set */ public void DFS(Node node, Set<Node> set)

  • C++递归算法处理岛屿问题详解

    目录 岛屿问题定义 例题一-岛屿的数量 例题二-岛屿的周长 岛屿问题定义 岛屿问题是指用二维数组进行模拟, 1的位置表示陆地, 0的位置表示海洋.岛屿是指 被水(0)包围的陆地(1) 如下图所示: 岛屿问题是一道典型的递归问题(一位大佬曾说将岛屿问题看成是4叉树,我觉得这个比喻非常好), 对每个陆地位置, 我们需要递归地检测它的上下左右位置是不是陆地. 下面我们来写一下对岛屿问题的递归模板: public void dfs(char[][] grid, int m, int n){ // 位置越

  • java并发编程_线程池的使用方法(详解)

    java并发编程_线程池的使用方法(详解)

    一.任务和执行策略之间的隐性耦合 Executor可以将任务的提交和任务的执行策略解耦 只有任务是同类型的且执行时间差别不大,才能发挥最大性能,否则,如将一些耗时长的任务和耗时短的任务放在一个线程池,除非线程池很大,否则会造成死锁等问题 1.线程饥饿死锁 类似于:将两个任务提交给一个单线程池,且两个任务之间相互依赖,一个任务等待另一个任务,则会发生死锁:表现为池不够 定义:某个任务必须等待池中其他任务的运行结果,有可能发生饥饿死锁 2.线程池大小 注意:线程池的大小还受其他的限制,如其他资源池:

  • C语言数据结构之图的遍历实例详解

    C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

随机推荐