演算法描述例題
① 10分求動態規劃演算法的形式化描述
動態規劃演算法沒有一個能表示所有情況的為代碼，動態規劃是解決多階段決策最優化問題的一種思想方法，萬能偽代碼估計很難說出來。
使用動態規劃的動機有兩種，一種是利用遞歸的重疊子問題進行記憶化求解，這樣的問題一般有比較明顯的遞歸特性，利用遞歸求解後可以發現其中重疊計算的部分，利用重疊子問題轉化成動態規劃。還有一種是多階段決策，所謂決策就對應著狀態轉移。多階段最優決策問題也就是使得最後的轉移是最優的，對於滿足最優子結構和無後效性的問題，都可以分析第i
個狀態到i+1狀態轉移的決策，而且這個決策應該是所有可以選的決策中最優的，這就是動態規劃更直觀的想法。
有這么一種取巧的方法，如果一個題目說明可以採用動態規劃的話，而你卻沒有動態規劃的思路，可以首先考慮用遞歸的方法來求解，一旦有了遞歸的思路來解決他，那麼一定能夠通過逆推求出動態規劃的演算法。
比如
例題1，已知兩個字元串，長為L，求他們的最長的公共子串。'abacad'和'bcaaca'的最長公共子串竄就是'baca'
如果題目要求用動態規劃求解，很可能根本沒有思路，但是考慮用遞歸怎麼能解決這個問題呢？
比較A[1...L]和B[1...L]這兩個字元串的公共子串是不是可以變成求A[1...L-1]和B[1...L-1]的公共子串呢？貌似可以，但是好像少考慮情況了，還應該包括A[1...L]和B[1...L-1]的公共子串以及A[1...L-1]和B[1...L]這兩種情況呀。這樣就分析出了遞歸的子結構。而這個遞歸的子結構就是動態規劃的基礎。
考慮 如果A〔L〕＝＝B〔L〕那麼 LCS( A[1...L] , B[1...L]) = LCS( A[1...L-1], B[1...L-1] ) + 1
否則 LCS( A[1...L] , B[1...L]) =MAX (LCS( A[1...L-1], B[1...L] )，LCS( A[1...L], B[1...L－1] ))
這樣就由遞推的演算法得到動態規劃的狀態轉移方程了。有了狀態轉移方程，動態規劃演算法就變成了一個添矩陣演算法了，這個偽代碼還是很簡單的。
② 請教一道數據結構的演算法題演算法具體描述如下： 設以帶頭結點的雙向循環鏈表L=（a1,a2,....,an).試寫一個時
有兩種思想供參考：（1）
整體思想
（2）化整為零
先來說說整體思想，我們可以發現序號為奇數的元素的前後相對位置未變，只是偶數位置有變化。這樣的話，我們可以將偶數按序號
逆序
（由大到小）插入到
鏈表
尾部。考慮到
時間復雜度
問題，在搜索偶數的過程中，可以先找到最大的偶數序號+1的位置（是個奇數，奇數相對位置不動），記下它的位置為L，L向前指的那個位置是偶數位置。這樣再找下一個時，直接用L-2，直至k-2等於3為止即可找到所有序號為偶數的位置。
怎麼化整為零呢？先來看看下面這個過程：
null
1
2
（1是從head的後面插入鏈表，2是從tail的前面插入鏈表）
1
3
2
（3是從1的後面插入鏈表）
1
3
4
2（4是從2的前面插入鏈表）
1
3
5
4
2（5是從3的後面插入鏈表）
......
1
3
5
...
n
...
6
4
2
由此，我們可以設置2個指針p，q，分別指向剛剛序號為奇數的元素插入的位置和剛剛序號為奇數的元素插入的位置，下一個序號為奇數的元素插入到p後，為偶數的插入到q前，並隨著插入的過程實時變化p，q，最後再將q和q指向的元素之間的2個指針接上就OK了。
程序交給你來寫吧，應該不太難。
③ 求c語言演算法例題祥解。
給你下一個中文的框架
開始肯定是
while(第一個判斷) //就是年份2000到2500
{
if(第一個判斷條件) //能被4整除
{
if(第二個判斷條件) //不能被100整除
{
s6；
}
else //不能被100整除的
if(第三個判斷) //能被400整除的
{
s6；
}
}
else
{ s5； } //這里就是你所指的s5 當前面的判斷都不成立時 他就會到這
}
這是具體思路 要是要代碼的話再寫。
④ 秦九韶演算法例題大全
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次,其中乘法有連續兩次相乘
⑤ 演算法時間復雜度的計算例題
第一題：
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);
⑥ c語言問題： 什麼是演算法試從日常生活中找3個例子，描述它們的演算法。 詳細點，謝謝！
c語言中的演算法是指：一系列解決問題的清晰指令，用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。通俗說就是解決問題的方法和步驟。
描述演算法的例子：
問題：從上海去到北京。
其中的演算法：做汽車、做飛機、或者徒步。
問題：喝茶。
其中的演算法：先找到茶葉，再燒一壺開水，然後將茶葉放到杯子里，將開水倒入杯中，等茶葉泡好。
問題：開車。
其中的演算法：首先要打開車門，駕駛員坐好，插上車鑰匙，發動汽車。
⑦ 演算法題目描述：編程： 定義兩個大於2的偶數之間的距離，為這兩個數之間質數的個數。
演算法如下：
package fileTest;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class ZhiShu {
public static boolean t(int n) {
boolean t = true;
if(n!=1){
for(int i = 2;i<=n/2;i++)
{
if (n%i != 0){
t = true;}
else{
t = false;
break;
}
}
}else {t = false;}
return t;
}
public static void main(String[] args) {
while(true){
System.out.println("結束計算輸入：0");
Scanner sc=new Scanner(System.in);
System.out.println("請輸入你需要計算的偶數個數");
int n=sc.nextInt();
if(n==0){
break;
}
Map<Integer,Integer> map=new LinkedHashMap<Integer, Integer>();
for(int i=0;i<n;i++){
System.out.println("請輸入第"+(i+1)+"個偶數");
int m=sc.nextInt();
if(i!=0){
if(m%2!=0||m<4||m<=map.get(i-1)){
i--;
System.out.println("輸入的不是大於4的偶數或者小於上一次輸入數字，請重新輸入！");
continue;
}
}
map.put(i, m);
}
Set<Integer> set = map.keySet();
System.out.println("你輸入的偶數為：");
for(int i:set){
System.out.print(map.get(i)+",");
}
System.out.println("");
int count=0;
for(int i=0;i<map.size();i++){
for(int j=1;j<=map.size()-i-1;j++){
int a=map.get(i);
int b=map.get(i+j);
for(int m=1;m<b-a;m++){
int c=a+m;
if(t(c)){
count++;
}
}
}
}
System.out.println("距離之和為："+count);
}
}
}
⑧ 第12題： 以下對演算法描述不正確的是_____。
你好！
很顯然
第三個是錯的
演算法是你解決一個題目,如何去解題的思路總稱.
是步驟的集合.
例如我們要給班上10個人每人一個蘋果.
那麼可以有這樣一種演算法.將這10人編號1到10,從1發到10,每人一個蘋果.
你可能覺得這是什麼思路,但如果這要讓計算機實現呢~你如果安排計算機去做呢~~就得使用某種演算法~例如我剛才說的.
如有疑問，請追問。
⑨ 貪心演算法的例題分析
例題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就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。