| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 611 人关注过本帖
标题:门外汉,求助算法分析与设计基础题解答,拜托各位!
只看楼主 加入收藏
shiseyu
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-11-16
收藏
 问题点数:0 回复次数:0 
门外汉,求助算法分析与设计基础题解答,拜托各位!
     各位仁兄仁姐,小妹没学过数据结构,被迫帮别人要做几道题,在网上查了半天还有6道没有解决。无奈时间有限,自己现学已来不及,不过感觉应该是些基础的,或者某些课本的原题。请知情者指点迷津,不胜感激!!
     先将原题粘上,希望学过的朋友,指点一下!

1.用Step Table的方法计算下面算法的时间复杂性

template <class T>
void Insert(T a[],int & n,const T& x)
{//Insert x into the sorted array a[0:n-1].
 //Assume a is of size > n.
  int i;
  for (i = n-1;i >= 0 && x < a[i]; i--)
    a[i+1] = a[i];
  a[i+1] = x;
  n++; //one element added to a
}
解:

2.证明下面的渐进表达式成立
E4:
图片附件: 游客没有浏览图片的权限,请 登录注册

I2:
图片附件: 游客没有浏览图片的权限,请 登录注册

解:

3.分别用迭代展开和Master方法计算下面递归关系的复杂性
图片附件: 游客没有浏览图片的权限,请 登录注册


解:

4.考虑
图片附件: 游客没有浏览图片的权限,请 登录注册
而不是
图片附件: 游客没有浏览图片的权限,请 登录注册
的连续背包问题。
一种可行的贪婪策略是:按价值密度非递减的顺序检查物品,若剩余容量能容下正在考察的物品,将其状如;否则,往背包中装入此物品的一部分。
1)对于n=3,w=[100,10,10],  p=[20,15,15]及c=105,上述装入方法获得的结果是什么?
2)证明这种贪婪算法总能获得最优解。
解:

5.使用2-优化方法求解以下0/1背包问题的实例并给出求解过程。n=4,c=20,w=(10,15,6,9),p=(2,5,8,1)

6.给出快速排序的非递归算法,要求堆栈中只需保存left和right中较小者的边界。证明所需要的栈空间大小为
图片附件: 游客没有浏览图片的权限,请 登录注册

搜索更多相关主题的帖子: 门外汉 基础 算法分析 解答 
2009-11-16 09:52
快速回复:门外汉,求助算法分析与设计基础题解答,拜托各位!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020819 second(s), 11 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved