Polaris6G's blog

Stay humble,stay hungry.

0%

蓝桥杯-2

Posted on Valine:

学习递推、递归

递推

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int a[1010]={0,1,1};//初始化前几项
int main()
{
	int n;
	cin>>n;
	for(int i=3;i<=n;++i){
		a[i]=a[i-1]+a[i-2];//递推
	}
	printf("%d\n",a[n]);
	return 0;
}

走楼梯问题

共有n阶台阶，上楼一步1、2、3阶，计算有几种走法。

输入样例：

1
2
3
4
5
6
7
8
9
1

2

3

4

0

输出样例

1
2
3
4
5
6
7
1

2

4

7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
long long d[110]={0};
int a;
int main(){
    d[1]=1;
    d[2]=2;
    d[3]=4;//初始化3种基本情况
    for(int i=4;i<=n;i++){
        d[i]=d[i-1]+d[i-2]+d[i-3];//递推式
        while(scanf("%d",&a)==l&&a)
            printf("%lld\n",d[a]);
    }
    return 0;
}

递推基本方式：

  • 找出基本子情况
  • 寻找出递推式

位数问题

在所有的N位数中，有多少个数中有偶数个数字3？结果可能很大，需要输出这个答案对12345取余的值。

数塔问题

](蓝桥杯-2/Screenshot_20220117_135426_com.chaoxing.mobile_ed.jpg)

跳马问题

递归

递归模型

1
2
fun(1) = 1 //递归出口
fun(n) = x * fun(n-1) //递归体
1
2
3
4
5
6
int fun(int n){
	if(n==1)
        return(1);
    else
        return (fun(n-1)*n);
}

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int a[11];//数列由小到大 
void search(int x,int bot,int top){
	int mid;
	if(bot <= top){
		mid=(top+bot)/2;
		if(x==a[mid])cout<<"Yes"<<endl;
		else if(x<a[mid])search(x,bot,mid-1);
		else search(x,mid+1,top);
	}
	else cout<<"no"<<endl
	return;
}

输出数字

输入一个大于零的十进制数n的个数字位，如n =123，输出各数字为123。

1
2
f(n) -> 不做任何事 当n=0时
f(n) -> f(n/10); 输入n%10 其他情况
1
2
3
4
5
6
void digits(int n){
	if(n!=0){
        digits(n/10);
        printf("%d",n%10);
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
void SelectSort(int a[],int n,int i){//对a[i..n-1]个元素增值排序
	int j,k;
    if(i==n-1)return;
    else{
        k=i;
        for(j=i+1;j<n;j++)
            if(a[j]<a[k])k=j;
        if(k!=i)swap(a[i],a[k]);
    }
    SelectSort(a,n,i+1);
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(int a[],int n,int i){
	int j;
    bool exchange;
    if(i==n-1)return;
    else{
        exchange=false;
        for(j=n-1;j>i;j--)
            if(a[j]<a[j-1]){
                swap(a[j],a[j-1]);
                exchange=true;
            }
        if(exchange==false)
            return;
        else BubbleSort(a,n,i+1);
    }
}

n皇后问题

汉诺塔问题

求最大公因数gcd

1
2
3
4
int gcd(int m,int n){
	if(m<n)swap(m,n);
    return (m%n==0)?n:gcd(n,m%n);
}