Encode pesan dengan abjad

Question

Saya mencoba menyelesaikan masalah di bawah ini untuk meningkatkan keterampilan saya. Saya akan sangat menghargai jika seseorang meningkatkan kode saya dengan cara yang lebih baik.

Mengingat pemetaan a = 1, b = 2, ... z = 26, dan pesan yang disandikan, hitung jumlah cara pesan itu dapat diterjemahkan. Misalnya, pesan '111' akan menghasilkan 3, karena itu bisa diterjemahkan sebagai 'aaa', 'ka', dan 'ak'. Anda dapat berasumsi bahwa pesan dapat didekodekan. Misalnya, '001' tidak diperbolehkan.

#include <stdio.h>
#include <stdlib.h>

#define MIN_ALPH 1
#define MAX_ALPH 26

//return number of possible encode methods
int encode(unsigned int num)
{
    int count=0;
    unsigned int ddigit;
    
    //encode by 2 digits
    for(int i=10; i<=num; i*=10)
    {
        ddigit = (num % (i*10)) / (i/10);
        if (ddigit >= MIN_ALPH && ddigit <= MAX_ALPH)
            count++;
    }
    
    //extra count for the single digit encoding since all digits are non-zero
    return ++count;
}

int main(void) 
{
    /*Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, 
    count the number of ways it can be decoded.
    For example, the message '111' would give 3, 
    since it could be decoded as 'aaa', 'ka', and 'ak'.
    You can assume that the messages are decodable. 
    For example, '001' is not allowed.*/
    
    printf( "result: %d\n",  encode(512));
    printf( "result: %d\n",  encode(542));
    printf( "result: %d\n",  encode(112));
   
}

Answer 1

Terminologi ini agak ceroboh - saya akan menyebut operasi beralih dari digit kembali ke karakter alfabetis decoding daripada encoding - dan fungsi kita tidak benar-benar salah satu dari itu: itu menghitung . (Saya menduga bahwa Anda bukan penutur asli bahasa Inggris, jadi jangan menerima kritik ini terlalu kasar!).

---

Antarmukanya mengejutkan: menerima tipe integer sangat membatasi panjang maksimum input, dan kita bisa mengembalikan tipe unsigned sebagai hasilnya:

unsigned int count_decodings(const char *input);

Sebagai petunjuk, aman untuk mengonversi karakter menjadi digit dengan mengurangkan '0'(C menjamin bahwa angka 0..9 memiliki pengkodean yang berurutan, terlepas dari pengkodean karakter lingkungan host).

---

Algoritme menghasilkan hasil yang salah :

Komentar ini tidak dibenarkan:

//extra count for the single digit encoding since all digits are non-zero
return ++count;

Beberapa digit mungkin memang nol - misalnya, 10dan 201masing-masing dapat diterjemahkan dengan tepat satu cara. Itu seharusnya menyarankan beberapa pengujian tambahan yang dapat (dan harus) Anda lakukan.

---

Ada baiknya kita memiliki beberapa tes main(); Saya akan melangkah lebih jauh dan membuat tes pemeriksaan diri . Alih-alih hanya mencetak hasil, kita harus membandingkan dengan nilai yang diharapkan, dan mengembalikan EXIT_SUCCESShanya jika semua tes lulus. Ada beberapa pustaka yang tersedia untuk membantu pengujian unit seperti ini, atau Anda dapat melakukannya dengan mudah:

int failures = 0;
failures += count_decodings("10") != 1;
failures += count_decodings("11") != 2;
// more tests here

Kami tidak memiliki indikasi tes mana yang gagal, dan apa hasil yang diharapkan dan sebenarnya. Kita dapat membuat makro untuk membantu di sini (yang persis seperti yang disediakan kerangka pengujian unit untuk kita).

Answer 2

Untuk pesan 111111saya mendapatkan 13 kombinasi:

......aaaaaa

_.... kaaaa
._... akaaa
.._.. aakaa
..._. aaaka
...._ aaaak


__..  kkaa
_._.  kaka
_.._  kaak
.__.  akka
._._  akak
..__  aakk

___   kkk

Dengan angka "3" di tempat pertama, Anda kehilangan kkk, kaak, kaka, kkaa, dan kaaaa. Saya pikir Anda harus mulai dari maksimum kombinatorial dan kemudian memeriksa berapa banyak Anda dapat mengesampingkan. Tapi ini pasti sangat tidak sepele. Dari mana asalnya?

Ini:

99991999919999199991999919

masih bisa dibaca dengan berbagai cara tergantung bagaimana Anda menggabungkan lima pilihan untuk "ai" atau "s".

---

Program ini hanya mencetak "6" untuk "111111". Ini hanya dihitung dari "aaaaaa" hingga "aaaak" (di atas).