基本递归

Question

这是我从学校收到的作业问题.问题是,写一个名为capitalizer的方法,它将获取字符串"ownage",然后显示(不必返回)它的所有可能的大写,例如"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);
   }
}

我的思绪现在完全混乱了.好像我有很多重复的案例.你们认为我接近正确的解决方案吗？如何使基本情况下没有任何事情发生而不是打印出来？我该如何避免重复？任何人请帮助我,我会非常感激.

Answer 1

为了避免重复 - 您应该仅在 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可能的字符串，因为对于每个字符，您需要选择：是否大写？您对每个字符重复这个问题，并且根据乘积规则- 它为您提供了确切2^n可能的字符串。