在另一个帖子里（ACM题目的那个）求全排列时要用到回溯法，但我看了好久都看不懂，求解释……int f3(int n, int m)
 int f3(int n, int m)
 {
     if(n < 1 || m < 1) return 0;
     if(n == 1 || m == 1) return 1;
     if(n < m) return f3(n, n);
     if(n == m) return f3(n, m - 1) + 1;
     return f3(n, m - 1) + f3(n - m, m);
 }
最好能举个简单的回溯法例子就好，谢谢了。

好眼熟的代码

强调一下，这不叫回溯法，这叫分治法。

你是想听回溯法？还是分治法？

整数划分f（n,m）表示把整数n划分成不大于m的数之和的所有组合。
如果n = 1， 很显然1只有1种划分，如果m = 1 ，也是只有1种划分，任何一个数n都只能表示成n个1相加。所以当n=1 或者m = 1时 返回 1.这是递归能实现的条件。（n < 0 ||  m < 0）也是一个道理。
那么当m 和 n 大于1时他们之间有3种比较关系。
1. n <  m 此时一个数n不可能标示成一个比他还大的数与另外一个数相加，所以f(n,m)相当于f(n,n).
2. n = m  此时f(n,m) = f(n ,n ) = f(n, n - 1) + 1.这个1就是n表示成n的那种方式。f(n, n - 1)是把n表示成不大于n - 1的所有情形。
3. n > m. 此时可以把这个问题划分成两块，第一种，包含m的情形。即（m + (^+^+&+&+^+%+%)）后面那一堆无论是哪些数组合在一起他的和一定是 n - m.那么就相当于把整数（n - m）划分成不大于m的情形，即f((n - m), m)（m 可能再次出现）。 第二种，不包含m的情形。就相当于把n划分成不大于m - 1的数的所有组合：f(n, m - 1).
综合上述就得到你上面的程序。

没看明白
....
对递归，有多少种啊，

是不是对递归,要一个一个去试数啊,

 return f3(n, m - 1) + f3(n - m, m);
能返回一个什么,

[ 本帖最后由 cuijingchun 于 2012-1-15 19:49 编辑 ]

不好意思啊，我在网站上看到是说这道题用回溯法会很简单，然后又看到laoyang103的解答里面的这个程序段号简单，所以就认为回溯法了
我想了解回溯法到底怎么回事，我知道回溯法的原理就是一条一条的路去尝试，但不知道怎么能写出代码来，所以麻烦各位了。

分析的不错。算法学到什么程度了？能不能把以上算法改写成动态规划法？

回溯法的本质是穷举法。以深度优先的策略遍历解空间。当确定某一子树不包含解时则不进入该子树，并回溯到该子树根结点的父结点继续遍历。由此减少无效遍历，提高效率。

老杨代码的算法就是回溯法。

3楼分析的真好，我想我差不多大概理解了
就当让自己更深一步理解吧，我也解说一下：
这段代码就是根据m的大小作为分段依据的，前面的n < m，n = m，都是通过递归转化为n > m的问题，然后n > m通过不断的递归，最终都可以化为f(n,1) + x*1（x的大小根据m的大小来确定）的问题，最终通过n=1 || m=1这个结束条件来结束程序，从而得到所有可能组合数的和。

[ 本帖最后由 ai8343512 于 2012-1-15 20:22 编辑 ]

最后一句其实是省略了if (n>m)的条件，因为经过前面四个if以后一定会转化为if (n>m)的情况，所以省略了if (n>m)这个条件不影响程序的进行

#include  <stdio.h>

#include  <string.h>

#include  <stdlib.h>

#define   N    101

int array[N][N];

int  main(void)

{
    int n, m;

    int  sum, i, j;

    char  ch;
   
    array[0][0] = 1;

    for (i = 1; i < N; i++)

        for (j = 1; j <= i; j++)       
       
            array[i][j] = array[i - 1][j - 1] + array[i - j][j];

    printf("Please input n & m:");

    while (scanf("%d%d", &n, &m) != EOF)

    {
        sum = 0;

        for (i = 1; i <= m; i++)
  
        sum += array[n][i]; 
       
        printf("The result is %d\n", sum);

        printf("CONTINUE?(Y /N):");

        getchar();

        ch = getchar();

        fflush(stdin);
   
            if (ch == 'Y' || ch == 'y')

                printf("Please input n & m:");

            else  break;               
    }

    return  0;
}

这个可以不？我是把n划分成m份来做的。一个数n可以看成是划分成1份--n份  每份对应的划分数之和就是总的划分数。而n划分成m份可以分成其中有1和没有1两种情形。

[ 本帖最后由 有容就大 于 2012-1-15 22:37 编辑 ]