Các bài toán phân tích số
Cao Minh Anh
Trong quá trình học chắc các bạn sẽ gặp rất nhiều các bài toán về phân tích số. Các bài này có rất nhiều dạng khác nhau. Sau đây tôi xin đề cập đến một số bài toán để cùng trao đổi với các bạn.
Bài 1: Cho số nguyên dương M(M<=232),tìm cách phân tích M ra các số nguyên dương khác nhau có tổng bằng M sao cho tích của chúng là lớn nhất.
Mart.inp
M
Mart.out
a1 a2 a3 … ak
Ví dụ:
Mart.inp
11
Mart.out
2 4 5
Với bài toán trên thì có nhiều cách giải khác nhau,sau đây tôi xin trình bày với các bạn một thuật toán để giải bài này có tính mô phỏng. Đó là “thuật toán rải đậu”.
Sau đây tôi xin trình bầy tư tưởng thuật toán như sau:
Thuật toán:
+Xây dựng mảng a với a[1]=2;
a[I]=a[I-1]+1;(I>=2)
Tìm k lớn nhất sau cho a[1]+a[2]+..+a[k]<=M;
+ Xét d:=M-(a[1]+a[2]+..+a[k]);
+ Bây giờ ta tưởng tượng ta đang có d hạt đậu, chúng ta bắt đầu rải từng hạt đậu vào các a[I](1<=I<=k) theo chiều từ k1. Nếu rải đến 1 mà vẫn còn thì ta vẫn rải lại bắt đầu từ k lại,cứ như thế cho đến khi không còn hạt đậu nào. Khi rải đậu đến ô nào thì tăng giá trị của ô đó lên.
Sau đó xuất mảng a[i] ra là giải quyết xong bài toán.
Xong trên chỉ là tư tưởng của thuật toán trên, nếu làm theo cách đó thì ta sẽ tốn nhiều thời gian và dữ liệu. Sau đây tôi xin giới thiệu một cách cài đặt giúp tăng thời gian và giảm dử liệu:
Ở bước một ta tìm K lớn nhất cho a[1]+a[2]+..+a[k]<=M
+ Giải phương trình:2+3+4+..+(k-1)<=M
<-> k(k-1)/2 <=M-1.
Giải phương trình trên tìm nghiệm k nguyên trong khoảng nghiệm là được.
Bước hai: Thay vì mỗi lần ta rãi 1 hạt, mà ta rải (d div k) hạt đậu từ a[k]àa[1] (Với d là số hạt đậu còn lại, k là số ô để ta bỏ đậu vào), sau đó sẽ còn dư (d mod k) ta lại rải lại từ cuối đến đầu. Như vậy chỉ mất 2 lần
rải.
Một điểm nữa là kết quả xuất ra là một dãy liên tiếp đức đoạn, có nghĩa là nó mất một số trên đoạn tăng đó.
Ví dụ: 22 à 2 3 4 6 7 (Mất 5)
40 à 2 3 5 6 7 8 9 (Mất 4)
Như vậy ta cũng không cần mảng để lưu nữa, ta sẽ tính xem những số từ đâu đến đâu tăng M div n,những số từ đâu đến đâu tăng (M div n) + 1.
