Asked May 24th, 2021 4:40 a.m. 71 0 1
  • 71 0 1
0

Thuật toán liệt kê các chuỗi khác nhau từ các kí tự ban đầu

Share
  • 71 0 1

Xin chào mọi người, mình có 1 thuật toán này mà chưa tìm được phương pháp tối ưu, mong mọi người giúp đỡ. input: cho 12 kí tự : A,B,C,D,E,F,G,H,I,J,K,L output: liệt kê các chuỗi khác nhau bao gồm 7 kí tự được lấy từ 12 kí tự trên, ví dụ :

  1. A,A,A,A,A,A,A
  2. A,A,A,A,A,A,B 3.A,A,A,A,A,B,A .... .... (n). L,L,L,L,L,L,L

bài toán trên giống bài toán lớp 11. Cho các số tự nhiên 1,2,3,4,5,6,7,8,9 liệt kê tất cả các số gồm 4 chữ số. vd: 1111, 1112, 1121, 1211, 2111.... 9999 Cho mình xin hướng giải quyết với ạ, mình cảm ơn ạ!

1 ANSWERS


Answered May 24th, 2021 4:43 a.m.
Accepted
+3

Nếu bạn dùng Python thì khá đơn giản:

from itertools import product
for chars in product('ABCDEFGHIJKL', repeat=7):
    print(''.join(chars))

Còn không thì có cách khác 😄 Đó là để ý mỗi chữ cái có 12 trường hợp, giống như các số base-12:

def i2b12(i: int):
    res = [0] * 7
    for idx in range(7):
        res[6 - idx] = i % 12
        i //= 12
    return res

for i in range(12 ** 7):
    print(''.join('ABCDEFGHIJKL'[x] for x in i2b12(i)))

Bạn có thể optimize bằng cách tăng dần idxs mà không phải tính lại base-12 representation mỗi lần, nhưng nó lằng nhằng nên sẽ để bạn tự tìm hiểu 😄

Share
May 24th, 2021 4:48 a.m.

oh, không biết bên javascript, C, php có không nhỉ, cảm ơn bạn nha, để mình cài python chạy thử

0
| Reply
Share
May 24th, 2021 4:56 a.m.

@ngoctnq mình đọc python ko hiểu lắm, để mình tìm hiểu thêm, cảm ơn bạn nhiều nha, mình đang muốn viết bằng js á

0
| Reply
Share
Avatar Ngoc N Tran @ngoctnq
May 24th, 2021 5:03 a.m.

@hoangkim1982 2 bên đó đều tương tự nhé bạn: ví dụ bên C:

#include <stdio.h>
#include <math.h>

int main() {
    unsigned int i, num;
    int j;
    char string[7];
    for (i = 0; i < pow(12, 7); ++i) {
        num = i;
        for (j = 6; j >= 0; --j) {
            string[j] = (char) ((int)'A' + num % 12);
            num /= 12;
        }
        printf("%s\n", string);
    }
    return 0;
}
0
| Reply
Share
Avatar Ngoc N Tran @ngoctnq
May 24th, 2021 5:09 a.m.

@hoangkim1982 còn code JS thì như sau:

let i, j, val;
for (i = 0; i < Math.pow(12, 7); ++i) {
  let s = "";
  val = i;
  for (j = 6; j >= 0; --j) {
    // 65 is charcode of 'A'
    s = String.fromCharCode(65 + val % 12) + s;
    val /= 12;
  }
  console.log(s);
}
0
| Reply
Share
May 24th, 2021 5:10 a.m.

@ngoctnq cảm ơn bạn nhiều nhé, mình hiểu rồi 😃

+1
| Reply
Share
May 24th, 2021 5:57 a.m.

@ngoctnq ah cái input mình ví dụ là chữ cái A,B,C vậy thôi còn thực tế nó là tên người đó cậu, ví dụ Hiep, Tien, Hoa.... thì cách trên bạn viết bằng js đó phải gán vào 1 mảng ví dụ A => Hiep, B => Tien đúng ko c nhỉ

0
| Reply
Share
Avatar Ngoc N Tran @ngoctnq
May 24th, 2021 9:23 a.m.

@hoangkim1982 à đúng rồi nhé, thay đổi chút xíu thôi, dùng indexing thay vì char + xài list thay vì string

0
| Reply
Share
Viblo
Let's register a Viblo Account to get more interesting posts.