Qua quá trình tham gia giảng dạy và bồi dưỡng học sinh giỏi chúng tôi thấy nhiều bài toán đòi hỏi học sinh phải tìm ra mô hình toán học cụ thể từ yêu cầu phức tạp của bài toán.

Bài học đầu tiên khi chúng ta tiếp xúc với hình học giải tích là bài giới thiệu về hệ tọa độ. Khi ta học về đồ họa máy tính, các thầy cô cũng sẽ giới thiệu một khái niệm tương tự: hệ tọa độ màn hình.

I. Giới thiệu.

Trong mỗi ngôn ngữ lập trình thường có một số kiểu dữ liệu chuẩn cho biết phạm vi giá trị có thể lưu trữ, dung lượng bộ nhớ cần thiết để lưu trữ và xác định các phép toán có thể tác động lên dữ liệu.

Và trong TP, một số kiểu dữ liệu dạng số như kiểu số nguyên (bao gồm kiểu: byte, integer, word, login) trong đó kiểu logint (có phạm vi lớn nhất): mỗi giá trị lưu giữ trong 4 byte, giá trị biến kiểu này nằm trong phạm vi từ - 2³¹ đến 2³¹-1 tức là từ (-2147483648 đến 2147483647) nên chỉ cho phép biến lưu giữ số tối đa có 10 chữ số.

Như tất cả chúng ta đều biết, một trong những yêu cầu không thể thiếu đối với việc giải quyết các bài tập tin học là độ phức tạp của thuật toán. Thông thường, để đạt được độ phức tạp thuật toán như mong muốn, cách làm thường là tìm ra một thuật toán ban đầu làm cơ sở, rồi từ đó dùng các kỹ năng để giảm độ phức tạp của thuật toán. Trong bài viết này, tôi xin giới thiệu với bạn đọc một phương pháp khá thông dụng: nhân ma trận.

Trong chương trình toán phổ thông, chúng ta thường hay gặp các dạng bài toán Giải phương trình, Bất phương trình, Khảo sát hàm số. Có nhiều phần mềm toán học để làm điều này, nếu bạn yêu thích toán học hoặc bạn là sinh viên ngành kỹ thuật điện, điện tử, xây dựng… thi MathLab la chương trình rất quen thuộc. Tuy nhiên để sử dụng chương trình cần có thời gian và hiểu biết về phần mềm.

Trong rất nhiều bài toán, một thao tác cơ bản cần phải thực hiện là tìm kiếm một dữ liệu (Chẳng hạn khi thực hiện loang trên một tập trạng thái, bạn cần tìm kiếm xem một trạng thái đã được thăm trước đó hay chưa, (mà không thể dùng mảng đánh dấu vì mỗi trạng thái lại là một dãy số, một ma trận hay một xâu ký tự...), bằng cách tìm kiếm trạng thái hiện tại trong danh sách tập trạng thái đã thăm; hay trong quá trình quy hoạch động, bạn cần kiểm tra xem một dãy số hay một chuỗi kí tự có nằm trong một tập cho trước không...). Để tìm kiếm một cách có hiệu quả là một việc không hề đơn giản. Có rất nhiều cấu trúc dữ liệu giúp bạn thực hiện thao tác tìm kiếm: binary search tree, hash table, ... Trong bài viết này, tôi xin đề cập đến cấu trúc dữ liệu Trie.

Bài toán tám quân hậu là bài toán đặt tám quân hậu trên bàn cờ vua kích thước 8×8 sao cho không có quân hậu nào có thể "ăn" được quân hậu khác, hay nói khác đi không quân hậu nào có để di chuyển theo quy tắc cờ vua. Mầu của các quân hậu không có ý nghĩa trong bài toán này. Như vậy, lời giải của bài toán là một cách xếp tám quân hậu trên bàn cờ sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường chéo.

1. Bài toán dãy con tăng – giảm dài nhất

Bài toán tìm dãy con tăng-giảm dài nhất được phát biểu như sau: cho một dãy số nguyên (hoặc 1 dãy số, một xâu ..) gồm n phần tử. Hãy tìm một dãy con gồm các phần tử của dãy ban đầu (giữ nguyên thứ tự) sao cho các phần tử của dãy con đó tạo thành một dãy tăng-giảm dần và dài nhất có thể được. Các phần tử của dãy con dài nhất tìm được (nghiệm của bài toán) không nhất thiết phải là các phần tử liên tiếp trong dãy ban đầu. Vì việc tìm một dãy con tăng dài nhất cũng tương tự như việc tìm một dãy con giảm dài nhất nên chúng ta sẽ chỉ xem xét bài toán tìm dãy con dài nhất. Các kiến thức tương tự cũng sẽ được áp dụng cho bài toán tìm dãy con giảm dài nhất.

Bài toán tính giai thừa là một trong các bài toán cơ bản khi học về lập trình (vòng lặp và đệ qui). Về cơ bản tính giai thừa (Factorial) là một bài toán tính tích n! = 1*2*...*n. Đối với các giá trị n nhỏ (n ≤ 20) thì giá trị của n! vẫn nằm trong vùng biểu diễn của số nguyên, tuy nhiên đối với số n lớn (khoảng vài trăm, vài nghìn) thì việc tính n! trở nên khó khăn vì giá trị của n! vượt quá khoảng biểu diễn của kiểu số nguyên lớn nhất. Trong bài báo này tôi sẽ giới thiệu với các bạn một thuật toán cơ bản dùng để tính giai thừa của một số nguyên lớn (n ≤ 100000) trên ngôn ngữ C/C++.

Bài toán: Trên mặt phẳng toạ độ cho N đoạn thẳng (1<=N<=100). Toạ độ các điểm đầu, cuối của N đoạn thẳng này là các số nguyên không âm nhỏ hơn 20000. Đường thẳng đi qua mỗi đoạn thẳng này tạo với 2 trục toạ độ những tam giác vuông cân. Hai đoạn thẳng bất kì trong N đoạn thẳng này không có điểm chung.

Trong giải Toán cực trị hình học, bất đẳng thức Cô-si là một trong những bất đẳng thức thường dùng. Bất đẳng thức Cô-si chính là một trong những phương pháp rất hữu hiệu để Đại số hóa các bài toán hình học. Ứng dụng của nó như thế nào? Phần mềm hình học động ứng dụng trong cực trị hình học ra sao? Chúng ta sẽ khám phá những điều này trong bài viết sau. Tuy nhiên, trước hết chúng ta hãy đến với một số dạng của bất đẳng thức Cô-si.

Bài toán: Trong mặt phẳng toạ độ trực chuẩn, cho N hình chữ nhật có các cạnh song song với trục toạ độ. Mỗi HCN được xác định bởi toạ độ đỉnh dưới bên trái và đỉnh trên bên phải của nó. Hãy tính diện tích phần mặt phẳng bị phủ bởi các HCN trên.

Ta biết rằng từ đồ thị hàm số (C): y = f(x) ta có thể vẽ đồ thị hàm số (C₁): y = f(|x|), (C₂): y =|f(x)|, (C₃): y = -f(x), (C₄):y = f(-x), (C₅): y = f ^-1(x) (nếu hàm số f có hàm số ngược trên khoảng xác định của nó), (C6): y = - f(-x), (C7): y = f(x + a), (C8): y = f(x) + b, bằng các phép đối xứng trục, phép đối xứng tâm, phép tịnh tiến phù hợp.

Vấn đề được đặt ra là: khi đã cho biết những đồ thị hàm số y = f1(x), y = f2(x), y = f(x) thì ta có thể vẽ các đồ thị hàm số có dạng y = k1.f1(x) + k2.f2(x) (k1, k2 là hai số thực khác không), hay không ? và cách vẽ như thế nào ?. Câu trả lời là được. Bài viết này sẽ giải quyết trọn vẹn vấn đề đó.

Ta biết rằng từ đồ thị hàm số (C): y = f(x) ta có thể vẽ đồ thị hàm số (C₁): y = f(|x|), (C₂): y =|f(x)|, (C₃): y = -f(x), (C₄):y = f(-x), (C₅): y = f ^-1(x) (nếu hàm số f có hàm số ngược trên khoảng xác định của nó), (C6): y = - f(-x), (C7): y = f(x + a), (C8): y = f(x) + b, bằng các phép đối xứng trục, phép đối xứng tâm, phép tịnh tiến phù hợp.

Vấn đề được đặt ra là: khi đã cho biết những đồ thị hàm số y = f1(x), y = f2(x), y = f(x) thì ta có thể vẽ các đồ thị hàm số có dạng y = k1.f1(x) + k2.f2(x) (k1, k2 là hai số thực khác không), hay không ? và cách vẽ như thế nào ?. Câu trả lời là được. Bài viết này sẽ giải quyết trọn vẹn vấn đề đó.

Hẳn các bạn đã biết đến hình vuông, một tứ giác đặc biệt có 4 cạnh bằng nhau và 4 góc bằng nhau (bằng 900), hình vuông là sự kết hợp hoàn hảo giữa hình chữ nhật và hình thoi. Trong Tin học, cũng có rất nhiều bài toán thú vị về hình vuông. Chúng ta hãy cùng tìm hiểu một trong số các bài toán ấy.

Chắc đã có lần trong công việc hàng ngày, chúng ta đã gặp bài toán sau: “Trong mặt phẳng, cho một hình đa giác bất kì với toạ độ các đỉnh là số thực. Vấn đề đặt ra là xác định trọng tâm của hình đa giác đó”.

Để làm được việc đó, sau đây xin tóm tắt lại lý thuyết đặc trưng hình học của mặt cắt ngang:

Kể từ khi máy tính điện tử ra đời, nhân loại đã bước vào một kỷ nguyên mới - Kỷ nguyên công nghệ thông tin. Sự ra đời của máy tính điện tử đã giúp đỡ cho chúng ta rất nhiều về mọi lĩnh vực khoa học và đời sống. Bất cứ lĩnh vực nào liên quan đến tính toán, thì máy tính có thể làm thay ta được. Đặc biệt trong đó có thể kể đến toán học. Toán học đã và đang đóng vai trò cơ bản cho sự hình thành và phát triển của ngành tin học. Thì ngày nay ngược lại, tin học cũng đóng vai trò rất quan trọng cho sự phát triển của toán học.

Trong Toán học có một bài toán đã trở nên cực kì quen thuộc đối với bất cứ ai trong chúng ta, đó là bài toán ba đường trung tuyến của tam giác. Bài toán ba đường trung tuyến là một bài toán có hấp lực vô cùng lớn. Đứng về phương diện hình học Afin nó là một trong những bài toán Afin đơn giản nhất. Đứng về phương diện Hình học Euclide nó là một bài toán có sức phát triển rất cao mà hết cả cuộc đời chúng ta không bao giờ đi tới tận cùng của nó. Vẻ đẹp của mối quan hệ giữa Hình học sơ cấp và Hình học cao cấp, đó là nét đẹp giữa cái đơn giản và phức tạp là mối quan hệ nhiều chiều mà ta cần quan tâm. Xin được chia sẻ với các bạn về những điều đã nói trước hết qua bài toán sau :

Đồ thị (Graph) có thể nói là một trong những cấu trúc rời rạc thường được sử dụng nhất trong ngành khoa học máy tính. Mỗi khi cần mô hình hóa một tập đối tượng cùng với các mối quan hệ giữa chúng, chúng ta luôn có thể trừa tượng hóa (abstract) chúng bằng đồ thị. Một mạng giao thông, mạng máy tính, quan hệ quen biết giữa một nhóm người, quan hệ về sở thích (A thích ăn cam, B thích ăn quýt)…v…v. tất cả đều có thể đưa về mô hình của một đồ thị.

Trong Toán học có một bài toán đã trở nên cực kì quen thuộc đối với bất cứ ai trong chúng ta, đó là bài toán ba đường trung tuyến của tam giác. Bài toán ba đường trung tuyến là một bài toán có hấp lực vô cùng lớn. Đứng về phương diện hình học Afin nó là một trong những bài toán Afin đơn giản nhất. Đứng về phương diện Hình học Euclide nó là một bài toán có sức phát triển rất cao mà hết cả cuộc đời chúng ta không bao giờ đi tới tận cùng của nó. Vẻ đẹp của mối quan hệ giữa Hình học sơ cấp và Hình học cao cấp, đó là nét đẹp giữa cái đơn giản và phức tạp là mối quan hệ nhiều chiều mà ta cần quan tâm. Xin được chia sẻ với các bạn về những điều đã nói trước hết qua bài toán sau :