Nhom_8_1212264_1212275_1212276_1212314 là file lịch can chi bằng exel do nhóm 8 làm. Nhập năm và tháng để tra cứu tháng tương ứng.
Bài tập nghiên cứu 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.
Yêu cầu bài toán
Nhập vào số nguyên n thỏa 1<=n<=500, in ra kết quả của F(x).
Đi tìm ý tưởng
Đầu tiên ta nhận thấy rằng nếu đi tính n! thì với n nhỏ điều này là hoàn toàn có thể nhưng nếu n nằm trong khoảng [1;500] thì điều này rất khó. Giả dụ khi n = 100 thì đã vượt xa giá trị lưu trữ của biến unsigned long. Nếu vậy thì việc tính n! sẽ đi theo lối mòn. Một số thuật toán dùng mảng để lưu số lớn vẫn có thể làm được điều này nhưng chương trình sẽ không hay, mất nhiều thời gian. Dựa trên một số gợi ý từ bạn Đỗ Chí Thiện với thuật toán tối ưu hơn, ta hoàn toàn có thể tính toán ngắn gọn hơn nhiều.
Trước hết ta tìm hiểu đối với n!<=9 thì F(n!)=n!. Ví dụ:
1! = 1
2! = 2
3! = 6
Đến 4! thì giá trị đã vượt quá 9 nên F(n!) = F(24) mà với x>9 thì F(x) = F(S(x)) nên F(24) = F(S(24)). Ta lại có S(24) là tổng các chữ số của 24, tức là 6. Lúc này F(24) = F(6) mà ta đã có x<=9 thì F(x) = x nên F(4!) = F(6) = 6. Đây là mấu chốt quan trọng để ta thấy được rằng nều tổng các chữ số của x vẫn lớn hơn 9 thì S(x) vẫn tiếp tục được tính đến khi x<=9. Do đó F(n!) cần tính luôn là một giá trị trong khoảng từ 1 đến 9. Đây chính là điều thú vị của bài toán mà một khi ta đã hiểu ra thì việc tìm thuật toán trở nên ngắn gọn hơn!
Ta lại có một nhận xét nữa là kể từ giá trị 6! thì bắt đầu xuất hiện một giá trị chia hết cho 9 (6! = 720 có tổng các chữ số bằng 9 nên chia hết cho 9). Nên kể từ 6! trở đi x=n! luôn là một số chia hết cho 9. Mà ta đã được biết một số chia hết cho 9 khi nó khỏa yêu cầu tổng các chữ số của nó chia hết cho 9. Nên x=n! với n>=6 thì S(x) luôn là một số chia hết cho 9. Khi thực hiên tính F(S(x)) thì đến một lúc nào đó nó sẽ trả về một giá trị <=9. Vậy giá trị này là gì. Tất nhiên đó là một giá trị chia hết cho 9 (vì các số chia hết cho 9 thì có tổng các chữ số chia hết cho 9). Một số chia hết cho 9 và <=9 chỉ có thể là 9 mà thôi ^^. Vậy ta đã đi đến một lời giải khá thú vị cho bài toán này bằng các trường hợp:
n = 1 => F(n) = 1
n = 2 => F(n) = 2
n = 3 => F(n) = 6
n = 4 => F(n) = 6
n = 5 => F(n) = 3
n >= 6 => F(n) = 9 🙂
Do đó mã nguồn của bài toán này sẽ vô cùng đơn giản:
Mã nguồn
#include <iostream>
using namespace std;
void main()
{
int n, f;
// Nhap vao so nguyen n trong khoang [1;500] neu khong thoa thi nhap lai
do
{
cout<<"Nhap vao so nguyen duong n: ";
cin>>n;
} while (n<1 && n>500);
// Tim gia tri cua F(n!) qua cac truong hop
switch (n)
{
case 1: f = 1; break;
case 2: f = 2; break;
case 3: f = 6; break;
case 4: f = 6; break;
case 5: f = 3; break;
default: f = 9;
}
// In ra gia tri cua F(n!)
cout<<"Gia tri cua F("<<n<<"!) = "<<f<<endl;
}
Bài tập nghiên cứu 2
Xem công thức sau:
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[0], a[1], a[2], … 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 tình để minh họa đề xuất đó.
Lưu ý: Phần này sinh viên chưa được 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.
Yêu cầu bài toán
Nhập vào số nguyên dương n (chính là số phần tử của dãy số thực cần nhập). Nhập vào n số thực mà không dùng mảng để lưu trữ. Nhập và tính toán trong một vòng lặp và xuất ra kết quả của biểu thức Aver.
Đi tìm ý tưởng
Đầu tiên ta có nhận xét rằng chúng ta hoàn toàn không thể khai báo n biến để lưu trữ số thực nhập vào được. Do đó chúng ta sẽ chỉ dùng 1 biến để lưu giá trị nhập vào trong một vòng lặp được lặp đi lặp lại n lần. Trong vòng lặp này ta dễ dàng tìm được max, min của dãy nhập vào bằng thuật toán đã biết. Nhưng làm sao để tính được biểu thức Aver trong khi nếu ra khỏi vòng lặp thì biến lưu trữ số thực sẽ chỉ lưu trữ giá trị của số thực cuối cùng.
Đến đây ta sẽ phân tách biểu thức Aver theo toán học:
Đến đây thì chúng ta đã có thể tính được Aver ngay trong vòng lặp bằng cách tính cách biểu thức có a[i] riêng lẻ. Các bạn có thể xem mã nguồn để hiểu rõ hơn cách thức tính toán.
Mã nguồn
#include <iostream>
using namespace std;
int main()
{
// Khai bao bien can thiet
int n, i;
double a, sum1, sum2, aver, max, min;
// Nhap vao so nguyen duong n
cout<<"Nhap vao so nguyen n: ";
cin>>n;
// Nhap vao so thuc a[0], sau do tinh toan cac gia tri khoi dau
cout<<"Nhap vao so a[0]: ";
cin>>a;
sum1 = 2*a*a;
sum2 = 2*a;
max = a;
min = a;
// Bat dau nhap cac gia tri con lai de tinh toan
for (i = 1; i<n; i++)
{
cout<<"Nhap vao so a["<<i<<"]: ";
cin>>a;
sum1 = sum1 + 2*a*a;
sum2 = sum2 + 2*a;
if (max<a)
max = a;
if (min>a)
min = a;
}
// Tinh bieu thuc Aver theo cung thuc da khai trien
aver = sum1 - sum2*max - sum2*min + n*(max*max + min*min) + n*(max - min)*(max - min)/2.0;
cout<<"Aver= "<<aver<<endl;
return 0;
}
Bài tập nghiên cứu 1
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 tình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị 1<= A <= 10^9.
Ví dụ:
A N
8 4
13 13
Yêu cầu bài toán:
Nhập vào số nguyên A, xuất ra số nguyên N nhỏ nhất sao cho N^N chia hết cho A.
Đi tìm ý tưởng
Đây là một bài toán khó ở phần lưu trữ số N^N. Nếu N chỉ là số nhỏ hơn 10 thì ta hoàn toàn có thể lưu giá trị N^N đó vào một số nguyên kiểu unsigned long. Nhưng vì A nằm trong khoảng từ 1 đến 10^9 nên N có thể rất lớn. Nên phương án tính N^N là một điều không thể. Vì vậy chúng ta phải đi phân tích bài toán để tìm một thuật toán tối ưu cho nó.
Đầu tiên ta thấy rằng để N^N chia hết cho A thì khi phân tích thành các thừa số nguyên tố thì A có thừa số nào , N phải có thừa số đó. Mặc khác, để đảm bảo N^N chia hết cho A thì số N phải lớn hơn hoặc bằng số mũ lớn nhất của thừa số nguyên tố trong A (tạm gọi là max). Vì khi N lớn hơn hoặc bằng max thì khi lũy thừa N lên thì thừa số nguyên tố của N mới có số mũ max. Lúc đo N^N mới chia hết cho A.
Đến đây thì ý tưởng đã khá rõ ràng, chỉ việc viết thuật toán dựa trên ý tưởng nữa mà thôi.
Mã nguồn
#include <iostream>
#include <cmath>
using namespace std;
void main()
{
// Khai bao bien
int i, j, max = 1;
long a, n, tich = 1;
// Nhap vao so nguyen A, neu a>10^9 hoac be hon 1 thi nhap lai
do
{
cout<<"Nhap vao so nguyen duong A: ";
cin>>a;
} while (a<1 && a>pow(10,9));
// Tinh tich ca thua so nguyen to cua a va so mu lon nhat
for (int i = 2; i <= sqrt(a); i++)
{
if (a % i == 0)
{
int j = 0;
while (a % i == 0)
{
a = a/i;
j++;
}
tich = tich *i;
if (j > max)
max = j;
}
}
// Truong hop so a sau khi phan tich la so nguyen to
if (a > 1)
tich = tich * a;
// Tinh N
i = 1;
while (i*tich < max)
i++;
n = tich * i;
cout<<"Gia tri N la: "<<n<<endl;
}
nhanthoang - 1212275 