Podstawowa rekursja

Question

To jest pytanie na temat zadania, które otrzymałem ze szkoły. Pytanie brzmi: napisz metodę o nazwie capitalizer, która pobierze ciąg "ownage", a następnie wyświetli (nie musi zwracać) wszystkie możliwe kapitalizacje, takie jak "OwNaGE" lub "OWNAGE". Nie musi działać dla każdego ciągu, wystarczy słowo "ownage" i musi zostać wykonane z rekursją.

Oto, co mam do tej pory.

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); 
    } 
} 

Mój umysł jest teraz całkowicie sponiewierany. Wygląda na to, że mam wiele powtarzających się przypadków. Czy uważasz, że jestem blisko właściwego rozwiązania? Jak zrobić to, aby nic się nie działo w podstawowym przypadku, zamiast drukować coś? Jak uniknąć powtórzeń? Niech ktoś mi pomoże, doceniłbym to bardzo.

Answer 1

Aby uniknąć powtórzeń - należy napisać ciąg tylko w klauzuli stop, a nie w każdej iteracji.

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); 
    } 
} 

Pomysł jeśli algorytm jest: W każdym etapie ty „zgadywać” co jest obecny charakter - jest to górna lub dolna postać i wywołać algorytm rekurencyjnie na mniejszym problemem (z następnego znaku) .
Powtarzacie to, ponieważ bieżąca litera jest i nie jest pisana wielkimi literami.

---

Powyższy kod nie powiodło, ponieważ drukowane struny to wygenerowane po każdej zmianie litery, co skutkuje znacznie więcej (prawie dwukrotnie), a następnie wszystkie 2^n możliwe sposoby, aby wydrukować słowo.

---

(1) Bonus: Istnieje dokładnie 2^n możliwych ciągów można wydrukować, ponieważ dla każdej postaci potrzebnych do wyboru: czy kapitalizowane lub nie? Powtórzyć to pytanie dla każdego znaku, a od rule of product - to daje dokładnie 2^n możliwych ciągów.

Answer 2

Spójrz na ten kawałek kodu:

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

wydrukować bieżące wersje napisu, a następnie zostały one ponownie przetwarzane. Jednak przy dalszym postępowaniu stanie się tak, że nic więcej się nie zmieni. Jednak w każdej iteracji wciąż drukujesz ten sam ciąg.

To, co chcesz zrobić, to usunąć te wydruki i dodać wydruk na samym końcu (w bloku if(b==-1)), gdzie wydrukujesz końcowy wynik określonego zestawu iteracji, które ukończyłeś w tym punkcie.

Answer 3

Myśląc rekurencyjnie, myśl w kategoriach powtarzających się kroków.

więc myśleć o ostatnim liście, trzeba:

ownage Ownage

Wracając krok masz:

ownage Ownage Ownage Ownage

See? Masz alternatywne wartości dla ostatniej litery, dla każdej alternatywy dla drugiej do ostatniej litery. I tak dalej.

Myśl w kategoriach "Jeśli mam wszystkie alternatywy dla pierwszych n liter, w jaki sposób mogę uzyskać alternatywne rozwiązania na podstawie następnego?

Pomyśl, jak rozwiązać ten problem, a otrzymasz rozwiązanie rekursywne.

Answer 4

Twój rekurencyjna funkcja powinna manipulować pierwszą literę słowa, że ​​jest podany i polegać na wywołań rekurencyjnych manipulować pozostałe litery. Jest to bardzo powszechny problem, który występuje, gdy trzeba powtórzyć wszystkie możliwe stany obiektu złożonego.

Nie będzie to skompilować, ale (chyba) jest tu rozwiązanie w Pseudokod:

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; 
} 

Answer 5

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"); 
} 

wyjście,

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