5

这是我从学校收到的一个作业问题。问题是，编写一个名为capitalizer 的方法，它将采用字符串“ownage”，然后显示（不必返回）它的所有可能的大写形式，例如“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);
   }
}

我的脑子现在完全乱了。好像我有很多重复的案例。你们认为我接近正确的解决方案吗？我该如何做到这一点，以便在基本情况下没有任何事情发生，而不是打印出一些东西？如何避免重复？任何人请帮助我，我将非常感激。

4

5 回答 5

4

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

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可能的字符串，因为对于您需要选择的每个字符：是否大写？您为每个字符重复这个问题，并根据产品规则- 它为您提供了完全2^n可能的字符串。

于 2012-10-16T22:37:51.780 回答
1

看看你的这段代码：

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

您打印字符串的当前版本，然后再次处理它们。但是，当进一步处理时，将发生任何事情都没有改变的情况。然而，在每次迭代中，您仍在打印相同的字符串。

您想要做的是删除这些打印，并在最后（在if(b==-1)块中）添加一个打印，您可以在其中打印您在该点完成的特定迭代集的最终结果。

于 2012-10-16T22:36:25.197 回答
1

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

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

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-16T22:47:13.630 回答
0

递归思考时，请根据重复的步骤进行思考。

所以考虑最后一个字母，你有：

自有自有

退一步你有：

拥有 拥有 拥有 拥有 拥有 拥有

看？对于倒数第二个字母的每个备选方案，您都有最后一个字母的备选值。等等。

因此，请考虑“如果我有前 n 个字母的所有备选方案，那么我如何根据下一个字母获得备选方案？

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

于 2012-10-16T22:37:14.417 回答
0 
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-17T01:26:08.637 回答