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");

}