算法第二+三章上机实验报告

2021/10/27 1:12:06

本文主要是介绍算法第二+三章上机实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法第三章上机实验报告

1. 实践报告任选一题进行分析。内容包括:

1.1 问题描述:

一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动。他要从网格的左上角进,右下角出。每穿越中间1个小方格,都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时,都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用?

注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。

1.2 算法描述:

本题求最优解,最优解依赖于最优子解,运用递归求出最优子解后即可求出最优解。代码如下:

#include <iostream>

#include <cstdio>

#define N 101

using namespace std;

int f[N][N], a[N][N], n;

int ans;

 

int main() {

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= n; j++) {

            scanf("%d", &a[i][j]);

            if(i == 1) f[i][j] = a[i][j] + f[i][j-1];

            if(j == 1) f[i][j] = a[i][j] + f[i-1][j];

        }

    for(int i = 2; i <= n; i++)

        for(int j = 2; j <= n; j++) f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];

    printf("%d\n", f[n][n]);

    return 0;

   }

1.3 问题求解:

1.1.1 根据最优子结构性质,列出递归方程式

f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];

当只有一个方格时,f[i][j]= f[1][1]

1.1.2 给出填表法中表的维度、填表范围和填表顺序

二维,i从1到n且j从1到n,从左至右从上至下

1.1.3 分析该算法的时间和空间复杂度

时间复杂度:二重循环,O2^n

空间复杂度:O2^n

1.3 心得体会(对本次实践收获及疑惑进行总结)

本次实验加强我分析问题的能力,有时候抽象的的问题可以具体化,一步步分析,从子问题一步步延伸到最后的问题。实验过程中易忽略边界值(为1)的定义而导致实现最后答案经历坎坷,在与同伴的讨论和老师的指点中修改了对边界条件的界定。

2. 你对动态规划算法的理解和体会

首先应该理清思路,写出正确的递归方程式,反复检查是否与题意相符合,根据递归方程式求出最优子解,进而求出最优解。填表法需注意顺序及边界条件的界定,胆大心细。

算法第二章实验报告

一.实践题目名称:二分法求函数的零点

二.问题描述:有函数:f(x)=x5−15x4+85x3−225x2+274x−121 已知f(1.5)>0,f(2.4)<0 且方程f(x)=0 在区间[1.5,2.4] 有且只有一个根,请用二分法求出该根。 提示:判断函数是否为0,使用表达式 fabs(f(x)) < 1e-7

三.算法描述:由题意知该函数单调递减。首先将[1.5,2.4]作为第一个区间并求出其中点的函数值f(mid)。若f(mid)>0,则将左端点的值替换为mid;若f(mid)<0,则将右端点的值换为mid。以此类推,不断缩小mid所在区间,直至符合题意。核心算法代码如下图所示:

 

 

 

四.算法时间及空间复杂度分析:

时间复杂度:第一次解决子问题的时间复杂度为O(n/2),第二次为O(n/4),则第n次为O(logn),分解子问题的时间复杂度为O(1),则总的时间复杂度为O(logn);空间复杂度:递归算法的空间复杂度=递归深度*每次递归所需的辅助空间,则空间复杂度为O(logn)

五.心得体会:

通过这次实验对分治法的应用有了更详细全面的认识。实验课堂上会针对老师的提问做更多的思考,与同伴进行探讨的过程中会修复自己原本的思维漏洞

六.对分治法的个人体会和思考:

  1. 分治法是将一个规模庞大的问题划分为可解决的、形式相同的子问题的算法,从而实现对问题的解决
  2. 分治法作为九大算法之一,其核心在与划分问题的方式,好的划分方式降低了解决问题的难度
  3. 分治法运用得当,将从时间复杂性和空间复杂性上均有助于问题的解决

 



这篇关于算法第二+三章上机实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程