Trả về số nguyên tố nhỏ nhất được tạo ra từ xâu s

hodenvavutru121 · June 7, 2020, 4:01am

Cho xâu s là xâu chỉ chứa các ký tự trong bảng chữ cái. Từ xâu s bạn có thể tạo ra nhiều số tự nhiên bằng cách thay các ký tự trong s bằng các số bất kỳ với mỗi ký tự chỉ tương ứng với một số duy nhất và số được tạo ra không bắt đầu bằng chữ số 0.

Ví dụ:

Với s = "aba" thì bạn có thể tạo ra các số 121, 212, 373, ...
Với s = "cbba" thì bạn có thể tạo ra các số 2334, 5661, 1223, ...
Với s = "uu" thì bạn có thể tạo ra các số 11, 22, 33, ...
Với s = "ab" thì bạn không thể tạo ra các số 11, 22, 33, 44, ... do a và b tương ứng với 2 số khác nhau.
Với s = "abc" thì bạn không thể tạo ra các số 012, 089, 043, ... do số được tạo ra không được có số 0 ở đầu.

Hãy viết hàm trả về số nguyên tố nhỏ nhất được tạo ra từ xâu s biết số nguyên tố là số nguyên dương mà chỉ có 2 ước số nguyên dương là 1 và chính nó. Nếu từ s không thể tạo ra được số nguyên tố thì trả về -1 .

rogp10 · June 7, 2020, 3:48am

Duyệt chỉnh hợp nhé mỗi chỉnh hợp thay số vào và quay RM thử.

hodenvavutru121 · June 7, 2020, 3:49am

bạn có thể nói rõ hơn không ạ?

rogp10 · June 7, 2020, 3:57am

Đầu tiên bạn cần tìm hiểu cách sinh tổ hợp, chỉnh hợp

hodenvavutru121 · June 7, 2020, 4:03am

sau khi tìm hiểu cách sinh tổ hợp, chỉnh hợp thì sao ạ?

noname00 · June 7, 2020, 4:05am

Thì đây, bạn phải đọc hết comment của bạn ấy đã.

hodenvavutru121 · June 7, 2020, 4:06am

dạ vâng, nhưng cho em hỏi quay RM là gì thế?

noname00 · June 7, 2020, 4:06am

Là dùng Rabin - Miller để kiểm tra tính nguyên tố.

Sherly1001 · June 7, 2020, 4:14am

Yếu thì mới phải tự code cho khỏe lên nhé.

hodenvavutru121 · June 7, 2020, 4:33am

bạn cho mình xin hướng giải chi tiết được không ạ?

Sherly1001 · June 7, 2020, 5:09am

Bạn còn muốn chi tiết tới mức nào nữa?

Chỉ có mỗi vậy thôi mà.

Liệt kê các chỉnh hợp ứng với sâu s.
Thay số với mỗi chỉnh hợp và kiểm tra xem số đó có phải là snt hay không.
Nếu là snt thì kiếm tra xem đó có phải là số nguyên tố nhỏ nhất trong các chỉnh hợp được liệt kê hay không, có thì trả về nó, còn không có snt nào thì trả về -1.

Và đó là những điều mà anh Rogp10 đã nói ở trên rồi.

Sherly1001 · June 7, 2020, 5:12am

Không, code hộ bạn mình được gì đâu.

Và quan trọng hơn tất cả các bước trên thì tài liệu trên mạng đều có nhé. :V :V

hodenvavutru121 · June 7, 2020, 5:16am

cho mình xin một số tài liệu được không ạ

Sherly1001 · June 7, 2020, 6:18am

Đầu tiên phải xử lý vài việc trước đã. Đếm số lượng chữ cái khác nhau trong sâu s, đếm được k chữ cái khác nhau, k phải nhỏ hơn hoặc bằng 10, vì chỉ có 10 chữ số khác nhau.

Giờ việc của bạn là liệt kê chỉnh hợp chập k của n phần tử. <- gg y nguyên như v luôn, hoặc đọc trong cuốn Lập trình và Giải thuật - LMH, ở ý 3.3 phần 1.

Chú ý là phần tử đầu phải khác 0, n bằng 10.

Các bước sau mình tin rằng bạn có thể làm được r.

hodenvavutru121 · June 7, 2020, 5:57am

cảm ơn bạn nhiều lắm

rogp10 · April 23, 2021, 12:14pm

Không hẳn

Nó ntn:

# pseudo
pattern = s
pb = pattern.chars
a = pb.uniq
return -1 if a.empty? or a.length > 10
generator = Permutation.new(10, a.count, [1,0,2,3,4,5,6,7,8,9])
# dùng lambda để thoát khỏi hàm gọi nó luôn.
generator.each do { |c|
   # dịch từ pattern đã thu gọn (là a) ra số trong mảng c
   num = pb.translate(str.maketrans(a, c)).join.to_i
   # thay vì join thì: num = num.reduce(0) do |r, v| r*10+v end
   if num.prime? : print(num); return; end
}
print -1

hodenvavutru121 · June 7, 2020, 12:56pm

rogp10:

# pseudo 
pattern = s 
pb = pattern.chars 
a = pb.uniq 
return -1 if a.length > 10 
Combination.new([1,0,2,3,4,5,6,7,8,9],a.count).each do |c| # :D 
     # dịch từ pattern đã thu gọn (là a) ra số trong mảng c 
     num = pb.translate(str.maketrans(a, c)).join.to_i 
     # thay vì join thì: num = num.reduce(0) do |r, v| r*10+v end 
     return num if num.prime?
end 
return -1

Đây là ngôn ngữ gì vậy ạ?

rogp10 · April 23, 2021, 7:00am

translate với maketrans là Python

p/s: bài này ko phải tổ hợp… mà là chỉnh hợp.