đệ quy cơ bản

Question

Đây là câu hỏi chuyển nhượng mà tôi nhận được từ trường học. Câu hỏi đặt ra là viết một phương thức gọi là trình viết hoa vốn sẽ lấy chuỗi "quyền sở hữu" và sau đó hiển thị (không phải trả lại) tất cả các chữ viết hoa có thể có của nó, chẳng hạn như "OwNaGE" hoặc "OWnAGE". Nó không phải làm việc cho mọi chuỗi, chỉ từ "sở hữu" là đủ, và nó phải được thực hiện với đệ quy.

Đây là những gì tôi có cho đến nay.

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

Tâm trí của tôi hoàn toàn bị rối loạn ngay bây giờ. Có vẻ như tôi có nhiều trường hợp lặp đi lặp lại. Các bạn có nghĩ rằng tôi đóng giải pháp đúng không? Làm thế nào để làm cho nó để không có gì xảy ra trong trường hợp cơ sở hơn là in ra một cái gì đó? Làm cách nào để tránh lặp lại? Bất cứ ai hãy giúp tôi, tôi sẽ đánh giá cao nó rất nhiều.

Answer 1

Để tránh lặp lại - bạn chỉ nên in chuỗi của mình trong mệnh đề dừng chứ không phải trong mỗi lần lặp lại.

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

Ý tưởng nếu thuật toán là: Trong mỗi giai đoạn bạn "đoán" là những gì các nhân vật hiện tại - là nó trở thành một nhân vật trên hoặc dưới, và gọi các thuật toán đệ quy vào vấn đề nhỏ hơn (với ký tự tiếp theo) .
Bạn lặp lại điều này cho cả chữ cái hiện tại và không được viết hoa.

---

Đoạn mã trên thất bại vì bạn in các dây nó được tạo ra sau mỗi lần thay đổi bức thư, mà kết quả trong nhiều (gần gấp đôi) thì tất cả 2^n cách có thể in từ đó.

---

(1) Bonus: Có chính xác 2^n chuỗi có thể bạn có thể in, bởi vì đối với mỗi nhân vật bạn cần phải chọn: Có vốn hay không? Bạn lặp lại câu hỏi này cho từng ký tự và từ rule of product - nó cung cấp cho bạn chính xác các chuỗi có thể là 2^n.

Answer 2

Nhìn vào đoạn mã này của bạn:

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

Bạn in các phiên bản hiện tại của chuỗi, và sau đó đã cho họ xử lý một lần nữa. Tuy nhiên, khi bị xử lý thêm, nó sẽ xảy ra mà không có gì thay đổi. Tuy nhiên, trong mỗi lần lặp lại, bạn vẫn in cùng một chuỗi này.

Những gì bạn muốn làm là xóa các bản in này và thêm bản in ở cuối (trong khối if(b==-1)) nơi bạn in kết quả cuối cùng của tập hợp lặp lại cụ thể mà bạn đã hoàn thành tại thời điểm đó.

Answer 3

Khi suy nghĩ đệ quy, hãy suy nghĩ về các bước lặp lại.

Vì vậy, suy nghĩ về bức thư cuối cùng, bạn phải:

Ownage Ownage

Quay trở lại một bước bạn có:

Ownage Ownage Ownage Ownage

Thấy không? Bạn có các giá trị thay thế cho chữ cái cuối cùng, cho mỗi lựa chọn thay thế cho chữ cái thứ hai. ANd như vậy.

Vì vậy, hãy suy nghĩ về 'Nếu tôi có tất cả các lựa chọn thay thế cho chữ cái đầu tiên, thì làm cách nào để nhận các lựa chọn thay thế dựa trên chữ cái tiếp theo?

Suy nghĩ về cách giải quyết vấn đề đó và bạn sẽ nhận được giải pháp đệ quy.

Answer 4

Chức năng đệ quy của bạn nên thao tác chữ cái đầu tiên của từ mà nó được cung cấp và dựa vào các cuộc gọi đệ quy để thao tác các chữ cái còn lại. Đây là một vấn đề rất phổ biến xảy ra khi bạn phải lặp qua tất cả các trạng thái có thể có của một đối tượng hỗn hợp.

này sẽ không biên dịch, nhưng (tôi nghĩ) đây là giải pháp trong giả:

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

đầu ra,

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