深度优先搜索和广度优先搜索

递归问题整理   http://blog.csdn.net/shallwake/article/details/5004541

深搜的

放苹果 (POJ1664)：（其实就是整数划分问题）

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？ 5，1，1和1，5，1 是同一种分法。（1<=M，N<=10）

如输入M = 7, N = 3，应输出8       （7 0 0 ）（6 1 0 ）（5 2 0 ）（5 1 1 ）（4 3 0 ）（4 2 1 ）（3 3 1 ）（3 2 2）

 参考  http://blog.csdn.net/jackyzhengx1990/article/details/6049218

/*解题分析：
        设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
        当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)　　
        当n<=m：不同的放法可以分成两类：
        1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);  
        2、所有盘子都有苹果，相当于先每个盘子放一个苹果，一共是n个，然后的m-n的苹果再分配到m的盘子，即f(m,n) = f(m-n,n).
        而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 
    递归出口条件说明：
        当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
        当没有苹果可放时，定义为１种放法；
        递归的两条路，第一条n会逐渐减少，终会到达出口n==1; 
        第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．
        http://www.cnblogs.com/dongsheng/archive/2012/08/15/2640468.html
*/
#include<stdio.h>

int fun(int m,int n)  //m个苹果放在n个盘子中共有几种方法
{
    if(m==0||n==1)  //因为我们总是让m>=n来求解的，所以m-n>=0,所以让m=0时候结束，如果改为m=1，
        return 1;    //则可能出现m-n=0的情况从而不能得到正确解    
    if(n>m)
        return fun(m,m);
    else
        return fun(m,n-1)+fun(m-n,n);
}

int main()
{
    int T,m,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&m,&n);
        printf("%d
",fun(m,n));
    }
}

 广义水仙花数

如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来水仙花数是N = 3的广义水仙花数现在，我们的任务是，输入一个m (m < 7) ，让你求出所有满足N = m的广义水仙花数。

3 (153 370 371 407)

5 (54748 92727 93084)

方法：数据规模很小，可以直接枚举所有情况，然后判断是否满足条件。

难点：循环层数不确定

 

于是我们现在的问题是，怎么实现这个m重循环？

答案是：递归。

#include <iostream>
#include <cstdio>
using namespace std;

int m;

int Pow(int x, int n)
{
    int res = 1;
    while (n--) 
        res *= x;
    return res;
}

//参数说明
//deep是深度  从1-m  curNum是当前的数  curNum是当前的数计算的结果，就是各位方次之后的和
void dfs(int deep, int curNum, int curSum)
{
    if (deep > m) //类似于base case
    {
        if (curNum == curSum)
            printf("%d
", curNum);
    }
    else if (deep <= m)
    {
        int start = (deep == 1); //第一位不为0
        for (int i = start; i <= 9; i++)
            dfs(deep + 1, curNum * 10 + i, curSum + Pow(i, m)); //缩小问题规模
    }
}

int main()
{

    while (scanf("%d", &m), m)
    {
        dfs(1, 0, 0);
    }
    return 0;
}

 全排列问题

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

 这也有资源

http://blog.csdn.net/morewindows/article/details/7370155

http://www.cnblogs.com/fxplove/articles/2598869.html

#include <stdio.h>
#include <string.h>
void pailie(char *str, int m, int n)
{
    if (n==0)
    {
        str = str-m;
        printf("%s
",str);
        return;
    }
    int length = strlen(str);
    for (int i=0;i<length;++i)
    {
        for (int j=i; j<length; ++j)
        {
            char tmp;
            tmp = str[0];
            str[0] = str[j];
            str[j] = tmp;
            pailie(str+1+i, m, n-1);
        }
        
    }
}

void main()
{
    char p[] = "123";
    pailie(p,strlen(p),strlen(p)); // 该处是全排列，可以将第一个strlen(p)替换为小于n的数，即可A(n,m)
}

框架

深度优先搜索解决问题的框架
void dfs(int deep, State curState)
{
    if (deep > Max) //深度达到极限
    {     
　　if (curState == target) //找到目标
        {
            //...
        }
    }
    else
　　{
        for (i = 1; i <= totalExpandMethod; i++)
    　　{
        　　dfs(deep + 1, expandMethod(curState, i));
    　　}
　　}
}

   广度优先搜索

三个水杯

http://acm.nyist.net/JudgeOnline/problem.php?pid=21

答案：   http://blog.csdn.net/code_pang/article/details/7802944

#include <cstdio>
#include <memory.h>
#include <queue>

using namespace std;

#define EMPTY    0

struct data_type
{
    int state[3];
    int step;
};

int cupCapacity[3], targetState[3];

bool visited[100][100][100];

bool AchieveTargetState(data_type current)
{
    for (int i = 0; i < 3; i++)
    {
        if (current.state[i] != targetState[i])
        {
            return false;
        }
    }
    return true;
}

void PourWater(int destination, int source, data_type &cup)
{
    int waterYield = cupCapacity[destination] - cup.state[destination];
    if (cup.state[source] >= waterYield)
    {
        cup.state[destination] += waterYield;
        cup.state[source] -= waterYield;
    }
    else
    {
        cup.state[destination] += cup.state[source];
        cup.state[source] = 0;
    }
}

int BFS(void)
{
    int i, j, k;
    data_type initial;
    queue<data_type> toExpandState;

    memset(visited, false, sizeof(visited));
    initial.state[0] = cupCapacity[0];
    initial.state[1] = initial.state[2] = 0;
    initial.step = 0;
    toExpandState.push(initial);
    visited[initial.state[0]][0][0] = true;

    while (!toExpandState.empty())
    {
        data_type node = toExpandState.front();
        toExpandState.pop();
        if (AchieveTargetState(node))
        {
            return node.step;
        }
        for (i = 0; i < 3; i++)
        {
            for (j = 1; j < 3; j++)
            {
                k = (i+j)%3;
                if (node.state[i] != EMPTY && node.state[k] < cupCapacity[k])
                {
                    data_type newNode = node;
                    PourWater(k, i, newNode);
                    newNode.step = node.step + 1;
                    if (!visited[newNode.state[0]][newNode.state[1]][newNode.state[2]])
                    {
                        visited[newNode.state[0]][newNode.state[1]][newNode.state[2]] = true;
                        toExpandState.push(newNode);
                    }
                }
            }
        }
    }
    return -1;
}

int main(void)
{
    int testNum;
    scanf("%d", &testNum);
    while (testNum -- != 0)
    {
        scanf("%d%d%d", &cupCapacity[0], &cupCapacity[1], &cupCapacity[2]);
        scanf("%d%d%d", &targetState[0], &targetState[1], &targetState[2]);
        printf("%d
", BFS());
    }
    return 0;
}

 树的层序遍历其实也是一种广度优先搜索吧  代码不写了