⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 贪心算法解决磁盘文件最优存储问题-一品浓茶 - 新浪blog.htm

📁 这是一个关于磁盘文件最优存储问题
💻 HTM
📖 第 1 页 / 共 3 页
字号:
🔍
123 
      class="toggleLink collapseArraw center" id=collapseButton title=展开或收缩模块 
      href="javascript:void(0)" 
      toggle="componentContent"><INPUT type=button></A><SPAN 
      id=titleText>访客</SPAN> </TD>
    <TD class=componentMenu id=componentMenu><A 
      class="icon refresh center invisible" id=refreshCompButton 
      href="javascript:void(0)">&nbsp;&nbsp;</A> <A 
      class="adminComp center invisible" id=adminCompButton 
      href="javascript:void(0)"></A><A class="closeComp center invisible" 
      id=closeCompButton title=隐藏模块 href="javascript:void(0)"><INPUT type=button></A> </TD></TR></TBODY></TABLE>
<DIV class=componentHead id=componentHead></DIV>
<DIV class=ccomponentTip id=componentTip></DIV>
<DIV class=componentContent id=componentContent>
<DIV class=componentDef type="dynamic" 
data="http://util.blog.sina.com.cn/rr?1240064164&amp;n"></DIV></DIV><!--componentContent-->
<DIV class=componentFooter></DIV><!--componentFooter--></DIV></DIV><!-- add dbid attribute.		by xp 07.07.05 --><!-- add adminCompButton.	chaoliang  7.7.29 -->
<DIV class="component withTitleBar" id=blog_toparticlesort dbid="">
<DIV class=componentInnderBorder>
<DIV class=componentSpecialArea id=componentSpecialArea></DIV>
<TABLE class="componentBar layout" id=componentBar>
  <TBODY>
  <TR>
    <TD class=componentTitle id=componentTitle><A 
      class="toggleLink collapseArraw center" id=collapseButton title=展开或收缩模块 
      href="javascript:void(0)" 
      toggle="componentContent"><INPUT type=button></A><SPAN 
      id=titleText>新浪博客推荐文章</SPAN> </TD>
    <TD class=componentMenu id=componentMenu><A 
      class="icon refresh center invisible" id=refreshCompButton 
      href="javascript:;">&nbsp;&nbsp;</A> <A class="adminComp center invisible" 
      id=adminCompButton href="javascript:void(0)">管理</A><A 
      class="closeComp center invisible" id=closeCompButton title=隐藏模块 
      href="javascript:void(0)"><INPUT type=button></A> </TD></TR></TBODY></TABLE>
<DIV class=componentHead id=componentHead></DIV>
<DIV class=ccomponentTip id=componentTip></DIV>
<DIV class=componentContent id=componentContent>
<SCRIPT 
src="贪心算法解决磁盘文件最优存储问题-一品浓茶 - 新浪BLOG.files/toparticlesort_113.js"></SCRIPT>
</DIV><!--componentContent-->
<DIV class=componentFooter></DIV><!--componentFooter--></DIV></DIV><!-- {$box_2}--></DIV><!--column_1--><!--gap is reserved for further usage such as munipulating page layout.-->
<DIV class=floatLeft id=gap_1></DIV>
<DIV class=floatLeft id=column_2><!-- add dbid attribute.		by xp 07.07.05 --><!-- add adminCompButton.	chaoliang  7.7.29 -->
<DIV class="component " id=blog_feeds dbid="">
<DIV class=componentInnderBorder>
<DIV class=componentSpecialArea id=componentSpecialArea></DIV>
<TABLE class="componentBar layout" id=componentBar>
  <TBODY>
  <TR>
    <TD class=componentTitle id=componentTitle><A 
      class="toggleLink collapseArraw center" id=collapseButton title=展开或收缩模块 
      href="javascript:void(0)" 
      toggle="componentContent"><INPUT type=button></A><SPAN 
      id=titleText>内容</SPAN> </TD>
    <TD class=componentMenu id=componentMenu><A 
      class="icon refresh center invisible" id=refreshCompButton 
      href="javascript:;">&nbsp;&nbsp;</A> <A class="adminComp center invisible" 
      id=adminCompButton href="javascript:void(0)">管理</A><A 
      class="closeComp center invisible" id=closeCompButton title=隐藏模块 
      href="javascript:void(0)"><INPUT type=button></A> </TD></TR></TBODY></TABLE>
<DIV class=componentHead id=componentHead></DIV>
<DIV class=ccomponentTip id=componentTip></DIV>
<DIV class=componentContent id=componentContent>
<DIV id=adminLinks>
<DIV id=loadingText>数据加载中...</DIV>
<DIV class=invisible id=guestPanel><A 
href="http://my2008.sina.com.cn/blog/index.shtml" 
target=_blank>写博客，参与“我的2008--我记录活动”，赢现金大奖！</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<A 
class=textIcon href="http://my.blog.sina.com.cn/member/signup/reg_step1.php" 
target=_blank>注册</A>┆<A class=textIcon id=login title="" 
href="http://my.blog.sina.com.cn/login/login_top.php" 
target=systemIframe>登录</A>┆<A class=textIcon id=newArticle 
title=发博文参加“我记录”活动，赢取大奖 
href="http://my.blog.sina.com.cn/writing/scriber/article_add.php?mode=1" 
target=_blank>发表文章</A> </DIV></DIV>
<SCRIPT type=text/javascript>		var isCommentAllowedBySystem = true;</SCRIPT>

<UL id=articleContainer>
  <LI>&nbsp; 
  <DIV class=toggleLink id=articleBar toggle="articleContentArea">
  <DIV class=article_info><A class="toggleLink collapseArraw center" 
  id=collapseButton title=展开或收缩 href="javascript:void(0)" 
  toggle="articleContentArea"><INPUT type=button></A> <!--Class name of articleTime specify 'sun' icon or 'moon' icon					in front of date-time text. Corresponding to class name 'sun' & 'moon'					-->
  <DIV class=articleTitleW><A id=articleTitle>贪心算法解决磁盘文件最优存储问题</A> </DIV></DIV>
  <DIV id=articleBarButton><A class="Link icon modify center invisible" id=edit 
  href="javascript:void(0)">&nbsp;</A> <A 
  class="Link icon delete center invisible" id=delete 
  href="javascript:void(0)">&nbsp;</A> </DIV></DIV>
  <DIV id=articleContentArea>
  <DIV id=articleTimeHolder><SPAN class="sun icon textIcon" id=articleTime 
  style="BACKGROUND-POSITION: 2px 3px">2007-08-13 07:54:12</SPAN> </DIV>
  <DIV id=articleContentFontSize><A onclick="setArticleContentSize('b')" 
  href="javascript:%20void(0);">大</A> <A onclick="setArticleContentSize('m')" 
  href="javascript:%20void(0);" )>中</A> <A onclick="setArticleContentSize('s')" 
  href="javascript:%20void(0);" )>小</A> </DIV>
  <DIV id=tagsArea>标签：<A class=tag 
  href="http://search.blog.sina.com.cn/blog/search?q=it%2F%BF%C6%BC%BC&amp;tag=n&amp;t=tag" 
  target=_blank>it/科技</A> <A class=tag 
  href="http://search.blog.sina.com.cn/blog/search?q=%CC%B0%D0%C4%CB%E3%B7%A8&amp;tag=n&amp;t=tag" 
  target=_blank>贪心算法</A> <A class=tag 
  href="http://search.blog.sina.com.cn/blog/search?q=%B4%C5%C5%CC&amp;tag=n&amp;t=tag" 
  target=_blank>磁盘</A> </DIV>
  <DIV class=middleSize id=articleContent>
  <DIV>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">郁闷了</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">3</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">天，终于把这算法写出来了，回过头在看着算法，其实十分简单，书上的代码也是，仔细看看，那些乱七八糟的代码挺容易理解的。小弟初学算法，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">c++</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">也是半桶水，欢迎高手大虾不吝赐教。</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21.1pt; TEXT-ALIGN: center" 
  align=center><B><SPAN style="FONT-FAMILY: 宋体">贪心算法解决磁盘最优存储问题</SPAN></B></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">问题描述：</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">设磁盘上有</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">n</SPAN><SPAN style="FONT-FAMILY: 宋体">个文件，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">f1,f2,</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">…</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">,fn</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">，，每个文件占磁盘上</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">1</SPAN><SPAN style="FONT-FAMILY: 宋体">个磁道。这</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">n</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">个文件的检索概率分别是</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">p1,p2,</SPAN><SPAN style="FONT-FAMILY: 宋体">…</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">,pn,</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">且</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">p1+p2+</SPAN><SPAN style="FONT-FAMILY: 宋体">…</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">+pn<SPAN>&nbsp;&nbsp;</SPAN> =1</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">。磁头从当前磁道移到被检信息磁道所需的时间可用这</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">2<SPAN>&nbsp;&nbsp;</SPAN></SPAN> <SPAN 
  style="FONT-FAMILY: 宋体">个磁道之间的径向距离来度量。如果文件</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">pi</SPAN><SPAN style="FONT-FAMILY: 宋体">存放在第</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">i</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">道上</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">,<SPAN>&nbsp;&nbsp;</SPAN></SPAN> <SPAN 
  style="FONT-FAMILY: 宋体">，则检索这</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">n<SPAN>&nbsp;&nbsp;</SPAN></SPAN> <SPAN 
  style="FONT-FAMILY: 宋体">个文件的期望时间是，</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">sum(</SPAN><SPAN style="FONT-FAMILY: 宋体">　</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">pi*pj*d(i,j)</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">　</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">),</SPAN><SPAN style="FONT-FAMILY: 宋体">其中</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">1&lt;=i&lt;j&lt;=n</SPAN> <SPAN 
  style="FONT-FAMILY: 宋体">，</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">d(I,j)</SPAN><SPAN style="FONT-FAMILY: 宋体">是第</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">i</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">道与第</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">j</SPAN><SPAN style="FONT-FAMILY: 宋体">道之间的径向距离</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">|i-j|</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">。</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US"><SPAN>&nbsp;</SPAN></SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">思路：</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">如何确定这</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">n<SPAN>&nbsp;&nbsp;</SPAN></SPAN> <SPAN 
  style="FONT-FAMILY: 宋体">个文件在磁盘上的存储位置，使期望检索时间达到最小。设计一个解此问题的算法，并分析算法的正确性与计算复杂性。</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">如果对任何</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">i</SPAN><SPAN style="FONT-FAMILY: 宋体">，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">j</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">，当</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">i&lt;&gt;j</SPAN><SPAN style="FONT-FAMILY: 宋体">时，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">pi&lt;&gt;pj</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">，则</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">n</SPAN><SPAN style="FONT-FAMILY: 宋体">个文件在磁盘上将有</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">N!</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">种不同的存储方式。如果考虑到</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">f1</SPAN><SPAN style="FONT-FAMILY: 宋体">，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">f2</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">……</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">fn</SPAN><SPAN style="FONT-FAMILY: 宋体">，这种排列方式与</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">fn</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">……</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">f1</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">排列的期望检索时间相等，则要计算</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">n!/2</SPAN><SPAN style="FONT-FAMILY: 宋体">种不同的盘列方式。</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">对于指定的</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">i</SPAN><SPAN style="FONT-FAMILY: 宋体">和</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">j</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">，</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">pi</SPAN><SPAN style="FONT-FAMILY: 宋体">和</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">pj</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">是不变的，可变因子是</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">d(i,j),</SPAN><SPAN style="FONT-FAMILY: 宋体">如果将</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">d(i,j)</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">视为一个元素恒定的集合，则他们与排列顺序无关。</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">采用谈心算法将文件</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">f1</SPAN><SPAN style="FONT-FAMILY: 宋体">放到中心磁道上，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">f2</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">，</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">f3</SPAN><SPAN style="FONT-FAMILY: 宋体">分别靠着</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">f1</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">的左右磁道，</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">f4</SPAN><SPAN style="FONT-FAMILY: 宋体">在</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">f2</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">右边……应该是最佳方案。</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN 
  style="FONT-FAMILY: 宋体">简单</SPAN><SPAN lang=EN-US 
  XML:LANG="EN-US">C++</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">算法代码：时间复杂度为nlogn</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN lang=EN-US 
  XML:LANG="EN-US">void GreedySearch(int n,double* p,int&amp; x)</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN lang=EN-US 
  XML:LANG="EN-US">{//p</SPAN><SPAN style="FONT-FAMILY: 宋体">为概率，</SPAN><SPAN 
  lang=EN-US XML:LANG="EN-US">x</SPAN><SPAN 
  style="FONT-FAMILY: 宋体">作为文件排列结果</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN lang=EN-US 
  XML:LANG="EN-US"><SPAN>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN> int 
  k[];</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN lang=EN-US 
  XML:LANG="EN-US"><SPAN>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN> int 
  r,l;</SPAN></P>
  <P class=MsoNormal style="TEXT-INDENT: 21pt"><SPAN lang=EN-US 
  XML:LANG="EN-US"><SPAN>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN></SPAN> 
  <SPAN style="FONT-FAMILY: 宋体">将</SPAN><SPAN lang=EN-US
123

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -