一个难忘的递归题，寻找高手

chandlersong

你好。我是marshall。
   其实对于递归我并不觉得很难。在递归其实只做两件事情。第一，确定最后一棒的该做什么。第二，在一棒之内做好一个工作，然后交给下一棒。
   其实我对于递归的理解只是把降低程序的逻辑难度，就好像类一样，至少对我这个初学者来说，类的存在大大降低了我解决复杂问题的难度。其实很多递归的问题都能用循环来解决，同时效率上来说也不及循环，但是递归之所以被使用和研究。主要是因为递归能够使得程序能够逻辑上简单。
   所以我觉得，学好递归或者逻辑结构，乃至编程，其首先是要学会用编程的思想去理清一个程序的逻辑结构。不知道做为一个新人，是不是有班门弄斧之嫌。

499803468

你说的递归程序编写只是一般规律，84年入学学计算机的人一般都是该学校的最高分，在当时的招生规模下可以认为大多数都是很聪明的人，那时大家都爱学习，但是无师自通的只有10%，学习课程完后30%，毕业时60%。递归程序不是遍出来就算懂，一定要调出来。这里出的题，不仅要会编递归程序，还要完全了解递归程序编译及动态的执行过程。否则无望。能够理解该题的难度就可以认为是高手。

chandlersong

想问一下，这道题的难点在哪里呢？
  其实，其实我觉得递归并不是很难掌握的东西。其对于循环的就好像代数对于算式。尽管来说运算效率要低，就好像解方程要比算式要慢。但是代数能够使得逻辑顺着来，而大大提高了对复杂问题寻找方法的时间，从而使得总体效率的提升。
  其实看了你那么多。我一直不太清楚你想表达什么意思。能否言明呢？

hotiice

http://zhidao.baidu.com/question/59422936.html?si=2

hotiice

http://zhidao.baidu.com/question/14101807.html?si=3

hotiice

http://zhidao.baidu.com/question/16051907.html?si=4

zhangzongjun

路过～

499803468

谢谢现在应该能够完全说明本题目了，以下是楼上朋友从白度上给出的C程序，这只是本题目的基础，


全排列和全组合
#include <iostream>
#include <fstream>
using namespace std;

const count = 5;
fstream f;

void perm(char *a, const int k, const int n)
{ int i; if (k==n-1)
{ for (i=0; i<n; i++) {
cout<<a<<" ";
f<<a;
}
cout<<endl;
f<<endl;
}

else
{
for (i=k; i<n; i++)
{
char temp = a[k];
a[k] = a;
a = temp;
perm(a, k+1, n);
temp = a[k];
a[k] = a;
a = temp;
}
}
}

void comb(char* a, int* b, const int k, const int n)
{
int i;
if (k==n)
{
char temp[count];

int j=0;
for (i=0; i<n; i++)
if(b == 1)
temp[j++] = a;
if (j)
perm(temp, 0, j);
}

else
{
b[k] = 0;
comb(a, b, k+1, n);
b[k] = 1;
comb(a, b, k+1, n);
}
}

void main()
{
f.open("test.txt", ios:ut);
char ex[5]={'a', 'b', 'c', 'd', 'e'};
int a[5];
comb(ex, a, 0, 5);
f.close();
}

他的递归过程就是

void comb(char* a, int* b, const int k, const int n)
{ int i; if (k==n) {
char temp[count];

int j=0;
for (i=0; i<n; i++)
if(b == 1)
temp[j++] = a;
if (j)
perm(temp, 0, j);
} else
{ b[k] = 0;
comb(a, b, k+1, n);
b[k] = 1;
comb(a, b, k+1, n);
}
}

该过程显然有很多分号，题目的要求就是“没有分号”

feiyangdefei

public class ListAll {

        /**
         * @param args
         */
        public static void main(String[] args) {
                ListAll a = new ListAll();
               
               
                String[] strings = a.returnAll(4);
                int length = strings.length;
                for(int i=0;i<length;i++){
                        System.out.print(strings.toString()+ "    ") ;
                        if((i+1)%4==0){
                                System.out.println();
                        }
                }

        }       
        /**
         * 分析全排列 我们发现 其有这么一个规律 即此数的全排列为在其前一个数的前排列所得到的数据的N个位置加上本身。1这本身
         * 如2 21 12 为 returnAll(2) = returnAll(1)+n 和 n + returnAll(1)
         * 3 为 m 0 to  2 returnAll(3) = returnAll(2)[t].subString(0,m) + n + returnAll(2)[t].subString(m); t 0 to returnAll(2).length
         * 所以 如下所示即可。
         * 出于效率的考虑，我设置了两个变量。这两个变量如果根据题目要求可以不要，不过那样效率会很低。
         * @param n
         * @return
         */
        private String[] returnAll(int n){
                int length = 1;
                for(int k = 1;k<=n;k++){
                        length = length*k;                       
                }
                String[] strings = new String[length];
                if(n==1){
                        strings[0]=new Integer(n).toString();
                }else{
                        String[] preStrings = returnAll(n-1);
                        String tmpString;
                        for(int t = 0 ; t<preStrings.length;t++){
                                tmpString = preStrings[t];
                                for (int m =0 ;m<n ;m++){
                                                strings[t*n+m] = tmpString.substring(0, m)+ n +tmpString.substring(m);
                                }
                        }
                       
                }
               
                return strings;
        }
}
下面是运行结果：
4321    3421    3241    3214   
4231    2431    2341    2314   
4213    2413    2143    2134   
4312    3412    3142    3124   
4132    1432    1342    1324   
4123    1423    1243    1234   
我不知道这样做是否可以。因为，我的分号也很多，但是也可以做到你所需要的就一个分号，但是那样程序执行效率会很慢。以下可能是你说的一个分号。不过程序只支持的最大数为9。10由于其长度的问题，会出现内容使用错误。
private String[] returnAllInOne(int n){
                int length = 1;
                for(int k = 1;k<=n;k++){
                        length = length*k;                       
                }
                String[] strings = new String[length];
                if(n==1){
                        strings[0]=new Integer(n).toString();
                }else{
//                        String[] preStrings = returnAll(n-1);
//                        String tmpString;
                        for(int t = 0 ; t<returnAll(n-1).length;t++){
//                                tmpString = returnAll(n-1)[t];
                                for (int m =0 ;m<n ;m++){
                                                strings[t*n+m] = returnAll(n-1)[t].substring(0, m)+ n +returnAll(n-1)[t].substring(m);
                                }
                        }
                       
                }
               
                return strings;
        }

[ 本帖最后由 feiyangdefei 于 2008-7-31 10:36 编辑 ]

499803468

谢谢，有新意。但还不是我想的结果。该程序不管效率问题，只追求形式。你可以把递归过程中的几个普通（非递归调用）语句放到递归之外，然后用一个过程调用去掉某些分号。也可以在参数表中采用数值型参去掉局部变量说明。但是，最后的结果递归程序中，没有一个分号。事实上，我的印象中，是没有FOR等循环语句。