㈠ 关于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;
}