?? online judge論壇-acm-icpc-[第10篇]acm-icpc競賽之算法策略.htm
字號:
case 10 :
if(dd>=24){return('<img src=Skins/Default/birth/z8.gif alt=天蝎座'+mm+'-'+dd+'>');}
else{return('<img src=Skins/Default/birth/z7.gif alt=天秤座'+mm+'-'+dd+'>');}
break;
case 11 :
if(dd>=23){return('<img src=Skins/Default/birth/z9.gif alt=射手座'+mm+'-'+dd+'>');}
else{return('<img src=Skins/Default/birth/z8.gif alt=天蝎座'+mm+'-'+dd+'>');}
break;
case 12 :
if(dd>=22){return('<img src=Skins/Default/birth/z10.gif alt=魔羯座'+mm+'-'+dd+'>');}
else{return('<img src=Skins/Default/birth/z9.gif alt=射手座'+mm+'-'+dd+'>');}
break;
default : return('');
}
}else{return('');}
}
function usercolor(UserGroupID,UserName)
{
UserGroupID = parseInt(UserGroupID);
var UserNameStyle=GroupUserName[UserGroupID].split("§");
return(UserNameStyle[0]+UserName+UserNameStyle[1]);
}
</script>
<a name="156" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema"></a><table cellPadding="5" cellSpacing="1" align="center" class="tableborder1" style="table-layout:fixed;word-break:break-all" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema">
<tr>
<td class="tablebody1" valign="top" width="175">
<table width="100%" cellpadding="4" cellspacing="0">
<tr>
<td width="*" valign="middle" style="filter:glow(color=#9898BA,strength=2)"> <script type="text/javascript" language="javascript">document.write (usercolor('1','Teacher彭'));</script></td>
<td width="25" valign="middle"><img src="Skins/Default/ofMale.gif" alt="帥哥喲，離線，有人找我嗎？"></td>
<td width="16" valign="middle"><script type="text/javascript" language="javascript">document.write (astro(''));</script></td>
</tr>
</table> <img src="Images/userface/image1.gif" width="32" height="32"><br> <img src="Skins/Default/star/level20.gif"><br> 等級：管理員<br> 文章：801<br> 積分：6804<br> 注冊：2005-09-02</td>
<td class="tablebody1" valign="top" height="100%">
<table width="100%" height="30">
<tr>
<td width="*" align="absmiddle"><a href="http://wpa.qq.com/msgrd?V=1&Uin=515957164&Site=By Dvbbs&Menu=yes" title="點擊發送QQ消息給Teacher彭" target="_blank"><img src="http://wpa.qq.com/pa?p=1:515957164:4" border="0" width="16" height="16" align="absmiddle"></a> <a href="http://wpa.qq.com/msgrd?V=1&Uin=515957164&Site=By Dvbbs&Menu=yes" title="點擊發送QQ消息給Teacher彭">QQ</a> <a href="messanger.asp?action=new&touser=Teacher%C5%ED" target="_blank"><img src="Skins/Default/message.gif" border="0" alt="給Teacher彭發送一個短消息" align="absmiddle"></a> <a href="friendlist.asp?action=addF&myFriend=Teacher%C5%ED" target="_blank"><img src="Skins/Default/friend.gif" border="0" alt="把Teacher彭加入好友" align="absmiddle"></a> <a href="dispuser.asp?id=2" target="_blank"><img src="Skins/Default/profile.gif" border="0" alt="查看Teacher彭的個人資料" align="absmiddle"></a> <a href="query.asp?stype=1&nSearch=3&keyword=Teacher%C5%ED&BoardID=9&SearchDate=ALL" target="_blank"><img src="Skins/Default/find.gif" border="0" alt="搜索Teacher彭在的所有貼子" align="absmiddle"></a> <a href="mailto:pengsw@mail.buct.edu.cn"><img alt="點擊這里發送電郵給Teacher彭" border="0" src="Skins/Default/email.gif" align="absmiddle"></a> <a href="http://coder.buct.edu.cn" target="_blank"><img alt="訪問Teacher彭的主頁" border="0" src="Skins/Default/homepage.gif" align="absmiddle"></a><a href="post.asp?action=re&BoardID=9&replyID=156&id=44&star=1&reply=true"><img src="Skins/Default/reply.gif" border="0" alt="引用回復這個貼子" align="absmiddle"></a> <a href="post.asp?action=re&BoardID=9&replyID=156&id=44&star=1"><img src="Skins/Default/reply_a.gif" border="0" alt="回復這個貼子" align="absmiddle"></a></td>
<td width="70" align="right"> 樓主</td>
</tr>
<tr>
<td height="1" colspan="3" class="singleborder"></td>
</tr>
<tr>
<td height="2" colspan="3"></td>
</tr>
</table>
<table border="0" align="center" width="95%" height="85%" style="table-layout:fixed;word-break:break-all">
<tr>
<td width="*" height="100%" style="font-size:9pt;line-height:12pt" valign="top"><img src="Skins/Default/topicface/face1.gif" border="0" alt="發貼心情" align="absmiddle"> <B>[第10篇]ACM/ICPC競賽之算法策略</B><BR><H1 align=center>第10篇 ACM/ICPC競賽之算法策略</H1><P>ACM/ICPC競賽其實就是算法設計和編碼的競賽，熟悉各種常用算法和算法設計策略并能靈活運用是非常必要的。</P><P>這里對幾種在競賽中經常用到的算法設計策略做一簡單的介紹。</P><H2>1、窮舉法</H2><P>窮舉法是最基本的算法設計策略，其思想是列舉出問題所有的可能解，逐一進行判別，找出滿足條件的解。</P><P>窮舉法的運用關鍵在于解決兩個問題：</P><P>如何列舉所有的可能解；</P><P>如何判別可能解是否滿足條件；</P><P>在運用窮舉法時，容易出現的問題是可能解過多，導致算法效率很低，這就需要對列舉可能解的方法進行優化。</P><P>以題1041--純素數問題為例，從1000到9999都可以看作是可能解，可以通過對所有這些可能解逐一進行判別，找出其中的純素數，但只要稍作分析，就會發現其實可以大幅度地降低可能解的范圍。根據題意易知，個位只可能是3、5、7，再根據題意可知，可以在3、5、7的基礎上，先找出所有的二位純素數，再在二位純素數基礎上找出三位純素數，最后在三位純素數的基礎上找出所有的四位純素數。</P><H2>2、分治法</H2><P>分治法也是應用非常廣泛的一種算法設計策略，其思想是將問題分解為若干子問題，從而可以遞歸地求解各子問題，再綜合出問題的解。</P><P>分治法的運用關鍵在于解決三個問題：</P><P>確定分治規則，即如何分解問題。</P><P>確定終結條件，即問題分解到什么狀態時可以直接求解。</P><P>確定歸納方法，即如何由子問題的解得到原問題的解。這一步并不總是需要的，因為對某些問題來說，并不需要對子問題的解進行復雜的歸納。</P><P>我們熟知的如漢諾塔問題、折半查找算法、快速排序算法等都是分治法運用的典型案例。</P><P>以題1045--Square Coins為例，先對題意進行分析，可設一個函數f(m, n)等于用面值不超過n<SUP>2</SUP>的貨幣構成總值為m的方案數，則容易推導出：</P><P>f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1) <br>這里的k是幣值為n<SUP>2</SUP>的貨幣最多可以用多少枚，即k=m/(n*n)。</P><P>也很容易分析出，f(m, 1) = f(1, n) = 1</P><P>對于這樣的題目，一旦分析出了遞推公式，程序就非常好寫了。所以在動手開始寫程序之前，分析工作做得越徹底，邏輯描述越準確、簡潔，寫起程序來就會越容易。</P><H2>3、動態規劃法</H2><P>動態規劃法多用來計算最優問題，動態規劃法與分治法的基本思想是一致的，但處理的手法不同。動態規劃法在運用時，要先對問題的分治規律進行分析，找出終結子問題，以及子問題向父問題歸納的規則，而算法則直接從終結子問題開始求解，逐層向上歸納，直到歸納出原問題的解。</P><P>動態規劃法多用于在分治過程中，子問題可能重復出現的情況，在這種情況下，如果按照常規的分治法，自上向下分治求解，則重復出現的子問題就會被重復地求解，從而增大了冗余計算量，降低了求解效率。而采用動態規劃法，自底向上求解，每個子問題只計算一次，就可以避免這種重復的求解了。</P><P>動態規劃法還有另外一種實現形式，即備忘錄法。備忘錄的基本思想是設立一個稱為備忘錄的容器，記錄已經求得解的子問題及其解。仍然采用與分治法相同的自上向下分治求解的策略，只是對每一個分解出的子問題，先在備忘錄中查找該子問題，如果備忘錄中已經存在該子問題，則不須再求解，可以從備忘錄中直接得到解，否則，對子問題遞歸求解，且每求得一個子問題的解，都將子問題及解存入備忘錄中。</P><P>例如，在題1045--Square Coins中，可以采用分治法求解，也可以采用動態規劃法求解，即從f(m, 1)和f(1, n)出發，逐層向上計算，直到求得f(m, n)。</P><P>在競賽中，動態規劃和備忘錄的思想還可以有另一種用法。有些題目中的可能問題數是有限的，而在一次運行中可能需要計算多個測試用例，可以采用備忘錄的方法，預先將所有的問題的解記錄下來，然后輸入一個測試用例，就查備忘錄，直接找到答案輸出。這在各問題之間存在父子關系的情況下，會更有效。例如，在題1045--Square Coins中，題目中已經指出了最大的目標幣值不超過300，也就是說問題數只有300個，而且各問題的計算中存在重疊的子問題，可以采用動態規劃法，將所有問題的解先全部計算出來，再依次輸入測試用例數據，并直接輸出答案。</P><H2>4、回溯法</H2><P>回溯法是基于問題狀態樹搜索的求解法，其可適用范圍很廣。從某種角度上說，可以把回溯法看作是優化了的窮舉法。回溯法的基本思想是逐步構造問題的可能解，一邊構造，一邊用約束條件進行判別，一旦發現已經不可能構造出滿足條件的解了，則退回上一步構造過程，重新進行構造。這個退回的過程，就稱之為“回溯”。</P><P>回溯法在運用時，要解決的關鍵問題在于：</P><P>如何描述局部解。</P><P>如何擴展局部解和回溯局部解。</P><P>如何判別局部解。</P><P>回溯法的經典案例也很多，例如全排列問題、N后問題等。</P><H2>5、貪心法</H2><P>貪心法也是求解最優問題的常用算法策略，利用貪心法策略所設計的算法，通常效率較高，算法簡單。貪心法的基本思想是對問題做出目前看來最好的選擇，即貪心選擇，并使問題轉化為規模更小的子問題。如此迭代，直到子問題可以直接求解。</P><P>基于貪心法的經典算法例如：哈夫曼算法、最小生成樹算法、最短路徑算法等。</P><P>但是，貪心法的運用是有條件的，必須能夠證明貪心選擇能夠導出最優解，且轉化出的子問題與原問題是同性質的問題，才能使用貪心法求解。</P><P>一個比較經典的貪心法求解的問題就是找硬幣問題：有1、2、5、10、20、50、100七種面值的硬幣，要支付指定的金額，問怎么支付所用的硬幣個數最少。這是一個非常日常化的問題，憑直覺我們會想到，盡可能先用大面值的硬幣，這就是“貪心選擇”，而在這個問題上，這個貪心選擇也是正確的。</P><H2>6、限界剪枝法</H2><P>限界剪枝法是求解較復雜最優問題的一種算法策略，與回溯法類似的是，限界剪枝法也是在問題狀態空間樹上進行搜索，但回溯法是搜索一般解，而限界剪枝法則是搜索最優解。限界剪枝法的基本思想是通過找出權值函數的上下界函數，以下界函數來指導搜索的方向，以上界函數來幫助剪除一些不可能含有最優解的分枝。</P><P>關于算法和算法策略的討論是一個非常龐大的話題，幾乎每個問題點都能擴展出一大堆可討論的內容和案例。我實在不知道該怎樣用簡短的幾篇文字就能夠把這個話題說透，這里只能蜻蜓點水地對競賽中經常用到的幾種策略做一極為簡略的介紹。</P><P>也許我們可以在以后的文章中，針對具體的題目進行算法和策略的分析，效果可能會更好。</P><br><div align=right><font color=#000066>[此貼子已經被作者于2005-10-6 21:04:54編輯過]</font></div></td>
</tr>
<tr><td><img src="Skins/Default/sigline.gif"><br>☆ Teacher 彭 ☆</td></tr>
<tr><td>
<div class="info"><img src="Skins/Default/jing.gif" border="0" title="本貼被加為精華" align="absmiddle"> </div>
</td></tr>
</table>
</td>
</tr>
<tr>
<td class="tablebody1" valign="middle" align="center" width="175"><img align="absmiddle" border="0" src="Skins/Default/ip.gif" alt="發貼IP已設置保密"> 2005-10-06 20:41</td>
<td class="tablebody1" valign="middle" width="*">
<table width="100%" cellpadding="0" cellspacing="0">
<tr>
<td valign="middle" align="left" width="*"> </td>
<td nowarp="true" valign="bottom" width="130" align="left"></td>
<td valign="middle" width="170" align="right"><a href="post.asp?action=edit&BoardID=9&replyID=156&ID=44&star=1"><img align="absmiddle" border="0" src="Skins/Default/edit.gif"></a> <a class="ImgOnclick" onMouseOver="showmenu(event,'','Menu_0');"><img align="absmiddle" border="0" src="Skins/Default/topicmanage.gif"></a> <a href="#top"><img align="absmiddle" border="0" src="Skins/Default/p_up.gif"></a></td>
<td valign="middle" align="left">
</td>
</tr>
</table>
</td>
</tr>
</table>
<div class="Menu_popup" id="Menu_0" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema">
<div class="menuitems"><a href="TopicOther.asp?t=6&BoardID=9&id=44&ReplyID=156" title="向管理員舉報該貼">舉報帖子</a><BR><a href="admin_postings.asp?action=copy_a&BoardID=9&replyID=156&ID=44&star=1&userid=2">復制貼子</a><BR><a href="admin_postings.asp?action=nobest_a&BoardID=9&replyID=156&ID=44&star=1&userid=2">解除精華</a><BR><a href="admin_postings.asp?action=islockpage_a&BoardID=9&replyID=156&ID=44&star=1&userid=2">單貼屏蔽</a><BR><a href="admin_postings.asp?action=RewardMoney&BoardID=9&replyID=156&ID=44&star=1" title="好評或差評，可獎勵或扣除該貼用戶相關分值">帖子評價</a><BR></div></div><a name="165" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema"></a><table cellPadding="5" cellSpacing="1" align="center" class="tableborder1" style="table-layout:fixed;word-break:break-all" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema">
<tr>
<td class="tablebody2" valign="top" width="175">
<table width="100%" cellpadding="4" cellspacing="0">
<tr>
<td width="*" valign="middle" style="filter:glow(color=white,strength=2)"> <script type="text/javascript" language="javascript">document.write (usercolor('9','bearscafe'));</script></td>
<td width="25" valign="middle"><img src="Skins/Default/ofMale.gif" alt="帥哥喲，離線，有人找我嗎？"></td>
<td width="16" valign="middle"><script type="text/javascript" language="javascript">document.write (astro(''));</script></td>
</tr>
</table> <img src="Images/userface/image1.gif" width="32" height="32"><br> <img src="Skins/Default/star/level0.gif"><br> 等級：新手上路<br> 文章：1<br> 積分：65<br> 注冊：2005-10-06</td>
<td class="tablebody2" valign="top" height="100%">
<table width="100%" height="30">
<tr>
<td width="*" align="absmiddle"><a href="messanger.asp?action=new&touser=bearscafe" target="_blank"><img src="Skins/Default/message.gif" border="0" alt="給bearscafe發送一個短消息" align="absmiddle"></a> <a href="friendlist.asp?action=addF&myFriend=bearscafe" target="_blank"><img src="Skins/Default/friend.gif" border="0" alt="把bearscafe加入好友" align="absmiddle"></a> <a href="dispuser.asp?id=88" target="_blank"><img src="Skins/Default/profile.gif" border="0" alt="查看bearscafe的個人資料" align="absmiddle"></a> <a href="query.asp?stype=1&nSearch=3&keyword=bearscafe&BoardID=9&SearchDate=ALL" target="_blank"><img src="Skins/Default/find.gif" border="0" alt="搜索bearscafe在的所有貼子" align="absmiddle"></a> <a href="mailto:bearscafe@163.com"><img alt="點擊這里發送電郵給bearscafe" border="0" src="Skins/Default/email.gif" align="absmiddle"></a> <a href="post.asp?action=re&BoardID=9&replyID=165&id=44&star=1&reply=true"><img src="Skins/Default/reply.gif" border="0" alt="引用回復這個貼子" align="absmiddle"></a> <a href="post.asp?action=re&BoardID=9&replyID=165&id=44&star=1"><img src="Skins/Default/reply_a.gif" border="0" alt="回復這個貼子" align="absmiddle"></a></td>
<td width="70" align="right">第 <font color="#FF0000">2</font> 樓</td>
</tr>
<tr>
<td height="1" colspan="3" class="singleborder"></td>
</tr>
<tr>
<td height="2" colspan="3"></td>
</tr>
</table>
<table border="0" align="center" width="95%" height="85%" style="table-layout:fixed;word-break:break-all">
<tr>
<td width="*" height="100%" style="font-size:9pt;line-height:12pt" valign="top"><img src="Skins/Default/topicface/face1.gif" border="0" alt="發貼心情" align="absmiddle"> <B></B><BR><P>終于坐到沙發了~~~~</P><P>老師最好能多給些經典題目的分析講解阿</P><P>~~</P><img src=Skins/Default/emot/em05.gif border=0 align=middle onmousewheel="return bbimg(this)" onload="javascript:if(this.width>screen.width-500)this.style.width=screen.width-500;"></td>
</tr>
<tr><td>
</td></tr>
</table>
</td>
</tr>
<tr>
<td class="tablebody2" valign="middle" align="center" width="175"><img align="absmiddle" border="0" src="Skins/Default/ip.gif" alt="發貼IP已設置保密"> 2005-10-06 23:03</td>
<td class="tablebody2" valign="middle" width="*">
<table width="100%" cellpadding="0" cellspacing="0">
<tr>
<td valign="middle" align="left" width="*"> </td>
<td nowarp="true" valign="bottom" width="130" align="left"></td>
<td valign="middle" width="170" align="right"><a href="post.asp?action=edit&BoardID=9&replyID=165&ID=44&star=1"><img align="absmiddle" border="0" src="Skins/Default/edit.gif"></a> <a class="ImgOnclick" onMouseOver="showmenu(event,'','Menu_1');"><img align="absmiddle" border="0" src="Skins/Default/topicmanage.gif"></a> <a href="#top"><img align="absmiddle" border="0" src="Skins/Default/p_up.gif"></a></td>
<td valign="middle" align="left">
</td>
</tr>
</table>
</td>
</tr>
</table>
<div class="Menu_popup" id="Menu_1" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema">
<div class="menuitems"><a href="TopicOther.asp?t=6&BoardID=9&id=44&ReplyID=165" title="向管理員舉報該貼">舉報帖子</a><BR><a href="admin_postings.asp?action=dele_a&BoardID=9&replyID=165&ID=44&star=1&userid=88">刪除單貼</a><BR><a href="admin_postings.asp?action=copy_a&BoardID=9&replyID=165&ID=44&star=1&userid=88">復制貼子</a><BR><a href="admin_postings.asp?action=isbest_a&BoardID=9&replyID=165&ID=44&star=1&userid=88">加為精華</a><BR><a href="admin_postings.asp?action=islockpage_a&BoardID=9&replyID=165&ID=44&star=1&userid=88">單貼屏蔽</a><BR><a href="admin_postings.asp?action=RewardMoney&BoardID=9&replyID=165&ID=44&star=1" title="好評或差評，可獎勵或扣除該貼用戶相關分值">帖子評價</a><BR></div></div><a name="168" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema"></a><table cellPadding="5" cellSpacing="1" align="center" class="tableborder1" style="table-layout:fixed;word-break:break-all" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema">
<tr>
<td class="tablebody1" valign="top" width="175">
<table width="100%" cellpadding="4" cellspacing="0">
<tr>
<td width="*" valign="middle" style="filter:glow(color=#9898BA,strength=2)"> <script type="text/javascript" language="javascript">document.write (usercolor('1','XiaoLin'));</script></td>
<td width="25" valign="middle"><img src="Skins/Default/ofMale.gif" alt="帥哥喲，離線，有人找我嗎？"></td>
<td width="16" valign="middle"><script type="text/javascript" language="javascript">document.write (astro('1982-10-12'));</script></td>
</tr>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -