首页 / 算法 / 信息学奥赛一本通 2.4：递归算法
信息学奥赛一本通 2.4：递归算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了信息学奥赛一本通 2.4：递归算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4721字，纯文字阅读大概需要7分钟。
内容图文
斐波那契数列
#include <iostream>
using namespace std;
int f(int a) {
if (a==1 || a==2) return 1;
return f(a-2) + f(a-1);
}
int main(){
int n, a;
cin >> n;
while (n--) {
cin >> a;
cout << f(a) << endl;
}
return 0;
}
爬楼梯
#include <iostream>
using namespace std;
int f(int n) {
if (n==1 || n==2) return n;
return f(n-1) + f(n-2);
}
int main() {
int n;
while (cin >> n) {
cout << f(n) << endl;
}
return 0;
}
Pell数列
#include <iostream>
using namespace std;
const int N=1e6+5, MOD=32767;
int a[N];
int f(int x) {
if (a[x]) return a[x];
if (x == 1) a[x] = 1;
else if (x == 2) a[x] = 2;
else a[x] = (f(x-1)*2 + f(x-2)) % MOD;
return a[x];
}
int main() {
int n;
cin >> n;
while (n --) {
int k;
cin >> k;
cout << f(k) << endl;
}
return 0;
}
数的计数
#include <iostream>
using namespace std;
const int N=1005;
int a[N];
int f(int x) {
if (a[x]) return a[x];
if (x==0 || x==1) a[x] = 1;
else a[x] = f(x-2) + f(x/2);
return a[x];
}
int main() {
int n;
cin >> n;
cout << f(n);
return 0;
}
放苹果
#include <iostream>
using namespace std;
int f(int m, int n) {
if (m==0 || n==1) return 1;
if (m < n) return f(m, m);
return f(m, n-1) + f(m-n, n);
}
int main() {
int t, m, n;
cin >> t;
while (t--) {
cin >> m >> n;
cout << f(m, n) << endl;
}
return 0;
}
集合的划分
#include <iostream>
using namespace std;
long long s(int n, int k) {
if(n==k || k==1) return 1;
return k*s(n-1,k) + s(n-1,k-1);
}
int main() {
int n, k;
cin >> n >> k;
cout << s(n,k) << endl;
return 0;
}
判断元素是否存在
#include <iostream>
#include <cstdio>
using namespace std;
int x;
bool f(int k){
if(k > x) return 0;
if(k == x) return 1;
return f(2*k+1) || f(3*k+1);
}
int main() {
int k;
scanf("%d,%d",&k, &x);
if(f(k)) cout << "YES";
else cout << "NO";
return 0;
}
求最大公约数问题
#include <iostream>
using namespace std;
int gcd (int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
return 0;
}
分数求和
#include <iostream>
#include <cstdio>
using namespace std;
int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x%y);
}
int main() {
int n;
cin >> n;
int a, b, c, d;
scanf("%d/%d", &a, &b);
for (int i = 2; i <= n; i ++) {
scanf("%d/%d", &c, &d);
int fz = a*d + b*c;
int fm = b*d;
int t = gcd(fz, fm);
a = fz / t;
b = fm / t;
}
printf("%d/%d", a, b);
return 0;
}
全排列
#include <iostream>
using namespace std;
string s;
char ans[6];
bool used[6];
int len;
void dfs(int x) {
if (x == len) {
for (int i = 0; i < len; i ++) cout << ans[i];
cout << endl;
return;
}
for (int i = 0; i < len; i ++) {
if (!used[i]) {
ans[x] = s[i];
used[i] = true;
dfs(x + 1);
used[i] = false;
}
}
}
int main() {
cin >> s;
len = s.size();
dfs(0);
return 0;
}
因子分解
#include <iostream>
using namespace std;
int ans[40], len;
void f(int x) {
if (x == 1) {
cout << ans[1];
int cnt = 1;
for (int i = 2; i <= len; i ++) {
if (ans[i] == ans[i-1]) cnt ++;
else {
if (cnt == 1) cout << '*' << ans[i];
else cout << '^' << cnt << '*' << ans[i];
cnt = 1;
}
}
if (ans[len] == ans[len-1]) cout << '^' << cnt;
}
for (int i = 2; i <= x; i ++) {
if (x%i == 0) {
ans[++len] = i;
f(x/i);
break;
}
}
}
int main() {
int n;
cin >> n;
f(n);
return 0;
}
分解因数
#include <iostream>
using namespace std;
int a, cnt;
int ans[20] = {2};
void dfs(int x) {
if (a == 1) {
cnt ++;
return;
}
for (int i = ans[x-1]; i <= a; i ++) {
if (a % i == 0) {
ans[x] = i;
a /= i;
dfs(x+1);
a *= i;
}
}
}
int main() {
int n;
cin >> n;
while (n --) {
cin >> a;
cnt = 0;
dfs(1);
cout << cnt << endl;
}
return 0;
}
2的幂次方表示
#include <iostream>
using namespace std;
int a[15] = {1};
void f(int x) {
for (int i = 14; i >= 0; i --) {
if (x >= a[i]) {
if (i == 0) cout << "2(0)";
else if (i == 1) cout << "2";
else {
cout << "2(";
f(i);
cout << ")";
}
x -= a[i];
if (x > 0) cout << "+";
else return;
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= 14; i ++) a[i] = a[i-1] * 2;
f(n);
return 0;
}
逆波兰表达式
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
char s[20];
double f() {
scanf("%s", s);
if (s[0] == '+') return f() + f();
if (s[0] == '-') return f() - f();
if (s[0] == '*') return f() * f();
if (s[0] == '/') return f() / f();
return atof(s);
}
int main() {
printf("%f\n", f());
return 0;
}
汉诺塔问题
#include <iostream>
#include <cstdio>
using namespace std;
int n;
char a,b,c;
void mov(int n, char a, char b, char c) {
if (n == 0) return;
mov(n-1, a, c, b);
printf("%c->%d->%c\n", a, n, c);
mov(n-1, b, a, c);
}
int main() {
cin >> n >> a >> b >> c;
mov(n, a, c, b);
return 0;
}
扩号匹配问题
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[100],b[100];
int up (int d) {
if (d==-1) return -1;
else if (b[d]=='$') return d;
else return up(d-1);
}
int main() {
while (cin>>a) {
cout << a << endl;
int len = strlen(a);
memset(b,' ',sizeof(b));
for (int i=0;i<len;i++) {
if (a[i]=='(') b[i]='$';
else if (a[i]==')') {
int m=up(i-1);
if (m==-1) b[i]='?';
else b[m]=' ';
}
}
cout << b << endl;
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的信息学奥赛一本通 2.4：递归算法全部内容，希望文章能够帮你解决信息学奥赛一本通 2.4：递归算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】