Phân tích một số N thành tổng các ước khác 1 của K

#1

Phân tích một số N thành tổng các ước khác 1 của K. Điều kiện: K<N<=300. Gợi ý em cách giải quyết đc k ạ?

#2

cho N = 259, K = 192
bạn biết giải tay không?

#3

Đề bài này không hợp lý. Ví dụ đơn giản N=15, K=7. K chỉ có ước là 7 và 15 không thể phân tích thành tổng các ước khác 1 của 7

#4

khi không phân tích được thì có thể trả ra thông báo mà bạn. Nhưng đề bài cũng hơi ngắn quá, các ước có phải khác nhau không hay có thể trùng, ví dụ phải là 2+4 hay có thể 2 + 2 + 2.

1 Like
#5

Để phân tích một số N thành tổng các ước khác 1 của K, ta có thể áp dụng thuật toán quy hoạch động. Bước đầu tiên là tạo một bảng hai chiều có kích thước (N - K) x K, và khởi tạo tất cả các giá trị trong bảng bằng 0. Giá trị tại vị trí (i, j) trong bảng này đại diện cho số cách phân tích số i + K thành tổng các ước khác 1 của K, trong đó ước lớn nhất của số đó không vượt quá j.

Sau khi khởi tạo bảng, ta thực hiện các bước sau đây:

  1. Với mỗi giá trị j từ 2 đến K, ta gán giá trị 1 cho ô (j-1, j) trong bảng. Ý tưởng ở đây là với mỗi số từ K đến 2K - 1, ta có thể phân tích nó thành tổng K + (i - K) = i và một ước là j. Vì vậy, ta có thể sử dụng các ước từ 2 đến K để phân tích các số này.
  2. Với mỗi giá trị i từ 1 đến N - K - 1, ta thực hiện vòng lặp từ 2 đến K và tính giá trị tại ô (i+j, j) bằng tổng của giá trị tại ô (i, j) và giá trị tại ô (i, j-1). Nếu i+j chia hết cho j, ta cập nhật giá trị tại ô (i+j, j) bằng giá trị tại ô (i+j, j) cộng với giá trị tại ô (i, j-1).
  3. Sau khi thực hiện xong bước 2, ta có thể xác định số cách phân tích N thành tổng các ước khác 1 của K bằng giá trị tại ô (N-K, K-1) trong bảng.
#6

Bài này có thể tách thành hai phần, phần 1 là tìm ước của K và phần 2 là QHĐ để giải bài phân tích N thành tổng.

Với dp[i][sum] là số số có tổng bằng sum, khi lấy i-1 ước:

  • Khởi tạo dp[0][0] = 0 (empty sum) và dp[…][…] = inf
  • Mỗi ước d chỉ xuất hiện tối đa 1 lần thì ta tính dp[i+1][j] = min(dp[i][j], dp[i][j-d] + 1) (vì (j-d) + d = j)
  • Mỗi ước d có thể xuất hiện nhiều lần thì dp[i+1][j+k*d] <?= dp[i][j] + k

Từ đây bạn có thể viết thêm để xuất ra dãy ngắn nhất có tổng bằng N.

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