对应课程:点击查看
起止时间:2020-03-09到2020-07-31
更新状态:已完结
作业第一章 绪论 时间复杂度分析作业
1、 给定以下两个算法：算法A：for(int i = 0; i < N; i++) for(int j = 0; j< N; j++) { S; }算法B：for(int i = 0; i < N; i++) for(int j = i; j< N; j++) { S; }其中N是一个比较大的自然数，S是有若干基本语句组成的程序段。1）在相同的计算机上，算法A比算法B运行速度慢？2）算法A的时间复杂度比算法B要高？请判断以上两个命题是否正确？并说明理由。
评分规则: 参考答案：1）正确，因为算法A执行S的次数比算法B要多，因此运行速度较慢。2）错误，算法复杂度的表示是最坏情况下关键操作执行次数的渐进阶，而不是算法执行的具体时间。此题算法A和算法B的渐进阶相同，因此，其复杂度也相同。评分标准：对于每一小题：结论正确，且论述理由充分，则得50分；对于每一小题：结论正确，且论述理由不充分，则得30分；对于每一小题：结论不正确，则得0分；
作业第二章 枚举算法（大道至简） 枚举算法作业
1、 题目描述李老师的lucky number 是3，5和7，他爱屋及乌，还把所有质因数只有3，5，7的数字也认定为lucky number，比如9, 15, 21, 25等等。请聪明的你帮忙算一算小于等于x的lucky number有多少个？输入数据一个正整数x，3 =< x <= 1000000000000输出数据小于等于x的lucky number的个数。样例输入49样例输出11
评分规则: 得分要求和标准：1）算法思路正确，得60分；2）代码规范，无明显错误，得20分；3）数值范围、边界条件等正确，得20分。参考答案：1）递归搜索方法，搜索3，5，7的个数，然后将对应个数的3，5，7乘起来，如果结果小于等于x则计数并继续搜索，否则剪枝。注意需要开数组vis[i][j][k]表示i个3，j个5，k个7的状态有没有被搜过，防止重复搜索2）循环枚举方法，直接三层for循环枚举3，5，7的个数，然后乘起来超过x就break，不超过就计数
递归搜索的参考程序（C++）：
include
define ll long long
using namespace std;
int ans = 0;
int vis[111][111][111];
void dfs(int n3,int n5,int n7,ll now,ll tar){
if(now>tar||vis[n3][n5][n7])
return;
vis[n3][n5][n7] = 1;
ans++;
dfs(n3+1,n5,n7,now3,tar);
dfs(n3,n5+1,n7,now5,tar);
dfs(n3,n5,n7+1,now*7,tar);
}
int main(){
ll a;
cin>>a;
dfs(0,0,0,1,a);
cout< return 0;
}
作业第三章 递归与分治（分而治之）-1 递归算法实践
1、 题目描述楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法由于答案很大，mod(1e9+7)输出输入数据一个正整数n，代表楼梯的阶数，n<=1000000输出数据方案数样例输入3样例输出4
评分规则: 算法基本思想：设f(n)为n阶台阶上楼的方案数，考虑最后一步可以跨过1级台阶，2级台阶或3级台阶，所以f(n)=f(n-1)+f(n-2)+f(n-3)，过程中要取模。算法思想正确得60分。
参考的程序（C++）：#include
using namespace std;
define ll long long
const int mod = 1000000007;
ll vis[1000011];
ll fun(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
if(vis[n]) return vis[n];
return vis[n] = (fun(n-1)+fun(n-2)+fun(n-3))%mod;
}
int main(){
int n;
cin>>n;
cout<
作业第三章 递归与分治（分而治之）- 2 矩阵搜索问题
1、 给定n行n列的整数矩阵A，其中每行的整数从左到右升序排列，每列的整数从上到下降序排列。即 i, j ∈ {1, …, n-1} 时，矩阵元素满足以下关系：A[i, j] < A[i, j + 1] 和 A[i, j] > A[i + 1, j]。给定一个整数x，试问矩阵A 是否有整数x。例如：给定以下矩阵A，如果 x = 5，返回true；如果 x = 10，返回false。A =7 8 9 3 4 61 2 5 请设计一个复杂度为O(n)的搜索算法。
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
获取更多MOOC答案，欢迎在浏览器访问我们的网站：http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
一键领取淘宝，天猫，京东，拼多多无门槛优惠券，让您购物省省省，点击这里，了解详情