• 周二. 10 月 8th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

C++递归之汉诺塔

admin

11 月 28, 2021

  简单来说,递归就是程序不断调用自身的一种方法。构成递归当然是有条件的,条件1:子问题需要与原问题是同一件事,而且要更加简单了。条件2:调用不能无限制,必须有一个终止条件。

  在数学和计算机科学中,递归指的是由一种简单的基本情况定义的一类对象或者方法,并规定其他所有情况都能被还原为基本情况。

  典型的递归问题有《斐波那契数列》《汉诺塔》《上楼梯》等,这次随笔记录汉诺塔问题。

  既然是原问题分解成子问题,我们需要从最小的问题开始看。

  汉诺塔的由来就不再赘述,假设有A,B,C三根柱子。那么如果有1块饼,简单!一次就到位了。

  2块饼的时候,从下往上定为cake[0]、cake[1]。那么cake[1]先到B柱,cake[0]到C柱,cake[1]再到C柱,完成。

  3块饼的时候,我们不难发现所有的操作其实都归结到了两块饼的操作上(如果有图示会更加明确)由此我们可以推断出f(n) = 2 * f(n) + 1这样一个递归公式来。还要补充当n = 1时,f(n) = 1。

//
//  main.cpp
//  HanoTower
//
//  Created by MadMarical on 15/11/23.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>

using namespace std;

int count(int n)
{
    int cnt;
    if (n == 1)
    {
        cnt = 1;
    }
    else
    {
        cnt = 2 * count(n - 1) + 1;
    }

    return cnt;
}

int main(int argc, const char * argv[])
{
    int n;
    cin>>n;
    int ans = count(n);
    cout<<ans<<endl;
    return 0;
}

反思:

1.递归思想在程序运用中特别重要,明确开始和结尾就是递归的核心部分。

2.递归并非绝佳的解决方式。不要盲目的选择递归。

发表回复