Pertanyaan Hanya sedikit masalah rekursi di Jawa


Saya saat ini hanya bekerja melalui beberapa masalah rekursi, dan saya saat ini terjebak pada satu.

Masalahnya adalah secara rekursif menyisipkan spasi ke dalam string, ke setiap lokasi yang mungkin, sehingga output terlihat seperti:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D
       A BC D
       AB CD
       AB C D
       ABC D

Saya saat ini bekerja pada masalah, dan sampai pada titik seperti:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D

Kode saya untuk masalah sejauh ini:

import java.util.Scanner;

public class Words 
{
    static int counter = 0;
    static String fString = "";
    static String fString2 = "";
    static String previous = "";
    static String input = "";
    static String other = "";

    public static String segment(String inputPrefix, String restOfString)
{
    if(restOfString.length() != 0)
    {   
        if(inputPrefix.equals(""))
        {
            fString += restOfString + "\n";
            segment(restOfString.substring(0,1), restOfString.substring(1));
        }
        else
        {
            previous += inputPrefix + " ";
            fString += previous + restOfString + "\n";
            fString2 = previous + restOfString;
            segment(restOfString.substring(0,1)
                            , restOfString.substring(1));
        }
    }
    /*else
    {
        counter++;
        other = fString2.replaceAll(" ", "");
        System.out.println(other);
        if((counter + 1) < other.length())
        {
            System.out.println("Other: " + other);
            input = other.substring(0, counter + 1);
            other = other.substring(counter + 1);
            System.out.println(counter);
            System.out.println("input: " + input);
            System.out.print("other: " + other);

            segment(input, other);
        }
        else
            return fString;
    }*/

    return fString;

}

public static void main (String[] args) 
{
    Scanner scan = new Scanner(System.in);
    System.out.print("Enter a string: ");
    String input = scan.next();
    System.out.println();
    System.out.println(segment("", input));

}
}

Klausul kedua yang lain adalah di mana saya mengalami masalah terbesar saya, karena setiap kali saya menjalankannya tanpa berkomentar, itu akan menjadi lingkaran tak terbatas. Saya bahkan memasukkan laporan jejak int (the println pernyataan) dan itu masih tidak membantu.

Saya sudah membacanya berkali-kali dan itu tidak masuk akal bagi saya mengapa itu tidak berhasil.


32
2018-04-01 15:51


asal


Jawaban:


Sepertinya Anda sudah bisa melakukan 'pengelompokan' pertama dengan benar, tetapi tidak dapat mendapatkan pengelompokan berikutnya.

Pengelompokannya adalah: 'A BCD', 'AB CD', dan 'ABC D'. Anda perlu menerapkan algoritma Anda untuk masing-masing pengelompokan ini. Anda telah menerapkannya ke yang pertama. Bagaimana Anda mendapatkan sisanya?

Sudah cukup waktu berlalu? Saya menulis solusi python hanya untuk melihat apa yang akan terlihat dibandingkan dengan Java.

def segment(input, separator=' ', start_from=0):
    print input
    # add spaces after each letter starting from start_from index, terminating at last letter-1
    for i in range(start_from, len(input)-1):
        # if the next letter is already a space, or this letter is a space, move on
        if separator in (input[i+1], input[i]): continue
        # whatever index we're on, do the next one recursively
        segment(input[:i] + input[i] + separator + input[i+1:], separator=separator, start_from=i+1)

segment('ABCD')

2
2018-04-02 03:30



Hal pertama yang membuat saya meragukan kode Anda adalah Anda harus mengembalikan serangkaian string, tetapi nilai kembali Anda adalah string.

Mungkin, Anda harus memakukan kasus dasar Anda dan langkah rekursif.

Sepertinya Anda sudah mulai dengan kasus dasar. Anda dapat memasukkan nol spasi dalam string kosong, jadi

allPossibleSpacings("") -> [ "" ]

tetapi Anda tidak ingin memasukkan spasi di bagian akhir, jadi Anda perlu kotak dasar kedua

allPossibleSpacings("x") -> [ "x" ]

dan kemudian langkah rekursif Anda bisa

allPossibleSpacings("x" + s) -> flatten(
    ∀ t : allPossibleSpacings(s), ["x" + t, "x " + t])

Saya tidak akan membantu Anda menulis itu di Java karena ini adalah pekerjaan rumah, tetapi harapan itu membantu.


4
2018-04-01 16:01



void recurse(String myString, int start){
        System.out.println(myString);
        for(int i = start; i < myString.length; i++) {
            if (myString.charAt(i) != ' ' ){
                recurse(myString.Substring(0,i) + ' ' + myString.Substring(i), i+2);
            }
        }
    }

panggilan pertama dengan recurse ("ABCD", 1);


3
2018-04-01 16:04