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.

Nhận định bài  toán:

Theo hướng đơn giản thông thường ta nhập vô số n thỏa  điều kiện trên, sau đó ta tính n!, rồi chia lấy phần nguyên n! cho 10 để tách từng  số ra rồi cộng tất cả lại, nếu lớn hơn 9 ta tiếp tục lặp lại bước trên. Với sử lý của máy tính thì cũng không mất thời  gian lắm. nhưng nếu vậy , ta gặp rắc rối đơn giản nếu ta nhập giá trị n =500 thì 500! là một số vô cùng lớn( khoảng 1300 chữ số), ta không có kiểu lưu trữ nào có thể đáp ứng yêu cầu như trên. Tham khảo ý kiến của mấy bạn trong lớp, mấy bạn pro chỉ tôi là dùng mảng, mỗi mảng biểu diễn 1 con số, vậy là  có thể giải quyết bài toán, nhưng do chưa có kiến thức lập trình tôi không biết xài mảng làm sao.( vì thầy chưa dạy).  nhưng nhờ mấy bạn nhắc là đâu nhất thiết phải tính số đó ra, đây là bài toán mẹo. bây giờ ta tinh giá trị của 10 tự nhiên ban đầu:

Giá trị n	Giá trị n!	Giá trị F(x)
0	1	1
1	1	1
2	2	2
3	6	6
4	24	6
5	120	3
6	720	9
7	5040	9
8	40320	9
9	362288	9

Nhận định thấy với n>=6 thì kết quả đều bằng 9 vì sao vậy?

Lý do : theo lý thuyết ta học lúc  trung học cơ sở ta có: với n là số nguyên ta luôn có: (n-2)(n-1)n luôn chia hết cho 3.

 Xét tiếp (n+1)(n+2)(n+3) luôn chia hết cho 3

Vì vậy ta suy ra => (n-2)(n-1)n(n+1)(n+2)(n+3) chia hết cho 9 hay 6! Chia hết cho 9

Với các số khác lớn hơn 6 ta luôn đưa về dạng : k*6! Chia hết cho 9

Xét   1 số chia hết cho 9 thì tổng các chữ số đó phải chia hết cho 9. Vậy bài toán tưởng chừng như phức tạp lại được giải quyết  1 cách dễ dàng. Dù giá tri n có lớn đến mấy ta đều tính được.

Code bài giải:

#include<iostream> #include<conio.h> using namespace std; void main() {        int n,s;        cout<<"nhap gia tri n:";        cin>>n;        if(n<0)        {               cout<<"nhap gia tri n sai!!!,nhap lai";               return;        }        else        {               if(n==0||n==1)               {                      s=1;               }               if(n==2)               {                      s=2;               }               if(n==3||n==4)               {                      s=6;               }               if(n==5)               {                      s=3;               }               if(n>=6)               {                      s=9;               }        }        cout<<"gia tri cua ham F(x) la: "<<s<<endl;        getch(); }

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.

Nhận định bài toán:

Ta có thể sử dụng nhiều vòng lặp để giải quyết

Vòng lặp thứ nhất ta sử dụng để nhập

Vòng lặp thứ hai ta tìm được  Min

Vòng thứ ba ta tìm được Max

Vòng thứ tư ta tìm  được tổng bình phương vế đầu        

Vòng thứ năm ta tìm được tổng bình phương vế sau.

Nhưng như thế ta  không thỏa mãn được yêu cầu bài toán là chỉ sử dụng  vòng  lặp.

Suy nghĩ theo hướng khác ta  khai triển biểu thức:

(­a_i-max²)+(a_i –min²)+n/2(max-min)²=2a_i²-2a_i(max+min)+(1+n/2)(max²+min²)-nmaxmin

Vậy chỉ dùng 1 vòng lặp tìm  được min, max, tổng bình phương S, tổng các số S2

Bài giải:

#include<stdio.h> #include<conio.h> #include<math.h> void main() {        double a,aver,n,s,s2,max,min;        printf("nhap gia  tri cua a: ");        scanf("%lf",&a);        if(a==0)        {               printf("vong lap dung lai");               return;        }        n=0;s=0;s2=0;max=a,min=a;        do        {               scanf("%lf",&a);               n=n+1;               s= s+pow(a,2.0);               s2=s2+a;               if(max<a)               {                      max=a;               }               if(min>a)               {                      min=a;               }        }        while(a!=0);        aver=2*s-2*s2*(max+min)+(1+n/2)*(pow(max,2.0)+pow(min,2.0))-n*min*max;        printf("ket qua của bieu  thuc la: %lf\n",aver);        getch(); }

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

Nhận định bài toán:

Yêu cầu bài toán tương đương:

x^x mod A =0 và X phải đạt giá  trị Min

thoạt nhìn ta nghĩ để chia hết cho A thì

X^x=A

ó X=log_xA          (1)

Từ đó ta giải hệ (1) ta được kết quả thỏa mãn x

Nhưng với nhận định trên ta không thể tìm được giá trị A Min để thỏa yêu cầu bài toán, hơn nữa,  trong lập trình không có chức năng slove như trên máy tính bỏ túi. Ta khó lòng tính được

Có cách đơn giản hơn chúng ta dùng vòng lặp for

Ta cho i chạy từ 1 đến A sao cho iⁱ mod A=0

Trường hợp A là số nguyên tố i sẽ chạy tới giá trị bằng A. Đồng thời khi tới giá trị nhỏ nhất ta dùng lệnh break để dừng lại,

Bài giải:

./*Code bai tap 1*/ #include<stdio.h> #include<conio.h> #include<math.h> void main() {        unsigned int a,i,x,n;        printf("nhap so nguyen tu nhien A: "); scanf("%d",&a); /*khai bao phan tu A*/        for(i=1;i<=a;i++)// tao vong lap        {               n= float(pow(float (i),int (i) ));               if(n%a==0)               {                      x=i;break;// ngung vong khi tim duoc gia tri i Min               }        }        printf("gia tri can tim cua X la: %d",x);        getch(); }

Nhưng thực sự kết quả chạy chỉ đúng được khi A có giá trị nhỏ, với những A có giá trị lớn thì kết quả X luôn bằng 16.

Vì vậy ta phải giải quyết vấn đề theo hướng khác

Bây giờ ta tách A ra bằng tích các thừa số nguyên tố, khi đó A có  dạng: A=a*b*c*d*e…. với a,b,c,d,e … là những số nguyên tố

Từ kết quả tách trên ta lấy tích của các số nguyên tố lại với số mũ lớn nhất ta được kết quả

Bài giải:

#include<stdio.h> #include<conio.h> void main() {        unsigned long max, n,i,b,s;        printf("nhap vao gia tri cua so nguyen n: "); scanf("%lu",&n);        s=1;max=0;i=1;        for(i=2;i<=n;i++)        {               b=0;               if(n%i==0)               {                      s=s*i;                      while(n%i==0)                      {                            b++;                            n=n/i;                      }                      if(b>max)                      {                            max=b;                      }               }        }        if(s<=max)        {               s=s*2;        }        printf("gia tri can tim la: %lu",s);        getch(); }

Với thuật toán này ta có thể rút ngắn được thời gian hơn rất nhiều cho vong lặp, và hạn chế được việc tràn số như trường hợp nêu trên.