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

20多年前，在进行计算机PASCAL语言教学时，让学生编写递归程序。改程序是输入数N，输出1到N的全排列。
这是一个普通题，但是有个学生写了一个程序，读不懂也不对，然后问他“这一句干什么，那一句干什么”，好像回答都没用，就直接删除。结果递归过程中就剩一句（没有分号），竟然程序正确。2004年给公司的技术高手说了这个故事，他满怀信心说可以重新编写出来，结果三个月后，他承认没有编写出来，并断言不可能。但是一周后，他自己编写出来并调试成功。
我这两次的程序都没有保留，看看还有没有高手能够解决。

什么叫全排列？举个例子？

对，举个例子

书上都有

例如

输入3  输出  123  132  213 231 312 321
输入4 输出   1234  1243  1324 1342  1423  1432
                    2134  2143  2314 2341  2413  2431
                    3124  3142.。。

很有难度啊

我刚开始学数据结构和算法方面的东西。用的是java来写的。这是我写的一个类，估计能满足你的需求。
  这个类就是要把的求组合的东西的排列输出来。你的要求的话么。基本上能满足了吧。只要再写一个类。输入的时候做个从1开始的循环就好了。如果要出来的是结构是数字，就改一下output的取值就可以了。
  不过楼主这种东西估计也就刚开始学的时候能够做一下。
public class teams {
    String[] a;                                   //the things to be put in the package.
    int nItems;                                   //how many things
    int max;                                      //the length of the array.
    public teams(int len){
            a = new String[len];
            nItems=0;
            max=len;
    }
    public void insert(String Item){
            if(max==nItems){
                    System.out.print("the array is full");
            }
            else{
                    a[nItems++]=Item;
            }
    }
    public int showteamchoice(int n,int y){
           int temp;
           if(y==1){
                   temp = n;
           }
           else if(n==y){
                   temp = 1;
           }
           else{
                   temp=showteamchoice(n-1,y-1);
                   temp=temp+showteamchoice(n-1,y);
           }
           return temp;
   }
    public void showteam(int n,int k,int index,String output){
            if(k==0){                                   //one kind of the combine
                    System.out.println(output);
                    return;
            }
            else if(index==nItems&&k!=0){               //not enough items for the combine
                    return;
            }
            else {                                          
                    int temp=k;
                String stemp=output;
                    while(index<=nItems-1){                //the loop is to decide the first items of the combine.
                            temp=k;
                            stemp=output;
                            stemp=stemp+","+a[index];
                            this.showteam(n-1, temp-1, index+1, stemp);
                            index=index+1;
                    }
            }
    }
}

[[i] 本帖最后由 Marshall605 于 2008-7-20 21:13 编辑 [/i]]

谢谢，我不会JAVA，不知你的程序是否经过调试，结果是否正确，
但是普通读你的程序可能不符合我的要求，你的递归主程序可能是


    public int showteamchoice(int n,int y){
           int temp;
           if(y==1){
                   temp = n;
           }
           else if(n==y){
                   temp = 1;
           }
           else{
                   temp=showteamchoice(n-1,y-1);
                   temp=temp+showteamchoice(n-1,y);
           }
           return temp;
   }

有多个分号


    public void showteam(int n,int k,int index,String output){
            if(k==0){                                   //one kind of the combine
                    System.out.println(output);
                    return;
            }
            else if(index==nItems&&k!=0){               //not enough items for the combine
                    return;
            }
            else {                                          
                    int temp=k;
                String stemp=output;
                    while(index<=nItems-1){                //the loop is to decide the first items of the combine.
                            temp=k;
                            stemp=output;
                            stemp=stemp+","+a[index];
                            this.showteam(n-1, temp-1, index+1, stemp);
                            index=index+1;
                    }
            }
    }
}
也有多个分号


应该是
    public void showteam(int n,int k,int index,String output){
       if(k==0){System.out.println(output)}
            else if(index==nItems&&k!=0){return}
            else {                                          
                   WHile(index<=nItems-1){this.showteam(n-1, temp-1, index+1, stemp)}
            }；
    }
这样的结构，才叫递归过程中没有分号；
再一次谢谢你

有用的只是showteam，showteamchoice估计是我的开始写的时候，思路比较乱时候的方法。毕竟刚刚开始学么，请见谅。
    其次，仔细看了你的要求，发觉不完全符合你的要求。因为我123，和321算一个的。
    不过关于你的问题，我只有个解决思路。基本上来说就是建一个类。基本和我一样，保留成员和insert方法。showteam做以下改变
    参数改为n 项目总共排序的个数。k 要取得数。
    index做大修改。因为要写一个类。这个类基本就是一个数组或者链表，建议用链表。然后除了insert方法之外，还有一个check方法，判断参数是否为链表当中的值，和display方法。（学了java之后觉得类真的很好用，就什么都往能用类上面靠。嘿嘿)
       然后就是showteam这个方法了。这个方法做两件事，就是当参数k=0的时候，调用index的display方法，然后返回。
     如果说k<>0，就做一个循环，在n里取一个数判断是不是在index这个了链表里面，如果不在，把这个数写入index，调用自己，参数为n，k-1，和改变了只偶的index。如果在，就countiue一下，下一个。
     至于你要的实例的话么。因为我是一个不是计算机专业，现在参加一个sap的abap的产前培训，觉得数据结构对提高代码效率和逻辑很有用。所以自学的。我只会vb和java。如果要例子的话么。我周末可以写利用excel中的vba写一个给你看。

[[i] 本帖最后由 Marshall605 于 2008-7-21 18:56 编辑 [/i]]

来学习一下了，较怕递归的问题

递归的本质是循环（个数可以不定），全排列的本质是两维循环。用一个递归解决两维循环很难。
编程的基本要求：
  1问：递归程序与非递归程序在编译成目标代码时有没有不同，回答没有，但不知道道理-----刚学编程
2问:递归程序与非递归程序在编译成目标代码时有没有不同，回答有，但不知道道理-----学了一年编程
3问：递归程序与非递归程序在编译成目标代码时有没有不同，回答没有，能知道为什么-----可以试试本题目

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

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

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

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

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

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

路过～

谢谢现在应该能够完全说明本题目了，以下是楼上朋友从白度上给出的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[i]<<" ";
f<<a[i];
}
cout<<endl;
f<<endl;
}

else
{
for (i=k; i<n; i++)
{
char temp = a[k];
a[k] = a[i];
a[i] = temp;
perm(a, k+1, n);
temp = a[k];
a[k] = a[i];
a[i] = 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[i] == 1)
temp[j++] = a[i];
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::out);
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[i] == 1)
temp[j++] = a[i];
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);
}
}

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

[font=宋体]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;
        }[/font]

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

回复 #19 feiyangdefei 的帖子

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