Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

用递归来解决汉诺塔问题的优缺点

  1. User

    用递归来解决汉诺塔问题的优缺点

  2. Assistant

    优点:

    1. 实现简单。用递归来解决汉诺塔问题非常简单,代码少,容易理解。
    2. 直观易懂。使用递归来解决汉诺塔问题可以直观地表现出其本质:移动盘子朝目标位置,然后移动其他盘子到目标位置的过程。

    缺点:

    1. 存在大量重复计算。递归算法的缺点之一是调用相同的函数多次,这会导致大量的重复计算,从而降低效率。
    2. 数据量大时可能会导致栈溢出。由于递归算法依赖于函数的堆栈,数据集太大时可能会导致堆栈溢出。
  3. User

    2.2 设盘子的移动次数为H(n)。汉诺塔问题的递归表达式: H⑴ = 1 H(n) = 2*H(n-1)+1 (n>1) 那么就能得到H(n)的一般式: H(n) = 2^n - 1 (n>0) 根据一般式,可以不使用递归,就能得到盘子的移动次数。 请根据这一现象,分析递归方法的优缺点。

  4. Assistant

    优点:

    1. 理解简单。递归方法的优点之一是能够通过简单的逻辑和表达式来实现问题的求解,可以减少代码量和实现难度。
    2. 直观易懂。递归方法可以非常直观地表达问题的求解过程,使得代码易于理解和维护。

    缺点:

    1. 存在大量重复计算。递归算法的缺点之一是调用相同的函数多次,这会导致大量的重复计算,从而降低效率。
    2. 可能会导致栈溢出。由于递归算法依赖于函数的堆栈,数据集太大时可能会导致堆栈溢出,从而使程序错误结束。特别地,在递归程序没有尾递归时,栈溢出的风险更大。
    3. 在某些情况下可能效率较低。递归调用的开销相较于迭代来说较大,在大数据集的情况下,可能造成效率低下,进而导致运行时间特别长。
  5. User

    2.3 请比较递归与迭代两种方法,包括控制结构,终止测试,计算代价,程序直观度。

  6. Assistant

    控制结构:

    • 递归:函数自身调用,需要使用条件判断语句限制递归深度,以防止无限递归
    • 迭代:通过循环结构来实现

    终止测试:

    • 递归:需要设定好递归终止条件,否则可能会出现无限递归的情况。
    • 迭代:通常使用计数器控制循环次数或者使用条件判断语句停止循环。

    计算代价:

    • 递归:相较于迭代计算代价较高,因为每一次递归都需要保存函数的返回值、参数、局部变量等信息,所需系统资源较大。
    • 迭代:计算代价浅,因为每次循环仅需要保存计数器的值和变量的值等少量信息。

    程序直观度:

    • 递归:递归方法可以非常直观地表达问题的求解过程,使得代码易于理解和维护。
    • 迭代:使用迭代方法的代码结构更加简单和清晰,因为它不包含递归方法的多层调用。
  7. User

    程序3:

    #include <stdio.h>

    void Swap(int a, int b);

    int main()

    {

    int a, b;
    
    printf("Input a, b:");
    
    scanf("%d %d", &a, &b);
    
    Swap(a, b); 
    
    printf("In main():a = %d, b = %d\n", a, b);
    
    return 0;
    

    }

    void Swap(int a, int b)

    {

    int temp;
    
    temp = a;
    
    a = b;
    
    b = temp;
    
    printf("In Swap():a = %d, b = %d\n", a, b);
    

    }

  8. Assistant

    程序运行结果:

    Input a, b:3 5

    In Swap():a = 5, b = 3

    In main():a = 3, b = 5

    对于这个程序来说,正常人的预期可能是输入两个数 a 和 b,并将其交换后输出。但是,实际运行结果与预期不符,输出了错误的结果。

    原因在于函数Swap()中的形参 a 和 b 仅仅是临时变量,函数操作的是它们的副本,而不是实参 main() 中的 a 和 b。因此,Swap() 函数并没有真正实现变量交换的目的,而只是在函数内部交换了两个副本的值。

    要实现变量交换,可以使用指针或者引用参数的方式,将变量的地址传递进函数,通过指针或者引用来修改实参的值。

  9. User

    步骤   变量a的值 变量b的值 1 main函数(调用swap前)     2 swap函数(return语句之前)     3 main函数(调用swap后)

  10. Assistant

    步骤 变量a的值 变量b的值 1 3 5 2 3 5 3 3 5

  11. User

    请你编写一个新的swap函数,要求使用传递变量地址的方法,实现对main函数中a,b值的交换。

  12. Assistant

    可以使用指针参数的方式来传递变量的地址,通过指针访问变量的值,实现变量交换的目的。新的Swap()函数代码如下所示:

    void Swap(int* a, int* b)
    {
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    

    在主函数中调用Swap()函数时,传递变量a和b的地址即可。代码如下所示:

    int a, b;
    printf("Input a, b:");
    scanf("%d %d", &a, &b);
    Swap(&a, &b);
    printf("In main():a = %d, b = %d\n", a, b);
    

    运行程序,输入两个数a和b,程序会交换其值并输出。

  13. User

    程序1是一个字符串反向的递归函数,请将该函数填写完整,回答下列问题。

    程序1:

    revstr ( char * s )

    { char *p = s, c;

    while (【1】 )

     p++;
    

    【2】;

    if ( s < p )

    { c = *s;

     【3】;   
    
     【4】 = ’\0’;
    
     revstr(s+1);
    
    【5】;    
    

    }

    }

  14. Assistant

    程序1已经定义好了递归函数revstr的框架,缺失的部分需要补充。补充后完整的程序如下所示:

    void revstr(char* s)
    {
        char* p = s, c;
        while (*p != '\0') // 如果p所指向的字符不是字符串的结尾符'\0',就继续向后移动指针p
            p++;
        p--; // 将指针p回退到字符串末尾的前一个字符
        if (s < p) // 如果指针s所指向的字符不是指针p所指向的字符的后面那个字符,说明还有多个字符,需要继续反转
        {
            c = *s;
            *s = *p; // 交换s所指向的字符和p所指向的字符
            *p = c;
            s++; // s指向下一个字符
            p--; // p指向前一个字符
            revstr(s); // 继续进行递归
        }
    }
    

    解释如下:

    • 在while循环中,指针p不断向后移动,直到指向了字符串的末尾符号'\0'之前的一个字符。
    • p--将指针p回退到字符串末尾的前一个字符。
    • if判断条件:如果指针s所指向的字符不是指针p所指向的字符的后面那个字符,说明还有多个字符,需要继续反转。如果指向了相同字符或者s在p的后面,则递归结束。
    • c保存了原来s所指向的字符。
    • 通过*s=*p和*p=c交换s所指向的字符和p所指向的字符。
    • s++将指针s移动到下一个字符的位置。
    • p--将指针p移动到前一个字符的位置。这时,s和p之间的所有字符都已经反转完毕。
    • 继续进行递归,对剩下的字符执行相同的操作。
  15. User

    这个函数的形式参数是               数据类型是     ,实际调用时实际的调用参数是           ,数据类型是                  ,实际调用参数与形式参数的类型一致吗?

  16. Assistant

    这个函数的形式参数是 char* s,数据类型是指向 char 类型的指针。

    实际调用时,实际的调用参数是字符串的名称或其首元素的地址,数据类型也是指向 char 类型的指针。

    实际调用参数与形式参数的数据类型一致,都是指向 char 类型的指针,因此类型一致。

  17. User

    程序只是一个片段,请你写出完整的主程序。

  18. Assistant

    由于只给出了函数的代码片段,没有说明程序的具体功能,因此无法给出完整的主程序。但是,可以给出一个常见的主程序框架,供参考:

    #include <stdio.h>
    
    void revstr(char* s);
    
    int main()
    {
        char str[100];
        printf("Enter a string: ");
        scanf("%s", str);
        revstr(str);
        printf("Reversed string: %s\n", str);
        return 0;
    }
    

    这个主程序包括了一个调用revstr()函数的框架,可以输入一个字符串,调用revstr()函数对其进行反转,输出反转后的字符串。具体实现需要将revstr()函数加入到这个程序中,并对输入和输出进行适当的调整。

  19. User

    str[2]的值是                      (若不存在,请填写不存在) *str[2]的值是                     (若不存在,请填写不存在) *(str[2]的值是                     (若不存在,请填写不存在) str[2][0]的值是                      (若不存在,请填写不存在)

  20. Assistant
    • str[2]表示字符串数组中第3个元素,即一个字符串,因此str[2]的值是该字符串的首字符地址。
    • *str[2]表示字符串数组中第3个元素的首字符,因为数组名str是指向数组首元素的指针,因此*str[2]实际上等价于str[2][0],表示该字符串的首字符,值为一个字符。
    • *(str[2])等价于str[2][0],表示该字符串的首字符,值也为一个字符。
    • str[2][0]表示字符串数组中第3个元素的第1个字符,即该字符串的首字符,因此str[2][0]的值是一个字符。
  21. User

    程序2:

    char *str[5]={“AAA”,”BBB”,”CCC”,”DDD”,”EEE”};

    str[2]的值是 (若不存在,请填写不存在)

    *str[2]的值是 (若不存在,请填写不存在)

    *(str[2])的值是 (若不存在,请填写不存在)

    str[2][0]的值是 (若不存在,请填写不存在)

  22. Assistant
    • str[2]表示字符串数组中第3个元素,值是字符串 "CCC" 的地址。
    • *str[2]等价于str[2][0],表示该字符串的首字符,值是字符 'C'。
    • *(str[2])等价于str[2][0],表示该字符串的首字符,值是字符 'C'。
    • str[2][0]表示该字符串的首字符,值是字符 'C'。