C++知识点总结(30)：递归进阶练习

一、$2$ 的幂数

1. 审题

如果这个整数是由若干个 $2$ 相乘得到的，那我们称它为 $2$ 的幂数。给你一个整数 $n$，请你判断该整数是否是 $2$ 的幂数。如果是，输出 $Y$ ；否则，输出 $N$。用 递归 和 循环 两种方法解决这个问题。

2. 参考答案

2.1 递归

#include <iostream>
#include <cstdio>
using namespace std;

double n;

bool isNum2(double n)
{
    if (n <= 0.0) return false;
    if (n == 1.0) return true;
    return isNum2(n / 2.0);
}

int main()
{
    freopen("num2.in", "r", stdin);
    freopen("num2.out", "w", stdout);
    
    cin >> n;
    cout << (isNum2(n) ? "Y" : "N");
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2.2 循环

#include <iostream>
#include <cstdio>
using namespace std;

double n;

int main()
{
    freopen("num2.in", "r", stdin);
    freopen("num2.out", "w", stdout);
    
    cin >> n;
    if (n == 1.0)
    {
        cout << "Y";
        return 0;
    }
    if (n <= 0.0)
    {
        cout << "N";
        return 0;
    }
    while (n)
    {
        n /= 2.0;
        if (n == 1)
        {
            cout << "Y";
            return 0;
        }
    }
    
    cout << "N";
    fclose(stdin);
    fclose(stdout);
    return 0;
}

二、汉诺塔移动次数

1. 审题

三根柱子 $A$，$B$，$C$ 的汉诺塔，最左侧 $A$ 共有 $n$ 个从小到大依次垒好的圆盘，请问按照汉诺塔的规则，将这些圆盘从最左侧 $A$ 柱移动到最右侧 $C$ 柱，一共需要移动多少次圆盘？

2. 思路

我们可以代入 教程 二、 中所写的程序，反推出最小移动次数为 $2^n-1$。我们可以直接输出。

而这个推出的公式原理是什么呢？最后还是回到我们发现的规律：

• 【打开冰箱】
  将上方的 $n-1$ 个盘子从 $A$ 柱（起始柱）移动到 $B$ 柱（临时柱）。借助 $C$ 柱作为辅助柱。
• 【放进大象】
  将最大的第 $n$ 个盘子从 $A$ 柱（起始柱）移动到 $C$ 柱。
• 【关上冰箱】
  将 $B$ 柱（临时柱）上的 $n-1$ 个盘子移动到 $C$ 柱（终点柱）。借助 $A$ 柱作为辅助柱。

那么我们可以推导出下面两个公式：
$$f(n)=f(n-1)+1+f(n-1)=2\times f(n-1)+1$$
$$f(n)=2^n-1$$

3. 参考答案

递归法

#include <iostream>
using namespace std;

int n;

int f(int x)
{
    if (x == 1) return 1;
    return 2 * f(x-1) + 1;
}

int main()
{
    cin >> n;
    cout << f(n);
    return 0;
}

公式法

#include <iostream>
#include <cmath>
using namespace std;

int n;

int main()
{
    cin >> n;
    cout << pow(2, n) - 1;
    return 0;
}

三、数字乘积分解

1. 审题

一个正整数，可以分解成多个大于 $1$ 的整数的乘积的形式，要求这些数字从左向右是不增的（即后一个数小于等于前一个数）。请你求出对于一个整数 $n$，请你按字典序从大到小输出所有的方案。

2. 参考答案

#include <iostream>
using namespace std;

int n;
int a[55];

void dfs(int x, int pos)
{
    if (x == 1)
    {
        cout << a[1];
        for (int i = 2; i <= pos-1; i++)
        {
            cout << "*" << a[i];
        }
        cout << endl;
        return;
    }
    for (int i = min(x, a[pos-1]); i >= 2; i--)
    {
    	if (x % i == 0)
        {
        	a[pos] = i;
        	dfs(x/i, pos+1);
        }
    }
}

int main()
{
    cin >> n;
    a[0] = n;
    dfs(n, 1);
    return 0;
}

四、数字重复分解

1. 审题

一个正整数，对它取数位之后相加，例如 $49$ 取数位相加 $4+9=13$，如果结果不是一位数，继续取数位相加，$13$ 取数位相加 $1+3=4$，直到结果是一位数为止。给你一个整数 $n$，求它不断取数位相加后的结果，要求使用递归的方法解答。

2. 参考答案

#include <iostream>
using namespace std;

int n;

int add(int x)
{
    if (x <= 9) return x;
    int num = x;
    int sum = 0;
    while (num)
    {
        sum += num % 10;
        num /= 10;
    }
    return add(sum);
}

int main()
{
    cin >> n;
    cout << add(n);
    return 0;
}

五、烤鸡调料

1. 审题

小明特别喜欢吃烤鸡，而且吃法很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克。烤鸡的美味程度为所有配料的重量之和。现在， 小明想要知道，如果它想让烤鸡的美味程度为 $n$，那么这 $10$ 种配料共有多少种放法。

2. 参考答案

#include <iostream>
using namespace std;

int n;
int cnt;
int temp[35];

void dfs(int step, int sum)
{
    if (step > 10)
    {
        if (sum == n)
        {
            cnt++;
        }
        return;
    }
    for (int i = 1; i <= 3; i++)
    {
        temp[step] = i;
        dfs(step + 1, sum + i);
    }
}

int main()
{
    cin >> n;
    dfs(1, 0);
    cout << cnt;
    return 0;
}