Đây là một bài tập khá cơ bản về tư duy lập trình. Có nhiều cách để giải nó tuy nhiên ở đây tôi chỉ đề cập đến phương pháp tối ưu nhất.
I) Số số không tận cùng là gì ?
Ở đây nó có nghĩa là bạn đang đi tìm số số 10 xuất hiện trong tích của số đó hay nói cách khác là tìm (2 . 5) trong tích của n!. Vậy một cách cơ bản thì bạn chỉ cần đếm số lượng số hai và số lượng số 5 rồi sau đó chọn số nhỏ hơn.
1 2 3 4 5 6 | vd: 10! = 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 = 1 . 2 . 3 . 2 . 2 . 5 . 2 . 3 . 7. 2 . 2 . 2 . 9 . 2 . 5 số lượng số 5: 2 ; số lượng số 2: 8; => Vậy chọn số 2 ( ở đây 2 là số lượng số 5). => có 2 số không. Kiểm tra kết quả: 10! = 3628800 (có 2 số không). |
Tuy nhiên, có thể dễ dàng nhận thấy rằng số số 2 trong tích của n! luôn lớn hơn số số 5. Thật vậy, bởi trong khoảng từ 1 -> n có khoảng n/2 số 2 (bởi mọi số chẵn đều chứa 2 trong tích (chưa kể đến những số là lũy thừa của 2 như 4,8,..). Còn với số 5 thì chỉ những số có tận cùng là 0, 5 thì mới chứa 5 trong tích.
1 2 | vd: n=10 khi phân tích ra thành thừa số nguyên tố thì có 8 (có sự chênh lệch tương đối so với n/2) số 2 trong khi chỉ có 2 số 5. |
Vậy nên số số 5 trong tích của n! luôn nhỏ hơn số số 2 do đó chỉ cần tìm số lần xuất hiện của 5 trong tích của n!.
II) Giải quyết vấn đề đặt ra:
Đến đây bạn đã biết rằng chỉ cần đếm số số 5 trong tích của n!, lấy một ví dụ: 15! có 3 số 5 trong tích => có 3 số không tận cùng của n!.
Vậy đếm số số 5 đó như thế nào???
Như đã đề cập ở trên hay theo kiến thức đã học ở bậc tiểu học thì những số chia hết cho 5 (có 5 trong tích) thì đều tận cùng bởi các số 0 hoặc 5 mà những số chia hết cho 5 sẽ cách đều nhau 5 đơn vị:
1 2 | 5, 10, 15, 20, 25 => Đều chia hết cho 5. |
Ta hoàn toàn có thể tính được số lượng số chia hết cho 5 trong khoảng từ 1 -> n bằng phép toán n/5. Phải chăng như thế là đủ??? Cùng đến với một ví dụ:
1 2 3 4 | 25! = 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 . 11 . 12 . 13 . 14 . 15 . 16 . 17 . 18 . 19 . 20. 21 . 22 . 23 . 24 . 25 Theo công thức thì 25/5 = 5 nghĩa là có 5 sô 0 Tuy nhiên, 25! = 15511210043330985984000000 (có 6 số không) => Kết quả tính của chúng ta thiếu mất một số không. |
Vậy số không đó ở đâu???
Hành trình đi tìm số 0 bị thiếu:
Trước hết ta cần phải hiểu rõ tại sao lại thiếu mất một giá trị:
Khi ta lấy n/5 chính là ta đang đếm các số chia hết cho 5. Tuy nhiên số chia hết cho 5 cũng có số this, số that cũng có các số chứa 2, 3, 4, … số 5 trong tích: 25, 50, 75, 125, 3125, … Nghĩa là đối với các số này ta không chỉ lấy được 1 số 5 mà còn có thể là 2, 3, 4 số. Do đó ta cần phải định nghĩa lại:
1 2 3 4 | n/5 không còn là có bao nhiêu số 5 trong tích nữa mà là số lượng số có chứa ít nhất một số 5 trong tích. Vậy theo những gì đã nói ở trên thì ta lại phải tiếp tục tìm các số có chứa ít nhất 2, 3, 4, ... số 5 trong tích. vd: 25 = 5*5 => Có 2 số 5 trong tích. |
Vậy ta lại tiếp tục tìm các số chia hết cho 5. Giống như trên ta lại sử dụng công thức n/25. Cứ tiếp tục như vậy với 125, 625, các lũy thừa của 5.
Như vậy, một cách tổng quát, ta có:
n5+n52+…+n5kfrac{n}{5} + frac{n}{5^2} + … + frac{n}{5^k}5n+52n+...+5kn
Code trên C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | <span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string"><iostream></span></span> <span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token keyword">int</span> n<span class="token punctuation">;</span> cin<span class="token operator">>></span>n<span class="token punctuation">;</span> <span class="token keyword">int</span> d<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token operator">>=</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">{</span> n<span class="token operator">=</span>n<span class="token operator">/</span><span class="token number">5</span><span class="token punctuation">;</span> d<span class="token operator">+=</span>n<span class="token punctuation">;</span> <span class="token punctuation">}</span> cout<span class="token operator"><<</span>d<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Vậy tại sao lại cứ liên tục n/5, không giống với công thức:
Vì n25=n55frac{n}{25} = frac{frac{n}{5}}{5}25n=55n nên chỉ cần làm như code là đươc.
Lời kết:
Cảm ơn vì đã xem