无标题文档

递归算法

1.已知数列:1 4 7 10 13 16 19 ......请输出前n项的值,每一项以空格隔开.
#include<iostream>
using namespace std;
int n;
int f(int x,int y){
        cout<<y<<" ";
	if(x>=n)return 0;
	f(x+1,y+3);
}

int main(){
	 
	cin>>n;
	 f(1,1);
	return 0;
}
作业:数列:2 5 11 23 47 95 191......的第2项为5,那么第n项为多少?

2.求1+2+3+..+n=?
方法1:
#include<iostream>
using namespace std;
 
int f(int k){
	if (k==1)return 1;
	else return f(k-1)+k;
}
int main(){int n;
        cin>>n;
	int s=f(n);
	cout<<s;
	
}
方法2:
#include<iostream>
using namespace std;
int n;
int f(int x,int s){
	if(x==n)return s;
	x=x+1;
	f(x,s+x);
}

int main(){
     cin>>n;
     int k=0;
	 k=f(0,0);
    cout<<k;
	return 0;
}

3.已知数列1,2,3,5,8,13,21,34,55,89,...求第n项的值，例如第7项为21，数列规律：从第3项开始，每一项都是相邻的前两项的和。要求0<n<100。

效率极其差的递归算法:
#include<iostream>
using namespace std;
int f(int k){

if (k==1)return 1;
        if(k==2)return 2;
        return f(k-1)+f(k-2);
}
int main(){
	 int n;
	 cin>>n;
	cout<<f(n);
        return 0;
	
}

效率高的递归算法:
#include<iostream>
using namespace std;
int n;
int f(int k,int x,int y,int z){
       //cout<<z<<" ";
	if (k==1)return 1;
        if(k==2)return 2;
        if(k>=n)return z;
        f(k+1,y,z,y+z);
}
int main(){
	 
	 cin>>n;
        if n<=2 cout<<i;else
	cout<<f(3,1,2,3);
        return 0;
	
}

4.已知数列1,1,3,1,3,5,1,3,5,7,.....例如第5项的值是3,求第n 项的值.
#include<iostream>
using namespace std;
int n;
int f(int k,int x,int y,int z){//k表示当前来到数列第k项，x表示当前项处于第x周期，y是当前项处于当前周期中的第y项，z表示当前项的值 
	// cout<<z<<" ";
	if(k==n)return z;
	
	if(x==y)f(k+1,x+1,1,1);//如果当前周期内项数已填满，则要到下一周期的第一项 
	else
	 f(k+1,x,y+1,z+2);//如果当前周期未满，则来到当前周期中的下一项 
	
}
int main(){
	 
	cin>>n;
	cout<<f(1,1,1,1);
        return 0;
	
}
作业:数列: 1 2 2 3 3 3 4 4 4 4.....求第n项的值
作业:数列: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1.....求第n项的值
作业:数列: 1 2 1 2 3 2 1 2 3 4 3 2 1 2 3 4.....求第n项的值  
5.输入一个非负的整数，输出这个数的倒序数。如输入123, 输出321。
#include<cstring>

#include<iostream>
using namespace std;
string s;
int n;
int f(int k){
	if (k<n)f(k+1);
	cout<<s[k-1];
}
int main(){
	getline(cin,s);
	n=s.length();
	f(1);
	
}
6.二分查找的递归算法：
已知n个整数，已经从小到大排列好，现在想找整数s在数列中出现的位置，如果没有输出-1.输入数据共2行，第一行为n 和s空格分开，第二行为从小到大排好的n个整数,空格隔开。 
输入:
10 23
3 5 8 16 20 23 65 89 401 854
输出:6
#include<iostream>
using namespace std;
int a[10000]={0};
int f(int l,int r,int x){
	int k=(l+r)/2;
	if(l>r)return -1;
	if(a[k]==x)return k;
	if(x<a[k])f(l,k-1,x);
	else f(k+1,r,x);
}
int main(){
	int i,n,s,t;
	scanf("%d %d",&n,&s);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	t=f(1,n,s);
	printf("%d",t);
	return 0;
}

7.
我们要求找出具有下列性质数的个数(包含输入的自然数n):
　　先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理
　　 l·不作任何处理:
　　2·茬它的左边加上一个自然数，但该自然数不能超过原数的一半;
　　3·加上数后，继续按此规则进行处理，直到不能再立生自然数为止。
样例:  输入:  6  
则满足条件的数有6个： 6  16   26 126  36  136 
输出:  6

#include<cstdio>
using namespace std;
int ans=0;
void f(int x){
ans++;
for(int i=1;i<=x/2;i++) f(i);
}
int main(){
int n;
scanf("%d",&n);
f(n);
printf("%d",ans);
return 0;
}

8.把自然数m分解为若干个自然数的和,输出每一种分法,从小到大排列.
样例:
输入:5
输出:

5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5

#include<iostream>
using namespace std;
int a[1000]={0};
int m;
int f(int k,int n){
	
	if(n==0){
		cout<<m<<"="<<a[1];
		for(int i=2;i<=k-1;i++)cout<<"+"<<a[i];
		cout<<endl;
		return 0;
	}
	if(n<a[k-1])return 0;
	for(int i=a[k-1];i<=n;i++){
       a[k]=i; 
	   f(k+1,n-i);
	}
}
int main(){
 
	cin>>m;
	a[0]=1;
	f(1,m);
	return 0;
}
作业1:把自然数m分解为若干个不同自然数的和,输出每一种分法,从小到大排列.
输入:10
输出:
10=1+2+3+4
10=1+2+7
10=1+3+6
10=1+4+5
10=1+9
10=2+3+5
10=2+8
10=3+7
10=4+6
10=10
作业2:把自然数m分解为若干个自然数的平方和,输出每一种分法,从小到大排列.
输入:9
输出:
9=1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1 
9=1*1+1*1+1*1+1*1+1*1+2*2
9=1*1+2*2+2*2
9=3*3

9.
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
输入格式 :
第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有n个物品；
接下来n行，分别表示这n个物品的各自体积。
输出格式:
一个整数，表示箱子剩余空间

#include<cstdio>
#include<iostream>
using namespace std;
int v=20000,m,n,a[100]={0};
int f(int k,int t){
  if(k>n){if(t<v)v=t;return 0;}
  if(t>=a[k])f(k+1,t-a[k]);
  f(k+1,t);
}
int main(){
   cin>>m>>n;
   for(int i=1;i<=n;i++)cin>>a[i];
   f(1,m);
   cout<<v;
   return 0;
}
作业:
题目描述:辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有22个整数T(1 \le T \le 1000)T(1≤T≤1000)和M(1 \le M \le 100)M(1≤M≤100)，用一个空格隔开，TT代表总共能够用来采药的时间，MM代表山洞里的草药的数目。
接下来的MM行每行包括两个在11到100100之间（包括11和100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
1个整数，表示在规定的时间内可以采到的草药的最大总价值。
样例:
输入 
70 3
71 100
69 1
1 2
输出: 
3
说明/提示
对于30%的数据，M \le 10M≤10；
对于全部的数据，M \le 100M≤100。

10.已知如下地图，0代表空位可以走，2代表障碍物，不能走动。现在从左上角到右下角，请找出一条可以达到的路径(不一定最短,能到达的其中一就行了)，并经过的路径用标记出来。
输入图形
5 5 //表示地图的行和列数
1 1 //出发点的行列号
5 5 //终点的行列号
0 0 0 0 0
0 2 0 2 0
0 0 2 0 0
2 0 2 0 2
0 0 0 0 0

输入图形:(四周用障碍块包围)
显示路径：
███████
█◇◇◇◇◇█
█  █  █◇█
█    █◇◇█
██  █◇██
█      ◇◇█
███████

#include <cstdio>
#include <cstdlib>
#include<iostream>
using namespace std; 
int visit ( int, int );
 
int maze[100][100] ={0};
 int m,n;
int startI, startJ ;  // 入口
int endI, endJ;  // 出口
int success = 0;
 
int main ( )
{
    int i, j;
    cin>>m>>n;
    cin>>startI>>startJ;
    cin>>endI>>endJ; 
    for(i=1;i<=m;i++) 
      for(j=1;j<=n;j++)
      cin>>maze[i][j];
     
	 for ( i = 0; i <=n+1; i++ ) {
	 	maze[0][i]=2;
	 	maze[m+1][i]=2;
	 } 
	 for ( i = 0; i <=m+1; i++ ) {
	 	maze[i][0]=2;
	 	maze[i][n+1]=2;
	 } 
	 	 
    
 
    if ( visit ( startI, startJ ) == 0 )
        printf ( "\n没有找到出口！\n" );
    else
    {
        printf ( "\n显示路径：\n" );
        for ( i = 0; i <= m+1; i++ )
        {
            for ( j = 0; j <=n+1; j++ )
            {
                if ( maze[i][j] == 2 )
                    printf ( "█" );
                else if ( maze[i][j] == 1 )
                    printf ( "◇" );
                else
                    printf ( "  " );
            }
            printf ( "\n" );
        }
    }
 
    return 0;
}
 
int visit ( int i, int j )
{
    maze[i][j] = 1;
 
    if ( i == endI && j == endJ )
        success = 1;
 
    if ( success != 1 && maze[i][j+1] == 0 ) visit ( i, j+1 );
    if ( success != 1 && maze[i+1][j] == 0 ) visit ( i+1, j );
    if ( success != 1 && maze[i][j-1] == 0 ) visit ( i, j-1 );
    if ( success != 1 && maze[i-1][j] == 0 ) visit ( i-1, j );
 
    if ( success != 1 )
        maze[i][j] = 0;
 
    return success;
}