Ini adalah program untuk menemukan jumlah karakter paling sedikit yang harus dimasukkan (pada posisi apa pun) untuk mengubah string yang diberikan menjadi palindrom. Adakah yang bisa menjelaskan kepada saya apa yang terjadi lebih detail di dalam fungsi palindrom? Saya kesulitan memahami fungsi rekursif yang dipanggil lagi di dalam kondisi lain. Terima kasih!

#include <stdio.h>
#include <string.h>


int min(int a, int b) 
{ 
    if(a > b)
        return b;
    else
        return a;
} 

int palindrome(char string[], int l, int h) 
{
    if (l >= h)
        return 0; 
    if(string[l] == string[h])
        return palindrome(string, l+1, h-1);
    else
    {
        int choice1 = 1 + palindrome(string, l+1, h);
        int choice2 = 1 + palindrome(string, l, h-1);
        return min(choice1, choice2);
    }  
} 

int main() 
{ 
    char string[20];
    printf("ENTER STRING: ");
    scanf("%s", string);
    printf("%d", palindrome(string, 0, strlen(string) - 1)); 
    return 0; 
} 
1
c0mp13x 17 April 2020, 22:26

1 menjawab

Jawaban Terbaik

Sepotong kode ini memecahkan masalah berikut:

Anda diberi string. Berapa banyak karakter yang harus Anda masukkan ke dalamnya untuk membuatnya menjadi palindrom?

Ada satu set pengamatan yang bagus yang bisa kita lakukan untuk memecahkan masalah ini. Sebagai permulaan, perhatikan bahwa string dengan panjang nol atau satu sudah merupakan palindrom. Akibatnya, jika kita diminta untuk menambahkan karakter ke string dengan panjang nol atau satu, maka kita tidak perlu menambahkan karakter sama sekali. Kami sudah memiliki palindrom! Itu memberi kami kasus dasar kami:

Base Case: Setiap string dengan panjang nol atau satu tidak memerlukan karakter tambahan untuk membuat palindrom.

Misalkan, sebagai gantinya, kita memiliki dua atau lebih karakter dalam string kita. Agar menjadi palindrom, karakter pertama dan terakhirnya harus cocok satu sama lain - jika tidak, itu bukan palindrom. Banyak hal lainnya yang harus terjadi agar string kita menjadi palindrom, tetapi tentu saja jika karakter pertama dan terakhir tidak cocok, kita dalam masalah.

Jadi mari kita mulai dengan melihat karakter pertama dan terakhir dari string kita. Entah mereka cocok, atau tidak. Dalam kasus di mana mereka cocok, kami dalam kondisi yang baik! Kami tidak perlu menambahkan karakter tertentu untuk secara khusus membuat kedua karakter tersebut cocok satu sama lain. Pada saat itu, yang harus kita lakukan adalah memastikan bahwa karakter yang tersisa - yang ada di dalam - cocok satu sama lain. Itu memberi kita kasus sederhana lain untuk dipertimbangkan:

Kasus Rekursif 1: Jika karakter pertama dan terakhir dari string cocok, anggap karakter tersebut tidak ada, lalu secara rekursif cari tahu berapa banyak karakter yang diperlukan untuk membuat karakter tengah string menjadi palindrom.

Di sisi lain, kita mungkin memiliki string di mana karakter pertama dan terakhir tidak cocok. Itu berarti kita sedang melihat, secara skematis, pada string yang terlihat seperti ini:

a - - - - - - - - - - - - - - - - - - b

Sekarang, apa yang harus terjadi untuk membuat string ini menjadi palindrom? Yah, kita harus memasukkan setidaknya satu karakter untuk membuat semuanya cocok, karena kita harus mendapatkan karakter pertama dan terakhir yang sama. Namun, ada dua cara berbeda yang bisa kita lakukan. Opsi pertama adalah menambahkan a ke akhir string, seperti ini:

a - - - - - - - - - - - - - - - - - - b a

Jika kita meletakkan a di sini, maka, dengan menggunakan aturan di atas, kita akan mengatakan bahwa karakter pertama dan terakhir cocok, jadi kita bisa membuang karakter pertama dan terakhir dan melihat apa yang tersisa:

- - - - - - - - - - - - - - - - - - b

Efek bersih dari ini adalah bahwa kita pada dasarnya telah membuang karakter pertama dari string (asli a) dengan menambahkan satu karakter lagi ke string. Dari sini, kami ingin melakukan apa pun yang terbaik untuk membuat sisa string menjadi palindrom.

Opsi lainnya adalah meletakkan b di depan string:

b a - - - - - - - - - - - - - - - - - - b

Di sini, kita dapat mencocokkan b baru ini dan yang lama, dengan memberikan ini:

a - - - - - - - - - - - - - - - - - -

Itu mengharuskan kami untuk menambahkan satu karakter, dan kemudian kami ingin (secara rekursif, tentu saja) mencari tahu jumlah karakter paling sedikit yang perlu ditambahkan ke sisa string untuk menjadikannya palindrom.

Secara keseluruhan, ini memberi kita aturan berikut:

Kasus Rekursif 2: Jika karakter pertama dan terakhir tidak cocok, maka kita perlu menambahkan satu karakter lagi, baik di depan atau di belakang, untuk mencocokkannya. Jadi coba hapus karakter pertama dari string dan lihat cara terbaik untuk melanjutkan dari sana, lalu jatuhkan karakter terakhir dari string dan lihat opsi terbaik dari sana, dan ambil opsi mana yang lebih baik. Jangan lupa tambahkan 1 untuk karakter yang kita masukkan!

Sekarang setelah Anda melihat deskripsi ini, dapatkah Anda memetakan kasus dasar ini dan dua langkah rekursif ke dalam kode yang telah Anda bagikan dengan kami?

Semoga ini membantu!

4
templatetypedef 17 April 2020, 19:56