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

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

算法第三章上机实验报告

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 分析该算法的时间和空间复杂度

时间复杂度：二重循环，O（2^n）

空间复杂度：O（2^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. 分治法运用得当，将从时间复杂性和空间复杂性上均有助于问题的解决

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