递归练习题

思考1.在不考虑n!溢出的情况下，编程实现阶乘问题

C++实现

比较简单，不多赘述，通过循环实现

ll fac(int n){
    ll res=1;
    for(int i=1;i<=n;i++)res*=i;
    return res;
}

子问题:求（n-1）！ 子问题合并 :n*（n-1）！

ll fac(int n){
    if(n==0)return 1;
    else return fac(n-1)*n;
}

python

from math import *
print(factorial(6))

---

习题1

题目：猴子吃桃，猴子每天吃一半多一个，第10天只剩1个，问第一天剩多少个

从最后一天开始递归，要是d=1，表示第一天，直接输出rest； 不然逆推上一天，x=x-1，rest=(rest+1)*2

C++实现

#include
using namespace std;
int f(int d,int rest){
    return ( d==1 ? rest : f(d-1,(rest+1)*2));
}
int main(){
    cout<<f(10,1);
    return 0;
}

python

def f(d,rest):
    if d==1 :
        return rest
    else :
        return f(d-1,(rest+1)*2)
print(f(10,1))

---

习题二

题目：三齿轮问题。三个齿轮，齿数分别为a,b,c，问各自转多少圈后，这两对齿重逢

说实话没咋看懂题目，但根据题目样例应该是输出lcm(本身gcd就递归实现的)

C++

#include
using namespace std;
int gcd(int a,int b){
    return !b ? a : gcd(b,a%b);
}
int main(){
    int a,b,c;cin>>a>>b>>c;
    cout<gcd(b,c)<<' ';
    cout<gcd(a,c)<<' ';
    cout<gcd(b,a)<<' ';
    // C++自带gcd: __gcd()
    return 0;
}

python

python math中带有lcm，gcd

from math import *
a,b,c=3,4,5
print(lcm(c,b),lcm(c,a),lcm(a,b))

---

习题三

题目：输入一个n（n\leqslant2000000000）求它的分解式总数（Eg.12 ---- 8）

此题如果规模扩大，应该要用pollard rho，这里直接分解 可以得到递归公式f(x)=1+\sum_{t_i}^{t_i为

C++

下面用了 miller_rabin判断素数，因为有模板，直接贴了 或者存个质数的表，二分查找判素也行

#include
#define ll long long
using namespace std;
ll cnt=0,fac[10010];
ll qpow(ll x,ll n,ll p) {
    ll res=1;
    while(n){
        if(n&1)res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res;
}
bool query(ll p) {
    int test[10]={2,3,5,7,11,13,17};
    if(p==1)return 0;
    ll t=p-1,k=0;
    while(!(t&1))k++,t>>=1;
    for(int i=0;i<4;i++){
        if(p==test[i])return 1;
        ll a=qpow(test[i],t,p),nxt=a;
        for(int j=1;j<=k;j++){
            nxt=(a*a)%p;
            if(nxt==1 && a!=1 && a!=p-1) return 0;
            a=nxt;
        }
        if(a!=1) return 0;
    }
    return 1;
}
ll f(ll x){
    if(query(x) || x==1)return 1;
    else {
        ll res=0;
        for(int i=0;i
            if(x%fac[i]==0)res+=f(x/fac[i]);
        }
        res+=1;
        return res;
    }
}
int main(){
    ll x;cin>>x;
    for(int i=2;i*2<=x;i++){
        if(x%i==0)fac[cnt++]=i;
    }
    cout<<f(x);
    return 0;
}

python

from Crypto.Util.number import *
def f(x):
    if isPrime(x) | x==1 :
        return 1
    else :
        res=0;
        for i in range(len(fac)):
            if fac[i]>=x :
                break
            if x%fac[i]==0 :
                res+=f(x//fac[i])
        res+=1;
        return res;
​
fac=[]
x=12
for i in range(2,x//2+1) :
    if x%i==0 :
        fac.append(i)
print(f(x))

---

习题四

题目：有重复元素的排列问题，输出有重复元素集合的排列

next_permutation yyds bool next_permutation(iterator start,iterator end) next_permutation会把调整序列改为下一个字典序

C++

#include
using namespace std;
int main(){
    string s("abcb");
    sort(s.begin(),s.end());
    do{
        for(int i=0;isize();i++)cout<' ';
        cout<
    }while(next_permutation(s.begin(),s.end()));
    return 0;
}

---

习题五

题目：求一个集合的全部子集

运用二进制数模拟子集的每个位置上的数是否取出

C++

#include
using namespace std;
int a[]={1,5,6,9};
int main(){
    for(int i=0;i<16;i++){
        int tem=i;
        for(int j=0;j<4;j++){
            if(j&1)cout<' ';
        }
        cout<
    }
    return 0;
}

---

习题六

题目：求n个数中r个数的全部组合问题

#include
using namespace std;
int n,r;
bool b[20];
void print(){
    for(int i=1;i<=n;i++)
        if(b[i])cout<' ';
    cout<
}
void dfs(int k,int p){//k表示已经标记的个数 p表示搜索到的位置
    if(k==r) print();
    else if(p>n)return;//到最后位置后的一个位置
    else {
        b[p]=true;
        dfs(k+1,p+1);
        b[p]=false;
        dfs(k,p+1);
    }
}
int main(){
    cin>>n>>r;
    dfs(0,1);
    return 0;
}

---

习题八

题目：某人上楼梯一次可以上1，2，3格，输出所有可能，总共n阶台阶

简单递归，从最后一个台阶往前，a记录每次走了几阶，step表示走了几步，rest表示还剩下几阶要走

C++

#include
using namespace std;
int a[6];
void f(int step,int rest){
    if(rest==0){
        for(int i=0;i
            cout<' ';
        cout<
    }
    else{
        for(int i=1;i<=3 && i<=rest;i++){
            a[step]=i;
            f(step+1,rest-i);
        }
    }
}
int main(){
    int n=5;
    f(0,5);
    return 0;
}

python

类似C++

a=[0]*6;
def f(step,rest) :
    if rest==0 :
        for i in range(1,step+1):
            print(a[i],end=' ')
        print()
    else :
        for i in range(1,4):
            if i>rest :
                break
            a[step+1]=i
            f(step+1,rest-i)
​
f(0,5)

---

习题九

题目：集合划分问题，将n个元素的集合划分为m个

这道题跟6思路基本相同，先用6的方法得到m-1个划分的位置的所有可能，然后按照划分位置分别输出即可

题解略

---

习题十

题目：n皇后问题（n*n棋盘)，输出所有摆放方案

$$
\begin{matrix}

0 & * & 0 \\

* & 0 & 0 \\

0 & 0 & *

\end{matrix} \tag{1}
$$

写了好多次了 懒得写了