第十四周程序设计课解题报告

痛定思痛。 2022-08-07 13:39 125阅读 0赞

第十四周程序设计课解题报告

上周 rp/\*int类型\*/=2147483647;  
今天 ： rp++；  
问：rp还有多少  
  
要跪了TAT，下周还要交论文。  
  
吭吭，说回正题，这周终于遇见递归大魔王了。其实递归解决子问题用的是一种假设的思路，把问题拆分成更小的问题。比如设一个函数f(x),f(x)表示他能解决规模为x的解。而f(x)能通过比x小的规模得到。比如我问n的阶乘是多少。那么他能由（n-1）的阶乘成于n得到。而只要我们在设定一个最小的子情况的解，那么对于任意规模的问题都可以直接用f来解决。（例如求阶乘，可以看作最小的子情况 为0的阶乘==1，那么f(x)=f(x-1)\*x.由此我们便可以解决了所有自然数的阶乘问题了）  
而在1001汉诺塔中，我们可以碰见这种思想。递归不一定要清晰地求出每一个步骤。只要我确定当前步是对的（这说明子问题的返回解一定也是正确的） ，而且确定边界条件（确定递归的最小子问题，同时保证递归不会无限进行下去）  
  
1000.  
题目大意:求两个数a，b的最大公约数  
解：按照辗转相除法的步骤，按照递归去实现。如果不懂辗转相除的同学请网上搜索一下吧~  
code：

\#include <cstdio>

\#include <iostream>

\#include <cstring>

\#include <string>

\#include <cmath>

\#include <algorithm>

\#include <cstdlib>

using namespace std;

\#define MAXN 11111

\#define MIN(a,b) ((a)<(b)?(a):(b))

\#define MAX(a,b) ((a)>(b)?(a):(b))

\#define SQR(x) ((x)\*(x))

\#define EPS (1e-8)

\#define WMZ\_MAX (2147483647)

int n, m, ans;

string a\[MAXN\];

int gcd(int a, int b)\{

if (b==0) return a;

else return (gcd(b, a%b));

int main()\{

//   freopen("test.txt", "r", stdin);

while (cin>>n>>m)\{

cout << gcd(n, m)<< endl;

return 0;

\}         
  
1001.  
题目大意：给出汉诺塔的一个解                             
解：参见开头一段（胡）话的思想。假设dfs(a,b,c,n)代表着我有n个盘子，放置在标号为a的柱子上，我要通过标号为b的柱子的帮助，把这n个盘子移到标号为c的柱子上。  
我们可以得到这样一个步骤：  
 ①：先把n-1个盘子移动到柱子b上  
由我们的设定可知，调用 dfs(a, c, b, n-1)可以为我们完成这个任务  
②：n-1个盘子移动到标号b后，把第n个（最低层的盘子）从a移动到c上，即直接输出 a c 即可  
③：将n-1个盘子从b移动到c，即调用 dfs(b, a, c, n-1)  
可见对于当前步骤是对的，那么对于dfs（n）规模的问题得到解决的前提为dfs（n-1）的问题能完美解决。那么又需要dfs（n-2）的问题能解决  
。。。。。。。。。。。。。。。。。。。。。  
好了，现在是时候确定边界了，显然，当n==1时，我们无需借助第三根柱子，可以把这一个盘直接从a 移动到 c  
即：  
    if (n==1) \{   
        cout << a << c << endl;  
        return ;  
    \}   
那么dfs（1）得到解决，如此2~n都可以证明其正确性。  
  
ps：再次强调，a，b，c存放的是柱子标号，而不是a表示柱子1，b表示柱子2.。a是出发柱子标号，b是辅助柱子标号，c是终点柱子标号。如果我有什么说不清楚的地方欢迎直接上来问我，这个地方的理解的确刚上手的时候会有点困难。当然我有错也欢迎直接上来指出，毕竟我写这个东西的时候大脑处于半迷糊状态。  
  
ps2：我发现我所规定的子问题边界是n==0，其实也是可以的，因为没有盘子的时候不需要移动步骤了  
  
code：

\#include <cstdio>

\#include <iostream>

\#include <cstring>

\#include <string>

\#include <cmath>

\#include <algorithm>

\#include <cstdlib>

using namespace std;

\#define MAXN 11111

\#define MIN(a,b) ((a)<(b)?(a):(b))

\#define MAX(a,b) ((a)>(b)?(a):(b))

\#define SQR(x) ((x)\*(x))

\#define EPS (1e-8)

\#define WMZ\_MAX (2147483647)

int n, m, ans;

int a, b, p;

void dfs(int a, int b, int c, int kok)\{

if (kok==0) return ;

dfs(a, c, b, kok-1);

printf("%d%d\\n", a, c);

dfs(b, a, c, kok-1);

int main()\{

//   freopen("test.txt", "r", stdin);

cin>>n;

dfs(1, 2, 3, n);

return 0;

\}                             
  
1002.  
题目大意：中文题目不提供题目大意啦  
解：这个技巧叫做快速幂。读明白题目下方的hint直接照着写就可以了，不过小心注意必须步步取模不然可能造成int的溢出。另外我一开始提交的是非递归版的二进制拆分快速幂。有兴趣的同学可以参考一下。  
//求a的b次幂%p的值，非递归二进制拆分

int pow(int a, int b)\{ //写得丑，其实用for循环实现会更好看

int sum=1;

a%=p;

while (b)\{

if (b%2==1)\{

sum\*=a;

sum%=p;

a\*=a; a%=p;

b>>=1;

return sum;

//题目hint版

\#include <cstdio>

\#include <iostream>

\#include <cstring>

\#include <string>

\#include <cmath>

\#include <algorithm>

\#include <cstdlib>

using namespace std;

\#define MAXN 11111

\#define MIN(a,b) ((a)<(b)?(a):(b))

\#define MAX(a,b) ((a)>(b)?(a):(b))

\#define SQR(x) ((x)\*(x))

\#define EPS (1e-8)

\#define WMZ\_MAX (2147483647)

int a, b, p;

int f(int now)\{

if (now==0) return 1;

else if (now&1==1)\{

return ((a%p)\*((f(now/2)\*f(now/2))%p))%p;

return (f(now/2)\*f(now/2))%p;

int main()\{

//   freopen("test.txt", "r", stdin);

cin>>a>>b>>p;

cout << f(b) << endl;

return 0;

\}            
  
1003.  
题目大意：定义绘图函数a(n),b(n),a(n)会为一个(2n-1)\*(2n-1)的方阵填充满点。而b(n)会画一个9个小方阵组成的大方阵，具体是：

B(n - 1) A(n - 1) B(n - 1)

A(n - 1) B(n - 1) A(n - 1)

B (n - 1) A(n - 1) B(n - 1)  
其中：  
b(1) 为一个1\*1的格子填上大写‘X’

解：这种可以拆分子问题的可以用递归实现。我们可以开一个很二维数组当画布，然后调用b(n)在上面画画，画完后在输出即可。而b(n)和b(n-1)的关系题目已经给出，直接实现即可，注意处理坐标问题。我这里设定为aa(n, x, y)为在以x,y为左上角画图。bb(n,x,y)在x，y为左上角画图  
  
ps：注意估价二维数组大小。可知a、b会画出3^(n-1)大小的方阵，而n<=7,3^7=2000+，所以我把数组开到了3000，实际上只要 3^6+1即可。不过开得大一点是我个人风格。

\#include <cstdio>

\#include <iostream>

\#include <cstring>

\#include <string>

\#include <cmath>

\#include <algorithm>

\#include <cstdlib>

using namespace std;

\#define MAXN 11111

\#define MIN(a,b) ((a)<(b)?(a):(b))

\#define MAX(a,b) ((a)>(b)?(a):(b))

\#define SQR(x) ((x)\*(x))