基本递归

这是我从学校收到的作业问题。问题是，写一个名为capitalizer的方法，它将字符串“拥有”，然后显示（不必返回）所有可能的大写字母，例如“OwNaGE”或“OWnAGE”。它不必为每一个字符串工作，只是“拥有”这个词就足够了，它必须用递归来完成。基本递归

这是我到目前为止。

import java.util.*; 

class MethodAssign2{ 
    static void capitalizer(String a,int b){ 
     if(b==-1){ 
     System.out.println("worked?"); 
     }else{ 
     char[] achars = a.toCharArray(); 
     achars[b] -= 32; 
     String caplet = new String(achars); 
     System.out.println(caplet); 
     System.out.println(a); 
     capitalizer(caplet,b-1); 
     capitalizer(a,b-1); 
     } 
    } 
    public static void main(String[]args){ 
     String word = "ownage"; 
     capitalizer(word,word.length()-1); 
    } 
}

我的大脑现在完全搞砸了。似乎我有很多重复的情况。你们认为我接近正确的解决方案吗？我该怎么做才能在基本案例中没有发生什么，而不是打印出某些东西？我如何避免重复？任何人都请帮助我，我会非常感激。

来源

2012-10-16 cook cook

这个网站是不是这种正确的地方的问题。试试代码审查网站。 – bmargulies

@bmargulies：我不同意。 CodeReview是“提供您对我的代码的看法”。这个问题是：“我有一个问题，这是我的尝试，但它失败了 - 我怎么能使它工作？”这是一个有效的SO问题。 – amit

不，操作员从不说他或她失败了，或者说什么是错的，只是他们发现代码很丑陋。 – bmargulies

为了避免重复 - 您应该只在stop子句中打印字符串，而不是在每次迭代中打印。

static void capitalizer(String a,int b){ 
    if(b==-1){ 
     System.out.println(a); //CHANGE: printing in the stop clause 
    }else{ 
     char[] achars = a.toCharArray(); 
     achars[b] -= 32; 
     String caplet = new String(achars); 
     //CHANGE: not printing every iteration 
     capitalizer(caplet,b-1); 
     capitalizer(a,b-1); 
    } 
}

如果算法的理念是：在每一个阶段你“猜测”是当前字符 - 是它的上限或下限的性格，并递归调用该算法上的小问题（下个字符）。
您可以重复这一点，因为当前的信件是和不是大写。

前面的代码失败，因为你印它的每一个字母的变化，这将导致更多的（几乎增加一倍）后生成的字符串，那么所有2^n 可能的方式打印的字。

（1）奖励：正好有2^n可能的字符串可以打印，因为每次你需要选择角色：它是大写或没有？你对每个字符重复这个问题，并从rule of product - 它给你完全2^n可能的字符串。

来源

2012-10-16 22:37:51 amit

我想我不应该只是复制你所拥有的东西，但我想我已经尝试过了，现在我明白了。非常感谢你。 –

@cookcook：你几乎到了那里，请注意，我在代码中所做的更改非常小。好工作，祝你好运！ – amit

看看这块你的代码：

System.out.println(caplet); 
System.out.println(a); 
capitalizer(caplet,b-1); 
capitalizer(a,b-1);

您打印字符串的当前版本，然后让他们重新办理。但是，当进一步处理时，就会发生没有更多变化。然而，在每一次迭代中，您仍然在打印相同的字符串。

你想要做的是删除这些打印，并在最后（在if(b==-1)区块）添加一个打印，您打印当前已完成的特定迭代集的最终结果。

来源

2012-10-16 22:36:25 Steven

递归思考时，请考虑重复步骤。

所以想最后一个字母，您有：

OWNAGE OWNAGE

让我们回到你有步：

OWNAGE OWNAGE OWNAGE OWNAGE

看到了吗？对于倒数第二个字母的每个选项，您都有最后一个字母的替代值。等等。

所以，想一想'如果我有前n个字母的所有替代品，那么我如何根据下一个字母来获得替代品？

想想如何解决这个问题，你会得到一个递归解决方案。

来源

2012-10-16 22:37:14 PaulJWilliams

您的递归函数应该处理它给出的单词的第一个字母，并依靠递归调用来操作剩余的字母。当你必须遍历一个复合对象的所有可能的状态时，这是一个非常常见的问题。

这不会编译，但（我认为）这里是伪代码的解决方案：

recursion(word){ 

List list = new List(); 

String firstLetter = firstLetter(word); 
String restOfWord = restOfWord(word); 

for(rest : recursion(restOfWord)){ 
list.append(firstLetter.uppercase()+rest); 
list.append(firstLetter.lowercase()+rest); 

return list; 
}

来源

2012-10-16 22:47:13

public static void capitalizer(String input) { 
    capitalizer("", input); 
} 

private static void capitalizer(String prefix, String buffer) { 
    if (buffer.isEmpty()) { 
     System.out.println(prefix); 
     return; 
    } 

    char c = buffer.charAt(0); 
    char cup = Character.toUpperCase(c); 

    String p = prefix + c; 
    String pup = prefix + cup; 

    String b = buffer.length() == 0 ? "" : buffer.substring(1, buffer.length()); 

    capitalizer(p, b); 
    capitalizer(pup, b); 
} 

public static void main(String[] args) { 
    capitalizer("ownage"); 
}

输出，

ownage 
ownagE 
ownaGe 
ownaGE 
ownAge 
ownAgE 
ownAGe 
ownAGE 
owNage 
owNagE 
owNaGe 
owNaGE 
owNAge 
owNAgE 
owNAGe 
owNAGE 
oWnage 
oWnagE 
oWnaGe 
oWnaGE 
oWnAge 
oWnAgE 
oWnAGe 
oWnAGE 
oWNage 
oWNagE 
oWNaGe 
oWNaGE 
oWNAge 
oWNAgE 
oWNAGe 
oWNAGE 
Ownage 
OwnagE 
OwnaGe 
OwnaGE 
OwnAge 
OwnAgE 
OwnAGe 
OwnAGE 
OwNage 
OwNagE 
OwNaGe 
OwNaGE 
OwNAge 
OwNAgE 
OwNAGe 
OwNAGE 
OWnage 
OWnagE 
OWnaGe 
OWnaGE 
OWnAge 
OWnAgE 
OWnAGe 
OWnAGE 
OWNage 
OWNagE 
OWNaGe 
OWNaGE 
OWNAge 
OWNAgE 
OWNAGe 
OWNAGE

来源

2012-10-17 01:26:08

回答

相关问题