㈠ 關於ACM的深搜和廣搜以及動態規劃
你好，親，這段講解使我們集訓隊代課老師給我們的，希望有幫助。
搜索演算法階段性總結：
BFS與DFS的討論：BFS：這是一種基於隊列這種數據結構的搜索方式，它的特點是由每一個狀態可以擴展出許多狀態，然後再以此擴展，直到找到目標狀態或者隊列中頭尾指針相遇，即隊列中所有狀態都已處理完畢。
DFS：基於遞歸的搜索方式，它的特點是由一個狀態拓展一個狀態，然後不停拓展，直到找到目標或者無法繼續拓展結束一個狀態的遞歸。
優缺點：BFS:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是內存耗費量大（需要開大量的數組單元用來存儲狀態）。
DFS：對於解決遍歷和求所有問題有效，對於問題搜索深度小的時候處理速度迅速，然而在深度很大的情況下效率不高
總結：不管是BFS還是DFS，它們雖然好用，但由於時間和空間的局限性，以至於它們只能解決數據量小的問題。
各種搜索題目歸類：
坐標類型搜索 ：這種類型的搜索題目通常來說簡單的比較簡單，復雜的通常在邊界的處理和情況的討論方面會比較復雜，分析這類問題，我們首先要抓住題目的意思，看具體是怎麼建立坐標系（特別重要），然後仔細分析到搜索的每一個階段是如何通過條件轉移到下一個階段的。確定每一次遞歸（對於DFS）的回溯和深入條件，對於BFS，要注意每一次入隊的條件同時注意判重。要牢牢把握目標狀態是一個什麼狀態，在什麼時候結束搜索。還有，DFS過程的參數如何設定，是帶參數還是不帶參數，帶的話各個參數一定要保證能完全的表示一個狀態，不會出現一個狀態對應多個參數，而這一點對於BFS來說就稍簡單些，只需要多設置些變數就可以了。
經典題目：細胞（NDK1435）、Tyvj：乳草的入侵、武士風度的牛
數值類型搜索：（雖然我也不知道該怎麼叫，就起這個名字吧），這種類型的搜索就需要仔細分析分析了，一般來說採用DFS，而且它的終止條件一般都是很明顯的，難就難在對於過程的把握，過程的把握類似於坐標類型的搜索（判重、深入、枚舉），注意這種類型的搜索通常還要用到剪枝優化，對於那些明顯不符合要求的特殊狀態我們一定要在之前就去掉它，否則它會像滾雪球一樣越滾越大，浪費我們的時間。
經典題目：Tyvj：派對；售貨員的難題，以及各種有關題目搜索演算法階段性總結
你好，明天可以發你幾道這類題，而且還有代碼，親。
㈡ c語言課程設計：選出一位幸運人士，一定要用遞歸演算法！要源代碼，流程圖，和演算法描述！
這道題做ACM題目的時候做過，當時使用數組做的，最後因為效率太低通過不了。
G Josephus Problem
Time Limit:1000MS Memory Limit:65535K
題型: 編程題 語言: 無限制
描述
Josephus Problem is an ancient problem named for Flavius Josephus. There are people standing in a circle waiting to be executed. The counting out begins at the
first point in the circle and proceeds around the circle in a fixed direction. In each step, one person is skipped and the next person is executed. The elimination
proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
For example, if there are 10 people in the circle, the executed order is 2, 4, 6, 8, 10, 3, 7, 1, 9. So the 5th person survives.
Now we define a function J(n) to be the survivor』s number when there are n person in the circle, and J^2(n)=J(J(n)), for instance J^2(10)=J(J(10))=J(5)=3,
and J^3(n)=J(J(J(n))), and so on. Could you calculate J^m(n)?
輸入格式
The input consists of a number of cases.
Each case contains integers n and m. 0<n, m<=10^9
The input is terminated by a case with m=n=0
輸出格式
For each case, print the number J^m(n)
輸入樣例
10 2
10 1
20 1
0 0
輸出樣例
3
5
9
Provider
admin
#include<stdio.h>
#include<malloc.h>
#include<math.h>
int J(int number,int * circle)
{
int i,length=number;
for(i=0;i<number;i++)
{
circle[i]=i+1;
}
while(length>1)
{
if(length%2==0)
{
for(i=0;i<length;i++)
{
circle[i]=circle[i*2];
}
length=length/2;
continue;
}
if(length%2==1)
{
circle[0]=circle[length-1];
for(i=1;i<length;i++)
{
circle[i]=circle[(i-1)*2];
}
length=length/2+1;
continue;
}
}
return circle[0];
}
int main()
{
int n,m,i,*circle;
circle=(int*)malloc(n*sizeof(int));
while(1){
{
scanf("%d%d",&n,&m);
}while(n<0||m<0||m>10);
if(n==0&&m==0)
break;
for(i=0;i<m;i++)
{
n=J(n,circle);
}
printf("%d\n",n);
}
return 0;
}