首页 > 代码库 > 解题报告——-2018级2016第二学期第三周作业

解题报告——-2018级2016第二学期第三周作业

解题报告——2018级2016第二学期第三周作业

 

A:NOIP2002P〗过河

题目:

描述

  如图,A 点有一个过河卒,需要走到目标 B   点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例 如上图 C  点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。 



棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20  的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。现在要求你计算出卒从 A 点能够到达 B  点的路径的条数。

输入

   B点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错}

输出

    一个整数(路径的条数)。

样例输入

6 6 3 2

样例输出

17

 

分析:

这题可以用回溯写,但这样一定会超时,所以我们只能用递推递归写;

一开始经过我的探究发现了这样的递归式:

 

但是这样是会显示wrong answer;

仔细思考后,会发现这个递归式有一个错误:

(如题目中的图一样)在P5p4中间

如果按照上面这个递归式就是1;但其实它是0

所以这个递归式是错误的;

那么正确的应该是:

 

但是要注意的是要用递推去写,否则会超时;

更需要注意的是要用long 去定义数,否则只会得60分;

 

代码:

#include<cstdio>#include<cmath>#include<iostream>#include<cstring>#include<cstdlib>

using namespace std;

long x,y,a,b;long js;long k[1000][1000];//long定义 

 

int main(){

 cin>>x>>y>>a>>b;

//输入

 for(int i=0;i<=x;i++)

     for(int j=0;j<=y;j++){//要从0开始,题目所述

      if(i==0&&j==0)k[i][j]=1;

      else if((i==a&&j==b)||abs(i-a)*abs(j-b)==2)k[i][j]=0;

      else if(i==0)k[i][j]=k[i][j-1];

      else if(j==0)k[i][j]=k[i-1][j];

      else k[i][j]=k[i-1][j]+k[i][j-1];//用递推表达正确的递归式

 }

 cout<<k[x][y]<<endl;//输出

 system("pause");

 return 0;}

 

算法:递推递归;

 

 

 

 

 

 

 

 

 

D:NOIP2003P〗栈

题目:

描述

  栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。


宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。
现在可以进行两种操作,
1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)
2.  将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2  3生成序列2 3 1的过程。(原始状态如上图所示)

 

你的程序将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。

输入

  输入文件只含一个整数n(1≤n≤18)

输出

  输出文件只有一行,即可能输出序列的总数目

样例输入

3

样例输出

5

 

分析:

其实这题可以把它当做进出火车;

所以可以用dfs(中间还能有多少车,最终车的编号,后面的车的位置)

中间当js==0m>n是出解了;

否则如果m<=n可以出

如果js!=0可以进;

但是这样会超时;

所以再进行优化;

其实只用考虑入的和出的;

那么如果ru==n&&chu==n就有解了;

否则如果ru<n就可以进入;

如果ru>chu就可以出;

但是这样扔能会超时;

所以再进行优化;

可有用递归递推;

跟第二个一样

如果ru==n&&chu==n返回1

否则如果ru<n进入ans+=dfs(ru+1,chu);

如果ru>chuans+=dfs(ru,chu+1);

最终返回ans

但是这样仍然会超时;

所以再次进行优化;

其实可以递推递归记忆化;

那么就是如果i==n&&j==m 那么sol[i][j]=1;

否则就想上面一样

If(i<n).........

If(j<i)............

但是这样要倒着推因为只有这样才能求出结果;

 

代码:

#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <iostream>

using namespace std;

int sol[20][20],n;

int main(){

cin>>n;for(int i=n;i>=0;i--)for(int j=n;j>=0;j--){if(i==n&&j==n) sol[i][j]=1;else{if(i<n) sol[i][j]=sol[i][j]+sol[i+1][j];if(j<i) sol[i][j]=sol[i][j]+sol[i][j+1];

}//递推(如上所述)

}

cout<<sol[0][0]<<endl;//输出

return 0;} 

 

算法:递推递归;

 

 

 

 

 

 

 

 

 

F【基本算法—递推递归】计数问题

题目:

描述

在所有的N位数中,有多少个数中有偶数个数字3

输入

一个数N。1<=N<=1000。

输出

一个整数,所有符合条件数的个数。由于结果可能很大,你只需要输出这个答案mod 12345的值。

样例输入

2

样例输出

73

 

分析:

通过分析

可有知道n位数有10^n-1*9个数;

如果我们用f数组来表奇数

g数组来表示偶数;

通过我们思考可得

F(n)=f(n-1)*9+g(n-1);//n代表位数

因为奇数只要不加上3就可以;

偶数加上3就可以;

同样gn=g(n-1)*9+f(n-1);

但要注意的是f1)和f2)不符合;

因为f1)多了一个0

所以单独注释;

而其他就不存在了;

 

代码:

#include<cstdio>#include<cmath>#include<iostream>#include<cstring>#include<cstdlib>

using namespace std;

int f[1111],g[1111];int n;//f代表奇数,g代表偶数

int main(){

  cin>>n;

  f[1]=9;

  g[1]=1;

  f[2]=73;

  g[2]=17;//单独注释

  for(int i=3;i<=n;i++){

    f[i]=(f[i-1]*9+g[i-1])%12345;

    g[i]=(g[i-1]*9+f[i-1])%12345;//余数定理

  }

  cout<<f[n]<<endl;

  return 0;}

 

算法:递推递归;

解题报告——-2018级2016第二学期第三周作业