C语言练习5：这些使用递归解决的经典问题

NC68：跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

解题：

递归思想：来到5级有两种方法——从4级一步到5级 或 从3级两步到5级
其中，到4级又有两种方法，3级也是
可以套用同样的函数，返回的是两种方法之和

程序：

/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
   
    if(number < 3){
   
        return number;
    }else{
   
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
}

NC527：最少素数拆分

现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。

解题：
为了更好的理解题目，我们可以先尝试对数据进行拆分，拆分数量尽可能的少，寻找规律

1. 其中质数所得到的拆分数都是1，比如7、11、13等等；
2. 对于哥德巴赫猜想可知任意大于2的偶数都可以拆分成两个质数之和，比如4、6、8、10等等；
3. 对于非质数的奇数，我们可以看一下前两位是不是质数，如果是就能拆分成两位，即 2+前面的数；
4. 如果上述条件都不符合，就只能拆分出三个质数的和，比如图中数字27

程序：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 判断给定的正整数最少能表示成多少个素数的和
 * @param N int整型 给定的正整数
 * @return int整型
 */
#include <stdbool.h>

// 判断该数是否为质数
bool Prime(int x){
   
    if(x==1) return false;
    if(x==2) return true;
    for(int i=2;i<=sqrt(x);++i){
   
        if(x%i == 0) return false;
    }
    return true;
}

int MinPrimeSum(int N ) {
   
    if(Prime(N)) return 1;          // 如果本身是质数，则本身就可以作为拆分源
    if(N%2==0 || Prime(N-2)) return 2;       // 能被2整除或者向前两位是质数，都能拆分两个
    return 3;        // 剩下的都是三个
}

这个题不是典型的递归题，只是函数的嵌套
本题要清楚几种判定情况
判断素数时，大于sqrt(x)的不用判断，避免重复判断的计算