Bài tập nghiên cứu 3

Bài 3: Tính F(x)

Cho hàm F(x), x ≥ 0 được định nghĩa như sau:
F(x) = x, nếu x ≤ 9
F(x) = F(S(x)), nếu x > 9
Trong đó S(x): tổng các chữ số của x.

Yêu cầu: Hãy viết chương trình tính F(n!), với 1 ≤ n ≤ 500.

Phân tích bài toán:

Để dễ hình dung hàm F(x), mình sẻ lấy một ví dụ:

Vd:  với x=123456789:

x>9 => F(x)=F(1+2+3+4+5+6+7+8+9)=F(45)

45>9 => F(45)=F(4+5)=F(9)

9≤9 => F(9)=9

Như thế, với việc tính F(n!) ta chỉ cần tính n!, xong rồi đi theo tuần tự của việc tính F(x) như trên thì bài toán được giải quyết. Nhưng có một vấn đề vô cùng lớn ở đây là việc tính n!. Với n khoản trên dưới 100 thì n! đã là một số vô cùng lớn (vài trăm chữ số) , với giới hạn của đề bài là n=500 thì theo ước tính của mình thì 500! khoảng vài nghìn chữ số. Nên phương pháp tính n! không phải là một phương pháp hay ở đây. Cần có một hướng đi thông minh hơn.

Đễ các bạn dễ hình dung hơn nữa về hướng đi của mình, mình sẻ đưa ra bảng giá trị F(n!) tương ứng các giá trị n:

n 1 2 3 4 5 6 7 8 9 10 11 100 1000 2222 F(n!) 1 2 6 6 3 9 9 9 9 9 9 9 9 9

Nếu để ý thì bạn sẻ nhận ra một điều thú vị ở đây là:  với các giá trị n≥6 thì F(n!)=9, và mình cũng thử tính với nhiều giá trị n>6 khác và vẫn được kết quả là F(n!) = 9 (ban đầu chỉ là phỏng đoán)

Và mình đã thử chứng minh xem liệu điều phỏng đoán này có đúng hay không!.

Và may mắn là điều này đúng!

Cách chứng minh như sau:

+Ta có một kết quả sau về số tự nhiên: Một số tự nhiên chia hết cho 9 thì tổng của các số đó cũng chia hết cho 9.

Với S(A) = tổng các chữ số của A (như để bài)

Kết quả này được trình bày lại như sau: Nếu A chia hết cho 9 => S(A) chia hết cho 9

+Như vậy:

Nếu N chia hết cho 9 => S(N) chia hết cho 9.

Mà S(N) chia hết cho  9 => S(S(N)) chia hết cho 9

…..

Vậy, đến cuối cùng chúng ta sẻ được số 9.

VD: 123458 chia hết cho 9 => S(123458)=18 chia hết cho 9 => S(18) = 9 chia hết cho 9. Đến ngang 9 thì dừng vì chỉ còn lại 1 chữ số

Giải thuật:

Nhờ điều may mắn trên mà bài toán của chúng ta trở nên vô cùng đơn giản:

Chỉ việc liệt kê các giá trị F(n!) khi n<6 , còn lại n ≥6 thì F(n!)=9

Mã nguồn:

#include <stdio.h> int f(int n); int f(int n) {    int k;        switch (n)        {        case 1 : k=1; break;        case 2 : k=2; break;        case 3 : k=6; break;        case 4 : k=6; break;        case 5 : k=3; break;           default: k=9;        }        return k; } void main() { int n;        printf("nhap n:");           scanf("%d",&n);            printf ("F(%d!) = %d ",n,f(n)); }

-----------------------

Thực ra, ban đầu mình đã phải làm một hướng khác, và sau khi làm xong, chạy thử với các số n thì mình mới phát hiện hiện ra điều may mắn trên. Nên mình cũng muốn chia sẻ thêm với các bạn về hướng giải này của mình:

Mình phát hiện ra kết quả sau:

F(a*b)= F(a*F(b))                             (1)

Hệ quả :  F(a*b)= F(F(a)*F(b))         (2)

Việc chứng mình mình để các bạn tự làm. Nhìn thì đơn giản, nhưng công thức này khá mạnh đấy ^_^.

VD:  Tính F(5214785632514965841 * 36524)
Việc tính con số trên cũng đã không hề đơn giản, nhưng áp dụng hệ quả của kết quả trên thì mọi việc đơn giản hơn nhiều:

F(5214785632514965841 * 36524) = F(F(5214785632514965841)* F(36524))

Mà F(5214785632514965841) =5;     F(36524) = 2 
=> F(5214785632514965841 * 36524)= F(5*2) =1

Để tính F(n!)  mình sẻ dùng kểt quả (1) (nếu dùng hệ quả (2) thì bài toán sẻ mạnh hơn, nhưng vì ở đây n ≤500 nên mình chỉ dùng (1) để bài toán được đơn giản)

Ta sẻ tính tuần tự như sau:

F(2!)

 -> F(3!) =F(3*F(2!))

-> F(4!)=F(4*F(3!))

->….

-> F(n!)=F(n*F( (n-1)!) )

Với hướng đi này, chúng ta có thể mở rộng bài toán tính F(x) với x  là các số lớn với dạng tích ví dụ như lũy thừa  N^N chẳng hạn.