精华内容
下载资源
问答
  • 栈与递归的实现

    2015-01-15 17:28:00
    对于有些问题还不是很熟悉,所以暂时需要些时间去理解,需要多写些代码去体会,,还有一个重要应用是在程序设计语言中实现递归,所以这次主要是讲递归的实现,大家熟悉的阶乘函数,2阶Fibonacci数列和Ackerman...

      对于栈有些问题还不是很熟悉,所以暂时需要些时间去理解,需要多写些代码去体会,,栈还有一个重要应用是在程序设计语言中实现递归,所以这次主要是讲递归的实现,大家熟悉的阶乘函数,2阶Fibonacci数列和Ackerman函数等,其次还有的数据结构,如二叉树、广义表等,由于结构本身固有的递归特性,则它们的操作可递归的描述,另外还有一类问题,虽然问题本身没有明显的递归结构,但是递归求解比迭代求解更简单,如八皇后问题、Hanoi塔问题等。

      递归是一种数学上分而治之的思想,它将大型复杂问题转化为与原问题相同但规模较小的问题进行处理,数学表示如下:

          

     

      下面我以一个八皇后问题来说一下这儿的递归问题,在一个8X8国际象棋中,有8个皇后,每个皇后占一格,要求皇后间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行,同一列或者同一对角线上。那么怎么来实现这个想法呢?下面是我的算法思路:先给两个了、变量i,j赋值为1,从第i行开始,恢复j的当前值,判断第j个位置。1、位置j可放入皇后,标记位置(i,j),i++,j = 1; 2、位置j不可放入皇后,j++,i = 1;  3、当j>8时候,j--,继续上述循环; 4、第八行有位置可以放入皇后。

      实现代码如下:

     1 #include <stdio.h>
     2 #define N 8
     3 
     4 typedef struct _tag_Pos
     5 {
     6     int ios;
     7     int jos;
     8 } Pos;
     9 
    10 static char board[N+2][N+2];
    11 static Pos pos[] = { {-1, -1}, {-1, 0}, {-1, 1} };
    12 static int count = 0;
    13 
    14 void init()
    15 {
    16     int i = 0;
    17     int j = 0;  
    18     for(i=0; i<N+2; i++)
    19     {
    20         board[0][i] = '#';
    21         board[N+1][i] = '#';
    22         board[i][0] = '#';
    23         board[i][N+1] = '#';
    24     }    
    25     for(i=1; i<=N; i++)
    26     {
    27         for(j=1; j<=N; j++)
    28         {
    29             board[i][j] = ' ';
    30         }
    31     }
    32 }
    33 
    34 void display()
    35 {
    36     int i = 0;
    37     int j = 1;  
    38     for(i=0; i<N+2; i++)
    39     {
    40         for(j=0; j<N+2; j++)
    41         {
    42             printf("%c", board[i][j]);
    43         }     
    44         printf("\n");
    45     }
    46 }
    47 
    48 int check(int i, int j)
    49 {
    50     int ret = 1;
    51     int p = 0;  
    52     for(p=0; p<3; p++)
    53     {
    54         int ni = i;
    55         int nj = j;       
    56         while( ret && (board[ni][nj] != '#') )
    57         {
    58             ni = ni + pos[p].ios;
    59             nj = nj + pos[p].jos;           
    60             ret = ret && (board[ni][nj] != '*');
    61         }
    62     }
    63     
    64     return ret;
    65 }
    66 
    67 void find(int i)
    68 {
    69     int j = 0;   
    70     if( i > N )
    71     {
    72         count++;       
    73         printf("Solution: %d\n", count);      
    74         display();       
    75         getchar();
    76     }
    77     else
    78     {
    79         for(j=1; j<=N; j++)
    80         {
    81             if( check(i, j) )
    82             {
    83                 board[i][j] = '*';               
    84                 find(i+1);               
    85                 board[i][j] = ' ';
    86             }
    87         }
    88     }
    89 }
    90 
    91 int main()
    92 {
    93     init();
    94     find(1);
    95     
    96     return 0;
    97 }
    queen

     

      编译结果如下图:

    当不断按Enter的时候,会陆续出现Solution一直到Solutioin92,再按Enter会退出了。如下图

     

    小结:

      递归是一种将问题分而治之的思想,解决问题的时候首先就要建立递归的模型;

      如上图到Solution92的时候就结束了,所以解决递归问题首先要有边界条件,否则将死循环;

     

    展开全文
  • 3.3栈与递归的实现

    千次阅读 2017-02-03 16:16:38
    3.3栈与递归的实现

    一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递归函数。

    (先说明下若在函数A中调用了函数B,则称函数A为调用函数,函数B为被调用函数)


    当一个函数的运行期间调用另一个函数时,在运行被调用的函数之前,系统要完成3件事情

    1.将所有的实参、返回地址等信息传递给被调用的函数保存。

    2.为被调用函数的局部变量分配存储区。

    3.将控制转移到被调用函数入口。


    被调用函数返回调用函数之前也要完成3件工作。

    1.保存被调用函数的计算结果。

    2.释放被调用函数的数据区。

    3.依照被调用函数保存的返回地址将控制转移到调用函数。


    这时要通过栈来实现,系统将整个程序运行所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,出栈就释放。

    图3.6(c)主函数调用函数first,first再调用second

    图3.6(a)当前正在执行函数second中某个语句时栈的状态

    图3.6(b)second退出后正执行的函数first中某个语句时栈的状态




    下面看看Hanoi塔的递归



    下面对这个表做出解释:

    这个表第列是运行语句行号:

    代码如下:

    void hanoi (int n, char x, char y, char z) {  // 
      // 将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到
      // 塔座z上,y可用作辅助塔座。
      // 搬动操作 move (x, n, z) 可定义为:
      //   (c是初值为0的全局变量,对搬动计数)
      //   printf("%i. Move disk %i from  %c  to  %c\n", ++c, n, x, z);
    
    1
    2  if (n==1)
    3    move(x, 1, z);        //将编号为1的圆盘从x移到z
    4  else {
    5    hanoi(n-1,x,z,y);
    6    move(x, n, z);        //将编号为n的圆盘从x移到z
    7    hanoi(n-1, y, x, z);  //将y上编号为1至n-1的圆盘移到z,x作辅助塔
    8  }
    9}


    下面分析下代码和过程:

    首先说明下,递归代码是非常巧妙的,基本上大家知道这个程序就可以了,考研的学生知道下原理,然后背下来,这个东西一般人是写不出的。

    下面来说明下思路,这个算法的巧妙之处在于他用了几行的代码实现了Hanoi塔(感觉是废话)。

    1.在第五步时,递归工作栈状态为 8,1,c,a,b

    这个8是返回第八行,1,是第一块行,c,a,b,是把c移到b,并且a为辅助,那么为什么是1,c,a,b,这个1是因为第二块圆盘第6步执行完成后,第5部的时候第二块圆盘把x,z,y(也就是a,c,b)给了hanoi的参数,这样的话x=a,y=c,z=b,在第7步时就是c,a,b了。


    2.在第五部里面,有move(x,1,z)这时,改变下次参数就是move(c,1,b)意思是把圆盘1从c移到b。


    整个hanoi的代码上难点就在这,基本上这个大家理解下思路,会了这个思路过程就可以了。

    展开全文
  • 前言:  栈还有一个总要应用是在程序设计语言中... 3、栈与递归的实现  4、队列  5、离散事件模型 正文:  3、栈与递归的实现  递归程序设计是一个强有力的工具。  1)很多数学函数是递归调用的  ...

    前言:

      栈还有一个总要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数。

     

    目录:

      1、栈

      2、栈的应用举例

      3、栈与递归的实现

      4、队列

      5、离散事件模型

     

    正文:

      3、栈与递归的实现

        递归程序设计是一个强有力的工具。

        1)很多数学函数是递归调用的

          阶乘:    Fact(n)=n * (n-1) * (n-2) * ...... * 2 * 1

          斐波那契数列、阿克曼函数 等

     

        2)有的数据结构,如二叉树、广义表等,由于数据结构本身固有的递归特性,则他们的操作可递归的描述。

        

        3)还有一类,虽然本身没有明显的递归结构,但用递归求解会更加简单,以 hanoi 汉诺塔 为例。

      

     

      代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #include <string.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    //Status是函数的类型,其值是函数结果状态码
    typedef int Status;
    typedef int SElemType;
    //typedef char SElemType;
    
    typedef struct {
        SElemType * base;
        SElemType * top;
        int stacksize;
    }SqStack;
    
    //构造空栈
    Status InitStack(SqStack &S){
        S.base=(SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
        if(!S.base) exit(OVERFLOW);
        S.top=S.base;
        S.stacksize=STACK_INIT_SIZE;
        return OK;
    }
    
    //插入元素 (入栈)
    Status Push(SqStack &S,SElemType e){
        if((S.top-S.base)==S.stacksize){                                        //空间不够,继续分配空间
            S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
            if(!S.base) exit(OVERFLOW);
            S.top=S.base+S.stacksize;
            S.stacksize+=STACKINCREMENT;
        }
        *S.top++=e;
        return OK;
    }
    
    //删除元素(出栈)
    Status Pop(SqStack &S,SElemType &e){
        if(S.top!=S.base){
            e=*(--S.top);
        }else{
            return ERROR;
        }
        return OK;
    }
    
    
    
    void printAllValues(SqStack &S){
        SElemType * q=S.top;
        printf("top:%p\n",q);
        while(q!=S.base){
            printf("地址:%p,",q-1);
            printf("值:%d\n",*(q-1));
            //printf("值:%c\n",*(q-1));
            q--;
        }
        printf("base:%p\n",S.base);
    }
    
    //gettop获取栈顶元素
    SElemType GetTop(SqStack &S){
        if(S.base==S.top){
            return 0;
        }
        return *(S.top-1);
    }
    
    
    
    //初始化 汉诺塔 X
    void HanoiInit(int n,SqStack &X){
        for(int i=1;i<=n;n--)
            Push(X,n);
    }
    
    //将元素 e 从栈 A 删除 ,插入到栈 B 上。
    void move(SqStack &A,int e,SqStack &B){
        if(GetTop(A)==e){
            SElemType c;
            Pop(A,c);
            Push(B,e);            
        }        
    }
    
    int MoveNum=0;
    
    //将汉诺塔 X 上的 N 个元素 按照同样的顺序 放到 塔 Z上。
    void Hanoi(int n,SqStack &X,SqStack &Y,SqStack &Z){    
        if(n==1){
            move(X,n,Z);                    //从X 柱 往 Y 柱 移动元素 n ,
            MoveNum++;
        }else{
            Hanoi(n-1,X,Z,Y);
            move(X,n,Z);
            MoveNum++;
            Hanoi(n-1,Y,X,Z);
        }
        
    }
    
    
    void main(){
        SqStack X;
        InitStack(X);
    
        SqStack Y;
        InitStack(Y);
    
        SqStack Z;
        InitStack(Z);
    
        int n=5;
        HanoiInit(n,X);
        printf("%s\n","X柱:");
        printAllValues(X);
    
        printf("%s\n","Y柱:");
        printAllValues(Y);
    
        printf("%s\n","Z柱:");
        printAllValues(Z);
        
        printf("\n%s\n\n","调用Hanoi 函数之后:");
    
        Hanoi(5,X,Y,Z);
    
        printf("%s\n","X柱:");
        printAllValues(X);
    
        printf("%s\n","Y柱:");
        printAllValues(Y);
    
        printf("%s\n","Z柱:");
        printAllValues(Z);
    
        printf("汉诺塔上的元素共移动:%d次\n",MoveNum);
    
    }

    运行结果:

      

     

    转载于:https://www.cnblogs.com/ahguSH/p/6202537.html

    展开全文
  • 栈与递归程序中“函数调用栈”是栈数据结构一种应用。函数调用栈一般是从高地址向低地址增长,栈底为内存高地址处,栈顶为内存低地址处。函数调用栈中存储数据为活动记录。活动记录是函数调用时一系列...

    栈与递归
    程序中的“函数调用栈”是栈数据结构的一种应用。
    函数调用栈一般是从高地址向低地址增长的,栈底为内存的高地址处,栈顶为内存的低地址处。
    函数调用栈中存储的数据为活动记录。活动记录是函数调用时一系列相关信息的记录。

    函数调用过程:

    程序中的栈空间可看做一个顺序栈的应用。
    栈保存了一个函数调用所需的维护信息:
    1.函数参数,函数返回地址;
    2.局部变量;
    3.函数调用上下文。
    什么是程序的栈溢出?

    在不断的压栈过程中造成栈空间耗尽而产生栈溢出。
    栈溢出常由于函数递归过深或局部数组过大造成。

    总结:

    1.程序栈空间在本质上是一种顺序栈;
    2.
    程序栈空间的访问是通过函数调用进行的;
    3.
    程序栈空间仍然遵从后进先出的规则。 

    递归的数学思想
    递归是一种数学上分而自治的思想。
    递归将大型复杂问题转化为与原问题相同但规模较小的问题进行处理。
    递归需要有边界条件:

    1.    当边界条件不满足时,递归继续进行;

    2.    当边界条件满足时,递归停止。

    用递归解决问题首先要建立递归的模型,下面就作重介绍介个递归的应用实例。

    1. 斐波拉契数列递归解法

    斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........

    这个数列从第3项开始,每一项都等于前两项之和。所以可以归纳成如下的递归模型。

    F(N)  = 0   (N = 0)

    F(N)  = 1   (N = 1)

    F(N)  = F(N-1) + F(N-2)   (N > 1)

    通过上面的模型可以编写如下函数:

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

    2. strlen递归解法

    strlen常规的写法是循环依次比对字符串的每一个字符,直至遇到’\0’停止,返回计数值。

    递归的写法是只要知道字符串第二个字符以后的长度就可以知道整个字符的长度,建立起的递归模型如下:strlen(str+1)+1。通过上面的模型可以编写如下函数:

    int strlen(const char* s)
    {
        if( s == NULL )
        {
            return -1;
        }
        else if( *s == '\0' )
        {
            return 0;
        }
        else
        {
            return strlen(s+1) + 1;
        }
    }

    相关代码下载地址:http://download.csdn.net/download/u014754841/10246751
    展开全文
  • // 将x上编号为1至n-1圆盘移到y,z作辅助塔(降阶递归调用) move (x,n,z); // 将编号为n圆盘从x移到z hanoi(n- 1 ,y,x,z); // 将y上编号为1至n-1圆盘移到z,x作辅助塔(降阶递归调用) } } - 算法2 ...
  •  汉诺塔问题是递归的一个典型例子,而且书上的讲解很详细,对理解C语言函数及函数传参的工作机制很有帮助,值得一看。而且,递归在我看来和分治、DP、贪心等一样是十分优美的思想,值得学习!!!  二.CPP文件 ...
  • 函数中有直接或间接地调用自身函数语句,这样函数称为递归函数。递归函数用 得好,可简化编程工作。但函数自己调用自己,有可能造成死循环。为了避免死循环,要 做到两点: (1) 降阶。递归函数虽然调用自身,...
  • 还有一个重要的应用时在程序设计语言中实现递归。 一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数,称作递归函数。   递归是程序设计中的一个强有力的工具。 其一:有许多数学函数式递归的,...
  • 是有"先进后出"原则,而嵌套函数也一样有一个原则是:"后调用先返回" 这就和栈的进出相符合了.这里拿Hanoi塔问题来分析(不画图了,要看图翻 数据结构那本书看下) //下面是算法./**************n阶Hanoi塔...
  • 定义是递归的 //阶乘的函数定义 long Fact(int n) { if(n==1) return 1; else return n*Fact(n-1); } 对于一类复杂的问题,能够分解成几个相对简单,解法相同或类似的子问题来求解,便称为递归求解。 这种分解-...
  • 栈与递归

    2021-04-11 11:54:16
    3.4 栈与递归 栈是一个重要应用是在程序设计语言中实现递归。递归是算法设计中最常用手段,它通常将一个大型复杂问题描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更容易设计,尤其是当问题本身或所...
  • 12、数据结构笔记之十二栈的应用之栈与递归之阶乘实现  :“人生的价值,应当看他贡献什么,而不应当看他取得什么。”  本篇学习关于栈和递归的应用。 1. 阶乘 一个正整数的阶乘(英语:factorial)是所有...
  • 递归的精妙之处不在于它能用少量的代码来实现十分复杂的功能,而在于它能表达出“分形”结构。 在数学上的分形我就不展开说了,在编程上的分形简单来说,就是想像一个任务由许许多多工人完成,他们只会机械的做事,...
  • 为什么要学习递归递归的转换的实现方法?1)并不是每一门语言都支持递归的.2)有助于理解递归的本质.3)有助于理解,树等数据结构.二.递归非递归转换的原理.递归递归的转换基于以下的原理:所有的递归程序都...
  • 迷宫问题求解 在学习了数据结构的栈和队列相关知识以后,我接触到了栈的一些应用,其中迷宫问题就是一种栈的应用。
  • 3.3栈与递归实现 3.3.1递归的定义 栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称为递归函数。其中直接调用自己的函数称为直接递归。间接调用自...
  • 栈与递归实现Hanoi塔问题

    千次阅读 2015-09-22 16:23:02
    1、用递归方法实现Hanoi问题源代码 //将塔座x上按直径大小由小到大排为1——n,要求将塔座x上n个圆盘搬至z塔座,可以以y为辅助塔 #include "stdio.h" #include "stdafx.h" #include "stdlib.h" int c = 0; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,694
精华内容 677
关键字:

栈与递归的实现