开发者社区> 问答> 正文

java 递归问题

数据结构与算法分析的课后习题
编写带有下列声明的例程:
public void permute( String str );
private void permute( char [] str, int low, int high );
第一个例程是驱动程序,它调用第二个例程并显示String str中的字符的所有排列。如果str是"abc",那么输出的串则是abc,acb,bac,bca,cab和cba。第二个例程使用递归。

public class Permute
{public void permute ( String str )
{
    permute (str.toCharArray (), 0, str.length ());
    String tmp = new StringBuilder ().append (str).reverse ().toString ();
    permute (tmp.toCharArray (), 0, tmp.length ());
}

private void permute ( char[] str, int low, int high )
{
    if (low == high)
    {
        return;
    }
    String result = "";
    for ( int i = low; i < high; i++ )
    {
        result += str[i];
    }
    if (result.length () < str.length)
    {
        int count = str.length - result.length ();
        for ( int i = 0; i < count; i++ )
        {
            result += str[i];
        }
    }
    System.out.println (result);
    permute (str, ++low, high);
}

public static void main ( String[] args )
{
    Permute permute = new Permute ();
    permute.permute ("abc");
}

上面的代码,虽然也是方法自己调用自身,但感觉permute (str, ++low, high);这样的调用其实用for循环就能写出来,这个应该不能算是递归吧,
求更好的递归解法

展开
收起
蛮大人123 2016-03-09 19:02:57 2536 0
1 条回答
写回答
取消 提交回答
  • 我说我不帅他们就打我,还说我虚伪

    递归和循环本质是都是多次执行,是可以互相替代的,只是递归是另外一种思想,你的代码是递归
    但是,你的代码没办法完成的题目中说的结果,递归思想有问题,没有得出全部结果,一个长度为n的个字符不重复的字符串有n!种排列这个应该都知道吧,你可以执行adcd是无法出来24种结果的。下面是我刚才写的一个递归,没仔细查,可能有不对的,map主要是用来去重的

    public static void main (String[] args){
            String a = "abcd";
            test t = new test();
            t.permute(a);
        }
        public void permute ( String str )
        {
            Map<String,String> m = newPermute(str.substring(1),str.toCharArray()[0]+"");
            for (Map.Entry<String, String> entry : m.entrySet()) {
                System.out.println(entry.getKey().toString());
            }
        }
    
    
        private Map<String,String> newPermute(String string,String a){
            Map<String,String> map = new HashMap<String,String>();
            char[] str = string.toCharArray();
            if(str.length==1){
                map.put(str[0]+a,str[0]+a);
                map.put(a+str[0],a+str[0]);
                return map;
            }else{
                Map<String,String> m = newPermute(string.substring(1),str[0]+"");
                for (Map.Entry<String, String> entry : m.entrySet()) {
                    String key = entry.getKey().toString();
                    map.put(a+key,a+key);
                    map.put(key+a,key+a);
                    for(int i = 1;i < key.toCharArray().length;i++){
                        String newKey = key.substring(0,i)+a+key.substring(i);
                        map.put(newKey,newKey);
                    }
                }
            }
            return map;
        }
    2019-07-17 18:56:38
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
相关产品:
问答排行榜
最热
最新

相关电子书

更多
Spring Cloud Alibaba - 重新定义 Java Cloud-Native 立即下载
The Reactive Cloud Native Arch 立即下载
JAVA开发手册1.5.0 立即下载