1. 编程号首页

简单递归算法_java下一页[通俗易懂]

编程小号 • • 未分类

简单递归算法_java下一页[通俗易懂]Fibonacci数列的增长速度是惊人的

1.什么是递归：

递归就是在函数里调用函数（必须是本身），这可能有点难理解，我给你们打段代码就行了。

#include <bits/stdc++.h>
using namespace std;
int kun(int a,int b){
    if(a!=1&&b!=1){
        return kun(a%b,b);
    }
}
int main(){
    int n,m;
    cin >> n >> m;
    cout << kun(n,m);
}

这是一个基础的递归代码，求两个数的最大公因数，在函数里调用函数，是不是看起来很简单，我们来做题。

第一题

斐波列契数列（Faibonacci）0，1，1，2，3，5，8，13，21，34……求此数列第n项 。
即： Fibonacci数列是这样定义的：
F[0]=0;
F[1]=1;
F[n]=F[n-1]+F[n-2], for n>1。
Fibonacci数列的增长速度是惊人的。当n=47时,F[47]=2971215073（>2^31）。由于数列的值增长太快，对于n，你只需要输出F[n]%2147483647。

这题非常简单，直接套公式就行了，上代码

#include<bits/stdc++.h>
using namespace std;
int inf=pow(2,31)-1;
int fibo(int n){
	if(n==0){
		return 0;
	}
	if(n==1){
		return 1;
	}
	return fibo(n-1)+fibo(n-2);
}
int main(){
	int n;
	cin >> n;
	cout << fibo(n)%inf;
	return 0;
}

第二题

汉诺塔由编号为1到n大小不同的圆盘和三根柱子a,b,c组成，编号越小盘子越小。开始时，这n个圆盘由大到小依次套在a柱上，如下图所示。要求把a柱上n个圆盘按下述规则移到c柱上：

①一次只能移一个圆盘，它必须位于某个柱子的顶部；

②圆盘只能在三个柱子上存放；

③任何时刻不允许大盘压小盘。

将这n个盘子用最少移动次数从a柱移动到c柱上，输出每一步的移动方法。

简单递归算法_java下一页[通俗易懂]

输入                                                                                                           

只有一行，一个整数 n (1≤n<20),表示盘子的数量       

输出                   

 输出若干行，每一行的格式是“步数.Move 盘子编号 from 源柱 to 目标柱”数

样例输入

3

样例输出

1.Move 1 from a to c
2.Move 2 from a to b
3.Move 1 from c to b
4.Move 3 from a to c
5.Move 1 from b to a
6.Move 2 from b to c
7.Move 1 from a to c

题解：

①若n=0，则退出，即结束程序；否则继续往下执行；

②用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上，调用函数mov(n-1,start,other,target);

③将a柱上剩下的一片移到c柱上；

④用a柱作为协助过渡，将b柱上的（n-1）片移到c柱上，调用函数mov(n-1,other,target,start)。

代码

#include <bits/stdc++.h>
using namespace std;
int sum=1;
void move(int n, char a, char c, char b){//用b柱作为协助过渡，将a柱上的n片移到c柱上 
	if(n==0){
		return ;
	}//如果n=0，则退出，即结束程序 
	move(n-1,a,b,c);//用c柱作为协助过渡，将a柱上的(n-1)片移到b柱上 
	cout << sum <<"."<< "Move" << " " << n << " " << "from"<< " " << a << " " << "to" << " " << c << endl;
	sum++;
	move(n-1,b,c,a);//用a柱作为协助过渡，将b柱上的(n-1)片移到c柱上 
}
int main(){
	int n;
	cin >> n;
	move(n, 'a', 'c', 'b');
}

第三题

给出正整数 n，要求按如下方式构造数列：

  1. 只有一个数字 n 的数列是一个合法的数列。
  2. 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列a,b 不同当且仅当两数列长度不同或存在一个正整数i≤|a|，使得ai≠bi。

输入

输入只有一行一个整数，表示 n。

输出

输出一行一个整数，表示合法的数列个数。

输入样例

6

输出样例

6

样例解释

满足条件的数列为：

6
6,1
6,2
6,3
6,2,1
6,3,1
即满足要求的数为：
6
16
26
126
36
136

对于全部的测试点，保证 1≤n≤10^3。

方法1

用递归，f(n)=1+f(1)+f(2)+…+f(n/2),当n较大时会超时，时间应该为指数级

代码

#include<bits/stdc++.h>
using namespace std;
int ans;
void f(int m){//统计m所扩展出的数据个数 
	ans++;//每出现一个原数，累加器加1 
	for(int i=1;i<=m/2;i++){//左边添加不超过原数一半的自然数，作为新原数 
		f(i);
	}
}
int main(){
	int n;
	cin >> n;
	dfs(n);
	cout << ans;
	return 0;
}

方法2

记忆化搜索，实际上是对方法一的改进。设h[i]为自然数i满足题意三个条件的树的个数。如果用递归求解，会重复来求一些子问题。例如求h[4[的时候，需要先求h[1]和h[2]的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。

代码

#include<bits/stdc++.h>
using namespace std;
int h[1001];
void f(int m){
	if(h[m]!=-1){
		return;
		//说明前面已经求得h[m]的值，直接引用即可，不需要在递归 
	}
	h[m]=1;//将h[m]设置为1，表示m本身为一种情况 
	for(int i=1;i<=m/2;i++){
		f(i);
		h[m]+=h[i];
	}
}
int main(){
	int n;
	cin >> n;
	memset(h,-1,sizeof(h));//h数组初始化为-1
	f(n);//由顶到下记忆化递归求解
	cout << h[n]; 
	return 0;
}

第四题

有n（1≦n≤10^9）只奶牛将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）。这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走。如果她们再次走到三岔路口，仍有可能继续分裂成两群继续走。但奶牛分裂的方式十分古怪：

  • 如果这群奶牛可以精确地分成两部分，这两部分的牛数恰好相差 11，那么在三岔路口牛群就会分裂。
  • 否则，牛群不会分裂，她们将围在一起呆在原地吃草。

输入

输入一个整数 n（1≦n≤10^9），代表一开始有 n 只奶牛

输出

输出一个整数，代表奶牛最终会分裂成多少群

输入样例

7

输出样例

3

题解

声明一个分裂的递归函数，如果n>1，而且n是奇数，就返回分裂n/2+1和分裂n/2，否则分裂不了，就返回1。

代码

#include <bits/stdc++.h>
using namespace std;
int fenlie(int n){//n表示这群奶牛的数量 
	int a=n/2+1,b=n/2;//后面好计算 
	if(n%2==1&&n>1){//判断满足条件 
		return fenlie(a)+fenlie(b);
	}else{//不满足条件 
		return 1;
	}
}
int main(){
	int n;
	cin >> n;
	cout << fenlie(n);
}

第五题

借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

现有2^n*2^n(n≤10)名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。给出 n，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

输入

一个整数 n。

输出

2^n*2^n的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。

输入样例

3

输出样例

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

题解

本题基本思路是分治，代码可以通过递归来实现，每次递归将左上方的正方形清零，并再次递归剩余的三个正方形，当正方形的边长为2时结束递归。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[2001][2001];//a数组就是输出的那玩样
void cai(int x,int y,int z){//x,y是坐标，z是正方形大小
	if(z==0){//如果搜索到正方形大小等于零，那个位置就不被赦免
		a[x][y]=1;
		return ;
	}
   //搜索除了左上角的那一个矩阵的其他三个矩阵
	dfs(x,y+(1<<z-1),z-1);
	dfs(x+(1<<z-1),y,z-1);
	dfs(x+(1<<z-1),y+(1<<z-1),z-1);
}
int main(){
	cin>>n;
	cai(1,1,n);
   //(1<<n)=pow(2,n),但是速度飞快
	for(int i=1;i<=(1<<n);i++){
		for(int j=1;j<=(1<<n);j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	} 
	return 0;
}

题目六

科学家发现了两种病毒：K 病毒和 L 病毒。K 病毒会危害人的身体，而 L 病毒不会。一开始，病人 D 的体内只有一个 K 病毒。但是病毒是会繁殖的，每小时后一个 K 病毒会“分身术”，变成 3 个 K 病毒和一个 L 病毒，而一个 L 病毒会变成 4 个 L 病毒。

简单递归算法_java下一页[通俗易懂]

例如红色圆圈表示K病毒，蓝色圆圈表示 L 病毒。现在医生要知道，H 小时后，病毒的分布情况。

 输入

输入一个正整数H (1≤H≤10)，表示时间

输出

输出一个二维数组，表示 H 小时后 病毒的分布情况，其中用 K 表示 K 病毒， L 表示 L 病毒

输入样例1

2

输出样例1

KKKK
KLKL
KKLL
KLLL

输入样例2

4

输出样例2

KKKKKKKKKKKKKKKK
KLKLKLKLKLKLKLKL
KKLLKKLLKKLLKKLL
KLLLKLLLKLLLKLLL
KKKKLLLLKKKKLLLL
KLKLLLLLKLKLLLLL
KKLLLLLLKKLLLLLL
KLLLLLLLKLLLLLLL
KKKKKKKKLLLLLLLL
KLKLKLKLLLLLLLLL
KKLLKKLLLLLLLLLL
KLLLKLLLLLLLLLLL
KKKKLLLLLLLLLLLL
KLKLLLLLLLLLLLLL
KKLLLLLLLLLLLLLL
KLLLLLLLLLLLLLLL

这题基本上和赦免战俘一样，直接看代码

#include<iostream>
using namespace std;
const int maxlen = 1050;
bool peo[maxlen][maxlen];
void fun(int a,int x, int y){ 
	if(a==1){
		return ;
	}
	int na=a/2;
	for(int i=x+na;i<x+a;i++){
		for(int j=y+na;j<y+a;j++){
			peo[i][j]=true;
		}
	}
	fun(na,x,y+na);
	fun(na,x+na,y);
	fun(na,x,y);
}
int main(){
	int n,len;
	cin >> n;
	len=1 << n;
	fun(len,1,1);
	for(int i=1;i<=len;i++){
		for(int j=1;j<=len;j++){
			if(peo[i][j]==true){
				cout << "L";
			}else{
				cout << "K";
			}
		}
		cout << endl;
	}
	return 0;
}

题目七

有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。

输入

输入包含多个数据集。一个数据集开头行包含两个正整数W和H，W和H分别表示矩形房间的列数和行数，且都不超过20.
每个数据集有H行，其中每行包含W个字符。每个字符的含义如下所示：
‘.’——黑砖
‘#’——红砖
‘@’——男子（每个数据集仅出现一次）
两个0表示输入结束。

输出

对每个数据集，程序应该输出一行，包含男子从初始瓷砖出发可到达的瓷砖数。

输入样例

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

输出样例

45
59
6
13

这题只需要把每个点递归一次，看能不能到终点。可以设两个数组来记录上下左右走，每递归一次答案加一。

代码

#include <bits/stdc++.h>
using namespace std;
int ww,hh,H,L,nh,nl,kuai;
int a[30][30],bh[4]={0,0,1,-1},bl[4]={-1,1,0,0};
char ch;
void dfs(int h,int l){
    a[h][l]=0;
    kuai++;
    for(int i=0;i<4;i++){
        nh=h+bh[i];//现在的坐标 
        nl=l+bl[i];
        if(a[nh][nl]&&nh>=1&&nh<=hh&&nl>=1&&nl<=ww){//判断边界 
            dfs(nh,nl);//递归 
        } 
    }
}
int main(){
    while(cin >> ww >> hh && ww>0 && hh>0){
        memset(a,0,sizeof(a));
        for(int i=1;i<=hh;i++){
            for(int j=1;j<=ww;j++){
               cin>>ch;
               if(ch=='.'){//初始化 
                   a[i][j]=1;
               } 
               if(ch=='@'){
                   H=i;
                   L=j;
               }
            }
        }
        kuai=0;
        dfs(H,L); 
        cout<<kuai<<endl;
    }
    return 0;
}

今天的文章简单递归算法_java下一页[通俗易懂]分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/86696.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注