Cải tiến thuật toán cho bài toán liệt kê số

Cho một số nguyên dương n và một số nguyên k (k >= 0) . Hãy tìm tất cả các số xn chữ số và các chữ số liền kề trong x cách nhau đúng k đơn vị (không có số 0 vô nghĩa ở đầu như 01). Các kết quả trả về lưu vào một mảng được sắp xếp tăng dần.

Ví dụ:

  • Với n = 3, k = 7 . Đầu ra createNumber(n,k) = [181,292,707,818,929] .

    Giải thích: Đối với số 181 thì số 1 ở vị trí 1 và số 8 ở vị trí 2 cách nhau 7 đơn vị, số 8 ở vị trí 2 và số 1 ở vị trí 3 cách nhau 7 đơn vị

Đầu vào/Đầu ra:

  • [Đầu vào] Integer n, k .
    1 <= n <= 9 0 <= k <= 9

  • [Đầu ra] Array Of Integers
    Số lượng số thỏa mãn đã được sắp xếp tăng dần
    Đây là cách làm của mình:

def hieu_cac_so(x):
	for i in range(len(x)-1):
		if i==0: ss1=abs(int(x[i])-int(x[i+1]))#
		ss2=abs(int(x[i])-int(x[i+1]))
		if ss2!=ss1: return -1
	return ss2
def createNumber(n,k):
	lst=[]
	for i in range(10**(n-1),10**n):
		if hieu_cac_so(str(i))==k:
			lst.append(int(i))
	return lst

Mọi người cho mình hỏi có cách nào hay hơn cách này không chứ mình chấm điểm bị sai mấy trường hợp test ẩn (chấm trên máy). Cảm ơn mọi người nhiều

Đối với các bài tìm dãy tất cả các số có n chữ số thỏa mãn điều kiện nào đó thì duyệt hết tất cả các số có n là cách đơn giản nhất, nhưng cũng chạy lâu nhất (người ta gọi là chạy trâu). Bài này không cần chạy trâu đâu, chỉ cần tìm tất cả các cặp 2 số có 1 chữ số cách nhau k đơn vị là được. Phức tạp hơn thì dùng đệ quy.

2 Likes

mình biết mà bạn, nhưng mà khi chấm máy nó bị sai mất mấy test ẩn. Trường hợp n=1 mình coppy thiếu, bạn thông cảm giúp mình

vòng for ấy đúng mà
nhưng
với n là 8 thì máy chấm chạy tắt thở rồi
bài này dùng đệ quy được rồi
số thứ i + 1 chỉ có 2 trường hợp là (a[i] + k) và (a[i] - k) và có thể ít hơn nếu một trong 2 số bị loại
DFS thôi, khi mảng a đủ độ dài n thì tăng biến đếm lên 1

4 Likes

mình có 2 vấn đề muốn hỏi kỹ lại bạn

  1. Đệ quy là gì, DFS là gì ?? (mình tự học nên hơi ngu tí)
  2. a[i] nó là cái gì ấy nhỉ ?? ‘khi mảng a đủ độ dài n thì tăng biến đếm lên 1’ : ý của bạn là gì mình ko hiểu rõ lắm

x có thể biểu diễn thành 1 mảng a, từng chữ số của x chính là a[i]
còn đệ quy là một kĩ thuật lập trình, bạn không biết thì có thể tìm hiểu , dfs cũng là một loại giải thuật (gọi là kĩ thuật chắc là hợp lí hơn)
bạn có thể google

2 Likes

ban đầu mình cx nghĩ giống bạn, nhưng mà sau khi cộng hoặc trừ a[i] r thì giá tri mảng a bị thay đổi. Giả sử mảng a nó có a[i] có thể cộng hoặc trừ k thì sau khi cộng hoặc trừ a[i] sẽ làm a thay đổi theo, làm hơi phức tạp xíu. Bạn chỉ mình phương án của cái bạn nói dc ko, chứ ban đầu mình làm giống bạn mà hơi rắc rối nên mình bỏ (hơi ngu xíu)

gợi ý cho bạn,
nếu số thứ i trong số x (là cái số thõa mãn đề bài) có giá trị là v
thì số tiếp theo sẽ rơi vào 2 trường hợp

  • a[i+1] = a[i] + k = v + k
    nếu lớn hơn 9 thì loại trường hợp này
  • a[i+1] = a[i] - k = v - k
    nếu nhỏ hơn 0 thì loại trường hợp này

tiếp tục tìm số thứ i + 2 từ các kết quả của các số thứ i+ 1…
tìm tới số cuối cùng, tăng biến kết quả thêm 1 chô mỗi kết quả tìm được

chỉ có vài dòng code mà bạn đã cảm thấy dài thì còn học chi nữa
cách làm này còn ngắn hơn cách của bạn làm

bạn cần tìm hiểu về đệ quy để làm bài này

3 Likes

mình có nói là code dài thì nản đâu, mình chỉ muốn hỏi là còn cách nào khác hay hơn không thôi.
Với lại bạn cho mình hỏi ngu phát nữa r mình thôi, mình ko làm phiền bạn nữa. Nếu 0<v+k<9 hoặc 0< v-k<9 thì làm ntn,ý mình là vậy, mình thấy bạn có nêu hai trường hợp, ý tưởng ban đầu của mình là vậy mà

bạn đã thử hiện thực theo cách đó chưa mà nghĩ nó không hay
làm sao đánh giá được một cách nào đó là hay hay không hay

vậy số kế tiếp còn trường hợp nào khác nữa sao? mình không nghĩ ra được ngoài (v - k) và (v + k) ra thì còn số nào khác cách v đúng k đơn vị

Cuối cùng mình gửi bạn một concept này
hàm tính bên dưới chỉ cần 3 dòng là xong và với n = 20 vẫn dư sức chạy
với n lớn hơn thì thêm 2 dòng nữa để tối ưu là xong

bài này giống với bài tính giai thừa bằng đệ quy, hoặc tính fibonaci bằng đệ quy
các từ khóa: đệ quy, quy hoạch động
nếu bạn ngại tìm hiểu kiến thức hay ngại viết thử code mới thì có thể bỏ qua
chúc bạn thành công

def count(v, n, k):
  # hàm này đếm số lượng - số có n chữ số
  # bắt đầi là v
  # các chữ số liền kề cách nhau đúng k đơn vị


cnt = 0
for i in range(9): 
  cnt += count(i+1, n, k) # số đầu tiên không được là số 0, nên chạy từ 1 - 9 
4 Likes

Tất nhiên là bài này tiếp cận theo đệ quy sẽ hiệu quả. Tuy nhiên do bạn chưa biết đệ quy là gì, bạn có thể tiếp cận theo cách lặp lại theo lối suy nghĩ thông thường.

Nôm na là thế này:
Thay vì bạn đang suy nghĩ về các con số thì hãy hình dung nó là 1 chuỗi các ký tự số.
n = 9 nghĩa là có 9 chữ số.
Do không có số 0 vô nghĩa, nên vị trí đầu tiên có 9 cách chọn.
Nghĩa là bạn chỉ cần xét 9 trường hợp 1->9.
Sau khi chọn được số thứ 1 thì số thứ 2 sẽ có 2 cách chọn (hoặc tăng lên k đơn vị , hoặc giảm xuống k đơn vị). Tuy nhiên nếu tăng hoặc giảm vượt quá giới hạn thì loại.

Cụ thể: n=4, k=1

  • Ta có: 1xxx , 2xxx, 3xxx, …
  • Tiếp theo sẽ là 12xx -> 121x và 123x
    Tương tự vậy

image

Sau cùng thì bạn in ra dạng string thay vì in số.

5 Likes

Chưa tiếp cận thì học thôi không thấy luật quy định đủ 60 tuổi mới được học đệ quy.

3 Likes

Tạo ra hai mảng, từ mảng 1 tính ra mảng 2.
Sau mỗi bước ta đổi vai trò của hai mảng (bước này đơn giản hơn bạn nghĩ :smiley: )

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?