Bài toán 1
Tính tổng : S = 1 + 3 + 5 + 7 + … + 99 .
Ta khoan hãy vội vàng tính tổng S này xem nó bằng bao nhiêu? Mà ta hãy quan tâm đến tổng Gauss quen thuộc :
Bài toán 2
Tính tổng : P = 1 + 2 + 3 + 4 + … + 100 .
Tương truyền rằng, khi cả lớp căm cụi lấy từng số một cộng với nhau, thì cậu bé Gauss loáng một cái đã giơ tay xin trình bày cách giải của mình. Cách giải đó như sau :
Vì 1 + 100 = 2 + 99 = 3 + 98 = … = 50 + 51 = 101 . Do có 50 cặp có kết quả như vậy, nên S = 101.50 = 5050 .
Cách giải này cho đến nay vẫn là một trong những cách giải đẹp nhất dành cho một bài toán mà loài người có thể nghĩ ra được . Sự sáng tạo trong cách giải đã đưa tên tuổi của Gauss gắn liền với bài toán , mặc dù ông không phải là người đầu tiên nghĩ ra nó .
Qua việc nghiên cứu, người ta đã tìm thấy rất nhiều cách giải cho bài toán 2 . Ở đây, tôi chỉ xin nêu thêm một cách giải khác, mà thông qua cách giải này, ta sẽ tìm thấy được ý nghĩa ứng dụng thực tế .
Bài toán 3
Có n người tham gia dự chương trình trò chơi X của đài truyền hình Y . Người ta muốn chọn 2 người vào vòng chơi. Hỏi có bao nhiêu cách chọn ?
Nếu có 2 người thôi thì có 1 cách chọn . Nếu có thêm người thứ ba thì có thêm các cách chọn người thứ ba này. Ta phải chọn một trong hai người lúc đầu để tham gia chơi với người này nên có hai cách chọn ... Nếu có thêm người thứ n thì có thêm các cách chọn có người thứ n này. Ta phải chọn một trong n – 1 người đã có để tham gia chơi với người thứ n nên có n – 1 cách chọn . Vậy số cách chọn sẽ là : 1 + 2 + 3 + 4 + … + n – 1 .
Mặt khác, ta có thể lập luận: Người thứ nhất có n cách chọn . Sau đó còn n – 1 người nên có n – 1 cách chọn người thứ hai . Vậy có n(n–1) cách chọn . Nhưng cách chọn 2 người AB cũng là cách chọn hai người BA . Hai cách này là một . Vậy số cách chọn chỉ bằng một phần hai số trên và bằng
. Vì hai cách lập luận là một , nên :
Với n = 101 thì
Thuật toán cho việc tính tổng P như sau:
1. Nhập vào giá trị của n .
1. P = 0 .
2. Cho i chạy từ 1 đến n
P = P + i .
3. Xuất ra kết quả P .
4. Kết thúc thuật toán .
Chương trình viết bằng ngôn ngữ C++:
#include
#include
void main()
{clrscr() ;
int n ; int P = 0 ;
cout<<"Moi nhap vao so n = "; cin>>n ;
for(int i=0 ; i<=n ; i++)
P = P + i ;
cout<<"Tong "<
getch() ;
}
Kết quả sau khi chạy chương trình :
Moi nhap vao so n = 100
Tong 100 so tu nhien lien tiep la: 5050
Moi nhap vao so n = 50
Tong 50 so tu nhien lien tiep la: 1275
Bây giờ , ta thêm bớt vào tổng các số lẻ S một tổng các số chẵn : 2 + 4 + 6 + 8 + … + 100 . Thế thì ta có cách tính tổng các số tự nhiên liên tiếp như sau :
Cách 1:
S = 1 + 3 + 5 + 7 + … + 99 = (1 + 2 + 3 + 4 + … + 100) – (2 + 4 + 6 + 8 + 10 +… + 100) = (1 + 2 + 3 + 4 + … + 100) – 2 (1 + 2 + 3 + 4 + … + 50) .
Theo tính toán ở phần lập trình trên ta có ngay: S = 5050 – 2.1275 ; hay S = 2500 .
Ngoài ra ta còn cách tiếp cận khác :
Cách 2 : S = 1 + 3 + 5 + 7 + … + 99
S = 99 + 97 + 95 + 93 + … + 1
Vì 1 + 99 = 3 + 97 = 5 + 95 = … = 99 + 1 = 100. Có cả thảy 50 cặp như vậy. Do đó: 2S = 100.50. Hay S = 50.50 = 2500 .
Một biểu diễn hình học của tổng các số lẻ (hình vẽ) .
Bài toán tính tổng các số lẻ liên tiếp có mối quan hệ mật thiết với bài toán tính tổng các số tự nhiên liên tiếp. Mối quan hệ này đã được ta đề cập trong trường hợp tổng các số lẻ liên tiếp từ 1 đến 99. Trong trường hợp tồng quát, làm tương tự, ta cũng có:
1 + 3 + 5 + … + 2n-1 = 1 + 2 + 3 + … + 2n – 2(1 + 2 + 3 + … + n) =
Vì thế, về mặt tư duy, có bao nhiêu cách tiếp cận tổng các số tự nhiên liên tiếp thì rất có thể ta sẽ có bấy nhiêu cách tiếp cận tổng các số lẻ liên tiếp. Ví dụ, ta đã có thuật toán tính tổng các số tự nhiên liên tiếp P thì ta sẽ có thuật toán tính tổng S tương tự .
Tổng các số lẻ liên tiếp, tổng các số tự nhiên liên tiếp cùng với bài toán tính giai thừa là ba trong những ví dụ tốt nhất để minh họa về khái niệm đệ quy trong tin học .
Ta đã đề cập bài toán tính tổng các số lẻ liên tiếp bắt đầu từ 1 . Trong trường hợp tổng quát ta sẽ đi tính tổng các số lẻ liên tiếp bắt đầu từ một số lẻ (2a – 1) đến một số lẻ (2b – 1 ) (b > a) . Thì ta có thuật toán :
1. Nhập vào số lẻ 2*a – 1 .
2. Nhập vào số lẻ 2*b – 1 .
3. P = 0 .
4. i = a .
5. Trong khi i <= b thì
5.1. P = P + 2*i – 1 .
5.2. i = i + 1 .
6. Quay lại bước 4 .
7. Kết thúc thuật toán .
Chương trình viết bằng ngôn ngữ C++:
#include
#include
void main()
{clrscr() ;
int a , b ; int P = 0 ;
cout<<"Moi nhap vao so a = " ; cin>>a ;
cout<<"Moi nhap vao so b = " ; cin>>b ;
int i = a ;
while (i<=b)
{ P = P + 2*i – 1 ;
i = i + 1 ;
}
cout<<"
Tong cac so le tu "<<2*a - 1<<" den "<<2*b - 1<<" la: "<
getch() ;
}
Kết quả sau khi chạy chương trình:
Moi nhap vao so a = 5
Moi nhap vao so b = 9
Tong cac so le tu 9 den 17 la: 65 .
Tuy nhiên , khi giải quyết bài toán tổng quát của bài toán 1 này thì về mặt toán học ta có cách tìm ra kết quả rất nhanh . Ta làm như sau:
Tổng các số lẻ liên tiếp, tổng các số tự nhiên liên tiếp cùng với bài toán tính giai thừa là ba trong những ví dụ tốt nhất để minh họa về khái niệm đệ quy trong tin học .
Ta đã đề cập bài toán tính tổng các số lẻ liên tiếp bắt đầu từ 1 . Trong trường hợp tổng quát ta sẽ đi tính tổng các số lẻ liên tiếp bắt đầu từ một số lẻ (2a – 1) đến một số lẻ (2b – 1 ) (b > a) . Thì ta có thuật toán :
1. Nhập vào số lẻ 2*a – 1 .
2. Nhập vào số lẻ 2*b – 1 .
3. P = 0 .
4. i = a .
5. Trong khi i <= b thì
5.1. P = P + 2*i – 1 .
5.2. i = i + 1 .
6. Quay lại bước 4 .
7. Kết thúc thuật toán .
Chương trình viết bằng ngôn ngữ C++:
#include
#include
void main()
{clrscr() ;
int a , b ; int P = 0 ;
cout<<"Moi nhap vao so a = " ; cin>>a ;
cout<<"Moi nhap vao so b = " ; cin>>b ;
int i = a ;
while (i<=b)
{ P = P + 2*i – 1 ;
i = i + 1 ;
}
cout<<"
Tong cac so le tu "<<2*a - 1<<" den "<<2*b - 1<<" la: "<
getch() ;
}
Kết quả sau khi chạy chương trình:
Moi nhap vao so a = 5
Moi nhap vao so b = 9
Tong cac so le tu 9 den 17 la: 65 .
Tuy nhiên , khi giải quyết bài toán tổng quát của bài toán 1 này thì về mặt toán học ta có cách tìm ra kết quả rất nhanh . Ta làm như sau:
1 + 3 + 5 + ... + 2a – 1 = a2 .
1 + 3 + 5 + ... + 2b – 1 = b2 .
Lập hiệu : H = b2 – a2 , ta có: H = (1 + 3 + 5 + … + 2a-1 + 2a+1 + … 2b - 1) – (1 + 3 + 5 + …+ 2a-1) . Hay H = (2a + 1 ) + (2a + 3) + … + (2b - 3) + (2b - 1) .
Vì thế, để tính tổng từ 9 đến 17 , ta có : 9 + 11 + 13 + 15 + 17 = 92 – 42 = 81 – 16 = 65 .
Tôi đã giới thiệu với các bạn đôi nét về tổng các số lẻ liên tiếp . Các cách nhìn về mặt tin học cũng như toán học của nó . Các yếu tố giữa hình học , số học , tin học cũng như những ứng dụng thực tế đã được tôi gửi gắm qua thông qua tổng các số lẻ liên tiếp này . Hy vọng, với cách nhìn đa dạng như thế, sẽ cung cấp cấp đầy đủ hơn cho các bạn những điều bổ ích, mới mẻ và đầy thú vị .