递推-找规律-过河卒

猴子吃桃子

猴子吃桃子问题：猴子第一天摘下若干个桃子，当即吃了一半还不过瘾，又多吃了一个；第二天又将剩下的桃子吃掉一半又多吃了一个；以后每天早上都吃了前一天剩下的一半零一个。到了第十天想再吃时，见只剩下一个桃子，求第一天共摘了多少个桃子？

题解

/*
设第九天剩x个tao
x/2-1=1; 
y/2-1=x;
(x+1)*2=y
*/#include
using namespace std;
int main(){int x=1;for(int i=9;i>=1;i--){x=(x+1)*2;}cout<<x; return 0;
}

数数小木块

在墙角堆放着一堆完全相同的正方体小木块，如下图所示：

因为木块堆得实在是太有规律了，你只要知道它的层数就可以计算所有木块的数量了。

输入格式

只有一个整数 n ，表示这堆小木块的层数，已知1 <= n <= 100 。

输出格式

只有一个整数 n ，表示这堆小木块的层数，已知1 <= n <= 100 。

题解

/*一层:1
二层：1+2=3
三层：3+3=7
四层：7+4=11 
五层：11+5=16 
n层：sum（n-1）+n 
*/#include
using namespace std;
int main()
{int n=0,sum=0,s=0;cin>>n;for(int i=1;i<=n;i++){sum=sum+i; s=s+sum;}cout<<s;return 0;
}

过河卒

A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如下图 C 点可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。 棋盘用坐标表示，现给定A 点位置为（0,0）B 点位置为（n,m）(n,m 为不超过 20 的整数)，马的位置为C（X,Y）（约定: C点与A点不重叠，与B点也不重叠）。要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入格式

B点的坐标（n,m）以及对方马的坐标（X,Y）（马的坐标一定在棋盘范围内，但要注意，可能落在边界的轴上）

样例输入

6 6 3 2

样例输出

17

题解

/*
卒： 
a[x][y]=a[x-1][y]、 a[x][y-1]
特殊情况：遇到马可以走的点 ，continue
*/ #include
using namespace std;
long B[21][21] ;//定义棋盘 int main()
{int n,m;//目标点的坐标 int a,b;//马所在点的坐标 cin>>n>>m>>a>>b;//初始化棋盘，假设到大目标点（m,n）前每个点都可以同性设置成1for(int i=0;i<=n;i++) for(int j=0;j<=m;j++)B[i][j]=1;//将马控制的点设置为0，代表不能通过//控制马上边的4个点，只要不超过边界，则为控制点if(a-2>=0&&b-1>=0)B[a-2][b-1]=0;if(a-2>=0&&b+1<=m)B[a-2][b+1]=0;if(a-1>=0&&b-2>=0)B[a-1][b-2]=0;if(a-1>=0&&b+2<=m)B[a-1][b+2]=0;//控制马下边的四个点，只要不超过边界，则为控制点 if(a+2<=n&&b-1>=0)B[a+2][b-1]=0;if(a+2<=n&&b+1<=m)B[a+2][b+1]=0;if(a+1<=n&&b-2>=0)B[a+1][b-2]=0;if(a+1<=n&&b+2<=m)B[a+1][b+2]=0;//马所在点B[a][b]=0;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){//如果可行if(B[i][j]){if(i==0&&j==0)continue;else if(i==0)B[i][j]=B[i][j-1];//目标点在最上面一行的时候else if(j==0)B[i][j]=B[i-1][j];//目标点在最左边一行elseB[i][j]=B[i-1][j]+B[i][j-1];//到达目标点路径=上点路径+左点路径 } }}cout<<B[n][m]<<endl; return 0;
}