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
≤ 109
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) a0, a1, …, an-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 ai. Bởi vậy , ta phải tìm ra cách để khi nhận giá trị của
ai, , 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ị ai mới ,ta có thể tìm Min mới
( bằng cách so sánh ai với giá trị Min cũ ), tương tự ta cũng tìm được
Max , cộng kết quả thêm 2*ai2, cập nhật biến tổng từ a0
đến ai…Đó 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 !
