您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
算法分析第三次作业答案(卜东波).doc4页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：150 &&
你可能关注的文档：
··········
··········
算法第三次作业答案
答：令A、B为已给两个数据库的数据集，其中A(i)、B(i)为A、B中第i个最小的值，给出求中值算法如下：
Median(n,a,b)
min(A(a+k),B(b+k))
A(a+k)和B(b+k)
A(a+k) R[j]
A[k] = L[i]
L[i] > 3R[j] then
InversionCount = InversionCount + j - k
A[k] = R[j]
显然Merge-and-Count (A,B)的算法复杂度为cn
令Sort-and-Count (L)的算法复杂度为T(n),则：
T(n)≤2T(n/2)+cn可推出T(n)= O(n log n)
（1）算法如下：
Find-Local-Min(T)
T has children
Let L and R be T’s children
Probe the values of X, X, X;
Return Find-Local-Min(L)
Else If X< X
Return Find-Local-Min(R)
（2）复杂度分析：
因n=2d-1，则完全二叉树的深度可表示为log(n+1)，上述算法是沿着树的节点逐层递归的，即算法的最深递归层次为树深（log(n+1)），每层节的要进行三次试探，故总的试探次数为3* log(n+1)，即算法的复杂度为O(3* log(n+1))=O(log(n))。
写成递推式如下：
H(n)=∑H(i)*H(n-i+1) （i=2,3,…,n-1） ----公式(1)
有了这个递归关系式，就可以用递推法或递归法解出H(n)。
设该算法复杂度为T(n),则由于
正在加载中，请稍后...1.输入课本各个例题，调试运行程序，并分析程序，将每一个程序改写2到3个版本，自己分析程序结果，然后再调试运行，核对分析结果的对错。
2.编写程序输入一个三角形的三条边，计算其面积和周长；
3.编写程序计算并输出课本本章习题3表达式的&#20540;并分析结果。
4.编写一个程序，输入一个一元二次方程的三个系数，并计算其方程的解，然后输出。
5.编写程序，自己确定一个加密算法，将自己的音标姓名（英文）加密，并输出加密后结果，请注释你的加密算法。
6.在一个自动控制设备中，控制字位数16位，控制设备产生机械动作（如削，压等）的是指令字的低8位，其中&#65279;&#65279;保护强制停机动作的控制命令是低8位是全为0，控制报警声音是指令的高第1位，0为报警，1为不报警。请编写程序，在紧急状况启动时，向控制器输入控制指令。
7.积累调试程序经验，收集错误信息原因（每个同学收集3-5条错误信息原因，并输入电脑形成文字）。
/*功能:布尔类型使用举例*/
#include&iostream&
//编译预处理命令
#include&iomanip&
//使用控制符波boolalpha需使用此头文件
//使用标准名空间std
int main()
bool flag =
//定义布尔型变量flag，并初始化为true
cout&&flag&&
//默认情况下为非bool字母（noboolalpha），输出整型值1
cout&&boolalpha&&flag&&
//使用输出格式控制符波boolalpha，输出布尔型值
cout&&flag+5&&
//在算术运算中，把布尔数据当作整型数据，输出6
//可以给bool类型的变量赋任意类型的值
cout&&&执行语句flag=0;后flag的值为:&&&boolalpha&&flag&&
//0.0为double类型的数值
cout&&&执行语句flag=0.0;后flag的值为:&&&boolalpha&&flag&&
/*功能：赋值表达语句的使用*/
#include&iostream&
int main()
int a,b,c,d;
cout&&&a=&&&a&&endl
&&&b=&&&b&&endl
&&&c=&&&c&&endl
&&&d=&&&d&&
#include&iostream&
int main()
short i,j,m,n;
cout&&&m=&&&m&&
cout&&&n=&&&n&&
#include&iostream&
int main()
int i=6,j,k,
//先对变量i自增,i的值变为7,之后把i的值7赋给变量j
//先对变量i的值7赋给变量k，然后i的值自增，i的值变为8
//++i可以作为左值,执行完该语句后变量i的值为1
cout&&&i=&&&i&&endl
&&&j=&&&j&&endl
&&&k=&&&k&&
#include&iostream&
int main()
cout&&&please inputa character:&;
ch=ch&='a'&& ch&='z'? ch-'a'+'A':
cout&&&The result is:&&&ch&&
#include&iostream&
int main()
double b=3.14;
char c='A';
ab=int(b);
ac=int(c);
cout&&&b=&&&b&&
cout&&&ab=&&&ab&&
cout&&&c=&&&c&&
cout&&&ac=&&&ac&&
#include&iostream&
#include&cmath&
int main()
float a,b,c,p,area,s;
cout&&&请输入三角形的三条边:&;
cin&&a&&b&&c;
p=(a+b+c)/2;
area=sqrt(p*(p-a)*(p-b)*(p-c));
cout&&&该三角形的周长为:&&&s&&
cout&&&该三角形的面积为:&&&area&&
/*功能：习题求值*/
# include &iostream&
# include &math.h&
int main ()
int e = 1 ,f = 4 , g = 2 ;
//定义e f g为整型变量 ，且赋予初值
float m = 10.5 , n = 4.0 ,
//定义m n k为实型变量 ，其中 m n赋予初值
k = (e + f) / g + sqrt ((double)n) * 1.2 /g +
//在运算过程中n被强制转换成double型
cout && &求出k的值为:& && k
return 0 ;
/*功能：求解一元二次方程*/
by Tin Lin
# include &iostream&
# include &math.h&
int main ()
float a , b , c , diaota , q ,x1 , x2 ;
cout && &请依次输入数据& &&
cout && &请输入方程的二次项系数& ;
cout && &请输入方程的一次项系数& ;
cout && &请输入方程的常数项系数& ;
diaota = b * b - 4 * a *
if (diaota & 0)
q = sqrt(diaota) ;
cout && &此方程的有两个不等的实根，分别为& &&
cout && &x1 = & && (x1 = (-b + q) / (2 * a )) ;
cout && &x2 = & && (x2 = (-b - q) /( 2 * a )) &&
if (diaota == 0 )
q = sqrt(diaota) ;
cout && &此方程有两个相等的实根x1=x2且为& && (x1 = x2 = (-b - q) /( 2 * a )) &&
if (diaota & 0)
cout && &此方程无实数根& &&
//不考虑虚根的情况
return 0 ;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1576次
排名：千里之外
(1)(2)(1)(2)2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
2016年10月优秀大版主2016年8月优秀大版主
2016年9月 总版技术专家分月排行榜第二
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。作业内容：
1.输入课本各个例题，调试运行程序，并分析程序，将每一个程序改写2到3个版本，自己分析程序结果，然后再调试运行，核对分析结果的对错。
2.编写程序输入一个三角形的三条边，计算其面积和周长；
3.编写程序计算并输出课本本章习题3表达式的&#20540;并分析结果。
4.编写一个程序，输入一个一元二次方程的三个系数，并计算其方程的解，然后输出。
5.编写程序，自己确定一个加密算法，将自己的音标姓名（英文）加密，并输出加密后结果，请注释你的加密算法。
6.在一个自动控制设备中，控制字位数16位，控制设备产生机械动作（如削，压等）的是指令字的低8位，其中&#65279;&#65279;保护强制停机动作的控制命令是低8位是全为0，控制报警声音是指令的高第1位，0为报警，1为不报警。请编写程序，在紧急状况启动时，向控制器输入控制指令。
（老师，这题不会做，希望您上课讲讲。）
7.积累调试程序经验，收集错误信息原因（每个同学收集3-5条错误信息原因，并输入电脑形成文字）。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2073次
排名：千里之外
评论：13条
(1)(1)(1)(3)后使用快捷导航没有帐号？
查看: 924|回复: 19
我怎么看不懂算法第三周的第一题作业？
高级会员, 积分 632, 距离下一级还需 368 积分
论坛徽章:6
哪位同学能帮讲一下？这个题目啥意思？
优先队列：有n个合同，每个合同的截止日期是d_i,有个程序员，它完成第i个合同的时间是b_i,对于合同I,如果给他x元钱，他完成第i个合同的时间就会变成b_i-a_i×x .求需要的最少总钱数，使得存在一个方案使得程序员按时完成所有合同。
数据范围：1≤n≤〖10〗^5,1≤a_i,b_i≤〖10〗^5,1≤d_i≤〖10〗^9
高级会员, 积分 632, 距离下一级还需 368 积分
论坛徽章:6
这是英文原题，看了原题才明白&&
高级会员, 积分 632, 距离下一级还需 368 积分
论坛徽章:6
哎，自己理解力这么差啊
注册会员, 积分 171, 距离下一级还需 29 积分
论坛徽章:6
我也是看不懂唉
论坛徽章:20
金牌会员, 积分 2394, 距离下一级还需 606 积分
论坛徽章:7
我也没有理解，如何用优先队列模型来解决这个问题
金牌会员, 积分 1353, 距离下一级还需 1647 积分
论坛徽章:13
没看懂 ＋1 ，这个助教貌似一个很年少的理工男
中级会员, 积分 228, 距离下一级还需 272 积分
论坛徽章:3
+1 是得看原文
中级会员, 积分 228, 距离下一级还需 272 积分
论坛徽章:3
只有一个程序员，真苦逼
论坛徽章:20
这是英文原题，看了原题才明白&&http://poj.org/problem?id=2970
我也是看了原题才搞明白要做什么。不过那个优先队列我也没搞明白，视频和教材中也没有提到过啊