bài 3 đề phức tạp nhưng cách làm đơn giải

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.

  Đề cho hơi bị phức tạp đòi hỏi phải có thời gian suy nghĩ. Bài toán có 2 vấn đề cần giải quyết là F(x) và n!.

  Đầu tiên là n!. có thể thấy 500! rất lớn (khỏi tính cũng biết)không có một dữ liệu cơ sở nào lưu trữ nổi. Vậy dùng gì để lưu trữ hay có cách khác khỏi cần tính số quá lớn như bài 1. Theo tìm kiếm trên mạng và mấy người bạn thì kêu dùng mảng để lưu trữ mà mảng là gì chưa học thôi tìm cách khác vậy.

  Phương pháp của bài 1 là bỏ qua việc tính số lớn mà đi sâu vào tính chất chia hết để giải quyết bài toán. Vậy bài 3 có tương tự. Như đã nói ở trên  có 2 vấn đề quan trọng là F(x) và n!. Vậy ta phải tìm hiểu tính chất của n! làm sao mà không cần tính giá trị của nó vẫn tìm được. Nhưng dường như rất khó sẽ dễ đi vào lối mòn.

  Vậy phải tìm hiểu F(x) coi có cách không. Có thể thấy F(x) chỉ có thể nằm trong khoảng [1;9] vì lớn hơn 9 sẽ lấy tổng các chữ số nên khi còn 1 chữ số thì đó sẽ là giá trị F(x). Vậy không cần tính n! có thể biết được F(x) mà đề hỏi. Nếu chú ý đến bước tính tổng chữ số và dấu hiệu chia hết cho 3 và 9 là tổng các chữ số chia hết cho 3 và 9.  Vậy đối với 1 số nếu chia hết cho 3 và 9 sau khi lấy tổng chữ số thì số tổng đó sẽ chia hết cho 3 và 9. Với suy luận trên thì tổng chữ số cuối cùng tương ứng với 1 chữ số có thể 3 và 9. Vậy khi nào n! chia hết cho 3 và 9. Với 3 thì ta thấy n>=3 thì n! đều chia hết cho 3 vì đều có thừa số 3. Tượng tự với 9 ta có n>=6 thì đều chia hết  cho 9 vì 6!=3*2*4*5*3*2=9*... . Vậy với n>=6 thì F(x)=9 vì tổng các chữ số cuối cùng đã chia hết cho 9 mà 9 lại là số lớn nhất trong khoảng[1;9].

 Vậy ta có kết luận sau:

n>=6 thì F(x)=9

 Vậy ta đã làm đơn giản bài toán rất nhiều.

 Với n<6 thì chỉ còn các trường hợp:

- n=1 thì F(X)=1

- n=2 thì F(X)=2

- n=3 thì F(X)=6

- n=4 thì F(X)=6

- n=5 thì F(X)=3

 Từ cách suy luận trên ta có đoạn mã sau:

#include <iostream>

using namespace std;

void bai3 (unsigned int ia, unsigned int& fx)

{

     switch(ia)

     {

           case 1: fx=1; break;

           case 2: fx=2; break;

           case 3:case 4: fx=6; break;

           case 5: fx=3; break;

           default: fx=9;

     }

}

void main ()

{

     unsigned int in,fx;

     cout<<"nhap 1 so nguyen n voi n(1 <= n <= 500)"<<endl;

     cin>>in;

     bai3(in,fx);

     cout<<"ket qua F(x) = "<<fx<<endl;

     system("pause");

}

Bài 2 Bài toán khó khăn nhưng đơn giản đến lạ kì

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.

Nếu đề cao học thì chúng ta thường nghĩ là rất khó và khi đọc đề lần đầu tiên thì nó thật sự khó. Có thể thấy bài toán có 2 vấn đề cần giải quyết là:

Công thức Aver, sử dụng 1 vòng lặp và không sử dụng mảng. vậy ta phải giải quyết từng vấn đề.

Vấn đề đầu tiên là công thức Aver: có thể thấy nó rất phức tạp, mang tính tổng quát và khó khăn khi lập trình vậy phải tìm một công thức đơn giản hơn. Nếu chú ít ta có thể thấy nếu khai triển 2 công thức bình phương theo hằng đẳng thức thì ta được:

Với Ʃ thứ nhất ta có: a₁² + a₂² +…a_n² + n.Max²   - 2.Max.(a1+...)

Với Ʃ thứ hai ta có: a₁² + a₂² +…a_n² + n.Min²   - 2.Min.(a1+...)

Đến đây ta bắt đầu thấy được cách giải bài toán.

          Vấn đề thứ 2 là cách nhập và lưu trữ giá trị của các a. mà không sử dụng mảng và chỉ với 1 vòng lặp.chỉ với 1 vòng lặp thì chỉ nhập 1 giá trị mỗi vòng t không thể khai báo n biến để lưu trữ n giá trị. Nhưng từ công thức khai triển từ công thức ban đầu ta có thể thấy có 4 biến cần để tính đó là  tổng của các bình phương và tổng thông thường, Max và Min. Với 1 vòng lặp ta có thể làm những gì:

Nếu chỉ dùng 1 biến lưu trữ giá trị thì sau mỗi vòng lặp nó sẽ thay đổi theo giá trị tương ứng vây đối với biến tổng bình phương và tổng thường thì sau mỗi vòng lặp nó sẽ tăng theo giá trị nhập mỗi vòng còn với Max và Min thì sao? Đương nhiên là phải đợi đến giá trị nhập cuối cùng rồi mới biết được giá trị thật sự.

Từ lập luận trên ta có công thức sau:

Tb.2+ n(Max² + Min²) -2(Min+Max).Tt - 4.Min.Max +(n/2) (Min-Max)²

Trong đó Tb tổng các  giá trị nhập bình phương và trừ Max² , Min²

 Tt là tổng các giá trị nhập và trừ đi Max, Min.

 Vậy là bài toán đã trở nên đơn giản Ta có đoạn mã sau:

#include <iostream>

using namespace std;

void main ()

{

     unsigned int ik,in; // ik la so luong so thuc

     double da,dn,dMax,dMin,db,dc;//da la aver, dn la so thuc can nhap, dMax la Max, dMin la Min

     cout<<"hay nhap so luong cua day so"<<endl;

     cin>>ik;

     cout<<"hay nhap so dau tien"<<endl;

     cin>>dn;

     dMax=dn;

     dMin=dn;

     db=dn*dn;

     dc=dn;

     in=2;

     while(in<=ik)

     {

           cout<<"hay nhap so thu "<<in<<endl;

           cin>>dn;

           db+=dn*dn;

           dc+=dn;

           in++;

           if(dn<dMin)

                dMin=dn;

           if(dn>dMax)

                dMax=dn;

     }

     db=db-dMax*dMax-dMin*dMin;

     dc=dc-dMax-dMin;

     da=2*db+ik*(dMax*dMax+dMin*dMin)-2*(dMax+dMin)*dc-4*dMax*dMin+((float)ik/2)*(dMax-dMin)*(dMax-dMin);

     cout<<"aver co gia tri la "<<da<<endl;

     system("pause");

}

Bài 1 Sự giới hạn của Vật Lý và lối thoát Toán học

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ới đề trên ta  có thể dùng thuật toán đơn giản: là cho vòng lặp cho N chạy từ 1 đến A và tính N^N chia hết cho A và xuất N như đề bài với thuận toán trên ta có đoạn mã sau:

#include <iostream>

#include <math.h>

using namespace std;

void main ()

{

     int in,ia;//in la N, ia la A

     cout<<"nhap so nguyen A (1<=A<=10^9)"<<endl;

     cin>>ia;

     for(in=0;in<=ia;in++)//cho N chay tu 1 den A

     {

           if((int)pow(float(in),(float)in)%ia==0)// tinh N ngu N tim se chia het cho A khong

                break;

           if(in==ia)// bang A tinh dung vong lap

                break;

     }

     cout<<"so nguyen N phu hop voi dieu kien de bai la "<<in<<endl;//xuat ra ket qua

     system("pause");

}

Ta có thể thấy được hạn chế của thuật toán này phụ thuộc vào quá nhiều khả năng lưu trữ của máy tính. Nên với số quá lớn thì ta sẽ không tính N^N để không sử dụng quá nhiều vào khả nẳng lưu trữ của máy tính. Vậy phải tìm một thuật toán tìm được N mà không cần tính N^N. Có thể thấy điểm quan trọng của bài toán là phép chia hết. Vậy ta phải tìm hiểu rõ tính chất chia hết.Theo nguồn tìm kiếm trên mạng, ta có định lý cơ bản của số học: “Định lý cơ bản của số học (hay định lý về sự phân tích duy nhất ra các thừa số nguyên tố) phát biểu như sau: Mọi số tự nhiên lớn hơn 1 có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố”...

“Một cách tổng quát: Mọi số tự nhiên n lớn hơn 1, có thể viết duy nhất dưới dạng:

trong đó  là các số nguyên tố. Vế phải của đẳng thức này được gọi là dạng phân tích tiêu chuẩn của n”. nguồn

vậy ta có thể thấy số nguyên A có thể phân tích thành tích các thừa số nguyên tố. Vậy để N^N chia hết cho A phải thỏa 2 điệu kiện:

-khi phân tích ra phải có các thừa số nguyên tố giống A.

- phải lớn hơn A tức số mũ của các thừa số nguyên lớn hơn của A.

Với đề bài cho  1 ≤ A ≤ 10⁹ thì  khi phân tích thừa số nguyên tố với mũ 1 thì ta có 3 trường hợp:

Trường hợp chỉ có 1 số nguyên tố , với các số 2,3,5,7 thì ta phải tìm số mũ để nó thỏa mãn điều kiện để N^N lớn hơn A. Nếu từ 11,13,… thì N sẽ bằng chính nó vì 11¹¹>10⁹.

Trường hợp 2 số nguyên tố trở lên, thì ta thấy chỉ có 2 và 3 phải xét độ lớn N^N còn các trường hợp còn lại thì nó sẽ chính bằng N vì với 2 và 5 tức 10¹⁰>10⁹.

Vậy làm sao tính độ lớn N^N khi ta đã chủ động tránh nó.

Đối với chỉ có 1 thừa số nguyên tố 2, 3, 5, 7 thì ta có: do cơ số của A và N bằng nhau và bằng thừa số nguyên tố tìm được nên để giảm độ lớn của phép tính thì ta chỉ so sánh mũ của A và N

Với x.N^x>a

-          x là số mũ cần tìm

-          N là thừa số nguyên tố

-          a là số mũ của nguyên A

vậy công việc của chỉ cần tìm x.

Đối với trường hợp thừa số nguyên tố 2 và 3 thì với mũ 1 tức N=6 thì sẽ giới hạn A < 6⁶. Vậy có cần tính N^N không hay tính số mũ như trên. Nếu chú ý thì ta sẽ thấy giới hạn của A ≤ 10⁹ vậy ta phải tìm số mũ lớn 9 như nhỏ nhất. Nếu phải tính mũ thông thường thì rất phức tạp làm cho thuật toán dài thêm. Vậy ta phải tìm N sao cho lớn hơn 9 và nhỏ nhất. vậy từ 2 và 3 số N chỉ có thể là 12. Với 2².3 < 2.3³ . vậy đối với A < 6⁶ thì N=12.

Theo các suy luân trên ta có thuật toán:

-          Phân tích A thành thừa số nguyên tố có mũ là 1

-          Sẽ các trường hợp đặc biệt: 2, 3 ,5 ,7; 2 và 3

Ta có đoạn mã mô tả thuật toán trên:



#include <iostream>

#include <math.h>

using namespace std;

void timsonguyento(unsigned int& it,unsigned int in)

//ham kiem tra so nguyen to

{

     unsigned int im;

     im=2;

      it=1;

           while(im<in)

           {

                if(in%im==0)

                {

                     it=0;

                     break;

                }

                     im++;

              }

}

void songuyento (unsigned int in,unsigned int& ib)// ham phan tich 1 so thanh tich cua cac so nguyen to

{  

     unsigned int im,it;

     im=1;

     while(im<=in)

     {

           if (in%im==0)

                timsonguyento(it,im);

           if(it==1)

                if(in%im==0)

                           ib*=im;

           im++;

     }

}

void motsonguyento (unsigned int ia,unsigned int& in)

//ham kiem tra cac truong hop 1 so nguyen to

{

     int ib,ic;

     for(ib=1;ia>in;ib++)

     {

           ia=ia/in;

     }

     for(ic=0;1!=0;ic++)

     {

           if((ic*pow((float)in,(float)ic))>ib)

           {

                in=pow((float)in,(float)ic);

                break;

           }

     }

}

void main ()

{

     unsigned int ia,in=1;

     do

     {

           cout<<"nhap so nguyen A (1<=A<=10^9) "<<endl;

           cin>>ia;

     } while(ia<=0);

     songuyento(ia,in);

     if(in==2||in==3||in==5||in==7)

           motsonguyento(ia,in);

     if(in==6)

//ham kiem tra truong hop 2 va 3

     {

           if(ia<pow(6.0,6))

                in=6;

           else

                in=12;

     }

     cout<<"N nho nhat de cho N ngu N chia het cho A la "<<in<<endl;

     system("pause");

}