Kĩ thuật lập trình Game – Cơ bản - part 2

VI.  Giao điểm của hai đường thẳng
Từ hai đoạn thẳng (hoặc vector) trong mặt phẳng 2D, ta có  thể tìm được giao điểm của chúng để 
tính toán các góc phản xạ và hướng di chuyển.
1.  Tạo phương trình đường thẳ ng từ đoạn thẳng
Ta có hai điểm A(x1,y1) và B(x2,y2) tạo thành một đoạn thẳng, để tạo được một phương trình 
đường thẳng từ  hai điểm  này, ta cần  tính được độ nghiêng của đường thẳng (slope) theo công 
thức:  
a = (y2 –  y1)/(x2 –  x1)
Thay thế x2, y2 bằng hai biến x,y:
a = (y –  y1)/(x –  x1)
=> y –  y1 = a(x –  x1)
Hay:
y = ax + (y1 – ax1)
Đặt b = y1 – ax1, ta có:
y = ax + b
2.  Tính giao điể m của hai đường thẳng
Ta có hai phương trình đường thẳng
(1): y = a1x + b1
(2): y = a2x + b2
Ta có thể tính được giao điểm của chúng bằng cách tìm   giao điểm x trước:
a1x + b1 = a2x + b2;
=> x(a1 – a2) = b2 – b1
=> x = (b2 – b1)/(a1 – a2)
Khi đã có x, ta sẽ thế vào (1) hoặc (2 ) để tính được y.  Để kiểm tra hai đoạn thẳng có cắt nhau 
không, ta chỉ cần kiểm tra điểm {x,y} thuộc cả hai đoạn thẳng hay không.   Ngoài ra ta cần loại 
trừ trường  hợp  hai đường thẳng song song  hoặc trùng nhau, khi đó  giá trị slope của chúng sẽ 
bằng nhau. 

Power-point: "Di tích Hoàng thành Thăng Long"

Kĩ thuật lập trình Game – Cơ bản - part 1

I.   Vòng lặp game (Game loop) hoạt động thế  nào?

Phần cốt lõi của hầu hết các game chính là vòng lặp được dùng để cập nhật và hiển thị trạng thái của game. Trong bài viết này,  ta  sẽ minh họa các phương pháp tạo vòng lặp   game với ngôn ngữ javascript.

1.  Vòng lặp cơ bản

Một vòng lặp game cơ bản bao gồm các việc được thực hiện theo thứ tự sau:

while(gameRunning)

{

 processInput(); // keyboard, mouse,...

 updateGame();

 draw();

 // checkGameOver();

}

Minh họa:

STL for newbies: STL ALGORITHMS (Thư viện thuật toán) - part 5

STL ALGORITHMS (THƯ VIỆN THUẬT TOÁN): 

-  Khai báo sử dụng: #include <algorithm> 
-  Các hàm trong STL Algorithm khá nhiều nên mình chỉ giới thiệu sơ qua về một số 
hàm hay sử dụng trong các bài toán. 
-  Có một lưu ý nhỏ cho các bạn là khi sử dụng các hàm mà thực hiện trong một đoạn 
phần tử liên tiếp nào đó thì các hàm trong c++ thuờng có tác dụng trên nửa đoạn [..). 
Ví dụ như: bạn muốn hàm f có tác dụng trong đoạn từ 1->n thì các bạn phải gọi hàm 
trong đoạn từ 1 ->n+1. 


Min, max: 
1.1.  min:trả về giá trị bé hơn theo phép so sánh (mặc định là phép toán less): 
Ví dụ: min(‘a’,’b’) sẽ return ’a’; 
 min(3,1) sẽ return 1; 
1.2.  max thì ngược lại với hàm min: 
Ví dụ: max(‘a’,’b’) sẽ return ‘b’ 
 max(3,1) sẽ return 1. 
1.3.  next_permutation:hoán vị tiếp theo. Hàm này sẽ return 1 nếu có hoán vị 
tiếp theo, 0 nếu không có hoán vị tiếp theo. 
Ví dụ: 
// next_permutation 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main () { 
int myints[] = {1,2,3}; 
cout << "The 3! possible permutations with 3 elements:\n"; 
do { 
cout << myints[0] << " " << myints[1] << " " << myints[2] << endl; 
} while ( next_permutation (myints,myints+3) ); 
return 0; 
} 
Output: 
The 3! possible permutations with 3 elements: 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3  1 2 
4  2 1 
1.4.  prev_permution: ngược lại với next_permutation

STL for newbies: CONTAINERS (Thư viện lưu trữ) - part 4

Associative containers 
-  Một container là một đối tượng cụ thể lưu trữ một tập các đối tượng khác (các phần tử 
của nó). Nó được thực hiện như các lớp mẫu ( class templates). 
-  Container quản lý không gian lưu trữ cho các phần tử của nó và cung cấp các hàm 
thành viên (member function) để truy cập tới chúng, hoặc trực tiếp hoặc thông qua 
các biến lặp (iterator – giống như con trỏ). 
-  Container xây dựng các cấu trúc thuờng sử dụng trong lập trình như: mảng động - 
dynamic arrays (vector), hàng đợi – queues (queue), hàng đợi ưu tiên – heaps (priority 
queue), danh sách kiên kết – linked list (list), cây – trees (set), mảng ánh xạ - 
associative arrays (map),... 
-  Nhiều container chứa một số hàm thành viên giống nhau. Quyết định sử dụng loại 
container nào cho nhu cầu cụ thể nói chung không chỉ phụ thuộc vào các hàm được 
cung cấp mà còn phải dựa vào hiệu quả của các hàm thành viên của nó (độ phức tạp 
(từ giờ mình sẽ viết tắt là ĐPT) của các hàm). Điều này đặc biệt đúng với container 
dãy (sequence containers), mà trong đó có sự khác nhau về độ phức tạp đối với các 
thao tác chèn/xóa phần tử hay truy cập vào phần tử. 


Set (Tập hợp): 
-  Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp 
(unique elements), và các phần tử này chính là các khóa (keys). 
-  Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép 
toán so sánh. 
-  Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo 
ý mình. 
-  Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree). 

STL for newbies: CONTAINERS (Thư viện lưu trữ) - part 3

Containers adpators
-  Một container là một đối tượng cụ thể lưu trữ một tập các đối tượng khác (các phần tử 
của nó). Nó được thực hiện như các lớp mẫu ( class templates). 
-  Container quản lý không gian lưu trữ cho các phần tử của nó và cung cấp các hàm 
thành viên (member function) để truy cập tới chúng, hoặc trực tiếp hoặc thông qua 
các biến lặp (iterator – giống như con trỏ). 
-  Container xây dựng các cấu trúc thuờng sử dụng trong lập trình như: mảng động - 
dynamic arrays (vector), hàng đợi – queues (queue), hàng đợi ưu tiên – heaps (priority 
queue), danh sách kiên kết – linked list (list), cây – trees (set), mảng ánh xạ - 
associative arrays (map),... 
-  Nhiều container chứa một số hàm thành viên giống nhau. Quyết định sử dụng loại 
container nào cho nhu cầu cụ thể nói chung không chỉ phụ thuộc vào các hàm được 
cung cấp mà còn phải dựa vào hiệu quả của các hàm thành viên của nó (độ phức tạp 
(từ giờ mình sẽ viết tắt là ĐPT) của các hàm). Điều này đặc biệt đúng với container 
dãy (sequence containers), mà trong đó có sự khác nhau về độ phức tạp đối với các 
thao tác chèn/xóa phần tử hay truy cập vào phần tử. 
Stack (Ngăn xếp): 
-  Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last - 
in first - out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ 
một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh 
(top) của ngăn xếp. 

STL for newbies: CONTAINERS (Thư viện lưu trữ) - part 2

Sequence containers 
-  Một container là một đối tượng cụ thể lưu trữ một tập các đối tượng khác (các phần tử 
của nó). Nó được thực hiện như các lớp mẫu ( class templates). 
-  Container quản lý không gian lưu trữ cho các phần tử của nó và cung cấp các hàm 
thành viên (member function) để truy cập tới chúng, hoặc trực tiếp hoặc thông qua 
các biến lặp (iterator – giống như con trỏ). 
-  Container xây dựng các cấu trúc thuờng sử dụng trong lập trình như: mảng động - 
dynamic arrays (vector), hàng đợi – queues (queue), hàng đợi ưu tiên – heaps (priority 
queue), danh sách kiên kết – linked list (list), cây – trees (set), mảng ánh xạ - 
associative arrays (map),... 
-  Nhiều container chứa một số hàm thành viên giống nhau. Quyết định sử dụng loại 
container nào cho nhu cầu cụ thể nói chung không chỉ phụ thuộc vào các hàm được 
cung cấp mà còn phải dựa vào hiệu quả của các hàm thành viên của nó (độ phức tạp 
(từ giờ mình sẽ viết tắt là ĐPT) của các hàm). Điều này đặc biệt đúng với container 
dãy (sequence containers), mà trong đó có sự khác nhau về độ phức tạp đối với các 
thao tác chèn/xóa phần tử hay truy cập vào phần tử. 

STL for newbies: ITERATOR (Biến lặp) - part 1

“C++ được đánh giá là ngôn ngữ mạnh vì tính mềm dẻo, gần gũi với ngôn ngữ máy. Ngoài ra, với khả nănglập trình theo mẫu ( template ), C++ đã khiến ngôn ngữ lập trình trở thành khái quát, không cụ thể và chi tiết như nhiều ngôn ngữ khác. Sức mạnh của C++ đến từ STL, viết tắt của Standard Template Library -một thư viện template cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn STL. Bộ thư viện này thực hiện toàn bộ các công việc vào ra dữ liệu (iostream), quản lý mảng (vector), thực hiện hầu hết các tính năng của các cấu trúc dữ liệu cơ bản (stack, queue, map, set...). Ngoài ra, STL còn bao gồm các thuật toán cơ bản: tìm min, max, tính tổng, sắp xếp (với nhiều thuật toán khác nhau), thay thế các phần tử, tìm kiếm (tìm kiếm thường và tìm kiếm nhị phân), trộn. Toàn bộ các tính năng nêu trên đều được cung cấp dưới dạng template nên việc lập trình luôn thể hiện tính khái quát hóa cao. Nhờ vậy, STL làm cho ngôn ngữ C++ trở nên trong sáng hơn nhiều.”

-  Thư viện mẫu chuẩn STL trong C++ chia làm 4 thành phần là:
  + Containers Library : chứa các cấu trúc dữ liệu mẫu (template) 
      + Sequence containers 
          + Vector 
          + Deque 
          + List 
     + Containers adpators 
          + Stack 
          + Queue 
          + Priority_queue 
    + Associative containers 
          + Set 
          + Multiset 
          + Map 
          + Multimap 
          + Bitset 
   + Algorithms Library: một số thuật toán để thao tác trên dữ liệu 
   + Iterator Library: giống như con trỏ, dùng để truy cập đến các phần tử dữ liệu 
của container. 
   + Numeric library: 
-  Để sử dụng STL, bạn cần khai báo từ khóa “using namespace std;” sau các khai báo 
thư viện (các “#include”, hay “#define”,...) 

Bài toán về sự liên quan giữa tổng các chữ số của n! và dấu hiệu chia hết cho 9

Đề bài:

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.

Bài toán về thừa số nguyên tố

Đề bài:

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⁹

Solution hỗ trợ giải mã thông điệp

Solution này dùng để giải các thông điệp được xây dựng trên cách mã hóa sau:

Quy tắc mã hóa :

Đoạn thông điệp được mã hóa là một đoạn văn bản có ý nghĩa. Đầu và cuối thông điệp không có khoảng trắng. Các ký tự sử dụng trong đoạn văn bản này là các ký tự có giá trị từ 32 đến 126 trong bảng mã ASCII.

Đoạn văn bản được mã hóa theo một khoá K. Khoá K có giá trị trong đoạn [0, 255].
     Bước 1: Các ký tự trong thông điệp ban đầu sẽ được chuyển sang dạng nhị phân. 
     Bước 2: Các ký tự này (ở dạng nhị phân) sẽ thực hiện phép toán XOR với khóa K cho trước để được bản tin đã mã hoá.
     Bước 3: Dãy nhị phân của bản tin đã mã hóa được chia thành các nhóm 5 bit. Mỗi nhóm 5 bit này được thêm vào bit 1 ở đầu và chuyển thành ký tự có mã ASCII tương ứng.

Lời giải tuyển sinh cao học ngành KHMT, năm 2011

Đề bài:
Tính :
            Aver=∑i=0n−1(ai−Max)2+∑i=0n−1(ai−Min)2+n2(Max−Min)2
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).