Đề 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\le A\le {{10}^{9}}

Ví dụ :

Số nhập vào là A :                                Số xuất ra là N :

8                                                                   4

13                                                                13

Thuật toán 1

 

Việc đầu tiên là phân tích n thành tích các thừa số nguyên tố :

A=\prod\limits_{i=1}^{k}{{{a}_{i}}^{{{b}_{i}}}}

Đặt :     {{a}_{0}}=\prod\limits_{i=1}^{k}{{{a}_{i}}}

{{b}_{m\text{ax}}}=m\text{ax(}{{\text{b}}_{i}})\Rightarrow {{a}_{m\text{ax}}}

Ở đây có 2 trường hợp :

                      TH1 : {{a}_{0}}\ge {{b}_{m\text{ax}}}\Rightarrow N={{a}_{0}}

                      TH2 : {{a}_{0}}<{{b}_{m\text{ax}}}\Rightarrow  cho chạy x đến khi biểu thức sau thỏa :

(x+1)({{a}_{0}}.a_{m\text{ax}}^{x})\ge {{b}_{m\text{ax}}}

Khi đó : N={{a}_{0}}.a_{m\text{ax}}^{x}

Ví dụ :

A=32\Rightarrow A={{2}^{5}}

{{a}_{0}}=2;{{a}_{m\text{ax}}}=2;{{b}_{m\text{ax}}}=5

Tính toán ta được : x=1\Rightarrow N={{2.2}^{1}}=4

Vậy {{4}^{4}} là số nhỏ nhất chia hết cho 32 thỏa yêu cầu.

Code 1

 

#include <stdio.h>
#include <conio.h>
#include <math.h>

int ktnt(long x);

void phantich(long x, long &maxa, long &maxb, long &tich);

void main()
{
long n, a, x, maxa, maxb, tich;

printf(“Nhap A : “);
scanf(“%ld”, &a);
phantich(a, maxa, maxb, tich);
if (tich >= maxb) {
n = tich;
}
if (tich < maxb) {
x = 0;
while ((x+1)*(tich*pow(double(maxa), double(x))) < maxb) {
x++;
}
n = tich*pow(double(maxa), double(x));
}
printf(“So N thoa man : %ld”, n);
getch();
}

int ktnt(long x)
{
int i;

if (x < 2) {
return 0;
}
if ((x >= 2) && (x <= 3)) {
return 1;
}
if (x >= 4) {
for (i = 2; i <= sqrt((double)x); i++) {
if (x % i == 0) {
return 0;
}
}
}
return 1;
}

void phantich(long x, long &maxa, long &maxb, long &tich)
{
int i, dem;

maxa = 0;
maxb = 0;
tich = 1;
for (i = 2; i <= x; i++) {
if (ktnt(i) == 1) {
dem = 0;
if (x % i == 0) {
tich = tich*i;
}
while (x % i == 0) {
dem++;
x = x/i;
}
if (dem > maxb) {
maxb = dem;
maxa = i;
}
}
}
}

Đề 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):
Aver=\sum\limits_{i=0}^{n-1}{{{({{a}_{i}}-M\text{ax})}^{2}}+\sum\limits_{i=0}^{n-1}{{{({{a}_{i}}-Min)}^{2}}+\frac{n}{2}}}{{(M\text{ax}-Min)}^{2}}
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 đó.

Thuật toán 2

 

Với các bài toán như trên, chúng ta không có thông tin về Max và Min trong quá trình nhập từ thiết bị nhập, vậy cách giải quyết trong trường hợp này là thực hiện một biến đổi nhỏ đối với công thức để đưa Max và Min ra ngoài. Aver có thể được biến đổi như sau :

{{S}_{1}}=\sum\limits_{i=0}^{n-1}{{{({{a}_{i}}-M\text{ax})}^{2}}=\sum\limits_{i=0}^{n-1}{a_{i}^{2}-2.M\text{ax}.\sum\limits_{i=0}^{n-1}{{{a}_{i}}}}}+n.M\text{a}{{\text{x}}^{2}}

{{S}_{2}}=\sum\limits_{i=0}^{n-1}{{{({{a}_{i}}-Min)}^{2}}=\sum\limits_{i=0}^{n-1}{a_{i}^{2}-2.Min.\sum\limits_{i=0}^{n-1}{{{a}_{i}}}}}+n.Mi{{n}^{2}}

Aver=2.\sum\limits_{i=0}^{n-1}{a_{i}^{2}-2.(M\text{ax}+Min).\sum\limits_{i=0}^{n-1}{{{a}_{i}}}}+n.(M\text{a}{{\text{x}}^{2}}+Mi{{n}^{2}})+\frac{n}{2}.{{(M\text{ax}-Min)}^{2}}

Code 2

 

#include <stdio.h>
#include <conio.h>

void main()
{
long i, n, tam;
double max, min, x, tong, tong1, tong2;

printf(“Nhap N : “);
scanf(“%ld”, &n);
tam = 1;
tong1 = 0;
tong2 = 0;
for (i = 1; i <= n; i++) {
printf(“Nhap phan tu thu %ld : “, i);
scanf(“%lf”, &x);
tong1 = tong1+x*x;
tong2 = tong2+x;
if (tam == 1) {
min = x;
max = x;
tam = 0;
}
else {
if (x > max) {
max = x;
}
if (x < min) {
min = x;
}
}
}
tong = 2*tong1-2*tong2*(max+min)+n*max*max+n*min*min+n/2.0*(max-min)*(max-min);
printf(“Aver = %lf”, tong);
getch();
}