Create Time: 10th June 2024
Title: "[[递归]]"
status: DONE
Author:
- AllenYGY
tags:
- Algorithm
- Share
- Recursion
created: 2024-06-10T18:37
updated: 2024-06-22T16:18
程序调用自身的编程技巧称为递归 Recursion
递归的能力在于用有限的语句来定义对象的无限集合。
递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。
循环:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门(若前面两扇门都一样,那么这扇门和前两扇门也一样;如果第二扇门比第一扇门小,那么这扇门也比第二扇门小,你继续打开这扇门,一直这样继续下去直到打开所有的门。但是,入口处的人始终等不到你回去告诉他答案。
1. 明确递归终止条件(递归出口)
我们知道,递归就是有去有回,既然这样,那么必然应该有一个明确的临界点,程序一旦到达了这个临界点,就不用继续往下递去而是开始实实在在的归来。换句话说,该临界点就是一种简单情境,可以防止无限递归。
2. 给出递归终止时的处理办法
我们刚刚说到,在递归的临界点存在一种简单情境,在这种简单情境下,我们应该直接给出问题的解决方案。一般地,在这种情境下,问题的解决方案是直观的、容易的。
3. 提取重复的逻辑,缩小问题规模
我们在阐述递归思想内涵时谈到,递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。从程序实现的角度而言,我们需要抽象出一个干净利落的重复的逻辑,以便使用相同的方式解决子问题。
柳州传说是歌仙刘三姐的传歌之地,最近举办了一次山歌大赛。 在这个项目中,参赛者每次完成一个段都会得到一个分数。总分数的计算方式基于一个特殊 的数学表达式 f(x,n)。表达式 f(x,n) 的定义如下:
其中,x 表示参赛者的基本得分,n 表示参赛者完成的山歌段落数。
津津、菲菲和皮皮的任务是编写一个程序,并计算选手 A(x=4.2,n=10)、选手 B(x=2.5,n=15) 时 f(x,n)的值
输入x和n。
函数值,保留两位小数。
Input
4.2 10
Output
3.68
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
double f(double x, int n){
if(n==1) return sqrt(1+x);
return sqrt(n+f(x,n-1));
}
signed main() {
double x;
int n;
cin>>x>>n;
cout<<fixed<<setprecision(2)<<f(x,n)<<endl;
return 0;
}
Hermite
多项式用递归的方法求 Hermite 多项式的值。
给定的
对给定的
Input
1 2
Output
4.00
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
double h(double x, int n){
if(n==0) return 1;
if(n==1) return 2*x;
return 2*x*h(x,n-1)-2*(n-1)*h(x,n-2);
}
signed main() {
int n;
double x;
cin>>n>>x;
cout<<fixed<<setprecision(2)<<h(x,n)<<endl;
return 0;
}
有一头母牛,从第二年起,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<55),n的含义如题目中描述。
n=0表示输入数据的结束,不做处理。
对于每个测试实例,输出在第n年的时候母牛的数量。每个输出占一行。
Input
2
4
5
0
Output
2
4
6
第n年的牛的数量为:n-1年的数量和今年新出生的牛的数量
今年新出生的牛的数量为 n-3 年前牛的数量
#include <bits/stdc++.h>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
const int MOD = 1000;
const int MAXN = 1000000;
int val[MAXN] = {0};
void solve(int x)
{
if(val[x]!=0){
cout << val[x] << endl;
return;
}
val[1]=1;
val[2]=2;
val[3]=3;
for(int i=4;i<=x;i++){
val[i]=(val[i-1]+val[i-3]);
}
cout << val[x] << endl;
}
signed main()
{
int x;
cin >> x;
while (x)
{
solve(x);
cin >> x;
}
return 0;
}