没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
27页
目 录 1 设计任务与目标(三号,黑体,居中) 1 1.1 设计任务与目标(标题均为小三号,宋体) 1 青蛙过河[中等] 1 1.2 任务分析 2 2 算法设计与验证(三号,黑体,居中) 3 2.1 二分法 3 2.2 贪心算法 3 2.3 程序设计与实现 4 2.4 程序运行、测试与分析 5 2.4.1二分答案法测试结果 6 2.4.2贪心算法测试结果 8 3 系统设计(三号,黑体,居中) 10 3.1 设计任务与目标(标题均为小三号,宋体) 10 3.2 系统设计 11 3.3 系统实现 12 3.4 程序运行、测试与分析 14 4 可视化设计(三号,黑体,居中) 16 4.1 设计任务与目标(标题均为小三号,宋体) 16 4.2 UI和可视化方案设计 16 4.3 UI和可视化系统实现 17 4.4 程序运行、测试与分析 18 4.4.1二分法测试结果 19 4.4.2贪心算法测试结果 20 5 结论与心得(三号,黑体,居中) 22 参考资料(三号,黑体,居中) 22
资源推荐
资源详情
资源评论
珠海科技学院
课 程 设 计 报 告
学 院:
珠海科技学院计算机学院
专业名称:
计算机科学与技术
设计科目:
数据结构与算法课程设计
学号姓名:
指导教师:
完成时间:
II
目 录
1 设计任务与目标(三号,黑体,居中)....................................................................................1
1.1 设计任务与目标(标题均为小三号,宋体)................................................................1
青蛙过河[中等]........................................................................................................................1
1.2 任务分析............................................................................................................................2
2 算法设计与验证(三号,黑体,居中)....................................................................................3
2.1 二分法................................................................................................................................3
2.2 贪心算法............................................................................................................................3
2.3 程序设计与实现................................................................................................................4
2.4 程序运行、测试与分析....................................................................................................5
2.4.1 二分答案法测试结果.....................................................................................................6
2.4.2 贪心算法测试结果.........................................................................................................8
3 系统设计(三号,黑体,居中)..............................................................................................10
3.1 设计任务与目标(标题均为小三号,宋体)..............................................................10
3.2 系统设计..........................................................................................................................11
3.3 系统实现..........................................................................................................................12
3.4 程序运行、测试与分析..................................................................................................14
4 可视化设计(三号,黑体,居中)..........................................................................................16
4.1 设计任务与目标(标题均为小三号,宋体)..............................................................16
4.2 UI 和可视化方案设计.....................................................................................................16
4.3 UI 和可视化系统实现.....................................................................................................17
4.4 程序运行、测试与分析..................................................................................................18
4.4.1 二分法测试结果...........................................................................................................19
4.4.2 贪心算法测试结果.......................................................................................................20
5 结论与心得(三号,黑体,居中)..........................................................................................22
参考资料(三号,黑体,居中)..................................................................................................22
1
1 设计任务与目标
1.1 设计任务与目标
不同路径[中等]
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为
“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右
下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/unique-paths
【算法设计】
请设计算法,求解上述问题。用结构化程序设计方法编程验证算法的正
确性。
输入格式:
每行输入的两个数 m 和 n,中间用空格隔开,分别作为题目描述中的 m 和
n,当 m=0 或者 n=0 的时候输入结束。
输出格式:
每行输出为一个整数,表示对应输入的计算结果。
样例输入:
3 7
3 2
7 3
3 3
0 0
样例输出:
28
3
28
6
解释:
当 m=3,n=3 时,从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10
9
2
1.2 任务分析
这个问题可以用动态规划来解决。我们可以定义一个二维数组 dp,其中
dp[i][j]表示从起点到网格 (i,j)的不同路径数。根据题目要求,机器人每次只
能向下或者向右移动,因此到达 (i,j)的路径数等于到达 (i−1,j) (i,j−1)的路径
数之和。
具体算法步骤如下:
1. 初始化一个 m×n 的二维数组 dp,并将[0][0]dp[0][0]初始化为 1。
2. 对于第一行和第一列,由于机器人只能向下或向右移动,所以到达这些
位置的路径数只能为 1,因此将第一行和第一列的 dp 值初始化为 1。
3. 对于其他位置 (i,j),根据状态转移方程
dp[i][j]=dp[i−1][j]+dp[i][j−1]更新 dp 数组。
4. 最终 dp[m−1][n−1]即为从起点到终点的不同路径数。
因此可以通过动态规划法或者排列组合法来解决该问题。
3
2 算法设计与验证
2.1 动态规划法
我们用 f(i,j) 表示从左上角走到 (i,j) 的路径数量,其中 i 和 j 的范
围分别是 [0,m)和 [0,n)。
由于我们每一步只能从向下或者向右移动一步,因此要想走到 (i,j),如果
向下走一步,那么会从 (i−1,j) 走过来;如果向右走一步,那么会从 (i,j−1)
走过来。因此我们可以写出动态规划转移方程:
f(i, j) = f(i-1, j) + f(i, j-1)
需要注意的是,如果 i=0,那么 f(i−1,j) 并不是一个满足要求的状态,我
们需要忽略这一项;同理,如果 j=0,那么 f(i,j−1) 并不是一个满足要求的状
态,我们需要忽略这一项。
初始条件为 f(0,0)=1,即从左上角走到左上角有一种方法。
最终的答案即为 f(m−1,n−1)。
为了方便代码编写,我们可以将所有的 f(0,j) 以及 f(i,0) 都设置为边界
条件,它们的值均为 1。
复杂度分析
时间复杂度 O(mn)。
空间复杂度: O(mn),即为存储所有状态需要的空间。注意到 f(i,j 仅与第 i
行和第 i−1 行的状态有关,因此我们可以使用滚动数组代替代码中的二维数组,
使空间复杂度降低为 O(n)。此外,由于我们交换行列的值并不会对答案产生影
响,因此我们总可以通过交换 m 和 n 使得 m≤n,这样空间复杂度降低至
O(min(m,n))。
剩余26页未读,继续阅读
资源评论
小柒_02
- 粉丝: 753
- 资源: 20
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于Javascript和Python的微商城项目设计源码 - MicroMall
- 基于Java的网上订餐系统设计源码 - online ordering system
- 基于Javascript的超级美眉网络资源管理应用模块设计源码
- 基于Typescript和PHP的编程知识储备库设计源码 - study-php
- Screenshot_2024-05-28-11-40-58-177_com.tencent.mm.jpg
- 基于Dart的Flutter小提琴调音器APP设计源码 - violinhelper
- 基于JavaScript和CSS的随寻订购网页设计源码 - web-order
- 基于MATLAB的声纹识别系统设计源码 - VoiceprintRecognition
- 基于Java的微服务插件集合设计源码 - wsy-plugins
- 基于Vue和微信小程序的监理日志系统设计源码 - supervisionLog
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功