Một vài bài toán hay 

Bài 1: Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 10⁹

Ví dụ:

Số nhập vào là A	Số xuất ra là N
8	4
13	13

Tiếp cận bài toán :

            Đây là bài toán khá phức tạp và có giới hạn lớn , không thể giải quyết bài toán theo phương pháp thông thường (làm theo định nghĩa) , cần tìm ra một phương pháp giải nhanh chóng và hiệu quả hơn .

Hướng suy nghĩ : Sử dụng phương pháp phân tích số thành thừa số nguyên tố .

Giải quyết :

            Theo ta biết , chúng ta có thể mô tả việc một số a chia hết cho một số b dựa vào thừa số nguyên tố của số a và số b .

            Giả sử a được phân tích thành : a=x1^a1*x2^a2*…*xn^an

                       b được phân tích thành : b=x1^b1*x2^b2*..*xm^bm             =>  a chia hết cho b.

                                                                                          an >=bm

                                                          a1>=b1, a2>=b2,….,an>=bn

Ta xem N^N là số a như trên , A là số b. Ta gọi X=(x1*x2*x3…*xm).Ta thấy rằng chỉ có những bội số của X mới có thể là kết quả của bài toán ( vì những số đó khi phân tích sẽ chứa tất cả các thừa số trong số A)  . Vậy ta chỉ cần xét các số N= i*X ( với i chạy từ 1 đến khi N>=A, tức là i*x>=A, bởi vì ta thấy kết quả tối đa là A, không thể lớn hơn A).Với mỗi N ta kiểm tra xem N có phải là kết quả của bài toán chưa ( việc kiểm tra này khá đơn giản , chỉ đơn thuần là kiểm tra xem N^N có chia hết cho A hay chưa , bằng phương pháp phân tích ra thừa số nguyên tố như đã nêu ở trên ), và bài toán đã được giải quyết…

Và đây là mã nguồn của chương trình, mời các bạn tham khảo :

#include <iostream>

using namespace std;

bool kt(int N,int a);

int X(int a);

int Tim(int a);

bool kt(int N, int a)

{

int p,q,tam;

tam=N;

for (int i=2;i*i<=a;i++)

        {

p=0;

while (a%i==0) {a=a/i;p++;}

if (p>0)

            {

q = 0;

while (N%i==0) {N=N/i; q++;}

if (q*tam<p) return false;

}

}

if ((a>1) && (N%a)) return false;

return true;

}

int X(int a)

{

int kq=1;

for (int i = 2; i*i<=a;i++)

       {

if (a%i==0) kq=kq*i;

while (a%i==0) a=a/i;

  }

if (a>1) kq=kq*a;

return kq;

}

int Tim(int a)

{

int x = X(a);

for (int i=1;i*x<=a;i++)

{

if (kt(i*x,a))

return (i*x);

}

return 0;

}

void main()

{

int a;

cin>>a;

cout<<Tim(a);

}

Nhận xét : Đây là một cách làm hay , cách làm này giúp chúng ta giảm thiểu thời gian đáng kể so với cách thông thường ( duyệt N từ 1 đến A ) . Và với cách làm này , chương trình chạy tốt trong thời gian cho phép .Nếu các bạn có những cách nào làm hay hơn cách trên , bạn hãy chia sẻ cho mọi người cung tham khảo.
  

Bài 2: Xem công thức tính sau đây (đề thi tuyển sinh cao học ngành KHMT, năm 2011):

Trong đó Max, Min lần lượt là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ thiết bị nhập chuẩn) a₀, a₁, …, a_n-1.

Chỉ dùng duy nhất 1 vòng lặp (for hoặc while), đề xuất cách thức để nhập n số thực như trên và tính giá trị của biểu thức Aver, xuất kết quả tính ra thiết bị xuất chuẩn. Viết chương trình để minh họa đề xuất đó.

Lưu ý: Phần này sinh viên chưa học về mảng, như vậy vấn đề chính của bài toán này là không thể dùng mảng để lưu giá trị của n số thực nói trên. Như vậy phải đề xuất một giải pháp “thông minh” để nhập và tính toán mà không đưa trước các số thực này vào mảng.

Tiếp cận bài toán :

            Thoạt nhìn vào cái biểu thức cần tính thì ta thấy khá đơn giản , chỉ cần thực hiện ….. vài vòng lặp là ta có thể tính dễ dàng biểu thức này.Tuy nhiên , vấn đề mà bài toán đặt ra ở đây là chỉ dùng duy nhất 1 vòng lặp để thực hiện việc này . Và đây chính là điểm mấu chốt của bài toán, gây khó khăn người giải .

Giải quyết bài toán :

Nếu giải quyết theo cách thông thường , ta cần phải có những vòng lặp để thực hiện lần lượt công việc sau đây :

1.      Nhập dãy

2.      Tìm min

3.      Tìm max

4.      Tính kết quả.

Quan sát và nhận xét ta có thể dùng duy nhất 1 vòng lặp để thực hiện 3 công việc đầu tiên cùng một lúc một cách dễ dàng.Vấn đề ở đây là chúng ta không được dùng mảng để lưu giá trị của các a_i. Bởi vậy , ta phải tìm ra cách để khi nhận giá trị của a_i, , ta phải cập nhật  thẳng nó vào kết quả cần tìm.(1)

Ta thấy biểu thức Aver gồm 3 cụm . Thấy rằng cụm thứ 3 ta có thể tính dễ dàng mà không cần đắn đo suy nghĩ gì cả khi đã tìm được Min và Max . Như vậy ta không cần quan tâm đến cụm thứ 3 nữa. Nếu nhìn vào biểu thức ban đầu , theo cách tư duy thông thường, chắc hẳn ai cũng nghĩ rằng phải tìm được min , max rồi mới tính được kết quả của cụm 1 và cụm 2. (2).

Nhưng nếu tinh tế hơn một tí , bạn có thể viết lại biểu thức ban đầu:

Chúng ta hãy cùng quan sát:

      

Sau khi ta viết lại biểu thức Aver , vấn đề (1) và (2) đã được giải quyết một cách dễ dàng .

Nếu nhìn lại biểu thức này , ta thấy công việc tính toán trở nên rất đơn giản chỉ bằng một vòng lặp.Với một vòng lặp , mỗi lần nhập vào giá trị a_i mới ,ta có thể tìm Min mới ( bằng cách so sánh a_i với giá trị Min cũ ), tương tự ta cũng tìm được Max , cộng kết quả thêm 2*a_i², cập nhật biến tổng từ a₀ đến a_i…Đó là tất cả mọi thứ mà ta cần tìm để cho ra kết quả của bài toán.

Và đây là phần mã nguồn cho bài toán này, mời các bạn tham khảo 

Bài học :

            Tích cực biến đổi để đơn giản hoá bài toán.

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.

Tiếp cận bài toán .

Đề bài yêu cầu tính F(n!) với 1<=n<=500 . 500! Một con số thật kinh khủng với hang ngàn chữ số . Suy nghĩ đầu tiên, đơn giản mà mọi người nghĩ để giải quyết bài toán này là phải tính n! , sau đó mới tính được F(n).Nếu n nhỏ , bài toán này có thể giải dễ dàng thông qua đệ quy . Nhưng do giới hạn n quá lớn , không kiểu dữ liệu nào trong máy tính có thể lưu trữ được con số 500! , giải quyết bằng cách này không khả thi . Tuy nhiên , các bạn vẫn có thể giải quyết được bằng cách tìm hiểu về vấn đề xử lý số lớn.

Bài toán cần tổng các chữ số của n! . Vậy ta đặt ra một câu hỏi : liệu không cần tính n! mà ta vẫn có thể tính được tổng các chữ số trong nó ??? Câu hỏi này làm tôi phải suy nghĩ khá nhiều , nhưng kết quả là tôi vẫn chưa tìm được cách để tính tổng các chữ số trong nó.

Giải quyết bài toán :

Nếu ta quan sát thì có thể thấy rằng , kết quả của bài toán chỉ có thể là từ 1 đến 9 , vậy trường hợp nào thì nó sẽ ra kết quả nào trong 9 con số ít ỏi kia … ???

Tôi đã thử nghiệm với nhiều kết quả , n=1 , 2 , 3 ,4 , … và nhận ra rằng từ 6 trở đi , kết quả của bài toán là con số 9 . Điều này khiến tôi suy nghĩ khá nhiều , và cuối cùng tôi đã tìm ra được nguyên nhân . 6! = 1*2*3*4*5*6 . Với n>=6 , trong n! sẽ xuất hiện tích 3*6=18 , khi đó với n>=6 ta luôn có n! chia hết cho 9. Như ta đã từng học,tổng các số trong một chữ số trong một số chia hết cho 9 thì số đó sẽ chia hết cho 9, như vậy tổng các chữ số trong n! sẽ chia hết cho 9. Theo định nghĩa ta có f(x)=f(f(x)) nếu x>9, như vậy nếu tính tiếp ta cũng sẽ được một tổng mới chia hết cho 9 ( tổng này là tổng của tổng các chữ số trong n!)… Và cuối cùng ta sẽ được kết quả là 9. Sự đặc biệt của con số 9 đã giúp chúng ta giải quyết được bài toán này.

Để dễ dàng quan sát hơn mình sẽ cho các bạn một ví dụ :9! = 362880 ->27->9 .Con số cuối cùng chúng ta nhận được là 9.

Một bài tập có vẻ rất khó , rất phức tạp , khó có thể giải quyết , nhưng nhờ thực nghiệm mà ta có thể tìm ra được lời giải một cách dễ dàng cho bài toán.

Đến đây , công việc của chúng ta khá đơn giản , một lệnh switch case có thể giúp ta giải quyết bài toán.

Với n=1 , kết quả sẽ là 1

Với n=2 , kết quả sẽ là 2

Với n=3 , kết quả sẽ là 6

Với n=4 , kết quả sẽ là 6

Với n=5 , kết quả sẽ là 3

Với n>=6 , kết quả sẽ là 9

Sau đây là mã nguồn bằng ngôn ngữ C++ , mời các bạn tham khảo

Bài học : Có thể thực nghiệm sẽ giúp bạn tìm ra kết quả , cứ thoả sức thử , tìm … và tìm ra quy luật . Đôi khi nó sẽ giúp bạn tìm ra được lời giải cho bài toán.Chúc bạn may mắn !