演算法例題
❶ 這個演算法與數據結構的例題是什麼意思
能按步驟給我剖析一下它每一步原理嗎?越詳細越好,謝謝?
❷ 回溯演算法的典型例題
八皇後問題:在8×8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即任意兩個皇後都不能處於同一行、同一列或同一斜線上,問有多少種擺法。
❸ 演算法時間復雜度的計算例題
第一題:
int i=1,k=100這條語句演算法步數是2步,執行頻率是1;
循環中, k=k+1;這條語句每次演算法步數是1;執行頻率是n/2-1; i+=2這條語句每次演算法步數是1;執行頻率是n/2-1;
所以演算法復雜度為1*(n/2-1)+1*(n/2-1)+2=n=o(n);
❹ 關於計算機編程的。編寫演算法!題目如下圖。各位大神們,幫幫忙!跪謝了!!!
拿兩組三個球用天平秤,如果天平平衡,那麼壞球在沒秤的里,拿其中的兩個再稱,還平衡就是沒稱的,把沒稱的和其中一個稱就知道是輕還是重了。如果第二次不平,那麼再稱一次也就知道了。如果第一次就不平那麼記一下輕重和沒稱的再稱。編程的話就是算重量和進行比較大小!思路一樣的
❺ 貪心演算法的例題分析
例題1、
[0-1背包問題]有一個背包,背包容量是M=150。有7個物品,物品不可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大,但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析:
目標函數:∑pi最大
約束條件是裝入的物品總重量不超過背包容量:∑wi<=M(M=150)
⑴根據貪心的策略,每次挑選價值最大的物品裝入背包,得到的結果是否最優?
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解?
⑶每次選取單位重量價值最大的物品,成為解本題的策略。
值得注意的是,貪心演算法並不是完全不可以使用,貪心策略一旦經過證明成立後,它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一,這是由於它簡單易行,構造貪心策略不是很困難。
可惜的是,它需要證明後才能真正運用到題目的演算法中。
一般來說,貪心演算法的證明圍繞著:整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略,都是無法成立(無法被證明)的,解釋如下:
⑴貪心策略:選取價值最大者。
反例:
W=30
物品:A B C
重量:28 12 12
價值:30 20 20
根據策略,首先選取物品A,接下來就無法再選取了,可是,選取B、C則更好。
⑵貪心策略:選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略:選取單位重量價值最大的物品。
反例:
W=30
物品:A B C
重量:28 20 10
價值:28 20 10
根據策略,三種物品單位重量價值一樣,程序無法依據現有策略作出判斷,如果選擇A,則答案錯誤。
【注意:如果物品可以分割為任意大小,那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略,可以再加一條優化的規則:對於單位重量價值一樣的,則優先選擇重量小的!這樣,上面的反例就解決了。
但是,如果題目是如下所示,這個策略就也不行了。
W=40
物品:A B C
重量:25 20 15
價值:25 20 15
附:本題是個DP問題,用貪心法並不一定可以求得最優解,以後了解了動態規劃演算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上,從任意指定方格出發,為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題,運用深度優先搜索進行求解。演算法如下:
⒈ 輸入初始位置坐標x,y;
⒉ 步驟 c:
如果c> 64輸出一個解,返回上一步驟c--
(x,y) ← c
計算(x,y)的八個方位的子結點,選出那些可行的子結點
循環遍歷所有可行子結點,步驟c++重復2
顯然⑵是一個遞歸調用的過程,大致如下:
C++程序: #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八個方位子結點ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調用s[tx][ty]=0;}}Pascal程序: ProgramYS;ConstFXx:array[1..8]of-2..2=(1,2,2,1,-1,-2,-2,-1);FXy:array[1..8]of-2..2=(2,1,-1,-2,-2,-1,1,2);VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1)and(Ny=y1)Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1);{讀入結束坐標}If(x>10)or(y>10)or(x1>10)or(y1>10)Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的,它輸入的是全部解,但是馬遍歷當8×8時解是非常之多的,用天文數字形容也不為過,這樣一來求解的過程就非常慢,並且出一個解也非常慢。
怎麼才能快速地得到部分解呢?
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出,且早在1823年,J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時,優先選擇『出口』最小的進行搜索,『出口』的意思是在這些子結點中它們的可行子結點的個數,也就是『孫子』結點越少的越優先跳,為什麼要這樣選取,這是一種局部調整最優的做法,如果優先選擇出口多的子結點,那出口少的子結點就會越來越多,很可能出現『死』結點(顧名思義就是沒有出口又沒有跳過的結點),這樣對下面的搜索純粹是徒勞,這樣會浪費很多無用的時間,反過來如果每次都優先選擇出口少的結點跳,那出口少的結點就會越來越少,這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法,也叫貪婪演算法或啟發式演算法,它對整個求解過程的局部做最優調整,它只適用於求較優解或者部分解,而不能求最優解。這樣的調整方法叫貪心策略,至於什麼問題需要什麼樣的貪心策略是不確定的,具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高,如果只要求出一個解甚至不用回溯就可以完成,因為在這個演算法提出的時候世界上還沒有計算機,這種方法完全可以用手工求出解來,其效率可想而知。
❻ 秦九韶演算法例題大全
f(x)=x^6+2x^5+3x^4+5x^2+6x+7
=x(x^5+2x^4+3x^3+5x+6)+7
=x(x(x^4+2x^3+3x^2+5)+6)+7
=x(x(x*x(x^2+2x+3)+5)+6)+7
=x(x(x*x(x(x+2)+3)+5)+6)+7
加法與乘法各5次,其中乘法有連續兩次相乘
❼ 如何理解分治演算法及相關例題
演算法步驟:
1 :從左上角起,給棋盤編號(1,1),(1,2)(8,8),計為集合qp。tracks記錄走過的每個點. (可以想像為坐標(x,y))
2:設起點為(1,1),記為 當前位置 cp,
3:搜索所有可走的下一步,根據「馬行日」的走步規則,可行的點的坐標是x坐標加減1,y坐標加減2,
或是x加減2,y加減1; (例如起點(1,1),可計算出(1+1,1+2),(1+1,1-2),(1-1,1+2),(1-1,1-2),(1+2,1+1),(1+2,1-1),(1-2,1+1),(1-2,1-1) 共8個點), 如果沒有搜到可行點,程序結束。
4:判斷計算出的點是否在棋盤內,即是否在集合qp中;判斷點是否已經走過,即是否在集合tracts中,不在才是合法的點。(在上面的舉例起點(1,1),則合法的下一步是(2,3)和 (3,2))
5:將前一步的位置記錄到集合tracts中,即tracts.add(cp);選擇一個可行點,cp=所選擇點的坐標。
6:如果tracts里的點個數等於63,退出程序,否則回到步驟3繼續執行。