經典的演算法題
public class Monkey
{
public static void main(String[] args)
{
int sum=0,remain=1;
//每天吃剩的桃子加一個正好是前一天桃子的一半，每天桃子的總數就是前一天剩下桃子的數量
for(int day=9;day>=1;day--)
{
sum=(remain+1)*2;
remain=sum;
System.out.println("第"+day+"天還剩"+remain+"個桃子");
}
System.out.println(sum);
}
}
『貳』 求NOI的經典題目與演算法。
皇後問題。在一個國際象棋棋盤上，放置8個皇後，使她們相互之間不能進攻(只要在一條直線上就不可，即在每一橫列豎列斜列只有一個皇後）。求出所有布局。
program eight;
var a:array [1..8] of integer;
b,c,d:array [-7..16] of integer;
t,i,j,k:integer;
procere print;
begin
t:=t+1;
write(t,' ');
for k:=1 to 8 do write(a[k],' ');
writeln;
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to 8 do {每個皇後都有8種可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突}
begin
a[i]:=j; {擺放皇後}
b[j]:=1; {宣布佔領第J行}
c[i+j]:=1; {佔領兩個對角線}
d[i-j]:=1;
if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後}
else print; {完成任務，列印結果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
for k:=-7 to 16 do {數據初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{從第1個皇後開始放置}
end.
這是深搜的內容
搜索資料：
搜 索 算 法
搜索演算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解
的一種方法。搜索過程實際上是根據初始條件和擴展規則構造一棵解答樹並尋找符合目標狀態的節點的過程。
所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分——控制結構和產生系統，而所有的算
法的優化和改進主要都是通過修改其控制結構來完成的。現在主要對其控制結構進行討論，因此對其產生系
統作如下約定：
Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;
表示對給出的節點狀態Sitution採用第ExpendWayNo種擴展規則進行擴展，並且返回擴展後的狀態。
（本文所採用的演算法描述語言為類Pascal。）
第一部分 基本搜索演算法
一、回溯演算法
回溯演算法是所有搜索演算法中最為基本的一種演算法，其採用了一種「走不通就掉頭」思想作為其控制結構，
其相當於採用了先根遍歷的方法來構造解答樹，可用於找解或所有解以及最優解。具體的演算法描述如下：
[非遞歸演算法]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Way-NO:Integer（已使用過的擴展規則的數目）;
End
<Var>
List(回溯表):Array[1..Max(最大深度)] of Node;
pos(當前擴展節點編號):Integer;
<Init>
List<-0;
pos<-1;
List[1].Situation<-初始狀態;
<Main Program>
While (pos>0(有路可走)) and ([未達到目標]) do
Begin
If pos>=Max then (數據溢出,跳出主程序);
List[pos].Way-NO:=List[pos].Way-No+1;
If (List[pos].Way-NO<=TotalExpendMethod) then (如果還有沒用過的擴展規則)
Begin
If (可以使用當前擴展規則) then
Begin
(用第way條規則擴展當前節點)
List[pos+1].Situation:=ExpendNode(List[pos].Situation,
List[pos].Way-NO);
List[pos+1].Way-NO:=0;
pos:=pos+1;
End-If;
End-If
Else Begin
pos:=pos-1;
End-Else
End-While;
[遞歸演算法]
Procere BackTrack(Situation:TSituation;deepth:Integer);
Var I :Integer;
Begin
If deepth>Max then (空間達到極限,跳出本過程);
If Situation=Target then (找到目標);
For I:=1 to TotalExpendMethod do
Begin
BackTrack(ExpendNode(Situation,I),deepth+1);
End-For;
End;
範例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發不重復的跳完棋盤上所有的點的路線。
評價：回溯演算法對空間的消耗較少，當其與分枝定界法一起使用時，對於所求解在解答樹中層次較深的問題
有較好的效果。但應避免在後繼節點可能與前繼節點相同的問題中使用，以免產生循環。
二、深度搜索與廣度搜索
深度搜索與廣度搜索的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了
所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。這兩種演算法每
次都擴展一個節點的所有子節點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個，
而廣度搜索擴展的則是本次擴展的節點的兄弟節點。在具體實現上為了提高效率,所以採用了不同的數據結構.
[廣度搜索]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Level:Integer(當前節點深度);
Last :Integer(父節點);
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:TSituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
List[1].Level:=1;
List[1].Last:=0;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
close:=close+1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Level:=List[close].Level+1;
List[open].Last:=close;
End-If
End-For;
End-While;
[深度搜索]
<Var>
Open:Array[1..Max] of Node;(待擴展節點表)
Close:Array[1..Max] of Node;(已擴展節點表)
openL,closeL:Integer;(表的長度)
New-S:Tsituation;(新狀態)
<Init>
Open<-0; Close<-0;
OpenL<-1;CloseL<-0;
Open[1].Situation<- 初始狀態;
Open[1].Level<-1;
Open[1].Last<-0;
<Main Program>
While (openL>0) and (closeL<Max) and (openL<Max) do
Begin
closeL:=closeL+1;
Close[closeL]:=Open[openL];
openL:=openL-1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(Close[closeL].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
openL:=openL+1;
Open[openL].Situation:=New-S;
Open[openL].Level:=Close[closeL].Level+1;
Open[openL].Last:=closeL;
End-If
End-For;
End;
範例：迷宮問題，求解最短路徑和可通路徑。
評價：廣度搜索是求解最優解的一種較好的方法，在後面將會對其進行進一步的優化。而深度搜索多用於只
要求解，並且解答樹中的重復節點較多並且重復較難判斷時使用，但往往可以用A*或回溯演算法代替。
第二部分 搜索演算法的優化
一、雙向廣度搜索
廣度搜索雖然可以得到最優解，但是其空間消耗增長太快。但如果從正反兩個方向進行廣度搜索，理想
情況下可以減少二分之一的搜索量，從而提高搜索速度。
範例：有N個黑白棋子排成一派，中間任意兩個位置有兩個連續的空格。每次空格可以與序列中的某兩個棋子
交換位置，且兩子的次序不變。要求出入長度為length的一個初始狀態和一個目標狀態，求出最少的
轉化步數。
問題分析：該題要求求出最少的轉化步數，但如果直接使用廣度搜索，很容易產生數據溢出。但如果從初始
狀態和目標狀態兩個方向同時進行擴展，如果兩棵解答樹在某個節點第一次發生重合，則該節點
所連接的兩條路徑所拼成的路徑就是最優解。
對廣度搜索演算法的改進：
1。添加一張節點表，作為反向擴展表。
2。在while循環體中在正向擴展代碼後加入反向擴展代碼，其擴展過程不能與
正向過程共享一個for循環。
3。在正向擴展出一個節點後，需在反向表中查找是否有重合節點。反向擴展時
與之相同。
對雙向廣度搜索演算法的改進：
略微修改一下控制結構，每次while循環時只擴展正反兩個方向中節點數目較少的一個，可以使兩邊的發
展速度保持一定的平衡，從而減少總擴展節點的個數，加快搜索速度。
二、分支定界
分支定界實際上是A*演算法的一種雛形，其對於每個擴展出來的節點給出一個預期值，如果這個預期值不
如當前已經搜索出來的結果好的話，則將這個節點(包括其子節點)從解答樹中刪去，從而達到加快搜索速度
的目的。
範例：在一個商店中購物，設第I種商品的價格為Ci。但商店提供一種折扣，即給出一組商品的組合，如果一
次性購買了這一組商品，則可以享受較優惠的價格。現在給出一張購買清單和商店所提供的折扣清單，
要求利用這些折扣，使所付款最少。
問題分析：顯然，折扣使用的順序與最終結果無關，所以可以先將所有的折扣按折扣率從大到小排序，然後
採用回溯法的控制結構，對每個折扣從其最大可能使用次數向零遞減搜索，設A為以打完折扣後優
惠的價格，C為當前未打折扣的商品零售價之和，則其預期值為A+a*C，其中a為下一個折扣的折扣
率。如當前已是最後一個折扣，則a=1。
對回溯演算法的改進：
1。添加一個全局變數BestAnswer，記錄當前最優解。
2。在每次生成一個節點時，計算其預期值，並與BestAnswer比較。如果不好，則調用回溯過程。
三、A*演算法
A*演算法中更一般的引入了一個估價函數f,其定義為f=g+h。其中g為到達當前節點的耗費，而h表示對從當
前節點到達目標節點的耗費的估計。其必須滿足兩個條件：
1。h必須小於等於實際的從當前節點到達目標節點的最小耗費h*。
2。f必須保持單調遞增。
A*演算法的控制結構與廣度搜索的十分類似，只是每次擴展的都是當前待擴展節點中f值最小的一個，如果
擴展出來的節點與已擴展的節點重復，則刪去這個節點。如果與待擴展節點重復，如果這個節點的估價函數
值較小，則用其代替原待擴展節點，具體演算法描述如下：
範例：一個3*3的棋盤中有1-8八個數字和一個空格，現給出一個初始態和一個目標態，要求利用這個空格，
用最少的步數，使其到達目標態。
問題分析：預期值定義為h=|x-dx|+|y-dy|。
估價函數定義為f=g+h。
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
g:Integer;(到達當前狀態的耗費)
h:Integer;(預計的耗費)
f:Real;(估價函數值)
Last:Integer;(父節點)
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:Tsituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
Begin
close:=close+1;
For I:=close+1 to open do (尋找估價函數值最小的節點)
Begin
if List.f<List[close].f then
Begin
交換List和List[close];
End-If;
End-For;
End;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I)
If Not (New-S in List[1..close]) then
(擴展出的節點未與已擴展的節點重復)
Begin
If Not (New-S in List[close+1..open]) then
(擴展出的節點未與待擴展的節點重復)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Last:=close;
List[open].g:=List[close].g+cost;
List[open].h:=GetH(List[open].Situation);
List[open].f:=List[open].h+List[open].g;
End-If
Else Begin
If List[close].g+cost+GetH(New-S)<List[same].f then
(擴展出來的節點的估價函數值小於與其相同的節點)
Begin
List[same].Situation:= New-S;
List[same].Last:=close;
List[same].g:=List[close].g+cost;
List[same].h:=GetH(List[open].Situation);
List[same].f:=List[open].h+List[open].g;
End-If;
End-Else;
End-If
End-For;
End-While;
對A*演算法的改進--分階段A*：
當A*演算法出現數據溢出時，從待擴展節點中取出若干個估價函數值較小的節點，然後放棄其餘的待擴展
節點，從而可以使搜索進一步的進行下去。
第三部分 搜索與動態規劃的結合
例1. 有一個棋子，其1、6面2、4面3、5面相對。現給出一個M*N的棋盤，棋子起初處於(1,1)點，擺放狀態
給定，現在要求用最少的步數從(1,1)點翻滾到(M,N)點，並且1面向上。
分析：這道題目用簡單的搜索很容易發生超時，特別當M、N較大時。所以可以考慮使用動態規劃來解題。對
於一個棋子，其總共只有24種狀態。在(1,1)點時，其向右翻滾至(2,1)點，向上翻滾至(1,2)點。而
任意（I，J）點的狀態是由（I-1，J）和（I，J-1）點狀態推導出來的。所以如果規定棋子只能向上
和向右翻滾，則可以用動態規劃的方法將到達（M，N）點的所有可能的狀態推導出來。顯然，從（1，
1）到達（N，M）這些狀態的路徑時最優的。如果這些狀態中有1面向上的，則已求出解。如果沒有，
則可以從（M，N）點開始廣度搜索，以（M，N）點的狀態組作為初始狀態，每擴展一步時，檢查當前
所得的狀態組是否有狀態與到達格子的狀態組中的狀態相同，如果有，則由動態規劃的最優性和廣度
搜索的最優性可以保證已求出最優解。
例2.給出一個正整數n，有基本元素a，要求通過最少次數的乘法，求出a^n。
分析：思路一：這道題從題面上來看非常象一道動態規劃題，a^n=a^x1*a^x2。在保證a^x1和a^x2的最優性之
後，a^n的最優性應該得到保證。但是仔細分析後可以發現，a^x1與a^x2的乘法過程中可能有
一部分的重復，所以在計算a^n時要減去其重復部分。由於重復部分的計算較繁瑣，所以可以
將其化為一組展開計算。描述如下：
I:=n;(拆分a^n)
split[n]:=x1;(分解方案)
Used[n]:=True;(在乘法過程中出現的數字)
Repeat(不斷分解數字)
Used[I-split[I]]:=True;
Used[split[I]]:=True;
Dec(I);
While (I>1) and (not Used[I]) do dec(I);
Until I=1;
For I:=n downto 1 do(計算總的乘法次數)
If Used[I] then count:=count+1;
Result:=count;(返回乘法次數)
思路二：通過對思路一的輸出結果的分析可以發現一個規律：
a^19=a^1*a^18
a^18=a^2*a^16
a^16=a^8*a^8
a^8=a^4*a^4
a^4=a^2*a^2
a^2=a*a
對於一個n，先構造一個最接近的2^k，然後利用在構造過程中產生的2^I,對n-2^k進行二進制分解，
可以得出解。對次數的計算的描述如下：
count:=0;
Repeat
If n mod 2 = 0 then count:=count+1
Else count:=count+2;
n:=n div 2;
Until n=1;
Result:=count;
反思：觀察下列數據：
a^15 a^23 a^27
Cost:5 Cost:6 Cost:6
a^2=a^1*a^1 a^2=a^1*a^1 a^2=a^1*a^1
a^3=a^1*a^2 a^3=a^1*a^2 a^3=a^1*a^2
a^6=a^3*a^3 a^5=a^2*a^3 a^6=a^3*a^3
a^12=a^6*a^6 a^10=a^5*a^5 a^12=a^6*a^6
a^15=a^3*a^12 a^20=a^10*a^10 a^24=a^12*a^12
a^23=a^3*a^20 a^27=a^3*a^24
這些數據都沒有採用思路二種的分解方法，而都優於思路二中所給出的解。但是經過實測，思路一二
的所有的解的情況相同，而卻得不出以上數據中的解。經過對a^2－a^15的數據的完全分析，發現對於
一個a^n，存在多個分解方法都可以得出最優解，而在思路一中只保留了一組分解方式。例如對於a^6
只保留了a^2*a^4，從而使a^3*a^3這條路中斷，以至採用思路一的演算法時無法得出正確的耗費值，從
而丟失了最優解。所以在計算a^n=a^x1*a^x2的重復時，要引入一個搜索過程。例如:a^15=a^3*a^12，
a^12=a^6*a^6，而a^6=a^3*a^3。如果採用了a^6=a^2*a^4，則必須多用一步。
<Type>
Link=^Node; （使用鏈表結構紀錄所有的可能解）
Node=Record
split:Integer;
next :Link;
End;
<Var>
Solution:Array[1..1000] of Link; （對於a^n的所有可能解）
Cost :Array[1..1000] of Integer; （解的代價）
max :Integer; （推算的上界）
<Main Program>
Procere GetSolution;
Var i,j :Integer;
min,c:Integer;
count:Integer;
temp,tail:Link;
plan :Array[1..500] of Integer;
nUsed:Array[1..1000] of Boolean;
Procere GetCost(From,Cost:Integer); （搜索計算最優解）
Var temp:Link;
a,b :Boolean;
i :Integer;
Begin
If Cost>c then Exit; （剪枝）
If From=1 then （遞歸終結條件）
Begin
If Cost<c then c:=Cost;
Exit;
End;
temp:=Solution[From];
While temp<>NIL do （搜索主體）
Begin
a:=nUsed[temp^.Split];
If not a then inc(cost);
nUsed[temp^.Split]:=True;
b:=nUsed[From - temp^.Split];
If not b then inc(cost);
nUsed[From-temp^.Split]:=True;
i:=From-1;
While (i>1) and (not nUsed) do dec(i);
GetCost(i,Cost);
If not a then dec(cost);
If not b then dec(cost);
nUsed[From-temp^.Split]:=b;
nUsed[temp^.Split]:=a;
temp:=temp^.next;
End;
End;
Begin
For i:=2 to Max do（動態規劃計算所有解）
Begin
count:=0;
min:=32767;
For j:=1 to i div 2 do （將I分解為I-J和J）
Begin
c:=32767;
FillChar(nUsed,Sizeof(nUsed),0);
nUsed[j]:=True;nUsed[i-j]:=True;
If j=i-j then GetCost(i-j,1)
Else GetCost(i-j,2);
If c<min then
Begin
count:=1;
min:=c;
plan[count]:=j;
End
Else if c=min then
Begin
inc(count);
plan[count]:=j;
End;
End;
new(solution); （構造解答鏈表）
solution^.split:=plan[1];
solution^.next:=NIL;
Cost:=min;
tail:=solution;
For j:=2 to count do
Begin
new(temp);
temp^.split:=plan[j];
temp^.next:=NIL;
tail^.next:=temp;
tail:=temp;
End;
End;
End;
背包問題：
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
『叄』 經典演算法題之兔子問題
就是那個遞歸演算法:f(1)=1;f(2)=1;f(3)=2;...f(n)=f(n-1)+f(n-2);程序是:(計算任一月兔子數)long fun(int x){ int i; if(x==1 || x==2) return 1; else return fun(x-1)+fun(x-2);}void main(){ int i,a; long s; scanf("%d",&a); printf("%ld\n",fun(a)); }
『肆』 經典c語言面試演算法題
經典C語言面試演算法題
1.寫一個函數,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字元串中找出連續最長的數字串，並把這個串的長度返回，並把這個最長數字串付給其中一個函數參數outputstr所指內存。例如："abcd12345ed125ss123456789"的首地址傳給intputstr後，函數將返回
9，outputstr所指的值為123456789。
#include
#include
#include
int FindMax_NumStr(char *outputstr,char *inputstr)
{
char *in = inputstr,*out = outputstr,*temp;
char *final;
int count = 0;
int maxlen = 0;
int i;
while(*in!=' ')
{
if(*in > 47 && *in < 58)
{
for(temp = in;*in> 47 && *in <58;in++)
count++;
}
else
in++;
if(maxlen < count)
{
maxlen = count;
count = 0;
final = temp;
}
}
for(i =0;i
{
*out = *final;
out++;
final++;
}
*out = ' ';
return maxlen;
}
void main(void)
{
char input[]="abc123def123456eec123456789dd";
char output[50] = {0};
int maxlen;
maxlen = FindMax_NumStr(output,input);
printf("the str %s ",output);
printf("the maxlen is %d ",maxlen);
}
2.求1000!的未尾有幾個0;
求出1->1000里,能被5整除的數的個數n1,能被25整除的數的個數n2,能被125整除的'數的個數n3,能被625整除的數的個數n4.1000!末尾的零的個數=n1+n2+n3+n4;
只要是末尾是5的數它乘以一個偶數就會出現一個0，而末尾是0的數乘以任何數也都會出現0
而末尾是0的如果是一個0肯定能被5整除，兩個0肯定能被25整數，以此類推3個0就能被5的三次方整除，也就是125
1000!就是1-1000數的相乘，能被5整除的所有數分別乘以一個偶數就會出現這些個的0，而例如100，既能被5整除，也能被25整除，所以就是兩個0
1000，既能被5，25，也能被125整除，所以算三個0
例如是10!=1*2*3*4*5*6*7*8*9*10，裡面有兩個數能被5整除，就是10和5，而
5隨便乘以一個偶數就出現一個0，而10乘以其它數也會出現一個0，所以10!會有兩個0
#include
#define NUM 1000
int find5(int num)
{
int ret = 0;
while(num%5==0)
{
num/=5;
ret++;
}
return ret;
}
int main(void)
{
int result = 0;
int i;
for(i=5;i<=NUM;i+=5)
result +=find5(i);
printf("the total zero number is %d ",result);
return 0;
}
3。編寫一個 C 函數，該函數在一個字元串中找到可能的最長的子字元串，且該字元串是由同一字元組成的。
char * search(char *cpSource, char ch)
{
char *cpTemp=NULL, *cpDest=NULL;
int iTemp, iCount=0;
while(*cpSource)
{
if(*cpSource == ch)
{
iTemp = 0;
cpTemp = cpSource;
while(*cpSource == ch)
++iTemp, ++cpSource;
if(iTemp > iCount)
iCount = iTemp, cpDest = cpTemp;
if(!*cpSource)
break;
}
++cpSource;
}
return cpDest;
}
;『伍』 最短路徑演算法
最短路徑演算法一般有Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。
從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。
最短路徑演算法問題：
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。演算法具體的形式包括：
（1）確定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra演算法。
（2）確定終點的最短路徑問題- 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
（3）確定起點終點的最短路徑問題- 即已知起點和終點，求兩結點之間的最短路徑。
（4）全局最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall演算法。
『陸』 演算法題套路總結（三）——動態規劃
前兩篇我總結了鏈表和二分查找題目的一些套路，這篇文章來講講動態規劃。動態規劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉移方程的題目，大部分動態規劃都不太會做。加上後來ACM更為令人頭禿的動態規劃，很多題解看了之後，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數優化，一度懷疑自己的智商。以前一直覺得動態規劃是給大佬准備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是後來慢慢的，我再做LC的時候，發現很多DP的題目我自己慢慢能夠推出轉移方程了，而且似乎也沒那麼難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是後者，但是同時我也發現，動態規劃其實是有套路的，我以前方法不對，總結太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態規劃畢竟要滿足：
因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經典DP模型，就需要通過大量的做題和總結，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結加深理解和融會貫通進而完成質的提升。
動態規劃是求解一個最優化問題，而最核心的思想就是：
解一道DP題目，先問自己幾個問題：
當然以上內容看起來比較抽象，雖然它深刻地揭露了動態規劃的本質，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結出幾個經典模型，剩下的都是些變種+優化而已。
一般來說，動態規劃可以分成4個大類:
線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是 經典模型 。
最長上升序列是一個非常經典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎上進一步優化而已。最長上升序列最基礎的轉移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 結尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的 f[j] 同時滿足 a[j]<a[i] 。因此是 N^2 的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關題目需要進一步優化，也就是有名的單調隊列優化，能夠把復雜度優化到nlogn。
說單調隊列優化之前必須明白一個貪心策略。因為要求的是最長上升序列，那麼很顯然長度為k的上升序列的最大值（最後一個數）越小越好，這樣後面的數才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最後一個數能達到的最小值，那麼對於後續每個數t，它要麼能放到某個長度為y的序列之後，組成長度為y+1的上升序列，要麼放到某個長度為x的序列後面，把長度為x+1的序列的最大值替換成t。同時我們可以發現，如果x<y，那麼長度為x序列的最後一個數一定比長度為y的序列最後一個數小。因此這個上升序列我們可以用一個數組來維護（所謂的單調隊列），數組下標就代表序列長度。 opt[i]=t 表示長度為i的上升序列最後一個數最小是t。那麼當我們在面對後續某個數x時，可以對單調隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關題目比如：
但是你可以發現，其實這個題型其實變種很有限，吃透了也就那麼回事。所以一定要總結。
最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種「模型」其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數組的最長公共子序列，最直觀地做法就是：設f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:
這個轉移方程也非常好理解，時間復雜度是 N^2 ，空間復雜度也是 N^2 。不過仔細觀察你可以發現，當我們計算第i行時只與i-1和i行有關。因此我們可以利用01滾動來優化空間復雜度為2N。
相關題目：
線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結的題型：
最終結果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發現，由於各個狀態只和前一維有關，且只能由固定的一個狀態轉移過來，因此我們可以省掉一維，只用4個變數來存儲：
剩下的，同123題類似，由於最多進行k次交易，那麼一天就有2k個狀態：第1次買/賣……第k次買/賣，結合123題的優化，我們只需要2k個變數就能存儲這些狀態。因此設f[i×2]為第i次買入的最優值，f[i×2+1]為第i次賣出的最優值：
以上都是對一些常見的線性DP的一些小結，實際上線性DP還有一個重要的題型就是背包。關於背包，有很多相關的講解，我這里就不多說了，推薦大家看看 背包九講 。下一章依然是DP專題，我講總結一些區間DP的題型。大部分區間DP都是hard級的，對於希望提高自己水平的人來說，需要投入更多精力去理解。
『柒』 演算法競賽入門經典習題3-9子序列（uva10340）
你判斷成功之後j還要再加1
『捌』 收集各類貪心演算法（C語言編程）經典題目
舉個例子,假如你買東西，老闆需要找給你99分錢，他有上面面值分別為25分，10分，5分，1分的硬幣（都是假如，不符合實際），他得找你3個25分，2個10分的，4個1分的才為最佳方案！
用貪心演算法編寫程序實現！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}
『玖』 c語言經典程序演算法
經典C源程序100例
【程序1】
題目：有1、2、3、4個數字，能組成多少個互不相同且無重復數字的三位數？都是多少？
1.程序分析：可填在百位、十位、個位的數字都是1、2、3、4。組成所有的排列後再去
掉不滿足條件的排列。
2.程序源代碼：
main()
{
int i,j,k;
printf("\n");
for(i=1;i<5;i++) ／*以下為三重循環*/
for(j=1;j<5;j++)
for (k=1;k<5;k++)
{
if (i!=k&&i!=j&&j!=k) /*確保i、j、k三位互不相同*/
printf("%d,%d,%d\n",i,j,k);
}
}
==============================================================
【程序2】
題目：企業發放的獎金根據利潤提成。利潤(I)低於或等於10萬元時，獎金可提10%；利潤高
於10萬元，低於20萬元時，低於10萬元的部分按10%提成，高於10萬元的部分，可可提
成7.5%；20萬到40萬之間時，高於20萬元的部分，可提成5%；40萬到60萬之間時高於
40萬元的部分，可提成3%；60萬到100萬之間時，高於60萬元的部分，可提成1.5%，高於
100萬元時，超過100萬元的部分按1%提成，從鍵盤輸入當月利潤I，求應發放獎金總數？
1.程序分析：請利用數軸來分界，定位。注意定義時需把獎金定義成長整型。
2.程序源代碼：
main()
{
long int i;
int bonus1,bonus2,bonus4,bonus6,bonus10,bonus;
scanf("%ld",&i);
bonus1=100000*0.1;bonus2=bonus1+100000*0.75;
bonus4=bonus2+200000*0.5;
bonus6=bonus4+200000*0.3;
bonus10=bonus6+400000*0.15;
if(i<=100000)
bonus=i*0.1;
else if(i<=200000)
bonus=bonus1+(i-100000)*0.075;
else if(i<=400000)
bonus=bonus2+(i-200000)*0.05;
else if(i<=600000)
bonus=bonus4+(i-400000)*0.03;
else if(i<=1000000)
bonus=bonus6+(i-600000)*0.015;
else
bonus=bonus10+(i-1000000)*0.01;
printf("bonus=%d",bonus);
}
==============================================================
【程序3】
題目：一個整數，它加上100後是一個完全平方數，再加上168又是一個完全平方數，請問該數是多少？
1.程序分析：在10萬以內判斷，先將該數加上100後再開方，再將該數加上268後再開方，如果開方後
的結果滿足如下條件，即是結果。請看具體分析：
2.程序源代碼：
#include "math.h"
main()
{
long int i,x,y,z;
for (i=1;i<100000;i++)
{ x=sqrt(i+100); /*x為加上100後開方後的結果*/
y=sqrt(i+268); /*y為再加上168後開方後的結果*/
if(x*x==i+100&&y*y==i+268)/*如果一個數的平方根的平方等於該數，這說明此數是完全平方數*/
printf("\n%ld\n",i);
}
}
==============================================================
【程序4】
題目：輸入某年某月某日，判斷這一天是這一年的第幾天？
1.程序分析：以3月5日為例，應該先把前兩個月的加起來，然後再加上5天即本年的第幾天，特殊
情況，閏年且輸入月份大於3時需考慮多加一天。
2.程序源代碼：
main()
{
int day,month,year,sum,leap;
printf("\nplease input year,month,day\n");
scanf("%d,%d,%d",&year,&month,&day);
switch(month)/*先計算某月以前月份的總天數*/
{
case 1:sum=0;break;
case 2:sum=31;break;
case 3:sum=59;break;
case 4:sum=90;break;
case 5:sum=120;break;
case 6:sum=151;break;
case 7:sum=181;break;
case 8:sum=212;break;
case 9:sum=243;break;
作者： zhlei81 2005-1-22 11:29 回復此發言
--------------------------------------------------------------------------------
2 經典C源程序100例
case 10:sum=273;break;
case 11:sum=304;break;
case 12:sum=334;break;
default:printf("data error");break;
}
sum=sum+day; /*再加上某天的天數*/
if(year%400==0||(year%4==0&&year%100!=0))/*判斷是不是閏年*/
leap=1;
else
leap=0;
if(leap==1&&month>2)/*如果是閏年且月份大於2,總天數應該加一天*/
sum++;
printf("It is the %dth day.",sum);}
==============================================================
【程序5】
題目：輸入三個整數x,y,z，請把這三個數由小到大輸出。
1.程序分析：我們想辦法把最小的數放到x上，先將x與y進行比較，如果x>y則將x與y的值進行交換，
然後再用x與z進行比較，如果x>z則將x與z的值進行交換，這樣能使x最小。
2.程序源代碼：
main()
{
int x,y,z,t;
scanf("%d%d%d",&x,&y,&z);
if (x>y)
{t=x;x=y;y=t;} /*交換x,y的值*/
if(x>z)
{t=z;z=x;x=t;}/*交換x,z的值*/
if(y>z)
{t=y;y=z;z=t;}/*交換z,y的值*/
printf("small to big: %d %d %d\n",x,y,z);
}
==============================================================
【程序6】
題目：用*號輸出字母C的圖案。
1.程序分析：可先用'*'號在紙上寫出字母C，再分行輸出。
2.程序源代碼：
#include "stdio.h"
main()
{
printf("Hello C-world!\n");
printf(" ****\n");
printf(" *\n");
printf(" * \n");
printf(" ****\n");
}
==============================================================
【程序7】
題目：輸出特殊圖案，請在c環境中運行，看一看，Very Beautiful!
1.程序分析：字元共有256個。不同字元，圖形不一樣。
2.程序源代碼：
#include "stdio.h"
main()
{
char a=176,b=219;
printf("%c%c%c%c%c\n",b,a,a,a,b);
printf("%c%c%c%c%c\n",a,b,a,b,a);
printf("%c%c%c%c%c\n",a,a,b,a,a);
printf("%c%c%c%c%c\n",a,b,a,b,a);
printf("%c%c%c%c%c\n",b,a,a,a,b);}
==============================================================
【程序8】
題目：輸出9*9口訣。
1.程序分析：分行與列考慮，共9行9列，i控制行，j控制列。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j,result;
printf("\n");
for (i=1;i<10;i++)
{ for(j=1;j<10;j++)
{
result=i*j;
printf("%d*%d=%-3d",i,j,result);/*-3d表示左對齊，佔3位*/
}
printf("\n");/*每一行後換行*/
}
}
==============================================================
【程序9】
題目：要求輸出國際象棋棋盤。
1.程序分析：用i控制行，j來控制列，根據i+j的和的變化來控制輸出黑方格，還是白方格。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
if((i+j)%2==0)
printf("%c%c",219,219);
else
printf(" ");
printf("\n");
}
}
==============================================================
【程序10】
題目：列印樓梯，同時在樓梯上方列印兩個笑臉。
1.程序分析：用i控制行，j來控制列，j根據i的變化來控制輸出黑方格的個數。
2.程序源代碼：
#include "stdio.h"
main()
{
int i,j;
printf("\1\1\n");/*輸出兩個笑臉*/
for(i=1;i<11;i++)
{
for(j=1;j<=i;j++)
printf("%c%c",219,219);
printf("\n");
}
}
作者： zhlei81 2005-1-22 11:29 回復此發言
--------------------------------------------------------------------------------
3 回復：經典C源程序100例
【程序11】
題目：古典問題：有一對兔子，從出生後第3個月起每個月都生一對兔子，小兔子長到第三個月
後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？
1.程序分析： 兔子的規律為數列1,1,2,3,5,8,13,21....
2.程序源代碼：
main()
{
long f1,f2;
int i;
f1=f2=1;
for(i=1;i<=20;i++)
{ printf("%12ld %12ld",f1,f2);
if(i%2==0) printf("\n");/*控制輸出，每行四個*/
f1=f1+f2; /*前兩個月加起來賦值給第三個月*/
f2=f1+f2; /*前兩個月加起來賦值給第三個月*/
}
}
==============================================================
【程序12】
題目：判斷101-200之間有多少個素數，並輸出所有素數。
1.程序分析：判斷素數的方法：用一個數分別去除2到sqrt(這個數)，如果能被整除，
則表明此數不是素數，反之是素數。
2.程序源代碼：
#include "math.h"
main()
{
int m,i,k,h=0,leap=1;
printf("\n");
for(m=101;m<=200;m++)
{ k=sqrt(m+1);
for(i=2;i<=k;i++)
if(m%i==0)
{leap=0;break;}
if(leap) {printf("%-4d",m);h++;
if(h%10==0)
printf("\n");
}
leap=1;
}
printf("\nThe total is %d",h);
}
==============================================================
【程序13】
題目：列印出所有的「水仙花數」，所謂「水仙花數」是指一個三位數，其各位數字立方和等於該數
本身。例如：153是一個「水仙花數」，因為153=1的三次方＋5的三次方＋3的三次方。
1.程序分析：利用for循環控制100-999個數，每個數分解出個位，十位，百位。
2.程序源代碼：
main()
{
int i,j,k,n;
printf("'water flower'number is:");
for(n=100;n<1000;n++)
{
i=n/100;/*分解出百位*/
j=n/10%10;/*分解出十位*/
k=n%10;/*分解出個位*/
if(i*100+j*10+k==i*i*i+j*j*j+k*k*k)
{
printf("%-5d",n);
}
}
printf("\n");
}
==============================================================
【程序14】
題目：將一個正整數分解質因數。例如：輸入90,列印出90=2*3*3*5。
程序分析：對n進行分解質因數，應先找到一個最小的質數k，然後按下述步驟完成：
(1)如果這個質數恰等於n，則說明分解質因數的過程已經結束，列印出即可。
(2)如果n<>k，但n能被k整除，則應列印出k的值，並用n除以k的商,作為新的正整數你n,
重復執行第一步。
(3)如果n不能被k整除，則用k+1作為k的值,重復執行第一步。
2.程序源代碼：
/* zheng int is divided yinshu*/
main()
{
int n,i;
printf("\nplease input a number:\n");
scanf("%d",&n);
printf("%d=",n);
for(i=2;i<=n;i++)
{
while(n!=i)
{
if(n%i==0)
{ printf("%d*",i);
n=n/i;
}
else
break;
}
}
printf("%d",n);}
==============================================================
【程序15】
題目：利用條件運算符的嵌套來完成此題：學習成績>=90分的同學用A表示，60-89分之間的用B表示，
60分以下的用C表示。
1.程序分析：(a>b)?a:b這是條件運算符的基本例子。
2.程序源代碼：
main()
{
int score;
char grade;
printf("please input a score\n");
scanf("%d",&score);
grade=score>=90?'A':(score>=60?'B':'C');
printf("%d belongs to %c",score,grade);
}
==============================================================
【程序16】
題目：輸入兩個正整數m和n，求其最大公約數和最小公倍數。
作者： zhlei81 2005-1-22 11:30 回復此發言
--------------------------------------------------------------------------------
4 回復：經典C源程序100例
1.程序分析：利用輾除法。
2.程序源代碼：
main()
{
int a,b,num1,num2,temp;
printf("please input two numbers:\n");
scanf("%d,%d",&num1,&num2);
if(num1 { temp=num1;
num1=num2;
num2=temp;
}
a=num1;b=num2;
while(b!=0)/*利用輾除法，直到b為0為止*/
{
temp=a%b;
a=b;
b=temp;
}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);
}
==============================================================
【程序17】
題目：輸入一行字元，分別統計出其中英文字母、空格、數字和其它字元的個數。
1.程序分析：利用while語句,條件為輸入的字元不為'\n'.
2.程序源代碼：
#include "stdio.h"
main()
{char c;
int letters=0,space=0,digit=0,others=0;
printf("please input some characters\n");
while((c=getchar())!='\n')
{
if(c>='a'&&c<='z'||c>='A'&&c<='Z')
letters++;
else if(c==' ')
space++;
else if(c>='0'&&c<='9')
digit++;
else
others++;
}
printf("all in all:char=%d space=%d digit=%d others=%d\n",letters,
space,digit,others);
}
==============================================================
【程序18】
題目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一個數字。例如2+22+222+2222+22222(此時
共有5個數相加)，幾個數相加有鍵盤控制。
1.程序分析：關鍵是計算出每一項的值。
2.程序源代碼：
main()
{
int a,n,count=1;
long int sn=0,tn=0;
printf("please input a and n\n");
scanf("%d,%d",&a,&n);
printf("a=%d,n=%d\n",a,n);
while(count<=n)
{
tn=tn+a;
sn=sn+tn;
a=a*10;
++count;
}
printf("a+aa+...=%ld\n",sn);
}
==============================================================
【程序19】
題目：一個數如果恰好等於它的因子之和，這個數就稱為「完數」。例如6=1＋2＋3.編程
找出1000以內的所有完數。
1. 程序分析：請參照程序<--上頁程序14.
2.程序源代碼：
main()
{
static int k[10];
int i,j,n,s;
for(j=2;j<1000;j++)
{
n=-1;
s=j;
for(i=1;i {
if((j%i)==0)
{ n++;
s=s-i;
k[n]=i;
}
}
if(s==0)
{
printf("%d is a wanshu",j);
for(i=0;i printf("%d,",k[i]);
printf("%d\n",k[n]);
}
}
}
==============================================================
【程序20】
題目：一球從100米高度自由落下，每次落地後反跳回原高度的一半；再落下，求它在
第10次落地時，共經過多少米？第10次反彈多高？
1.程序分析：見下面注釋
2.程序源代碼：
main()
{
float sn=100.0,hn=sn/2;
int n;
for(n=2;n<=10;n++)
{
sn=sn+2*hn;/*第n次落地時共經過的米數*/
hn=hn/2; /*第n次反跳高度*/
}
printf("the total of road is %f\n",sn);
printf("the tenth is %f meter\n",hn);
}
作者： zhlei81 2005-1-22 11:30 回復此發言
--------------------------------------------------------------------------------
『拾』 大公司筆試面試有哪些經典演算法題目
1、二維數組中的查找
具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？