Tag Archives: hướng đối tượng

Chỉ dẫn thực hành về mô phỏng máy tính

Tác giả: Alexander K. Hartmann

Đại học Gottingen, Đức
hartmann@theorie.physik.uni-goettingen.de

Heiko Rieger
Đại học Saarbrucken, Germany
rieger@lusi.uni-sb.de

1/2/2008

Tóm lược nội dung của bài báo “…”, vốn được trích từ cuốn sách: A.K. Hartmann and H. Rieger, Optimization Algorithms in Physics, (Wiley-VCH, Berlin, Weinheim 2001), ISBN 3-527-40307-8, với sự đồng ý của Wiley-VCH, xem http://www.wiley.com.

Bài báo gốc (bản tiếng Anh) có thể được tự do phân phối dưới dạng bản điện tử (file PDF) và bản in, nhưng không được thay đổi. Chính vì vậy trong bài post này, tôi chỉ tóm tắt lại nội dung bằng tiếng Việt sau đó chỉ đến những trang cụ thể để bạn đọc xem trong file tiếng Anh.

Tóm tắt

Bài này thảo luận các khía cạnh thực tế của việc tiến hành nghiên cứu bằng mô phỏng máy tính. Các vấn đề sau được làm rõ: gia công phần mềm, phát triển phần mềm hướng đối tượng, phong cách lập trình, macro, các file make, các văn lệnh, thư viện, số ngẫu nhiên, kiểm tra, gỡ lỗi, vẽ đồ thị, khớp đường cong, giãn tỉ lệ cỡ hữu hạn, truy cập thông tin, và chuẩn bị thuyết trình.

Do khuôn khổ có hạn, mỗi lĩnh vực thường chỉ có mục giới thiệu ngắn và có trích dẫn đến những học liệu bao quát vấn đề rộng hơn. Tất cả mã lệnh đều dùng ngôn ngữ C/C++.

Nội dung

1 Kĩ thuật phần mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Phát triển phần mềm hướng đối tượng. . . . . . . . . . . . . . 10

3 Phong cách lập trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Công cụ để lập trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.1 Dùng macro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Các file make . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3 Các văn lệnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Những thư viện phần mềm . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1 Phương pháp số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 LEDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3 Tự lập ra thư viện của riêng bạn . . . . . . . . . . . . . . . . . . 33

6 Số ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.1 Phát sinh số ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2 Phương pháp nghịch đảo . . . . . . . . . . . . . . . . . . . . . . . . 38
6.3 Phương pháp loại bỏ . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.4 Phân bố Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

7 Các công cụ kiểm thử chương trình . . . . . . . . . . . . . . . . . 42
7.1 gdb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.2 ddd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.3 checkergcc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

8 Đánh giá dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
8.1 Vẽ đồ thị số liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
8.2 Khớp đường cong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
8.3 Giãn tỉ lệ cỡ hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9 Truy tìm thông tin và xuất bản . . . . . . . . . . . . . . . . . . . . 57
9.1 Tìm văn liệu nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . 58
9.2 Chuẩn bị xuất bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Trong tài liệu này, các khía cạnh thực dụng trong việc tiến hành nghiên cứu bằng mô phỏng máy tính đã được thảo luận. Giả thiết rằng bạn đã làm quen với một hệ điều hành kiểu UNIX (như Linux), một ngôn ngữ lập trình bậc cao như C, Fortran hoặc Pascal và có một chút kinh nghiệm với ít nhất là những dự án phần mềm nhỏ.
Do khuôn khổ có hạn, thường chỉ có những đoạn giới thiệu ngắn về các lĩnh vực cụ thể được trình bày, cùng những trích dẫn đến nguồn tài liệu phong phú. Tất cả ví dụ mã lệnh đều được viết bằng C/C++.
Trước hết là phần trình bày ngắn về kĩ thuật phần mềm và một số gợi ý cho phép lập trình mã lệnh hiệu quả và đáng tin cậy. Ở mục thứ hai có trình bày giới thiệu ngắn gọn về phát triển phần mềm hướng đối tượng. Cụ thể, bài viết còn cho thấy rằng phong cách lập trình này cũng có thể đạt được bằng những ngôn ngữ thủ tục tiêu chuẩn như C. Tiếp theo là những gợi ý thực dụng về quá trình thực sự viết mã lệnh. Ở mục thứ tư, các macro được giới thiệu. Sau đó trình bày cách phát triển những đoạn mã lệnh lớn hơn có thể được tổ chức nhờ các file make. Trong mục tiếp theo, lợi ích của việc dùng các thư viện như Numerical Recipes (Phương pháp số) hoặc LEDA được giải thích và cho bạn thấy cách tự thiết lập các thư viện riêng của bạn.

Trong mục thứ sáu, cách phát sinh số ngẫu nhiên sẽ được trình bày còn mục thứ 8 đề cập đến ba công cụ gỡ lỗi rất hữu ích. Sau đó, sẽ giải thích các chương trình thực hiện phân tích dữ liệu, khớp đường cong và giãn cỡ hữu hạn. Mục cuối là một đoạn giới thiệu về truy tìm thông tin, tìm kiếm tài liệu nghiên cứu trên mạng và cách chuẩn bị thuyết trình và xuất bản.

1. Kĩ thuật phần mềm

Hãy lập kế hoạch trước khi lao vào viết chương trình. Ngay cả khi bạn viết các chương trình nghiên cứu mà không hợp tác với ai. Lập kế hoạch giúp chương trình được linh động và dễ tìm lỗi. Lĩnh vực này có tên “Software engineering”, và được đề cập trong nhiều cuốn sách tin học. Những phương pháp trong kĩ thuật phần mềm gồm có:

  • Định nghĩa vấn đề và chiến lược giải quyết
    • Cần nhập vào dữ liệu gì? nhập ít dữ liệu qua dòng lệnh, hay có file thông số riêng?
    • Cần thu nhận kết quả nào, cần phân tích những đại lượng gì? Số liệu thô (đầy đủ) hay số liệu nén (tiết kiệm dung lượng đĩa)?
    • Bạn có thể nhận diện những “đối tượng” trong bài toán không? Đối tượng có thể là những thực thể (nguyên tử, phân tử) hay khái niệm tin học (nút, phần tử). Khi khái quát hóa hệ thống thành một cấu trúc phân cấp sẽ dễ thiết kế chương trình hơn.
    • Chương trình về sau này có được mở rộng không? (khả năng tái sử dụng)
    • Bạn có những chương trình nào có sẵn để có thể kèm vào trong dự án phần mềm không?
    • Những thuật toán nào đã biết rồi? Hãy tìm những gì có sẵn trước khi sáng tạo, bởi sáng tạo mất nhiều thời gian.
  • Thiết kế cấu trúc dữ liệu

Một khi đã nhận diện được các đối tượng cơ bản trong hệ thống, bạn cần nghĩ cách biểu diễn chúng. Thiết kế tỉ mỉ cấu trúc dữ liệu sẽ làm cho chương trình được tổ chức tốt hơn và thường chạy nhanh hơn.

Khi dùng các thư viện bên ngoài, các thư viện này thường có sẵn một số kiểu dữ liệu mà bạn có thể tận đụng để thiết kế chương trình.

  • Định nghĩa những tác vụ nhỏ

Sau khi thiết lập các kiểu dữ liệu, bạn cần nghĩ về những thao tác đơn giản và phức tạp (thủ tục/chương trình con) để thao tác trên những đối tượng.  Hãy chia nhiệm vụ lớn “mô phỏng” thành những tác vụ nhỏ (cách tiếp cận từ trên xuống / top down). Song khi viết lệnh thì phải thực hiện từ dưới lên. Nghĩa là bắt đầu viết từ những phép toán cơ bản nhất. Sau đó dùng những phép toán cơ bản này để lập những phép tính phức tạp hơn.

  • Phân phối công việc

Trong trường hợp nhiều người đang cùng tham gia vào một dự án, thì bước tiếp theo là phân chia công việc giữa những cộng sự này. Nếu có vài kiểu đối tượng xuất hiện trong thiết kế chương trình, thì một cách tiếp cận tự nhiên sẽ là phân công từn người có trách nhiệm với một số đối tượng cùng những phép toán liên quan đến nó. Mã lệnh phải được chia thành nhiều mô đun (file mã nguồn), để cho mỗi mô đun chỉ do một người viết.

Khi nhiều người cùng biên tập một file mã lệnh, ta nên dùng hệ thống quản lý mã lệnh như RCS trong hệ GNU/Linux [5] (lưu ý cái này khá cổ điển).

  • Viết mã lệnh
  • Kiểm tra (testing)
    • Các trường hợp kiểm tra (test case) cần đặc biệt và hiếm để phát hiện được lỗi.
    • Thay vì cách thủ công (chèn lệnh print vào trong mã lệnh), hãy dùng bộ gỡ lỗi (debugger).
    • Kiểm tra kết quả của bài toán nhỏ, so sánh nó với kết quả mà bạn tự nhẩm tính được.
    • So sánh kết quả của nhiều phương pháp khác nhau với cùng một bài toán.
    • Mỗi khi viết xong một chương trình con, hãy kiểm tra ngay nó.
    • Giữ phiên bản mã lệnh cũ trước khi thay đổi, cải tiến.
    • Lập trình C nên dùng tùy chọn bật tất cả cảnh báo (-Wall). Lưu ý dấu == thay vì =
  • Viết tài liệu (documentation)
    • Ghi chú (comment) trong mã nguồn
    • Trợ giúp trực tuyến – theo nghĩa thông tin trợ giúp khi người dùng gọi chương trình từ cửa sổ lệnh
    • Tài liệu ngoài
  • Sử dụng mã lệnh: có một số vấn đề cần cân nhắc
    • Mỗi lần chạy mất bao lâu? Trước hết nên chạy với các bài toán nhỏ, rồi suy ra thời gian chạy bài toán lớn
    • Thời gian chạy nên được trung bình hóa với các mẫu khác nhau
    • Kết quả lưu vào đâu?  Cần tổ chức file và thư mục hợp lý, có file README để chỉ dẫn
    • Các file log rất có ích để tự động ghi thông tin trong quá trình mô phỏng.

Các vấn đề trên không nhất thiết phải làm tuần tự. Phát triển phần mềm thường là một chu trình khép kín. Sau khi chạy chương trình, có thể quay về cải thiện khâu thiết kế.

2. Phát triển phần mềm hướng đối tượng

Phong cách lập trình hướng đối tượng khác với ngôn ngữ lập trình hướng đối tượng. Bạn có thể lập dự án với các phương thức hướng đối tượng mà chỉ cần những ngôn ngữ lập trình thủ tục như C, Pascal hay Fortran. Một số nguyên tắc khi phát triển phần mềm hướng đối tượng như sau:

  • Đối tượng và phương thức. Các đối tượng được phân vào các lớp. Đối tượng có thể sở hữu trạng thái. Đối tượng hiện diện trong môi trường thể hiện bởi những hoạt động (phương thức tác động lên đối tượng đó). Đối tượng và các phương thức liên quan sẽ hình thành nên những khối rõ rệt. Từ quan điểm lập trình hướng đối tượng, chương trình có thể được tổ chức như một tập hợp các đối tượng gọi những phương thức của lẫn nhau.
  • Bao gói dữ liệu. Nguyên tắc chung của lập trình hướng đối tượng là che giấu phần mã lệnh cấu thành những đối tượng. Việc truy cập đến đối tượng là được thực hiện thông qua giao diện, tức là các phương thức. Cấu trúc dữ liệu bên trong được ẩn giấu (từ khóa private trong C++). Việc bao gói dữ liệu có một số ưu điểm:
    • Bạn không cần phải nhớ chi tiết cấu thành nên đối tượng; coi đối tượng như những hộp đen.
    • Sau này bạn có thể thay đổi chi tiết cấu thành đối tượng mà không phải thay đổi toàn bộ chương trình. Rất cần nếu cần nâng cao hiệu năng chương trình hay bổ sung những tính năng mới.
    • Bạn có cấu trúc dữ liệu linh hoạt, ví dụ cùng cấu trúc cây dữ liệu: nếu cây thưa thớt bạn có thể dùng kiểu con trỏ, cây dữ liệu đặc có thể dùng kiểu mảng.
    • Dễ gỡ lỗi hơn.
  • Thừa kế. Các đối tượng cấp thấp có thể là những dạng đặc biệt của đối tượng cấp cao hơn. Chẳng hạn trong vật lý có lớp “nguyên tử” và cấp thấp hơn là “nguyên tử tích điện” (thêm thuộc tính điện tích), và những đối tượng của lớp mới này vẫn dùng lại được các thủ tục tính toán như đối tượng lớp trên. Ngược lại, đối tượng cấp cao cũng có thể định nghĩa là tập hợp của các đối tượng cấp thấp.
  • Trùng tải toán tử (operator overloading). Bạn có thể có những phương thức cùng tên để dùng với các lớp khác nhau. Ví dụ nếu dùng C hay Pascal thì các phép cộng số nguyên và cộng số phức phải được đặt tên khác nhau, còn trong C++ chỉ cần đặt một tên (toán tử “+”).
  • Sử dụng lại phần mềm.

Như đã nói, ta vẫn có thể lập trình hướng đối tượng bằng các ngôn ngữ thủ tục như C. Chẳng ahjn, ta lập một lớp có tên “histo” để lập trình cho histogram bằng C.

#define _HISTO_NOM_   9       /* No. of (statistical) moments */

/* holds statistical informations for a set of numbers:   */
/* histogram, # of Numbers, sum of numbers, squares, ... */
typedef struct
{
  double from, to;         /* range of histogram */
  double delta;            /* width of bins */
  int n_bask;              /* number of bins */
  double *table;           /* bins */
  int low, high;           /* No. of data out of range */
  double sum[_HISTO_NOM_]; /* sum of 1s, numbers, numbers^2 ...*/
} histo_t;

Ở đây histo_t là một kiểu dữ liệu. Ta có thể viết phương thức tạo lập và xóa bỏ histogram:

/** creates a histo-element, where the empirical histogram  **/
/** table covers the range ['from', 'to'] and is divided    **/
/** into 'n_bask' bins.                                     **/
/** RETURNS: pointer to his-Element, exit if no memory.     **/
histo_t *histo_new(double from, double to, int n_bask)
{
  histo_t *his;
  int t;

  his = (histo_t *) malloc(sizeof(histo_t));
  if(his == NULL)
  {
    fprintf(stderr, "out of memory in histo_new");
    exit(1)
  }
  if(to < from)
  {
    double tmp;
    tmp = to; to = from; from = tmp;
    fprintf(stderr, "WARNING: exchanging from, to in histo_new\n");
  }
  his->from = from;
  his->to = to;
  if( n_bask <= 0)
  {
    n_bask = 10;
    fprintf(stderr, "WARNING: setting n_bask=10 in histo_new()\n");
  }
  his->delta = (to-from)/(double) n_bask;
  his->n_bask = n_bask;
  his->low = 0;
  his->high = 0;
  for(t=0; t< _HISTO_NOM_ ; t++) /* initialize summarized moments */
    his->sum[t] = 0.0;
  his->table = (double *) malloc(n_bask*sizeof(double));
  if(his->table == NULL)
  {
    fprintf(stderr, "out of memory in histo_new");
    exit(1);
  }
  else
    for(t=0; t<n_bask; t++)
      his->table[t] = 0;
  }
  return(his);
}
/** Deletes a histogram 'his'    **/
void histo_delete(histo_t *his)
{
  free(his->table);
  free(his);
}

Đối tượng histogram có thể được tạo bằng cách động thông qua việc gọi histo_new(), việc này tương ứng với gọi một constructor hay gọi new trong C++. Và khi không dùng đối tượng, ta gọi histo_delete(), tương ứng với destructor trong C++.

Ví dụ sau đây thực hiện việc chèn một phần tử vào bảng rồi tính trị trung bình. Toàn bộ mã lệnh có thể tham khảo ở [10].

/** inserts a 'number' into a histogram 'his'. **/
void histo_insert(histo_t *his, double number)
{
  int t;
  double value;
  value = 1.0;
  for(t=0; t< _HISTO_NOM_; t++)
  {
    his->sum[t]+= value;;     /* raw statistics */
    value *= number;
  }
  if(number < his->from)
  /* insert into histogram */
  his->low++;
  else if(number > his->to)
    his->high++;
  else if(number == his->to)
    his->table[his->n_bask-1]++;
  else
    his->table[(int) floor( (number - his->from) / his->delta)]++;
}

/** RETURNS: Mean of Elements in 'his' (0.0 if his=empty) **/
double histo_mean(histo_t *his)
{
  if(his->sum[0] == 0)
  return(0.0);
  else
    return(his->sum[1] / his->sum[0]);
}

3. Phong cách lập trình

Mã lệnh cần được viết theo phong cách thống nhất mà tác giả hoặc người khác sau này có thể hiểu và tiếp tục chỉnh sửa. Một số quy tắc như sau:

  • Chia nhỏ mã lệnh thành nhiều module. Ưu điểm gồm có:
    • Nếu cần sửa thì chỉ biên dịch lại những module nào thay đổi.
    • Những thủ tục (hàm) nào liên quan với nhau thì có thể được gom về chung một module.
    • Mỗi module một khi đã được hoàn thành và kiểm thử thì sẽ sử dụng được cho dự án khác.
    • Có nhiều  file (module) giúp các lập trình viên hợp tác tốt hơn so với 1 file (phải dùng Hệ thống quản lý phiên bản, CVS).
  • Để giữ cấu trúc logic của chương trình, bạn cần đặt riêng từng file chứa cấu trúc dữ liệu và file thực hiện tính toán (như file .h và .c/.cpp).
  • Gắng tìm những tên có ý nghĩa đặt cho các biến và hàm/thủ tục.
  • Thụt đầu dòng thật chuẩn, giúp người đọc hiểu được cấu trúc chương trình.
  • Tránh dùng những lệnh kiểu GOTO để nhảy đến chỗ khác trong chương trình.
  • Không dùng biến toàn cục. Vẻ ngoài tiện dụng của biến toàn cục sẽ gây khó khăn sau này nếu có lỗi gây ra bởi việc dùng sai biến toàn cục: bạn phải kiểm tra một danh sách dài dằng dặc các biến.
  • Đừng quá tiết kiệm lời chú thích mã lệnh. Các loại chú thích bao gồm:
    • Chú thích module: ngay đầu mỗi module cần nêu rõ tên, công dụng, tác giả, thời điểm viết.
    • Chú thích kiểu: với mỗi kiểu dữ liệu (struct trong C hay class trong C++) định nghĩa trong file header, bạn cần giải thích vài dòng về cấu trúc và ứng dụng của kiểu dữ liệu đó. Với lớp (class) thì giải thích cả những phương thức. Đồng thời mỗi phần tử trong cấu trúc cũng cần được giải thích.
    • Chú thích hàm/thủ tục: giải thích công dụng của hàm/thủ tục này, những biến vào – ra và các điều kiện tiên quyết cần đảm bảo trước khi gọi. Nếu bạn dùng một phương pháp số hay thuật toán khéo léo để giải quyết vấn đề, nhất thiết phải ghi tên phương pháp hoặc thuật toán đó.
    • Chú thích khối: một hàm có thể chia thành các khối theo logic, mỗi khối không nên dài quá 1 trang màn hình.
    • Chú thích dòng lệnh

4. Công cụ lập trình

Macro

Macro là cách làm tắt để phát sinh ra đoạn mã lệnh. Trong C, macro được tạo thành bằng dẫn hướng #define, và được thực hiện trong giai đoạn tiền xử lý của trình biên dịch.

#define PI 3.1415926536

Sau đó, trong mã lệnh nếu có đoạn 2.0*PI*omega

thì bộ tiền xử lý sẽ chuyển đổi mã lệnh thành: 2.0*3.1415926536*omegaSong tất nhiên macro không được thay thế trong chuỗi kí tự như: printf(“PI”);

Có thể kiểm tra sự tồn tại của macro bằng dẫn hướng #ifdef , chẳng hạn

#ifdef UNIX
  ...
#endif

Một ví dụ là quản lý các file header trong dự án phần mềm lớn. Làm thế nào đảm bảo rằng một file header chỉ được đọc 1 lần mà không bị đọc lặp lại?

/** example .h file: myfile.h **/
#ifndef _MYFILE_H_
#define _MYFILE_H_
  .... (rest of .h file)
  (may contain other #include directives)
#endif /* _MYFILE_H_ */

Macro không chỉ đóng vai trò hằng số mà có thể nhận những đối số (tương tự một hàm):

#define MIN(x,y) ( (x)<(y) ? (x):(y) )

Lưu ý trong phần “định nghĩa” của “hàm” (macro) MIN, dấu ngoặc (x) và (y) là cần thiết. Song lưu ý rằng macro không giống như hàm. Chẳng hạn khi viết MIN(a++, b++) thì các biến a và b sẽ được tăng hai lần khi thực hiện chương trình.

Một ví dụ với macro là bài toán hệ thống Ising spin: một ma trận trong đó từng vị trí i có một hạt σi. Mỗi hạt có đúng hai trạng thái σi = ±1. Đánh số thứ tự các vị trí i = 1 đến N, trong một bảng vuông có cạnh L (N = L × L). Số được đánh từ góc trên bên trái, đánh hết hàng trên xuống hàng dưới.

Nếu vị trí thứ i không phải trên cạnh biên thì phần tử này sẽ tương tác với bốn spin: i + 1 (hướng +x), i – 1 (hướng -x), i + L (hướng +y), và i – L (hướng -i). Nếu phần tử ở đường biên, thì việc dùng dạng biên tuần hoàn sẽ đảm bảo cho phần tử đó vẫn có 4 tương tác với 4 vị trí xung quanh (xem hình). Xét lưới 10 x 10 thì spin thứ 5 (giữa hàng trên cùng) sẽ tương tác với các spin số 5 + 1 = 6 , 5 – 1 = 4 , 5 + 10 = 15, và số 95 (đối diện). Để xét đến trường hợp đối diện ta có thể tính modulo L (cho hướng ±x), và modulo L² (hướng ±y).

Lưới ô 10 x 10

Để việc tính toán được thuận tiện, ta dùng ý tưởng thiết lập một ma trận liệt kê các vị trí lân cận (ma trận next); và có một chương trình con (không trình bày ở đây) để khởi tạo ma trận next này.

next là ma trận 1 chiều. Mỗi phần tử ở vị trí i có num_n phần tử lân cận (num_n = 4 với trường hợp trước); và vị trí của các lân cận này được lưu ở next[i*num_n], next[i*num_n+1], …, next[i*num_n + num_n -1]. Có thể dùng macro để truy cập i một cách tiện dụng như sau:

#define NEXT(i,r) next[(i)*num_n + r]

NEXT(i,r) chứa lân cận của phần tử i theo hướng r. Chẳng hạn, với lưới chữ nhật trong tọa độ Đề-các 2 chiều, r = 0 theo hướng +x, r=1 theo hướng -x, r=2 theo hướng +y, r=3 theo hướng -y (tùy bạn chọn thứ tự) và num_n = 4.

Trong hệ thống Ising, cần phải lưu lực tương tác (cả dấu lẫn độ lớn) giữa các phần tử vào một mảng j[]. Để truy cập vào mảng này được thuận tiện, ta lập macro J:

#define J(i,r) j[(i)*num_n + r]

Một chương trình con để tính năng lượng H = \sigma_{i,j} J_ij \sigma_i \sigma_j có thể như sau:

double spinglass_energy(int N, int num_n, int *next, int *j, short int *sigma)
{
  double energy = 0.0;
  int i, r;                 /* counters */
  for(i=1; i<=N; i++)       /* loop over all lattice sites */
    for(r=0; r<num_n; r++)  /* loop over all neighbors */
      energy += J(i,r)*sigma[i]*sigma[NEXT(i,r)];

  return(energy/2);         /* each pair has appeared twice in the sum */
}

trong đó N là số các spin (phần tử).

File make

Khi dự án phần mềm phình to ra, nó sẽ gồm vài file mã nguồn khác nhau. Thường sẽ nảy sinh sự ràng buộc giữa các file, chẳng hạn một kiểu dữ liệu được định nghĩa trong file header này có thể được dùng trong vài module khác. Do vậy, khi thay đổi một trong các file mã nguồn, có thể ta sẽ phải biên dịch lại một phần của chương trình. Nếu không muốn phải biên dịch thủ công, bạn có thể chuyển nhiệm vụ này cho công cụ make trên nền UNIX/Linux. Xem thêm chi tiết về file make trong [12].

Ý tưởng cơ bản của file make là bạn giữ một file có chứa tất cả ràng buộc giữa các file mã nguồn (sources) với nhau. Hơn nữa, nó cũng bao gồm các lệnh (như lệnh biên dịch) để sinh ra các file kết quả (file đích, target) là những chương trình hoặc file đối tượng (.o) (object file). Mỗi cặp ràng buộc và câu lệnh hợp thành một quy tắc (rule). File có chứa tất cả những quy tắc này cho một dự án phần mềm được gọi là file make. Nó thường được đặt tên Makefile và nằm ở thư mục chứa các file mã nguồn.

Quy luật được viết dưới dạng

target : sources
<tab> commands

Trong đó dòng thứ nhất chứa các ràng buộc còn dòng theo sau là (các) lệnh. Các dòng sau phải bắt đầu bằng dấu <tab>. Được phép dùng file đích khác nhau cho cùng một nguồn. Bạn có thể kéo dài các dòng sau với dấu \ ở cuối mỗi dòng. Một dòng lệnh cũng được phép để trống. Một ví dụ về cặp ràng buộc/lệnh như sau:

simulation.o: simulation.c simulation.h
<tab>   cc -c simulation.c

Điều này có nghĩa rằng file simulation.o phải được biên dịch nếu file simulation.c hoặc simulation.h bị thay đổi. Chương trình make được gọi khi ta gõ make vào dòng lệnh UNIX. Máy sẽ xem ngày giờ thay đổi cuối cùng, vốn được lưu giữ theo file, để quyết định xem có cần lập lại các file đích không. Đặc biệt, khi không có file đích, thì lệnh sẽ được gọi.

Cũng có thể tạo nên các quy tắc meta, tức là chỉ dẫn cách xử lý tất cả những file có phần đuôi tên cụ thể nào đó.

Lưu ý rằng công cụ make chỉ cố gắng biên dịch nên file đối tượng đầu tiên được yêu cầu trong file make, nên để biên dịch ra nhiều file đối tượng object1, object2, object3, cần thêm một quy luật đầu tiên như sau:

all: object1 object2 object3
object1: <các file mã nguồn của object1>
<tab>   <câu lệnh để tạo ra object1>
object2: ...
<tab>   <câu lệnh để tạo ra object2>
object3: ...
<tab>   <câu lệnh để tạo ra object3>

Còn nếu bạn chỉ muốn biên dịch lại đối tượng 3, thì hãy gõ lệnh make object3.

Thường người ta sẽ viết đích clean trong file make để cho tất cả file đối tượng được xóa đi sau khi gọi make clean. Bằng cách đó, lần gọi sau chỉ gõ make sẽ biên dịch toàn bộ chương trình từ đầu. Quy tắc với clean sẽ như sau:

clean:
<tab>  rm -f *.o

Thứ tự của các quy tắc không quan trọng trừ quy tắc thứ nhất là cái mà công cụ make luôn thực hiện đầu tiên.

Bạn cũng có thể định nghĩa các biến, đôi khi còn được gọi là macro theo mẫu:

biến=định nghĩa

Các biến môi trường như $HOME cũng dùng được trong file make nhưng tên biến phải được bọc trong cặp ngoặc: $(HOME) hoặc ${HOME}. Biến CC được chỉ định là lệnh biên dịch, bạn có thể thay đổi nó bằng cách viết, chẳng hạn,

CC=gcc

trong file make. Trong phần lệnh của một một quy tắc, ta sẽ gọi với tên $(CC).

Một ví dụ mô phỏng: chương trình khi hoàn thành sẽ có tên simulation. Có hai module init.c, run.c và các file .h tương ứng. Trong file datatypes.h, các kiểu dữ liệu được định nghĩa để dùng trong module. Ngoài ra, một file đối tượng đã biên dịch sẵn, analysis.o trong thư mục $HOME/lib cần được liên kết đến, và coi như file header tương ứng được đặt trong $HOME/include. Với init.o và run.o không cần câu lệnh nào. TRong trường hợp này, make áp dụng các lệnh tiêu chuẩn định nghĩa sẵn với những file có phần đuôi tên là .o, cụ thể:

<tab> $(CC) $(CFLAGS) -c $@

trong đó biến CFLAGS có thể chứa những tùy chọn được truyền đến trình biên dịch và ban đầu thì biến này để trống. Toàn bộ file make như sau, lưu ý rằng các dòng bắt đầu bằng dấu # là dòng chú thích:

#
# sample make file
#
OBJECTS=simulation.o init.o run.o
OBJECTSEXT=$(HOME)/lib/analysis.o
CC=gcc
CFLAGS=-g -Wall -I$(HOME)/include
LIBS=-lm
simulation: $(OBJECTS) $(OBJECTSEXT)
<tab>  $(CC) $(CFLAGS) -o $@ $(OBJECTS) $(OBJECTSEXT) $(LIBS)
$(OBJECTS): datatypes.h
clean:
<tab>  rm -f *.o

Văn lệnh (script)

Văn lệnh là những công cụ thậm chí còn tổng quát hơn file make. Thực ra, đó là các chương trình nhỏ, song không được biên dịch: văn lệnh là những chương trình ngắn được soạn ra nhanh chóng nhưng chạy tương đối chậm. Văn lệnh có thể được dùng để thực hiện công việc quản lý hệ thống như sao lưu dữ liệu, cài đặt phần mềm hoặc chạy nhiều chương trình mô phỏng với nhiều thông số. Văn lệnh có thể được viết bằng Bourne Shell (bash) trong Linux, hoặc Perl hay Python, v.v.

5. Thư viện

Thư viện là tập hợp các chương trình con và kiểu dữ liệu mà ta có thể dùng trong các chương trình khác. Có những thư viện về phương pháp số như tính tích phân hay giải phương trình vi phân, thư viện để tìm kiếm và sắp xếp dữ liệu, thư viện dành cho các kiểu dữ liệu đặc biệt như danh sách hoặc cây, hay thư viện đồ họa … Việc sử dụng thư viện sẽ rút ngắn thời gian phát triển phần mềm đáng kể. Bởi vậy luôn cần phải kiểm tra xem có sẵn thư viện hỗ trợ không, trước khi bạn bắt tay viết chương trình. Ở đây, chúng tôi trình bày hai thư viện phục vụ mô phỏng. Và mục cuối sẽ đề cập đến cách tự tạo thư viện của riêng bạn.

Numerical Recipes

Numerical Recipes hay NR [3] là thư viện chứa nhiều chương trình con để giải các bài toán số trị như:

  • giải phương trình tuyến tính
  • nội suy
  • lượng giá hàm và tính tích phân
  • giải phương trình phi tuyến
  • cực tiểu hóa các hàm
  • chéo hóa ma trận
  • biến đổi Fourier
  • giải các phương trình vi phân thường và vi phân riêng

Chẳng hạn, đoạn chương trình sau để tính các giá trị riêng:

#include <stdio.h>
#include <stdlib.h>
#include "nrutil.h"
#include "nr.h"

int main(int argc, char *argv[])
{
    float **m, *d, *e;        /* 1 ma tran, 2 vecto */
    long n = 10;            /* kich thuoc cua ma tran */
    int i, j;                        /* loop counter */
    
    m = matrix(1, n, 1, n);        /* cap phat bo nho cho ma tran */
    for(i=1; i<=n; i++)                /* khoi tao ma tran mot cach ngau nhien */
    for(j=i; j<=n; j++)
    {
        m[i][j] = drand48();
        m[j][i] = m[i][j];                /* o day, ma tran phai doi xung */
    }
    
    d = vector(1,n);                    /* cac phan tu tren duong cheo chinh  */
    e = vector(1,n);                    /* cac phan tu ngoai duong cheo chinh */
    tred2(m, n, d, e);                /* chuyen ma tran doi xung m. -> ba duong cheo */
    tqli(d, e, n, m);                    /* tinh cac gia tri rieng */
    
    for(j=1; j<=n; j++)                /* in nhung gia tri hien luu trong mang 'd' */
        printf("ev %d = %f\n", j, d[j]);
    
    free_vector(e, 1, n);                /* tra lai bo nho */
    free_vector(d, 1, n);
    free_matrix(m, 1, n, 1, n);
    return(0);
}

LEDA

Nếu như Numerical Recipes được dành riêng cho các bài toán số trị, thì Library of Efficient Data types and Algorithms (LEDA, Thư viện thuật toán và kiểu dữ liệu hiệu quả) [4] có thể trợ giúp nhiều trong việc lập trình nói chung. Thư viện được viết bằng C++, nhưng từ C cũng có thể gọi đến các thủ tục C++ được. LEDA có chứa nhiều kiểu dữ liệu cơ bản và nâng cao như:

  • chuỗi
  • số với độ chuẩn xác tùy ý
  • mảng 1 và 2 chiều
  • danh sách và những đối tượng tương tự khác như ngăn xếp và hàng đợi
  • tập hợp
  • cây
  • đồ thị (có hướng, không hướng, có gán nhãn)
  • từ điển, ở đó bạn có thể lưu những đối tượng với các từ khóa tùy ý đóng vai trò chỉ số
  • những kiểu dữ liệu trong hình học 2 và 3 chiều như các điểm, đoạn thẳng hay hình cầu.

Một chương trình có dùng LEDA cần được biên dịch bằng trình biên dịch C++. Tùy theo hệ thống máy tính của bạn, có thể dùng những cờ phù hợp, chẳng hạn:

g++ -I$LEDAROOT/incl -L$LEDAROOT -o leda_test leda_test.cc -lG -lL

Viết riêng thư viện của bạn

Tập hợp các chương trình con bạn thường hay dùng có thể đưa vào thư viện: khi đó bạn không cần phải nạp (include) file object mỗi khi biên dịch chương trình của mình. Nếu thư viện tự tạo của bạn được đặt trong một đường dẫn tìm kiếm chuẩn, thì bạn có thể truy cập nó như một thư viện hệ thống, và thậm chí không cần nhớ xem file đối tượng đó nằm ở đâu.

Để tạo một thư viện bạn cần phải có một file đối tượng như task.o và một file header task.h trong đó mọi kiểu dữ liệu và nguyên mẫu của hàm được định nghĩa. Ngoài ra, để dễ sử dụng thư viện, bạn nên viết một trang hướng dẫn (man page) trong hệ thống UNIX. Từ dấu nhắc hệ thống, bạn dùng câu lệnh ar:

ar r libmy.a tasks.o

Một thư viện có thể tập hợp vài file object. Tùy chọn “r” thay thế các file object đã cho, nếu chúng sẵn thuộc về thư viện; nếu không chúng sẽ được bổ sung thêm. Nếu thư viện chưa tồn tại thì sẽ được tạo ra.

Sau khi bao gồm file object, ta cần phải cập nhật bảng đối tượng nội trong thư viện. Điều này được thực hiện nhờ lệnh:

ar s libmy.a

Bây giờ bạn có thể biên dịch một chương trình prog.c có dùng thư viện mới lập, bằng lệnh:

cc -o prog prog.c libmy.a

 

6. Số ngẫu nhiên

Việc phát sinh số ngẫu nhiên được dùng nhiều kể cả khi hệ thống không mang tính ngẫu nhiên. Mục này sẽ giới thiệu các phương pháp khác nhau: phương pháp đảo, phương pháp Box-Muller và phương pháp bác bỏ. Chi tiết về các phương pháp này và phương pháp khác có ở [3, 16].

6.1 Phát sinh số ngẫu nhiên

Máy tính thực hiện tính toán theo cách đã định sẵn, bởi vậy yếu tố ngẫu nhiên phải từ bên ngoài (ít ra là từ người dùng). Ví dụ khoảng thời gian giữa những lần gõ phím kế tiếp. Song ngẫu nhiên hoàn toàn thì lại không thể tái hiện lại  được thí nghiệm. Bởi vậy người ta thường phát sinh số giả ngẫu nhiên. Việc phát sinh được thực hiện bằng nhữn quy tắc xác định, nhưng kết quả lại có dáng dấp giống những số ngẫu nhiên thực thụ.

Phần còn lại của mục này, bạn có thể xem lại Bài “Phát sinh các số giả ngẫu nhiên”.

7. Các công cụ kiểm thử

Những công cụ này hoạt động trong môi trường UNIX/Linux, gồm có: gdb (trình gỡ lỗi), ddd (giao diện đồ họa cho gdb), và checkergcc (tìm những lỗi gây ra do quản lý sai bộ nhớ).

7.1 gdb

gdb (GNU debugger) là trình gỡ lỗi. Khi dùng nó, bạn có thể theo dõi dòng thực thi mã lệnh. Bạn có thể dừng chương trình tại những điểm bất kì định trước bằng cách đặt các breakpoint tại các dòng hoặc các chương trình con. Với chương trình ngắn sau:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
  int t, *array, sum = 0;
  array = (int *) malloc (100*sizeof(int));
  for(t=0; t<100; t++)
    array[t] = t;
  for(t=0; t<100; t++)
    sum += array[t];
  printf("sum= %d\n", sum);
  free(array);
  return(0);
}

Khi biên dịch, nhớ chọn -g để có thể gỡ lỗi:

cc -o gdbtest -g gdbtest.c

Sau đó kích hoạt gỡ lỗi bằng lệnh:

gdb gdbtest

Một số lệnh để gõ vào dấu nhắc (gdb) có thể là

(gdb) 1

Liệt kê toàn văn file lệnh (từ dòng 1)

(gdb) b 11

Đặt breakpoint tại dòng 11

(gdb) r

Chạy chương trình

(gdb) p array 
(gdb) p array[99]

In ra mảng hoặc phần tử của mảng.

(gdb) set array 
(gdb) n

Đặt giá trị một phần tử của mảng. Sau đó chạy tiếp.

Mặt khác, có thể chạy chương trình theo từng bước

(gdb) step

và dò từng bước để tìm ra lỗi rồi thì bạn có thể tiếp tục chạy đến hết chương trình (hoặc đến breakpoint kế tiếp, nếu còn):

(gdb) continue

7.2 ddd

Đây là giao diện đồ họa của công cụ gỡ lỗi, xem hình.

ddd

7.3 checkergcc

Trong nhiều trường hợp chương trình đổ vỡ vì quản lý, truy cập bộ nhớ không hợp lệ. Thông báo lỗi có thể là Segmentation fault. Để phát hiện những lỗi đáng sợ này, ta có thể dùng một số công cụ [19]. Ở đây chúng tôi giới thiệu checkergcc, một công cụ tiện lợi và miễn phí. Nó chạy trong môi trường UNIX và biên dịch bằng checkergcc thay vì cc hay gcc. Thật không may là nó không hỗ trợ hoàn toàn cho C++, nhưng bạn cứ thử dùng xem. Trình biên dịch này sẽ thay thế tất cả việc cấp phát, giải phóng, truy cập bộ nhớ bằng những chương trình con riêng. Bất kì việc truy cập bộ nhớ trái phép nào cũng sẽ được báo cáo.

Với đoạn chương trình trên có thể biên dịch:

checkergcc -o gdbtest -g gdbtest.c

Sau đó kích hoạt gỡ lỗi:

gdbtest

8. Đánh giá dữ liệu

Dưới đây sẽ trình bày cách dùng gnuplot để xem và khớp dữ liệu trực tiếp trên máy, còn xmgr để tạo ra các hình vẽ trong các ẩn phẩm. fsscale là một chương trình tiện dụng để thu phóng kích thước hữu hạn (một phương pháp phân tích chuyên ngành vật lý tính toán).

8.1 Vẽ đồ thị

Chương trình gnuplot chạy trong môi trường UNIX cung cấp một cửa sổ dòng lệnh, ngoài ra còn thông dịch được các file văn lệnh (script). Chẳng hạn một file command.gp sẽ được thực hiện bằng câu lệnh:

gnuplot command.gp

Một ví dụ: ta vẽ đồ thị file sg_e0_L.dat. Cột đầu là các giá trị L, cột thứ hai là giá trị năng lượng và cột thứ ba sai số chuẩn của năng lượng. Lưu ý: các dòng bắt đầu bằng dấu # là dòng ghi chú.

# ground state energy of +-J spin glasses
# L    e_0  error
  3 -1.6710 0.0037
  4 -1.7341 0.0019
  5 -1.7603 0.0008
  6 -1.7726 0.0009
  8 -1.7809 0.0008
 10 -1.7823 0.0015
 12 -1.7852 0.0004
 14 -1.7866 0.0007

Để vẽ đồ thị số liệu này, gõ lệnh

gnuplot> plot "sg_e0_L.dat" with yerrorbars

Dòng lệnh này có thể viết gọn là

p "sg e0 L.dat" w e

với kết quả như hình dưới

foo

Để in ra file eps thì trước đó cần gõ vào lệnh

set terminal postscript
set output "test.eps"

Có thể chỉnh sửa tiêu đề trục, chẳng hạn như

set xlabel "L"

Chương trình xmgr (viết tắt của x motiv graphic) có tính năng mạnh hơn nhưng chạy chậm hơn gnuplot một chút. Và phải dùng chuột click các menu và menu con. Có thể vẽ nhiều loại biểu đồ với đừng nét và kí hiệu khác nhau, có thể viết kí hiệu lên bản vẽ.

xmgrxmgr_menu

8.2 Khớp đường cong

Cả hai chương trình gnuplot và xmgr nêu trên đều khớp được đường cong cho nhiều dạng hàm khác nhau. Nên dùng gnuplot vì nó linh động hơn, và cũng cung cấp thông tin kĩ hơn để đánh giá chất lượng khớp.

Giả sử cần khớp hàm f(L) = e_\infty + a L^b cho số liệu ở file sg_e0_L.dat nêu trên.  Trước hết, cần phải định nghĩa hàm và cung cấp một số ước lượng đại khái (khác không) của các tham số. Biến số của hàm thường đặt là x, song bạn có thể tự chọn:

gnuplot> f(x)=e+a*x**b
gnuplot> e=-1.8
gnuplot> a=1
gnuplot> b=-1

Việc khớp được thực hiện qua lệnh fit. Thuật toán được dùng là Marquardt-Levenberg [3], vốn cho ta

gnuplot> fit f(x) "sg_e0_L.dat" via e,a,b

Gnuplot sẽ in ra nhiều thông tin về kết quả khớp hàm này. Có kết quả về số bậc tự do, sai số (theo chỉ tiêu khi-bình phương).

Để xem kết quả khớp cùng với số liệu gốc, ta chỉ cần gõ lệnh:

gnuplot> plot "sg_e0_L.dat" w e, f(x)

fit

Lưu ý rằng độ hội tụ phép khớp đường cong này phụ thuộc vào giá trị ban đầu của các tham số. Thuật toán có thể sa vào cực tiểu địa phương nếu các tham số nằm quá xa giá trị tối ưu của chúng. Hãy thử đặt các giá trị ban đầu e=1, a=-3 và b=1 !

Ngoài ra, không cần thiết phải thay đổi tất cả các tham số trong phép khớp: tham số nào giữ nguyên thì bỏ ra ngoài lệnh fit.

Có thể đặt trọng số cho các tham số; hãy thử lệnh

fit f(x) "sg e0 L.dat" using 1:2:3 via a,b,c

8.3 Thu phóng kích thước hữu hạn

Trong vật lý thống kê, ứng xử của các hệ thống được biểu diễn bằng rất nhiều hạt (phần tử). Số lượng các hạt này quá nhiều, không dễ biểu diễn trên máy tính. Do đó, người ta đưa vào kĩ thuật “thu phóng kích thước hữu hạn” (finite-size scaling), xem [21]. Ý tưởng cơ bản là mô phỏng các hệ thống với các kích thước khác nhau rồi ngoại suy ra giá trị giới hạn ứng với hệ thống lớn.

Sau đây là phần thực hằng bằng gnuplot và fsscale. Xét độ từ hóa m của thủy tinh spin 3 chiều với tỉ lệ p phần liên kết phi-sắt từ và 1 – p phần sắt từ. Với p nhỏ thì đúng như dự kiến: hệ thống có trạng thái trật tự sắt từ, xem hình biểu diễn trường hợp L = 3, 5,14.

fig11

Giờ cần tìm giá trị tới hạn của p là p_c, khi m triệt tiêu. Theo phương trình:

m(p, L) = L^{-\beta/\nu} \tilde{m} (L^{1/\nu}(p - p_c))

với \tilde{m} là một hàm không đổi. Số mũ \beta\nu là các tham số. Ta sẽ vẽ đồ thị của L^{\beta/\nu} m(p,L) theo $L^{1/\nu}(p – p_c)$ với các tham số \beta, \nu. Dùng gnuplot có thể tìm ra p_c = 0.222, \nu = 1.1\beta = 0,27. Giả sử ta chọn các thông số này và vẽ

 gnuplot> b=0.27
 gnuplot> n=1.1
 gnuplot> pc=0.222
 gnuplot> plot [-1:1] "m_scale.dat" u (($2-pc)*$1**(1/n)):($3*$1**(b/n))

Ở đây $1, $2, $3 là số liệu trên các cột 1, 2, 3 của file. Kết quả biểu đồ thu được, và ta quan sát được

collapse

Công việc được thuận tiện hơn khi dùng fsscale [22], link ftp://ftp.thp.uni-duisburg.de/pub/fsscale/ .

fsscale

Trong file đầu vào fsscale có 3 cột: cột thứ nhất là kích thước hệ thống, cột 2 các giá trị của x, và cột 3 các giá trị của.

Nếu có nhiều cột quá, bạn có thể dùng awk trong UNIX để trích ra những cột cần thiết.

9. Truy tìm thông tin và xuất bản

9.1 Tìm tài liệu

Nhiều thông tin cần cho nghiên cứu lại không có trong sách giáo khoa thông thường. Sẽ rất tốt nếu bạn thạo dùng trình duyệt để truy cập Internet. Một số nguồn lưu trữ thông tin gồm có

  • Trong thư viện
  • Trong cơ sở dữ liệu toàn văn nghiên cứu
  • Trên hệ thống máy chủ lưu file bản thảo
  • Trong các tạp chí (tập san) khoa học
  • Trong cơ sở dữ liệu trích dẫn
  • Các trang đặc biệt (như Phys Net)
  • Google, v.v.

9.2 Chuẩn bị xuất bản

Với bản thảo viết, bạn nên dùng TeX/LaTeX với các ưu điểm:

  • Chất lượng bản thảo đẹp
  • Quản lý được văn bản đồ sộ
  • Dễ đánh công thức toán học
  • Nhiều gói phần mềm để mở rộng tính năng và kiểu dáng văn bản
  • Dùng trình soạn thảo văn bản đơn giản
  • Vẫn có trình soạn thảo công phu  với giao diện đồ họa như LyX [42].

Đoạn mã sau sẽ tạo ra văn bản thể loại “bài báo khoa học” với font cỡ 12 và hiển thị chữ nghiêng, chữ đậm, chữ nhỏ, logo LaTeX cùng  phương trình toán học:

\documentclass[12pt]{article}
\begin{document}
This is just a small sample text. You can write some words {\em
emphasized}\/, or in {\bf bold face}. Also different {\small sizes}
are possible.
An empty line generates a new paragraph. \LaTeX\ is very convenient
for writing formulae, e.g.
\begin{equation}
M_i(t) = \frac{1}{L^3} \int_V x_i \rho(\vec{x},t) d^3\vec{x}
\end{equation}
\end{document}

Xem các hướng dẫn thêm về LaTeX [40,41].

Trong môi trường UNIX/Linux, trình kiểm tra chính tả tiếng Anh là ispell có thể dùng để soát văn bản LaTeX.

Nhiều văn bản báo cáo khoa học trình bày các sơ đồ hình vẽ. Một công cụ đơn giản, tiện dụng để tạo sơ đồ là xfig. Chương trình này cho phép tạo bản vẽ vec tơ (đường thẳng, mũi tên, đường cong, đa giác, cung tròn, chữ nhật, … và có thể thêm chữ viết, file hình ảnh (eps, jpg)). Các đối tượng hình có thể được đặt trên các lớp khác nhau. Có thể thao tác lên các đối tượng (dịch chuyển, xoay hình, phóng to – thu nhỏ, ghép hình, v.v.)  Dưới đây là minh họa sử dụng xfig để vẽ một sơ đồ tính toán.

xfig

Để tạo ra các sơ đồ mô hình 3 chiều, có thể dùng công cụ PovRay (Persistence of Vision RAYtracer) [43]. PovRay là một chương trình raytracer (chương trình tạo nên hình ảnh bằng cách phát một số tia sáng từ nguồn và theo dõi quá trình truyền của nó (hấp thụ, phản xạ, khúc xạ khi truyền) đến khi tia sáng này lọt vào camera hay bị tắt hết. Quá trình tính truyền này có thể rất lâu tùy theo độ phức tạp của khung cảnh. Kết quả sẽ là một file ảnh giống như được chụp thật.

Một khung cảnh có thể được khai báo bởi file văn bản. Chẳng hạn, file khung cảnh sau có 3 khối cầu được nối bởi hai khối trụ, và một mặt phẳng ngang cùng màu sắc của vật thể được chỉ định.

#include "colors.inc"
background { color White }
sphere { <10, 2, 0>, 2
  pigment { Blue } }
cylinder { <10, 2, 0>, <0, 2, 10>, 0.7
  pigment { color Red } }
sphere { <0, 2, 10>, 4
  pigment { Green transmit 0.4} }
cylinder { <0, 2, 10>, <-10, 2, 0>, 0.7
  pigment { Red } }
sphere { <-10, 2, 0>, 2
  pigment { Blue } }
plane { <0, 1, 0>, -5
  pigment { checker color White, color Black}}
light_source { <10, 30, -3> color White}
camera {location <0, 8, -20>
  look_at <0, 2, 10>
  aperture 0.4}

povray

Tài liệu tham khảo

[1] I. Sommerville, Software Engineering , (Addisin-Wesley, Reading (MA) 1989)
[2] C. Ghezzi, M. Jazayeri, and D. Mandrioli, Fundamentals of Software Engineering , (Prentice Hall, London 1991)
[3] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C (Cambridge University Press, Cambridge 1995)
[4] K. Mehlhorn and St. Naher, The LEDA Platform of Combinatorial and Geometric Computing (Cambridge University Press, Cambridge 1999); xem thêm http://www.mpi-sb.mpg.de/LEDA/leda.html
[5] M. Loukides and A. Oram, Programming with GNU Software , (O’€™Reilly, London 1996); xem thêm http://www.gnu.org/manual
[6] H.R. Lewis and C.H. Papadimitriou, Elements of the Theory of Computation, (Prentice Hall, London 1981)
[7] J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen, Object-Oriented Modeling and Design, (Prentice Hall, London 1991)
[8] R. Johnsonbaugh and M. Kalin, Object Oriented Programming in C++, (Macmillan, London 1994)
[9] J. Skansholm, C++ from the Beginning , (Addisin-Wesley, Reading (MA) 1997)
[10] Gửi Mail đến hartmann@theorie.physik.uni-goettingen.de
[11] B.W. Kernighan and D.M. Ritchie, The C Programming Language, (Prentice Hall, London 1988)
[12] A. Oram and S. Talbott, Managing Projects With Make, (O’€™Reilly, London 1991)
[13] Các chương trình và hướng dẫn sử dụng có thể tìm thấy ở http://www.gnu.org. Một số có cả file texinfo. Để đọc file này, khởi động trình biên tập “€™emacs€” rồi gõ <crtl>+h€ tiếp theo là i€™ để vào chế độ texinfo.
[14] J. Phillips, The Nag Library: A Beginner’s Guide (Oxford University Press, Oxford 1987); xem thêm http://www.nag.com
[15] A. Heck, Introduction to Maple , (Springer-Verlag, New York 1996)
[16] B.J.T. Morgan, Elements of Simulation, (Cambridge University Press, Cambridge 1984)
[17] A.M. Ferrenberg, D.P. Landau and Y.J. Wong, Phys. Rev. Lett. 69, 3382 (1992); I. Vattulainen, T. Ala-Nissila and K. Kankaala, Phys. Rev. Lett. 73, 2513 (1994)
[18] J.F. Fernandez and C. Criado, Phys. Rev. E 60, 3361 (1999)
[19] http://www.cs.colorado.edu/homes/zorn/public html/MallocDebug.html
[20] Giấy phép công cộng gnu có thể lấy về từ http://www.gnu.org/software/checker/checker.html
[21] J. Cardy, Scaling and Renormalization in Statistical Physics, (Cambridge University Press, Cambridge 1996)
[22] Chương trình fsscale được viết bởi A. Hucht, có thể liên lạc tác giả thông qua email: fred@thp.Uni-Duisburg.DE
[23] A.K. Hartmann, Phys. Rev. B 59 , 3617 (1999)
[24] K. Binder and D.W. Heermann, Monte Carlo Simulations in Statistical Physics , (Springer, Heidelberg 1988)
[25] http://www.inspec.org/publish/inspec/
[26] http://xxx.lanl.gov/
[27] http://www.aip.org/o js/service.html
[28] http://publish.aps.org/
[29] http://www.elsevier.nl
[30] http://www.eps.org/publications.html
[31] http://www.iop.org/Journals/
[32] http://www.springer.de/
[33] http://www.wiley-vch.de/journals/index.html
[34] http://ejournals.wspc.com.sg/journals.html
[35] http://wos.isiglobalnet.com/
[36] http://physnet.uni-oldenburg.de/PhysNet/physnet.html
[37] http://www.yahoo.com/
[38] http://www.altavista.com/
[39] http://www.metacrawler.com/index.html
[40] L. Lamport and D. Bibby, LaTeX : A Documentation Preparation System User’s Guide and Reference Manual, (Addison Wesley, Reading (MA) 1994)

 

Advertisements

Bạn nghĩ gì về bài viết này?

Filed under Tin học

Phụ lục A: Đồ họa

Trở về Mục lục cuốn sách

A.1  Đồ họa Java 2 chiều

Phụ lục này đưa ra các ví dụ và bài tập minh họa cho tính năng đồ họa trong Java. Có một số cách tạo nên đồ họa trong Java; cách đơn giản nhất là dùng java.awt.Graphics. Sau đây là một ví dụ hoàn chỉnh: Tiếp tục đọc

6 phản hồi

Filed under Think Java

Chương 16: GridWorld, phần 3

Trở về Mục lục cuốn sách

Nếu bạn chưa làm bài tập trong các Chương 5 và 10, bạn hãy nên làm đi trước khi đọc chương này. Xin được nhắc lại, bạn có thể tìm tài liệu về các lớp GridWorld ở http://www.greenteapress.com/thinkapjava/javadoc/gridworld/.

Phần 3 của cuốn Hướng dẫn sinh viên về GridWorld trình bày những lớp cấu thành GridWorld và các mối tương tác giữa chúng. Đây là một ví dụ về thiết kế hương đối tượng và làm một cơ hổi để ta bàn luận những vấn đề thiết kế hướng đối tượng.

Nhưng trước khi bạn đọc cuốn Hướng dẫn sinh viên, sau đây có thêm một số điều mà bạn cần biết. Tiếp tục đọc

%(count) bình luận

Filed under Think Java

Chương 15: Lập trình hướng đối tượng

Trở về Mục lục cuốn sách

15.1  Các ngôn ngữ và phong cách lập trình

Có nhiều ngôn ngữ lập trình khác nhau, và không kém mấy về số lượng là các phong cách lập trình (còn gọi là mẫu hình). Những chương trình mà ta đã viết đến giờ đều thuộc phong cách thủ tục, bởi chú ý được dồn vào việc quy định các thủ tục tính toán. Tiếp tục đọc

%(count) bình luận

Filed under Think Java

Chương 14: Đối tượng chứa các mảng

Trở về Mục lục cuốn sách

CẢNH BÁO: Trong chương này, ta tiến thêm một bước nữa về lập hướng đối tượng nhưng vẫn chưa hẳn đến được đó. Bởi vậy, nhiều ví dụ vẫn chưa đúng giọng Java, nghĩa là chưa phải mã lệnh Java chuẩn. Hình thức trung chuyển này (hi vọng rằng) sẽ giúp bạn học, nhưng thực tế tôi không viết mã lệnh như thế này.

Bạn có thể tải về mã lệnh cho chương này từ: http://thinkapjava.com/code/Card2.java.

14.1  Lớp Deck

Ở chương trước, ta đã làm việc với một mảng các đối tượng, nhưng cũng đề cập rằng hoàn toàn có thể có đối tượng có chứa biến thực thể là mảng. Trong chương này, ta tạo ra một đối tượng Deck có chứa một mảng những đối tượng Card. Tiếp tục đọc

7 phản hồi

Filed under Think Java

Chương 11: Tự tạo nên những đối tượng riêng

Trở về Mục lục cuốn sách

11.1  Lời định nghĩa lớp và các kiểu đối tượng

Trở về tận Mục 1.5 khi chúng ta định nghĩa lớp Hello, ta đồng thời tạo nên một kiểu đối tượng có tên Hello. Ta không tạo nên biến nào thuộc kiểu Hello này, và cũng không dùng new để tạo ra đối tượng Hello nào, song việc đó là hoàn toàn có thể!

Ví dụ đó chẳng có mấy tác dụng minh họa, bởi không lý gì để ta tạo ra một đối tượng Hello như vậy, và dù có tạo nên thì cũng chảng để làm gì. Trong chương này, ta sẽ xét đến những định nghĩa lớp để tạo nên các kiểu đối tượng có ích.

Sau đây là những ý tưởng quan trọng nhất trong chương:

  • Việc định nghĩa một lớp mới đồng thời cũng tạo nên một đối tượng mới cùng tên.
  • Lời định nghĩa lớp cũng giống như một bản mẫu cho các đối tượng: nó quy định những biến thực thể nào mà đối tượng đó chứa đựng, và những phương thức nào có thể hoạt động với chúng.
  • Mỗi đối tượng thuộc về một kiểu đối tượng nào đó; như vậy, nó là một thực thể của một lớp nào đó.
  • Khi bạn kích hoạt new để tạo nên một đối tượng, Java kích hoạt một phương thức đặc biệt có tên là constructor để khởi tạo các biến thực thể. Bạn cần cung cấp một hoặc nhiều constructor trong lời định nghĩa lớp.
  • Các phương thức thao tác trên một kiểu được định nghĩa trong lời định nghĩa lớp cho kiểu đó.

Sau đây là một số vấn đề về lời định nghĩa lớp:

  • Tên lớp (và do đó, tên của kiểu đối tượng) nên bắt đầu bàng một chữ in, để phân biệt chúng với các kiểu nguyên thủy và những tên biến.
  • Bạn thường đặt một lời định nghĩa lớp vào trong mỗi file, và tên của file phải giống như tên của lớp, với phần mở rộng .java. Chẳng hạn, lớp Time được định nghĩa trong file có tên Time.java.
  • Ở bất kì chương trình nào, luôn có một lớp được giao làm lớp khởi động. Lớp khởi động phải chứa một phương thức mang tên main, đó là nơi mà việc thực thi chương trình bắt đầu. Các lớp khác cũng có thể chứa phương thức cùng tên main, song phương thức đó sẽ không được thực thi từ đầu.

Khi đã nêu những vấn đề này rồi, ta hãy xét một ví dụ về lớp do người dùng định nghĩa, lớp Time.

11.2  Time

Một động lực chung cho việc tạo nên kiểu đối tượng, đó là để gói gọn những dữ liệu liên quan vào trong một đối tượng để ta có thể coi như một đơn vị duy nhất. Ta đã gặp hai kiểu như vậy, đó là Point và Rectangle.

Một ví dụ khác, mà ta sẽ tự tay lập nên, là Time, để biểu diễn giờ đồng hồ. Dữ liệu được gói trong một đối tượng Time bao gồm có số giờ, số phút, và số giây. Bởi mỗi đối tượng Time đều chứa những dữ liệu này, nên ta cần biến thực thể để lưu giữ chúng.

Bước đầu tiên là xác định xem từng biến phải thuộc kiểu gì. Dường như rõ ràng là hour (giờ) và minute (phút) đều phải là những số nguyên. Để cho vấn đề được thú vị hơn, ta hãy đặt second (giây) là một double.

Các biến thực thể được định nghĩa ở đoạn đầu của lời khai báo lớp, bên ngoài bất kì lời khai báo phương thức nào khác, như sau:

class Time { 
  int hour, minute; 
  double second; 
}

Đoạn mã này tự bản thân nó đã là lời khai báo lớp hợp lệ. Sơ đồ trạng thái cho một đối tượng Time sẽ trông như sau:

Sau khi khai báo các biến thực thể, bước tiếp theo là định nghĩa một constructor cho lớp mới này.

11.3  Constructor

Các constructor có nhiệmvụ khởi tạo các biến thực thể. Cú pháp của constructor cũng giống như của các phương thức khác, trừ ba điểm sau:

  • Tên của constructor phải giống như tên lớp.
  • Constructor không có kiểu trả về và cũng không có giá trị trả về.
  • Từ khoá static được bỏ qua.

Sau đây là một ví dụ cho lớp Time:

public Time() { 
  this.hour = 0; 
  this.minute = 0; 
  this.second = 0.0; 
}

Ở chỗ mà bạn trông đợi một kiểu trả về, giữa public and Time, lại không có gì cả. Điều đó cho thấy cách mà chúng ta (và trình biên dịch nữa) có thể phân biệt được rằng đây là một constructor.

Constructor này không nhận tham số nào. Mỗi dòng của constructor khởi tạo một biến thực thể cho một giá trị mặc định (trong trường hợp này là nửa đêm). Cái tên this là một từ khóa đặc biệt để tham chiếu tới đối tượng mà ta đang tạo nên. Bạn có thể dùng this theo cách giống như dùng tên của bất kì đối tượng nào khác. Chẳng hạn, bạn có thể đọc và ghi các biến thực thể của this, và cũng truyền được this với vai trò tham số đến những phương thức khác.

Nhưng bạn không khai báo cái this này và cũng không thể gán giá trị cho nó. this được tạo bởi hệ thống; tất cả những gì bạn phải làm đó là khởi tạo các biến thực thể của nó.

Một lỗi thường gặp khi viết ra constructor là việc đưa câu lệnh return vào cuối. Hãy kiềm chế, tránh làm việc này.

11.4  Thêm các constructor

Constructor có thể được chồng chất [xem thêm phần “Quá tải”], cũng như các phương thức khác, theo nghĩa bạn có thể có nhiều constructor với các tham số khác nhau. Java biết rõ cần phải kích hoạt constructor nào bằng cách khớp những tham số của new với các tham số của constructor.

Việc có constructor không nhận đối số (như trên) là hoàn toàn bình thường, cũng như constructor nhận một danh sách tham số giống hệt với danh sách các biến thực thể. Chẳng hạn:

public Time(int hour, int minute, double second) { 
  this.hour = hour; 
  this.minute = minute; 
  this.second = second; 
}

Các tên và kiểu của những tham số cũng giống với tên và kiểu của các biến thực thể. Tất cả những gì mà constructor này làm chỉ là sao chép thông tin từ các tham số sang các biến thực thể.

Nếu xem tài liệu về Point và Rectangle, bạn sẽ thấy rằng cả hai lớp này đều có những constructor kiểu như trên. Việc chồng chất constructor cho phép linh hoạt tạo nên đối tượng trước rồi sau đó mới điền vào phần trống, hoặc để thu thập toàn bộ thông tin trước khi lập ra đối tượng.

Điều này nghe thì có vẻ không đáng quan tâm, song thực ra thì khác. Việc viết những constructor là quá trình máy móc, buồn tẻ. Một khi bạn đã viết được hai constructor rồi, bạn sẽ thấy rằng mình có thể viết chúng nhanh chóng chỉ qua việc trông vào danh sách các biến thực thể.

11.5  Tạo nên đối tượng mới

Mặc dù trông giống như phương thức, song constructor không bao giờ được kích hoạt trực tiếp. Thay vì vậy, khi bạn kích hoạt new, hệ thống sẽ huy động dung lượng bộ nhớ cho đối tượng mới và kích hoạt constructor này.

Chương trình sau giới thiệu hai cách làm để lập thành và khởi tạo các đối tượng Time:

class Time { 
  int hour, minute; 
  double second; 
  public Time() { 
    this.hour = 0; 
    this.minute = 0; 
    this.second = 0.0; 
  } 
  public Time(int hour, int minute, double second) { 
    this.hour = hour; 
    this.minute = minute; 
    this.second = second; 
  } 
  public static void main(String[] args) { 
    // một cách lập thành và khởi tạo đối tượng Time 
    Time t1 = new Time(); 
    t1.hour = 11; 
    t1.minute = 8; 
    t1.second = 3.14159; 
    System.out.println(t1); 
    // một cách khác để thực hiện việc tương tự 
    Time t2 = new Time(11, 8, 3.14159); 
    System.out.println(t2); 
  } 
}

Trong main, lần đầu tiên kích hoạt new, ta không cấp cho đối số nào, bởi vậy Java kích hoạt constructor thứ nhất. Vài dòng phía dưới thực hiện gán giá trị cho các biến thực thể.

Lần thứ hai kích hoạt new, ta cấp các đối số khớp với các tham số của constructor thứ hai. Cách khởi tạo biến thực thể này gọn gàng hơn và hiệu quả hơn một chút, song cách làm này có thể khó đọc, bởi nó không rõ ràng là giá trị nào được gán cho biến thực thể nào.

11.6  In các đối tượng

Kết quả của chương trình nêu trên là:

Time@80cc7c0
Time@80cc807

Khi Java in giá trị của kiểu đối tượng do người dùng định nghĩa, nó sẽ in tên kiểu cùng một mã thập lục phân đặc biệt riêng của từng đối tượng. Mã này bản thân nó chẳng có ý nghĩa gì; thực tế nó khác nhau tuỳ máy tính và thậm chí tuỳ cả những lần chạy chương trình. Nhưng có thể nó giúp ích cho việc gỡ lỗi, trong trường hợp bạn muốn theo dõi từng đối tượng riêng rẽ.

Để in các đối tượng theo cách có ý nghĩa hơn đối với người dùng (chứ không phải đối với lập trình viên), bạn có thể viết một phương thức với tên gọi kiểu như printTime:

public static void printTime(Time t) { 
  System.out.println(t.hour + ":" + t.minute + ":" + t.second); 
}

Hãy so sánh phương thức này với phiên bản printTime ở Mục 3.10.

Kết quả của phương thức này, nếu ta truyền t1 hoặc t2 làm đối số, sẽ là 11:8:3.14159. Mặc dù ta có thể nhận ra đây là giờ đồng hồ, nhưng cách viết này không hề theo chuẩn quy định. Chẳng hạn, nếu số phút hoặc số giây nhỏ hơn 10, ta sẽ luôn dự kiển rằng có số 0 đi trước. Ngoài ra, có thể ta còn muốn bỏ phần thập phân của số giây đi. Nói cách khác, ta muốn kết quả kiểu như 11:08:03.

Trong đa số những ngôn ngữ lập trình, có nhiều cách đơn giản để điều khiển định dạng đầu ra cho kết quả số. Trong Java thì không có cách đơn giản nào.

Java có những công cụ mạnh dành cho việc in dữ liệu được định dạng như giờ đồng hồ và ngày tháng, đồng thời cũng có công cụ để diễn giải dữ liệu vào được định dạng. Song thật không may là những công cụ như vậy không dễ sử dụng, nên tôi sẽ bỏ qua chúng trong khuôn khổ cuốn sách này. Nếu muốn, bạn có thể xem qua tài liệu của lớp Date trong gói java.util.

11.7  Các thao tác với đối tượng

Trong một vài mục tiếp theo, tôi sẽ giới thiệu ba dạng phương thức hoạt động trên các đối tượng:

hàm thuần tuý:
Nhận các đối tượng làm tham số nhưng không thay đổi chúng. Giá trị trả lại thuộc kiểu nguyên thuỷ hoặc một đối tượng mới tạo ra bên trong phương thức này.
phương thức sửa đổi:
Nhận đối số là các đối tượng rồi sửa đổi một vài, hoặc tất cả những đối tượng đó. Thường trả lại đối tượng rỗng (void).
phương thức điền:
Một trong các đối số là đối tượng “trống trơn” sẽ được phương thức điền thông tin vào. Về mặt kĩ thuật, đây cũng chính là một dang phương thức sửa đổi.

Với một phương thức cho trước ta thường có thể viết nó dưới dạng hàm thuần túy, phương thức sửa đổi hay phương thức điền. Tôi sẽ bàn thêm về ưu nhược điểm của từng hình thức một.

11.8  Các hàm thuần túy

Một phương thức được coi là hàm thuần túy nếu như kết quả chỉ phụ thuộc vào các đối số, và phương thức này không có hiệu ứng phụ như thay đổi một đối số hoặc in ra thông tin gì. kết quả duy nhất của việc kích hoạt một hàm thuần túy, đó là giá trị trả lại.

Một ví dụ là isAfter, để so sánh hai đối tượng Time rồi trả lại một boolean để chỉ định xem liệu toán hạng thứ nhất có xếp trước toán hạng thứ hai hay không:

  public static boolean isAfter(Time time1, Time time2) { 
    if (time1.hour > time2.hour) 
      return true; 
    if (time1.hour < time2.hour) 
      return false; 
    if (time1.minute > time2.minute) 
      return true; 
    if (time1.minute < time2.minute) 
      return false; 
    if (time1.second > time2.second) 
      return true; 
    return false; 
  }

Kết quả của phương thức này sẽ là gì nếu hai thời gian đã cho bằng nhau? Liệu đó có phải là kết quả phù hợp đối với phương thức này không? Nếu bạn viết tài liệu cho phương thức này, liệu bạn có đề cập rõ đến trường hợp đó không?

Ví dụ thứ hai là addTime, phương thức tính tổng hai thời gian. Chẳng hạn, nếu bây giờ là 9:14:30, và người làm bánh cần 3 giờ 35 phút, thì bạn có thể dùng addTime để hình dung ra khi nào bánh ra lò.

Sau đây là bản sơ thảo của phương thức này; nó chưa thật đúng:

  public static Time addTime(Time t1, Time t2) { 
    Time sum = new Time(); 
    sum.hour = t1.hour + t2.hour; 
    sum.minute = t1.minute + t2.minute; 
    sum.second = t1.second + t2.second; 
    return sum; 
  }

Mặc dù phương thức này trả lại một đối tượng Time, song nó không phải là constructor. Bạn cần xem lại và so sánh cú pháp của một phương thức dạng này với cú pháp của một constructor, vì chúng dễ gây nhầm lẫn.

Sau đây là một ví dụ về cách dùng phương thức. Nếu như currentTime chứa thời gian hiện tại và breadTime chứa thời gian cần để người thợ nướng bánh, thì bạn có thể dùng addTime để hình dung ra khi nào sẽ nướng xong bánh.

    Time currentTime = new Time(9, 14, 30.0); 
    Time breadTime = new Time(3, 35, 0.0); 
    Time doneTime = addTime(currentTime, breadTime); 
    printTime(doneTime);

Kết quả của chương trình, 12:49:30.0, là đúng. Mặt khác, cũng có những trường hợp mà kết quả không đúng. Bạn có đoán được một trường hợp như vậy không?

Vấn đề là ở chỗ phương thức này không xử lý được tình huống khi số giây hoặc số phút cộng lại vượt quá 60. Trong trường hợp đó, ta phải “nhớ” số giây còn dư vào cột số phút, hoặc nhớ số phút dư vào cột giờ.

Sau đây là một dạng đúng của phương thức này.

  public static Time addTime(Time t1, Time t2) { 
    Time sum = new Time(); 
    sum.hour = t1.hour + t2.hour; 
    sum.minute = t1.minute + t2.minute; 
    sum.second = t1.second + t2.second; 
    if (sum.second >= 60.0) { 
      sum.second -= 60.0; 
      sum.minute += 1; 
    } 
    if (sum.minute >= 60) { 
      sum.minute -= 60; 
      sum.hour += 1; 
    } 
    return sum; 
  }

Mặc dù cách này đúng, song chương trình bắt đầu dài dòng. Sau này tôi sẽ gợi ý một giải pháp khác ngắn hơn nhiều.

Đoạn mã lệnh trên giới thiệu hai toán tử mà ta chưa từng gặp, += và -=. Những toán tử này cho ta viết ngắn gọn lệnh tăng hoặc giảm biến. Chúng cũng gần giống như ++ và --, chỉ khác ở chỗ (1) chúng làm việc được cả với double lẫn int, và (2) lượng tăng hoặc giảm không nhất thiết bằng 1. Câu lệnh sum.second -= 60.0; tương đương với sum.second = sum.second - 60;

11.9  Phương thức sửa đổi

Xét một ví dụ về phương thức sửa đổi, phương thức increment, nhằm tăng thêm một số giây cho trước vào một đối tượng Time. Một lần nữa, ta có bản nháp phương thức này như sau:

  public static void increment(Time time, double secs) { 
    time.second += secs; 
    if (time.second >= 60.0) { 
      time.second -= 60.0; 
      time.minute += 1; 
    } 
    if (time.minute >= 60) { 
      time.minute -= 60; 
      time.hour += 1; 
    } 
  }

Dòng đầu tiên thực hiện thao tác cơ bản; những dòng còn lại để xử lý các trường hợp ta đã xét.

Liệu phương thức này có đúng không? Điều gì sẽ xảy ra nếu đối số secs lớn hơn nhiều so với 60? Trong trường hợp như vậy, trừ đi 60 một lần là chưa đủ; ta phải tiếp tục trừ đến khi second nhỏ hơn 60. Ta có thể làm điều này bằng cách thay các lệnh if bằng các lệnh while:

  public static void increment(Time time, double secs) { 
    time.second += secs; 
    while (time.second >= 60.0) { 
      time.second -= 60.0; 
      time.minute += 1; 
    } 
    while (time.minute >= 60) { 
      time.minute -= 60; 
      time.hour += 1; 
    } 
  }

Giải pháp này đúng đắn, nhưng chưa hiệu quả lắm. Bạn có thể nghĩ ra lời giải nào không cần đến tính lặp hay không?

11.10  Các phương thức điền

Thay vì việc tạo nên đối tượng mới mỗi khi addTime được kích hoạt, ta có thể yêu cầu chương trình gọi hãy cung cấp một đối tượng nơi mà addTime lưu kết quả. Hãy so sánh đoạn mã sau với phiên bản trước:

  public static void addTimeFill(Time t1, Time t2, Time sum) { 
    sum.hour = t1.hour + t2.hour; 
    sum.minute = t1.minute + t2.minute; 
    sum.second = t1.second + t2.second; 
    if (sum.second >= 60.0) { 
      sum.second -= 60.0; 
      sum.minute += 1; 
    } 
    if (sum.minute >= 60) { 
      sum.minute -= 60; 
      sum.hour += 1; 
    } 
  }

Kết quả được lưu trong sum, nên kiểu trả về là void.

Các phương thức sửa đổi và phương thức điền đều hiệu quả vì chúng không phải tạo nên đối tượng mới. Nhưng chúng lại gây khó khăn trong việc cô lập các phần khác nhau của chương trình; trong những dự án lớn chúng có thể gây nên lỗi rất khó tìm ra.

Các hàm thuần túy giúp ta quản lý tính chất phức tạp của những dự án lớn, phần là nhờ ngăn không cho những loại lỗi nhất định không thể xảy ra. Hơn nữa, hàm thuần túy còn thích hợp với những kiểu lập trình ghép và lồng. Và vì kết quả của hàm thuần túy chỉ phụ thuộc vào tham số, ta có thể tăng tốc cho nó bằng cách lưu giữ những giá trị đã tính toán từ trước.

Tôi gợi ý rằng bạn nên viết hàm thuần túy mỗi lúc thấy được, và chỉ dùng đến phương thức sửa đổi khi thấy rõ ưu điểm vượt trội.

11.11  Lập kế hoạch và phát triển tăng dần

Trong chương trình này tôi giới thiệu một quá trình phát triển chương trình với tên gọi lập nguyên mẫu nhanh1. Với từng phương thức, tôi viết một bản sơ thảo để thực hiện tính toán cơ bản, rồi kiểm tra nó với một vài trường hợp, sửa những lỗi bắt gặp được.

Cách tiếp cận này có thể hiệu quả, song nó có thể dẫn đến mã lệnh phức tạp một cách không cần thiết—vì nó xử lý quá nhiều trường hợp đặc biệt—và cũng kém tin cậy—vì thật khó tự thuyết phục rằng bạn đã tìm thấy tất cả những lỗi trong chương trình.

Một cách khác là xem xét kĩ hơn vấn đề nhằm tìm mấu chốt có thể giúp việc lập trình dễ dàng hơn. Trong trường hợp này điểm mấu chốt bên trong là: Time thực ra là một số có ba chữ số trong hệ cơ số 60! Số giây, second, là hàng đơn vị, số phút, minute, là hàng 60, còn số giờ, hour, là hàng 3600.

Khi ta viết addTime và increment, thực chất là ta đang tính cộng ở hệ 60; đó là lý do tại sao ta phải “nhớ” từ hàng này sang hàng khác.

Một cách tiếp cận khác đối với tổng thể bài toán là chuyển Time thành double rồi lợi dụng khả năng tính toán của máy đối với double. Sau đây là một phương thức chuyển đổi Time thành double:

  public static double convertToSeconds(Time t) { 
    int minutes = t.hour * 60 + t.minute; 
    double seconds = minutes * 60 + t.second; 
    return seconds; 
  }

Bây giờ tất cả những gì ta cần là cách chuyển từ double sang đối tượng Time. Ta có thể viết một phương thức để thực hiện điều này, song có lẽ hợp lý hơn la viết một constructor thứ ba:

  public Time(double secs) { 
    this.hour =(int)(secs / 3600.0); 
    secs -= this.hour * 3600.0; 
    this.minute =(int)(secs / 60.0); 
    secs -= this.minute * 60; 
    this.second = secs; 
  }

Constructor này hơi khác những constructor khác; nó bao gồm những tính toán bên cạnh phép gán cho các biến thực thể.

Có thể bạn phải suy nghĩ để tự thuyết phục bản thân rằng kĩ thuật mà tôi dùng để chuyển từ hệ cơ số này sang cơ số kia là đúng. Nhưng một khi bạn đã bị thuyết phục rồi, ta có thể dùng những phương thức này để viết lại addTime:

  public static Time addTime(Time t1, Time t2) { 
    double seconds = convertToSeconds(t1) + convertToSeconds(t2); 
    return new Time(seconds); 
  }

Mã lệnh trên ngắn hơn phiên bản gốc, và dễ thấy hơn hẳn rằng mã lệnh này đúng đắn (với giả thiết thường lệ rằng những phương thức nó kích hoạt cũng đều đúng). Việc viết lại increment theo cách tương tự được dành cho bạn như một bài tập.

11.12  Khái quát hóa

Trong chừng mực nào đó, việc chuyển đổi qua lại giữa các hệ cơ số 60 và 10 khó hơn việc xử lý thời gian đơn thuần. Việc chuyển hệ cơ số thì trừu tượng hơn, còn trực giác của ta xử lý thời gian tốt hơn.

Nhưng nếu ta có hiểu biết sâu để coi thời gian như các số trong hệ 60, và đầu tư công sức viết những phương thức chuyển đổi (convertToSeconds và constructor thứ ba), ta sẽ thu được một chương trình ngắn hơn, dễ đọc và gỡ lỗi, đồng thời đáng tin cậy hơn.

Việc bổ sung các đặc tính sau này cũng dễ dàng hơn. Hãy tưởng tượng ta cần trừ hai đối tượng Time để tìm ra khoảng thời gian giữa chúng. Cách làmthực hiện tính trừ có nhớ. Nhưng dùng phương thức để chuyển đổi sẽ dễ hơn nhiều.

Điều trớ trêu là, đôi khi việc làm cho bài toán khó hơn (tổng quát hơn) lại khiến cho dễ dàng hơn (ít trường hợp đặc biệt, ít khả năng gây ra lỗi).

11.13  Thuật toán

Khi bạn viết một lời giải tổng quát cho một lớp các bài toán, thay vì tìm lời giải riêng cho một bài toán riêng lẻ, bạn đã viết một thuật toán. Thật không dễ định nghĩa thuật ngữ này, bởi vậy tôi sẽ cố gắng thử vài cái tiếp cận khác nhau.

Trước hết, hãy xét một số thứ không phải là thuật toán. Khi bạn học tính nhân giữa hai số, có lẽ bạn đã ghi nhớ bản cửu chương. Thật ra, bạn đã học thuộc lòng 100 lời giải cụ thể, bởi vậy kiến thức này thực sự không phải là thuật toán.

Nhưng nếu bạn “lười biếng,” có thể bạn đã học hỏi được mấy mẹo vặt. Chẳng hạn, để tính tính của một số n với 9, bạn có thể viết n−1 là chữ số thứ nhất và 10−n là chữ số thứ hai. Mẹo này là lời giải tổng quát để nhân một số dưới mười bất kì với 9. Đó chính là thuật toán!

Tương tự, những kĩ thuật bạn học để cộng có nhớ, trừ có nhớ, và phép chia số lớn đều là những thuật toán. Một trong những đặc điểm của thuật toán là chúng không cần trí thông minh để thực hiện. Chúng chỉ là những cơ chế máy móc trong đó từng bước nối tiếp nhau theo một loạt những nguyên tắc đơn giản.

Theo ý kiến của tôi, thật đáng ngại khi thấy rằng chúng ta dành quá nhiều thời gian trên lớp để học cách thực hiện những thuật toán mà, nói thẳng ra là, không cần trí thông minh gì cả. Mặt khác, quá trình thiết kế những thuật toán lại thú vị, đầy thử thách trí tuệ, và là phần trung tâm của việc mà ta gọi là lập trình.

Có những việc mà con người làm theo lẽ tự nhiên, chẳng khó khăn hay phải suy nghĩ gì, lại là những thứ khó biểu diễn bằng thuật toán nhất. Việc hiểu ngôn ngữ là một ví dụ điển hình. Chúng ta ai cũng làm vậy, nhưng đến nay chưa ai giải thích được rằng ta làm vậy bằng cách nào, ít nhất là biểu diễn dưới dạng thuật toán.

Bạn sẽ sớm có cơ hội thiết kế những thuật toán đơn giản cho nhiều bài toán khác nhau.

11.14  Thuật ngữ

lớp:
Trước đây, tôi đã định nghĩa lớp là một tập hợp các phương thức có liên quan. Trong chương này ta còn được biết rằng lời định nghĩa lớp cũng đồng thời là một bản mẫu của một kiểu đối tượng mới.
thực thể:
Thành viên của một lớp. Mỗi đối tượng đều là thực thể của một lớp nào đó.
constructor:
Một phương thức đặc biệt để khởi tạo các biến thực thể của một đối tượng mới lập nên.
lớp khởi động:
Lớp có chứa phương thức main nơi bắt đầu việc thực thi chương trình.
hàm thuần túy:
Phương thức mà kết quả chỉ phụ thuộc vào các tham số của nó, và không gây hiệu ứng phụ nào ngoài việc trả lại một giá trị.
phương thức sửa đổi:
Phương thức làm thay đổi một hay nhiều đối tượng nhận làm tham số, và thường trả lại void.
phương thức điền:
Kiểu phương thức nhận tham số là một đối tượng “trống không” và điền vào những biến thực thể của nó thay vì việc phát sinh một giá trị trả lại.
thuật toán:
Một loạt những chỉ dẫn nhằm giải một lớp các bài toán theo một quá trình máy móc.

11.15  Bài tập

Bài tập 1   Trong trò chơi trên bàn có tên Scrabble2, mỗi miếng vuông để xếp lên bàn sẽ chứa một chữ cái, để xêm nên các từ có nghĩa, và đồng thời có một điểm số; từ đó ta tính được điểm cho các từ khác nhau.

  1. Hãy viết một định nghĩa lớp có tên Tile để biểu diễn các miếng vuông Scrabble. Các biến thực thể sẽ gồm một kí tự có tên letter và một số nguyên có tên value.
  2. Hãy viết một constructor để nhận các tham số letter và value rồi khởi tạo các biến thực thể.
  3. Viết một phương thức có tên printTile để nhận tham số là một đối tượng Tile rồi in ra các biến thực thể dưới định dạng mà người thường có thể đọc được.
  4. Viết một phương thức có tên testTile để tạo nên một đối tượng Tile có chữ cái Z và giá trị 10, rồi dùng printTile để in ra trạng thái của đối tượng này.

Mục đích của bài tập này là để luyện tập phần cơ chế tạo nên một lời định nghĩa lớp và mã lệnh để kiểm tra nó.

Bài tập 2   Hãy viết một định nghĩa lớp của Date, một kiểu đối tượng bao gồm ba số nguyên là yearmonth và day. Lớp này cần phải có hai constructor. Constructor thứ nhất không nhận tham số nào. Constructor thứ hai nhận các tham số mang tên yearmonth và day, rồi dùng chúng để khởi tạo các biến thực thể. Hãy viết một phương thức main để tạo nên một đối tượng Date mới có tên birthday. Đối tượng mới này để chứa ngày sinh nhật của bạn. Có thể dùng constructor nào cũng được.

Bài tập 3  Phân số là số có thể biểu điễn được dưới dạng tỉ số giữa hai số nguyên. Chẳng hạn, 2/3 là một phân số,  và bạn cũng có thể coi 7 là một phân số với mẫu số ngầm định bằng 1. Ở bài tập này, bạn sẽ viết một lời định nghĩa lớp cho các phân số.

  1. Lập một chương trình mới có tên Rational.java để định nghĩa một lớp tên là Rational. Một đối tượng Rational phải có hai biến thực thể số nguyên để lưu trữ tử số và mẫu số.
  2. Viết một constructor không nhận tham số nào để đặt tử số bằng 0 và mẫu số bằng 1.
  3. Viết một phương thức có tên printRational để nhận vào đối số là một đối tượng Rational rồi in nó ra theo định dạng hợp lý.
  4. Viết một phương thức main để lập nên một đối tượng mới có kiểu là Rational, đặt các biến thực thể của nó bằng giá trị cụ thể, rồi in đối tượng này ra.
  5. Đến đây, bạn đã có một chương trình tối thiểu có thể chạy thử được. Hãy chạy để kiểm tra nó, và gỡ lỗi, nếu cần.
  6. Viết một constructor thứ hai cho lớp này có nhận vào hai đối số rồi sử dụng chúng để khởi tạo các biến thực thể.
  7. Hãy viết một phương thức có tên negate để đảo dấu của phân số. Phương thức này phải là một phân thức sửa đổi, và vì vậy cần phải trả lại void. Hãy viết thêm dòng lệnh trong main để kiểm tra phương thức mới này.
  8. Viết một phương thức có tên invert để nghịch đảo số bằng cách tráo đổi tử số và mẫu số. Hãy viết thêm dòng lệnh trong main để kiểm tra phương thức mới này.
  9. Viết một phương thức có tên toDouble để chuyển đổi phân số thành một số double (số dấu phẩy động) rồi trả lại kết quả. Phương thức này là một hàm thuần tuý; nó không thay đổi đối tượng. Như thường lệ, hãy kiểm tra phương thức mới viết.
  10. Viết một phương thức có tên reduce để rút gọn một phân số về dạng tối giản bằng cách tìm ước số chung lớn nhất của tử số và mẫu số rồi cùng chia cả tử lẫn mẫu cho ước chung này. Phương thức nêu trên phải là một hàm thuần tuý; nó không được phép thay đổi các biến thực thể của đối tượng mà nó được kích hoạt lên. Để tính ước số chung lớn nhất, hãy xem Bài tập 10 của Chương 6).
  11. Viết một phương thức có tên add để nhận hai đối số là hai Rational rồi trả lại một đối tượng Rational mới. Đối tượng được trả lại phải chứa tổng của các đối số. có vài cách thực hiện phép cộng này. Bạn có thể dùng bất kì cách nào, nhưng hãy đảm bảo rằng kết quả của phép tính phải được rút gọn sao cho tử và mẫu không có ước số chung nào khác (ngoài 1).

Mục đích của bài tập này là nhằm viết một lời định nghĩa hàm có chứa nhiều loại phương thức, bao gồm constructors, phương thức sửa đổi, và hàm thuần tuý.


1
Cái mà tôi gọi là “nguyên mẫu nhanh” (rapid prototyping)  ở đây rất giống với cách phát triển dựa trên kiểm thử (test-driven development, TDD); sự khác biệt là ở chỗ TDD thường dựa trên kiểm thử tự động. Xem http://en.wikipedia.org/wiki/Test-driven_development.
2
Scrabble là một nhãn hiệu đã đăng kí ở Hoa Kì và Canada, thuộc về cty Hasbro Inc., và ở các nước còn lại trên thế giới, thì thuộc về J.W. Spear & Sons Limited ở Maidenhead, Berkshire, Anh Quốc, công ty nhánh của Mattel Inc.

3 phản hồi

Filed under Think Java

Chương 10: Grid World, phần 2

Trở về Mục lục bài viết

Phần 2 của nghiên cứu cụ thể GridWorld có sử dụng một số đặc điểm mà ta chưa từng gặp, vì vậy bạn sẽ xem qua bây giờ và seau này sẽ xem xét kĩ hơn. Hãy nhớ lại rằng, bạn có thể tìm tài liệu cho các lớp GridWorld ở http://www.greenteapress.com/thinkapjava/javadoc/gridworld/.

Khi cài đặt GridWorld, bạn sẽ có một thư mục mang tên projects/boxBug, trong đó chứa BoxBug.javaBoxBugRunner.java và BoxBug.gif.

Hãy sao chép những file này vào thư mục hiện thời của bạn rồi nhập chúng vào môi trường phát triển. Có những chỉ dẫn trong tài liệu sau mà bạn có thể tham khảo: http://www.collegeboard.com/prod_downloads/student/testing/ap/compsci_a/ap07_gridworld_installation_guide.pdf.

Sau đây là mã lệnh lấy từ BoxBugRunner.java:

import info.gridworld.actor.ActorWorld; 
import info.gridworld.grid.Location; 
import java.awt.Color; 
public class BoxBugRunner { 
  public static void main(String[] args) { 
    ActorWorld world = new ActorWorld(); 
    BoxBug alice = new BoxBug(6); 
    alice.setColor(Color.ORANGE); 
    BoxBug bob = new BoxBug(3); 
    world.add(new Location(7, 8), alice); 
    world.add(new Location(5, 5), bob); 
    world.show(); 
  } 
}

Ở đây mọi thứ có lẽ đều quen thuộc, ngoại trừ Location, thuộc về GridWorld, và đối tượng này tương đương với java.awt.Point.

BoxBug.java chứa lời định nghĩa lớp cho BoxBug.

public class BoxBug extends Bug { 
  private int steps; 
  private int sideLength; 
  public BoxBug(int length) { steps = 0; sideLength = length; } 
}

Dòng đầu tiên nói rằng lớp này mở rộng Bug, nghĩa là BoxBug là một dạng của Bug.

Hai dòng kế tiếp là những biến thực thể. Từng con Bug có một biến tên là sideLength, để quy định kích thước ô mà nó vẽ nên, và steps, để theo dõi xem con Bug này đi bao nhiêu bước rồi.

Dòng tiếp theo định nghĩa một constructor; đây là một phương thức đặc biệt để khởi tạo biến thực thể. Khi bạn tạo nên một Bug bằng cách kích hoạt new, Java sẽ kích hoạt constructor này.

Tham số cho constructor này là chiều dài cạnh.

Hành vi của Bug được điều khiển bởi phương thức act. Sau đây là phương thức act của BoxBug:

  public void act() { 
    if (steps < sideLength && canMove()) { 
      move(); 
      steps++; 
    } else { 
      turn(); 
      turn(); 
      steps = 0; 
    } 
  }

Nếu BoxBug có thể di chuyển, và chưa thực hiện đủ số bước đi theo yêu cầu, thì nó sẽ di chuyển và đồng thời tăng biến steps.

Nếu nó đụng phải tường hoặc đi hết một cạnh của hộp, thì con bọ sẽ quay 90 độ sang phải đồng thời chỉnh biến steps về 0.

Hãy chạy chương trình và xem nó làm gì. Bạn có thấy được con bọ có hành vi như dự kiến không?

10.1  Con mối

Tôi đã viết ra một lớp có tên Termite để mở rộng Bug và bổ sung khả năng tương tác với những bông hoa. Để chạy được lớp này, bạn hãy tải về những file sau rồi nhập chúng vào môi trường phát triển đang dùng:

http://thinkapjava.com/code/Termite.java
http://thinkapjava.com/code/Termite.gif
http://thinkapjava.com/code/TermiteRunner.java
http://thinkapjava.com/code/EternalFlower.java

Vì Termite mở rộng Bug, tất cả những phương thức của Bug đều hoạt động được với các Termite. Nhưng Termite có thêm những phương thức khác mà Bug không có.

/** 
 * Trả lại true nếu con mối có mang bông hoa.
 */ 
  public boolean hasFlower(); 
/** 
 * Trả lại true nếu con mối quay mặt về phía bông hoa.
 */ 
  public boolean seeFlower(); 
/** 
 * Tạo nên bông hoa trừ khi con mối đã có sẵn một bông.
 */ 
  public void createFlower(); 
/**
 * Bỏ lại bông hoa tại vị trí con mối đang đứng.
 *
 * Lưu ý: trên mỗi ô chỉ có được một vật, bởi vậy hiệu ứng
 * của việc đánh rơi bông hoa sẽ được hoãn lại đến khi con mối di chuyển.
 */ 
  public void dropFlower(); 
/**
 * Ném bông hoa vào chỗ mà con mối đang hướng tới.
 */ 
  public void throwFlower(); 
/**
 * Nhặt bông hoa tại vị trí con mối hướng tới, nếu có,
 * và nếu con mối chưa mang theo hoa.
 */ 
  public void pickUpFlower();

Có những phương thức mà Bug cung cấp một lời định nghĩa này và Termite lại cung cấp cái khác. Trong trường hợp như vậy, phương thức Termite sẽ ghi đè lên phương thức Bug.

Chẳng hạn, Bug.canMove trả lại true nếu có một bông hoa ở vị trí kế tiếp, bởi vậy các có thể Bug có thể giẫm lên Flower. Còn Termite.canMove sẽ trả lại false nếu có bất kì đối tượng nào khác ở vị trí kế tiếp, nên biểu hiện của Termite sẽ khác đi.

Một ví dụ khác, các đối tượng con mối có một phiên bản turn trong đó nhận tham số là số nguyên chỉ độ góc. Sau cùng, đối tượng con mối có randomTurn, với tác dụng quay ngẫu nhiên qua trái hoặc phải với góc quay 45 độ.

Sau đây là mã lệnh từ file TermiteRunner.java:

public class TermiteRunner {
  public static void main(String[] args) {
    ActorWorld world = new ActorWorld();
    makeFlowers(world, 20);
    Termite alice = new Termite();
    world.add(alice);
    Termite bob = new Termite();
    bob.setColor(Color.blue);
    world.add(bob);
    world.show();
  } 
  public static void makeFlowers(ActorWorld world, int n) { 
    for (int i = 0; i<n; i++) { 
      world.add(new EternalFlower());
    }
  }
}

Ở đây mọi thức có lẽ đều quen thuộc. TermiteRunner tạo nên một ActorWorld với 20 EternalFlowers và hai Termite.

Mỗi EternalFlower là một Flower ghi đè lên act sao cho các bông hoa không được tô thẫm đi.

public class EternalFlower extends Flower { 
  public void act() {
  } 
}

Nếu bạn chạy TermiteRunner.java, bạn sẽ thấy hai con mối di chuyển ngẫu nhiên quanh những bông hoa.

MyTermite.java giới thiệu những phương thức tương tác với các bông hoa. Sau đây là lời khai báo lớp này:

public class MyTermite extends Termite { 
  public void act() {
    if (getGrid() == null) 
      return; 
    if (seeFlower()) { 
      pickUpFlower(); 
    } 
    if (hasFlower()) { 
      dropFlower();
    } 
    if (canMove()) {
      move();
    }
    randomTurn();
  }
}

MyTermite mở rộng Termite và ghi đè lên act. Nếu MyTermite thấy một bông hoa, nó sẽ nhặt lên. Nếu có bông hoa rồi, thì nó sẽ bỏ lại bông hoa này.

10.2  Con mối của Langton

Con kiến của Langton là một mô hình đơn giản về biểu hiện của kiến nhưng hiển thị những biểu hiện phức tạp đáng ngạc nhiên. Con kiến sống trong một lưới ô như GridWorld trong đó từng ô có màu trắng hoặc đen. Kiến di chuyển theo những quy tắc sau:

  • Nếu con kiến đứng trên ô trắng; nó quay sang phải, tô màu ô thành đen, rồi tiến bước.
  • Nếu con kiến đứng trên ô đen; nó quay sang trái, tô màu ô thành trắng, rồi tiến bước.

Vì những quy luật này rất đơn giản nên bạn sẽ trông đợi rằng con kiến này sẽ làm những điều đơn giản như chạy vòng quanh hoặc lặp lại một mẫu hình đơn giản. Song nếu kiến ta bắt đầu trên lưới ô toàn màu trắng thì nó sẽ đi hơn 10000 bước theo một dạng mẫu tưởng như ngẫu nhiên trước khi vào một vòng lặp gồm 104 bước.

Bạn có thể đọc thêm về con kiến Langton tại http://en.wikipedia.org/wiki/Langton_ant.

Thật không dễ lập nên con kiến Langton trong GridWorld vì ta không thể đặt màu của các ô. Song thay vào đó, ta có thể dùng những bông hoa để đánh dấu ô. Có điều là ta không thể có đồng thời cả kiến lẫn hoa trên cùng một ô, nên ta không hoàn toàn thực hiện đúng được những quy luật với con kiến.

Thay vào đó ta sẽ tạo nên một con mối có tên LangtonTermite, trong đó dùng seeFlower để kiểm tra xem ô trước mặt có bông hoa không, và nếu ô trước mặt có bông hoa, thì dùng pickUpFlower để hái nó, và throwFlower để đặt hoa xuống ô kế tiếp. Bạn có thể sẽ muốn đọc mã lệnh của những phương thức này để chắc rằng chúng làm gì.

10.3  Bài tập

Bài tập 1   Bây giờ bạn đã biết đủ kiến thức để làm bài tập trong cuốn Sách bài tập (Student Manual), Phần 2. Hãy làm những bài này, rồi xem tiếp những bài lý thú dưới đây.
Bài tập 2   Mục đích của bài tập này là khám phá biểu hiện của các con mối khi tương tác với những bông hoa. Hãy sửa chữa TermiteRunner.java để tạo nên những MyTermite thay vì các Termite. Sau đó chạy lại. MyTermite sẽ chạy vòng quanh  một cách ngẫu nhiên, làm dịch chuyển những bông hoa. Tổng số bông hoa phải không đổi (kể cả những mông mà MyTermite đang giữ). Trong cuốn “Termites, Turtles and Traffic Jams”, Mitchell Resnick đã mô tả một mô hình đơn giản cho biểu hiện của con mối:

  • Nếu bạn thấy bông hoa, hãy nhặt nó lên. Trừ khi bạn đã có hoa rồi; trong trường hợp này thì vứt bỏ bông hoa hiện có.
  • Tiến bước, nếu có thể.
  • Quay sang trái hoặc phải một cách ngẫu nhiên.

Hãy sửa chữa MyTermite.java để thực hiện mô hình này. Theo bạn thì thay đổi trên sẽ có hiệu ứng gì đối với biểu hiện của các MyTermite?

Hãy thử chạy chương trình. Một lần nữa, tổng số bông hoa không đổi, nhưng dần dần hoa sẽ tụ lại thành một số ít các đống, nhiều khi chỉ là một đống.

Biểu hiện này là một thuộc tính nổi, mà bạn có thể tham khảo ở http://en.wikipedia.org/wiki/Emergence. Các con MyTermite tuân theo những quy tắc đơn giản chỉ bằng thông tin quy mô nhỏ, song kết quả sẽ là sự tổ chức có quy mô lớn.

Hãy thử nghiệm với những quy tắc khác nhau và xem chúng có tác động gì lên hệ thống. Những thay đổi nhỏ có thể gây nên kết quả không lường trước!

Bài tập 3

  1. Sao chép lại file Termite.java rồi đặt tên thành LangtonTermite và sao chép TermiteRunner.java thành LangtonRunner.java. Hãy sửa chữa sao cho những định nghĩa lớp có tên trùng với tên file, và do đó LangtonRunner tạo nên một LangtonTermite.
  2. Nếu bạn tạo một file tên là LangtonTermite.gif, GridWorld sẽ dùng nó để biểu diễn cho Termite của bạn. Bạn có thể tải về những ảnh côn trùng đẹp từ http://www.cksinfo.com/animals/insects/realisticdrawings/index.html. Để chuyển chúng về dạng GIF, bạn có thể dùng một ứng dụng như ImageMagick.
  3. Sửa chữa act để thực hiện những quy tắc tương tự cho kiến Langton. Hãy thử những quy tắc khác nhau, và với cả hai góc quay 45 và 90 độ. Hãy tìm những quy tắc để chạy được nhiều ô nhất trước khi con mối bắt đầu chạy vòng.
  4. Để cho mối có đủ chỗ chạy, bạn có thể nới rộng lưới ô hay chuyển sang dùng một UnboundedGrid.
  5. Tạo nên nhiều con LangtonTermite rồi xem chúng tương tác như thế nào.

%(count) bình luận

Filed under Think Java

Chương 9: Đối tượng có thể biến đổi

Trở về Mục lục cuốn sách

String là các đối tượng, song chúng là đối tượng không điển hình bởi lẽ

  • Chúng không thể biến đổi.
  • Chúng không có thuộc tính.
  • Bạn không bắt buộc phải dùng new để tạo nên một chuỗi mới.

Trong chương này, ta dùng hai đối tượng thuộc thư viện Java, là đối tượng Point và Rectangle (điểm và hình chữ nhật). Song trước hết, tôi muốn nói rõ rằng những điểm và hình chữ nhật này không phải là những đối tượng đồ hoạ xuất hiện trên mà hình. Chúng chỉ là những giá trị có chứa số liệu, cũng như các int và double. Giống những giá trị khác, chúng được sử dụng bên trong chương trình để thực hiện tính toán.

9.1  Các gói chương trình

Các thư viện Java được chia thành các gói, trong đó có java.lang là gói chứa hầu hết các lớp mà ta dùng cho đến giờ, và java.awt, tên đầy đủ Abstract Window Toolkit (AWT), là gói chứa các lớp gồm cửa sổ, nút bấm, đồ hoạ, v.v.

Để dùng một lớp được định nghĩa trong gói khác, bạn phải nhập nó. Point và Rectangle nằm trong gói java.awt, bởi vậy để nhập chúng ta làm như sau:

    import java.awt.Point; 
    import java.awt.Rectangle;

Tất cả câu lệnh import đều xuất hiện ở điểm đầu chương trình, bên ngoài lời định nghĩa lớp.

Các lớp trong java.lang, như Math và String, được nhập một cách tự động, bởi vậy từ trước đến giờ ta chưa cần dùng đến câu lệnh import nào.

9.2  Đối tượng Point

Một điểm là hai con số (toạ độ) mà ta coi chúng hợp nhất như một đối tượng đơn lẻ. Theo kí hiệu toán học, điểm thường được viết trong cặp ngoặc tròn, với dấu phẩy phân cách giữa các toạ độ. Chẳng hạn, (0, 0) chỉ định gốc toạ độ, còn (xy) chỉ định điểm cách điểm gốc x đơn vị về bên tay phải và y đơn vị lên trên.

Trong Java, một điểm được biểu diễn bởi một đối tượng Point. Để tạo nên một điểm mới, bạn phải dùng đến new:

    Point blank; 
    blank = new Point(3, 4);

Dòng thứ nhất là một lời khai báo biến thông dụng: blank có kiểu Point. Dòng thứ hai kích hoạt new, quy định kiểu của đối tượng mới, và cung cấp các đối số. Ở đây các đối số là toạ độ của điểm mới, (3, 4).

Kết quả của new là một tham chiếu đến điểm mới,  vì vậy blank chứa một tham chiếu đến đối tượng mới tạo nên. Có một cách tiêu chuẩn để sơ đồ hoá phép gán này, xem trên hình vẽ.

Như thường lệ, tên biến, blank, được ghi bên ngoài ô và giá trị của nó ở trong ô. Với trường hợp này, giá trị là một tham chiếu, và được biểu diễn bởi một mũi tên. Mũi tên này chỉ đến đối tượng mà ta tham chiếu tới.

Ô lớn biểu diễn đối tượng mới tạo lập cùng với hai giá trị bên trong. Các tên gọi x và y là các tên của biến thực thể.

Xét tổng thể, tất cả các biến, giá trị, và đối tượng trong một chương trình thì được gọi là trạng thái. Những biểu đồ như thế này, dùng để biểu diễn trạng thái chương trình, được gọi là biểu đồ trạng thái. Khi chương trình chạy, trạng thái của nó thay đổi; bởi vậy bạn nên coi biểu đồ trạng thái như một ảnh chụp tại một thời điểm cụ thể trong quá trình thực thi.

9.3  Các biến thực thể

Những đơn vị thông tin hợp thành đối tượng được gọi là các biến thực thể vì từng đối tượng, vốn là một thực thể cho kiểu của nó, có một bản sao riêng của biến thực thể này.

Cũng giống như ngăn trước [nơi để CD, giấy tờ ở ghế ngồi phía trước] của một chiếc xe hơi. Mỗi cái xe là thực thể của kiểu “xe hơi,” và từng chiếc xe có ngăn riêng của nó. Nếu bạn yêu cầu tôi lấy đồ từ ngăn trước của xe hơi bạn đang dùng, thì hãy cho tôi biết xe bạn đang dùng là xe nào.

Tương tự như vậy, nếu bạn muốn đọc một giá trị từ biến thực thể, bạn phải chỉ định đối tượng mà bạn cần lấy giá trị từ đó. Ở Java, điều này được thực hiện bằng cách dùng “kí pháp dấu chấm.”

    int x = blank.x;

Biểu thức blank.x nghĩa là “đến đối tượng mà blank chỉ tới, rồi lấy giá trị của x.” Trong trường hợp này ta gán giá trị đó vào một biến địa phương có tên là x. Không hề có xung đột gì giữa biến địa phương tên x này và biến thực thể mang tên x. Mục đích của kí pháp dấu chấm là để quy định rõ ràng xem biến nào mà bạn đang tham chiếu tới.

Bạn có thể dùng kí pháp dấu chấm làm một thành phần trong bất kì biểu thức Java nào, bởi vậy các biểu thức sau đều hợp lệ.

    System.out.println(blank.x + ", " + blank.y); 
    int distance = blank.x * blank.x + blank.y * blank.y;

Dòng thứ nhất in ra 3, 4; dòng thứ hai tính giá trị của 25.

9.4  Đối tượng trong vai trò của tham số

Bạn có thể truyền đối tượng như những tham số theo cách thông thường. Chẳng hạn:

  public static void printPoint(Point p) { 
    System.out.println("(" + p.x + ", " + p.y + ")"); 
  }

Phương thức này nhận một điểm làm đối số rồi in nó ra dưới định dạng tiêu chuẩn. Nếu bạn kích hoạt  printPoint(blank), nó sẽ in ra (3, 4). Thực tế là Java đã có sẵn một phương thức để in ra các Point. Nếu kích hoạt System.out.println(blank), bạn sẽ nhận được

java.awt.Point[x=3,y=4]

Đây là định dạng tiêu chuẩn mà Java dùng để in các đối tượng. Nó in ra tên của kiểu dữ liệu, tiếp theo là các tên và giá trị của những biến thực thể.

Một ví dụ thứ hai là ta có thể viết lại phương thức distance ở Mục 6.2 để nó nhận hai Point làm tham số thay vì bốn double.

  public static double distance(Point p1, Point p2) { 
    double dx = (double)(p2.x - p1.x); 
    double dy = (double)(p2.y - p1.y); 
    return Math.sqrt(dx*dx + dy*dy); 
  }

Các phép đổi kiểu dữ liệu ở đây đều không thật sự cần thiết. Tôi chỉ viết vào để tự nhắc rằng các biến thực thể trong một Point đều là các số nguyên.

9.5  Hình chữ nhật

Rectangle (hình chữ nhật) cũng giống như các điểm, chỉ khác rằng chúng có bốn biến thực thể: xywidth (bề rộng) và height (chiều cao). Ngoài điều này ra thì những thứ còn lại vẫn y nguyên.

Ví dụ sau đây tạo nên một đối tượng Rectangle rồi khiến box tham chiếu đến nó.

    Rectangle box = new Rectangle(0, 0, 100, 200);

Hình vẽ này mô tả hiệu ứng của lệnh gán nêu trên.

Nếu in box ra, bạn nhận được

java.awt.Rectangle[x=0,y=0,width=100,height=200]

Một lần nữa, đây là kết quả của một phương thức Java vốn biết cách in những đối tượng Rectangle.

9.6  Đối tượng với vai trò là kiểu được trả lại

Bạn có thể viết những phương thức trả lại đối tượng. Chẳng hạn, findCenter lấy một Rectangle làm đối số rồi trả lại một Point có chứa toạ độ của tâm Rectangle:

  public static Point findCenter(Rectangle box) { 
    int x = box.x + box.width/2; 
    int y = box.y + box.height/2; 
    return new Point(x, y); 
}

Lưu ý rằng bạn có thể dùng new để tạo nên một đối tượng mới, và rồi lập tức dùng kết quả này làm giá trị trả lại.

9.7  Đối tượng có tính thay đổi

Bạn có thể thay đổi nội dung của một đối tượng bằng cách viết lệnh gán cho một trong số những biến thực thể của nó. Chẳng hạn, để “dịch chuyển” một hình chữ nhật mà không làm thay đổi kích thước của nó, bạn có thể chỉnh sửa các giá trị x và y:

    box.x = box.x + 50; 
    box.y = box.y + 100;

Kết quả được biểu diễn trên hình:

Ta có thể bao bọc đoạn mã lệnh trên vào một phương thức rồi khái quát hoá nó để dịch chuyển hình chữ nhật đi một khoảng cách bất kì:

  public static void moveRect(Rectangle box, int dx, int dy) { 
    box.x = box.x + dx; 
    box.y = box.y + dy; 
  }

Các biến dx và dy chỉ định khoảng cách dịch chuyển hình theo từng hướng riêng. Việc kích hoạt phương thức này có ảnh hưởng làm thay đổi Rectangle được truyền vào dưới dạng tham số.

    Rectangle box = new Rectangle(0, 0, 100, 200); 
    moveRect(box, 50, 100); 
    System.out.println(box);

sẽ in ra java.awt.Rectangle[x=50,y=100,width=100,height=200].

Việc thay đổi các đối tượng bằng cách truyền chúng làm tham số cho các phương thức mặc dù có thể hữu ích, song nó cũng có thể gây khó khăn cho việc gỡ lỗi vì không phải lúc nào cũng dễ thấy là việc kích hoạt một phương thức có thay đổi các đối số của nó hay không. Về sau, tôi sẽ thảo luận những ưu nhược điểm của phong cách lập trình này.

Java có các phương thức thao tác với Point và Rectangle. Bạn có thể đọc tài liệu ở http://download.oracle.com/javase/6/docs/api/java/awt/Point.html và http://download.oracle.com/javase/6/docs/api/java/awt/Rectangle.html.

Chẳng hạn, translate có hiệu ứng tựa như moveRect, song thay vì phải truyền Rectangle làm đối số, bạn lại dùng kí pháp dấu chấm:

    box.translate(50, 100);

9.8  Aliasing

Hãy nhớ rằng khi bạn gán một đối tượng vào cho một biến, bạn đang gán một tham chiếu đến đối tượng. Hoàn toàn có thể có nhiều biến cùng tham chiếu tới một đối tượng. Chẳng hạn, đoạn mã sau:

    Rectangle box1 = new Rectangle(0, 0, 100, 200); 
    Rectangle box2 = box1;

tạo nên một biểu đồ trạng thái trông như sau:

box1 và box2 cùng chỉ đến một đối tượng. Nói cách khác, đối tượng này có hai tên gọi, box1 và box2. Việc người nào đó dùng hai tên được gọi là aliasing (dùng bí danh). Với đối tượng cũng như vậy.

Khi hai biến được dùng bí danh, bất kì sự thay đổi nào ảnh hưởng tới biến này thì cũng ảnh hưởng tới biến kia. Chẳng hạn:

    System.out.println(box2.width); 
    box1.grow(50, 50); 
    System.out.println(box2.width);

Dòng lệnh thứ nhất in ra 100, vốn là bề rộng của Rectangle được tham chiếu qua biến box2. Dòng thứ hai kích hoạt phương thức grow lên box1, để mở rộng Rectangle thêm 50 điểm ảnh theo mỗi chiều (hãy đọc tài liệu để biết thêm thông tin). Hiệu ứng được cho thấy ở hình vẽ dưới đây:

Bất kể thay đổi nào thực hiện đối với box1 thì cũng ảnh hưởng đến box2. Do vậy, giá trị được in ra bởi dòng lệnh thứ ba là 200, bề rộng của hình chữ nhật sau khi mở rộng. (Nói thêm, việc các toạ độ của một Rectangle nhận giá trị âm là hoàn toàn hợp lệ.)

Từ ví dụ đơn giản này bạn có thể thấy rằng mã lệnh có chứa bí dạng nhanh chóng khiến ta nhầm lần và có thể khó gỡ lỗi. Nói chung, nên tránh dùng bí danh hoặc dùng thật cẩn thận.

9.9  null

Khi bạn tạo nên một biến đối tượng, hãy nhớ rằng bạn đang tạo nên một tham chiếu đến đối tượng. Trước khi bạn khiến cho một biến chỉ tới đối tượng, thì giá trị của biến vẫn là nullnull là một giá trị đặc biệt (và cũng là một từ khoá trong Java) có nghĩa là “không có đối tượng.”

Lời khai báo Point blank; thì tương đương với lệnh khởi tạo sau

     Point blank = null;

và được biểu diễn bởi biểu đồ trạng thái sau:

Giá trị null được biểu thị bằng một hình vuông nhỏ không kèm theo mũi tên.

Nếu bạn cố thử dùng một đối tượng null, qua việc truy cập một biến thực thể hay kích hoạt một phương thức, thì Java sẽ phát một biệt lệ có tên NullPointerException, in một thông báo lỗi và kết thúc chương trình.

    Point blank = null; 
    int x = blank.x; // NullPointerException 
    blank.translate(50, 50); // NullPointerException

Mặt khác, sẽ hoàn toàn hợp lệ nếu ta truyền một đối tượng null làm đối số hoặc nhận một null làm giá trị trả về. Thực ra, điều này rất thông dụng, với mục đích chẳng hạn là biểu diễn một tập hợp rỗng hay để chỉ một điều kiện có lỗi.

9.10  Thu dọn rác

Ở Mục 9.8 ta đã nói về những gì đã xảy ra khi nhiều biến cùng tham chiếu tới một đối tượng. Thế còn điều gì sẽ xảy ra khi không có biến nào tham chiếu đến đối tượng? Chẳng hạn:

    Point blank = new Point(3, 4); 
    blank = null;

Dòng thứ nhất tạo ra một đối tượng Point mới rồi khiến cho blank tham chiếu đến nó. Dòng thứ hai sửa chữa blank để cho, thay vì tham chiếu đến đối tượng, nó không tham chiếu đến gì cả (hay tham chiếu đến đối tượng null).

Nếu không có ai tham chiếu đến đối tượng, thì cũng chảng ai có thể đọc hay ghi giá trị bất kì nào từ nó, hay kích hoạt một phương thức lên nó. Hệ quả là, nó sẽ ngừng tồn tại. Ta có thể vẫn giữ đối tượng này trong bộ nhớ, song làm như vậy chỉ tốn dung lượng; bởi vậy khi chương trình chạy, theo định kì hệ thống sẽ tìm kiếm các đối tượng lang thang rồi thu hồi lại nó, theo một quá trình mang tên thu dọn rác. Sau này, dung lượng nhớ bị chiếm bởi đối tượng sẽ về tay người dùng để phục vụ đối tượng mới.

Bạn không cần phải làm bất cứ điều gì để tiến hành thu dọn rác, và nói chung bạn sẽ không nhận thức được quá trình này. Song bạn cần biết rằng quá trình luôn được ngầm chạy một cách định kì.

9.11  Các đối tượng và kiểu nguyên thủy

Trong Java có hai loại kiểu dữ liệu, kiểu nguyên thủy và kiểu đối tượng. Kiểu nguyên thủ, như int và boolean đều bắt đầu bằng chữ viết thường; kiểu đối tượng bắt đầu bằng chữ viết in. Sự phân biệt này rất có ích vì chúng nhắc ta một số điểm khác nhau giữa chúng:

  • Khi khai báo một biến nguyên thủy, bạn được một dung lượng lưu trữ dành cho giá trị nguyên thủy. Khi bạn khai báo một biến đối tượng, bạn nhận được một dung lượng chứa tham chiếu tới đối tượng. Để giành được dung lượng cho bản thân đối tượng đó, bạn phải dùng đến new.
  • Nếu bạn không khởi tạo một kiểu nguyên thủy, thì nó sẽ được điền giá trị mặc định tùy theo kiểu đó là gì. Chẳng hạn, 0 với trường hợp int và false với boolean. Giá trị mặc định của kiểu đối tượng là null, nghĩa là không có đối tượng nào.
  • Các biến nguyên thủy tách biệt hoàn toàn, theo nghĩa bất cứ bạn làm gì trong một phương thức này sẽ không ảnh hưởng đến một biến ở phương thức khác. Các biến đối tượng thì lại cần phải khéo léo khi thao tác vì chúng không được biệt lập như vậy. Nếu bạn truyền một tham chiếu đến đối tượng để làm đối số, thì phương thức mà bạn kích hoạt có thể sẽ thay đổi đối tượng, và trong trường hợp này bạn sẽ thấy hiệu ứng. Dĩ nhiên, đó có thể là điều hay, song bạn cần nhận thức được việc này.

Còn một điểm khác biệt giữa kiểu nguyên thủy và kiểu đối tượng. Bạn không thể bổ sung kiểu nguyên thủy mới nào vào Java (trứ khi bạn là thanh viên trong hội đồng tiêu chuẩn), nhưng bạn có thể tạo nên kiểu đối tượng mới! Bạn sẽ biết cách làm như vậy trong chương sau.

9.12  Thuật ngữ

gói:
Một tập hợp các lớp. Các lớp Java được tổ chức thành các gói.
AWT:
Abstract Window Toolkit, một trong các gói Java lớn nhất và thông dụng nhất.
thực thể:
Ví dụ lấy từ một thể loại nào đó. Con mèo nhà tôi là một thực thể thuộc thể loại “động vật họ miêu.” Mỗi đối tượng đều là thực thể của một lớp nào đó.
biến thực thể:
Một trong số các đơn vị dữ liệu được đặt tên để cấu thành một đối tượng. Từng đối tượng (thực thể) đều có bản sao riêng các biến thực thể trong lớp mà nó thuộc vào.
tham chiếu:
Một giá trị để chỉ định một đối tượng. Trên sơ đồ trạng thái, một tham chiếu xuất hiện dưới dạng hình mũi tên.
aliasing (bí danh):
Tình trạng khi có nhiều biến cùng tham chiếu tới một đối tượng.
thu dọn rác:
Quá trình tìm các đối tượng không có tham chiếu và thu hồi dung lượng bộ nhớ mà chúng chiếm giữ.
trạng thái:
Một hình thức diễn tả đầy đủ tất cả các biến và đối tượng cùng những giá trị của chúng tại một thời điểm trong khi chương trình được thực thi.
sơ đồ trạng thái:
Một hình ảnh “chụp lại” trạng thái của chương trình.

9.13  Bài tập

Bài tập 1

  1. Với chương trình sau đây, hãy vẽ một sơ đồ ngăn xếp cho thấy các biến địa phương và các đối số của main và riddle, rồi cho thấy mọi đối tượng mà hai biến này chỉ đến.
  2. Kết quả của chương trình này là gì?
  public static void main(String[] args) { 
    int x = 5; 
    Point blank = new Point(1, 2); 
    System.out.println(riddle(x, blank)); 
    System.out.println(x); System.out.println(blank.x); 
    System.out.println(blank.y); 
  } 
  public static int riddle(int x, Point p) { 
    x = x + 7; 
    return x + p.x + p.y; 
  }

Mục đích của bài tập này là để đảm bảo rằng bạn hiểu cơ chế truyền đối tượng làm tham số.

Bài tập 2

  1. Với chương trình sau, hãy vẽ một biểu đồ ngăn xếp thể hiện trạng thái của chương trình ngay trước khi distance trả về. Hãy kèm theo tất cả các biến số và tham số cùng với những đối tượng mà các biến này tham chiếu tới.
  2. Kết quả của chương trình này là gì?
  public static double distance(Point p1, Point p2) { 
    int dx = p1.x - p2.x; 
    int dy = p1.y - p2.y; 
    return Math.sqrt(dx*dx + dy*dy); 
  } 
  public static Point findCenter(Rectangle box) { 
    int x = box.x + box.width/2; 
    int y = box.y + box.height/2; 
    return new Point(x, y); 
  } 
  public static void main(String[] args) { 
    Point blank = new Point(5, 8); 
    Rectangle rect = new Rectangle(0, 2, 4, 4); 
    Point center = findCenter(rect); 
    double dist = distance(center, blank); 
    System.out.println(dist); 
  }

Bài tập 3   Phương thức grow thuộc về lớp Rectangle. Hãy đọc tài liệu ở http://download.oracle.com/javase/6/docs/api/java/awt/Rectangle.html#grow(int, int).

  1. Kết quả của chương trình sau là gì?
  2. Hãy vẽ một sơ đồ trạng thái chỉ ra trạng thái của chương trình ngay trước khi main kết thúc, trong đó bao gồm tất cả những biến địa phương cùng các đối tượng mà những biến này tham chiếu tới.
  3. Ở điểm cuối của main, liệu p1 và p2 có cùng là bí danh không? Tại sao (không)?
  public static void printPoint(Point p) { 
    System.out.println("(" + p.x + ", " + p.y + ")"); 
  } 
  public static Point findCenter(Rectangle box) { 
    int x = box.x + box.width/2; 
    int y = box.y + box.height/2; 
    return new Point(x, y); 
  } 
  public static void main(String[] args) { 
    Rectangle box1 = new Rectangle(2, 4, 7, 9); 
    Point p1 = findCenter(box1); 
    printPoint(p1); 
    box1.grow(1, 1); 
    Point p2 = findCenter(box1); 
    printPoint(p2); 
  }

Bài tập 4   Đến giờ có thể bạn đang tương tư về phương thức giai thừa, nhưng ta sẽ viết thêm một dạng mới.

  1. Hãy tạo một chương trình mới có tên Big.java rồi viết một dạng lặp cho factorial.
  2. In ra một bảng các số nguyên chạy từ 0 đến 30 cùng với giai thừa của chúng. Ở tầm khoảng 15, có thể bạn sẽ thấy kết quả không còn đúng nữa. Tại sao vậy?
  3. BigIntegers là các đối tượng Java với khả năng biểu diễn những số nguyên lớn tùy ý. Không có giới hạn trên nào trừ giới hạn kích thước bộ nhớ và tốc độ xử lý. Hãy đọc tài liệu về BigIntegers athttp://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html.
  4. Để dùng được BigIntegers, bạn phải thêm dòng import java.math.BigInteger vào đầu chương trình của bạn.
  5. Có vài cách tạo nên một BigInteger, nhưng tôi khuyên bạn cách dùng valueOf. Đoạn mã sau chuyển đổi một số nguyên thành BigInteger:
    int x = 17; 
    BigInteger big = BigInteger.valueOf(x);

    Hãy gõ đoạn mã lệnh này rồi chạy thử. Cố gắng in ra một BigInteger.

  6. Vì BigIntegers không phải là kiểu nguyên thủy nên các toán tử toán học thông thường không thể thao tác với chúng. Thay vào đó, ta phải dùng những phương thức như add. Để cộng hai BigInteger, hãy kích hoạt add lên một số rồi truyền số kia làm đối số. Chẳng hạn:
    BigInteger small = BigInteger.valueOf(17); 
    BigInteger big = BigInteger.valueOf(1700000000); 
    BigInteger total = small.add(big);

    Hãy thử một số phương thức khác, như multiply và pow.

  7. Chuyển đổi factorial sao cho nó tính toán với BigInteger rồi trả lại kết quả cũng là một BigInteger. Bạn có thể mặc kệ tham số—nó vẫn sẽ là một số nguyên.
  8. Hãy thử in lại bảng bằng phương thức giai thừa mà bạn vừa sửa đổi. Liệu nó có đúng đến 30 không? Bạn có thể làm cho nó lớn đến bao nhiêu? Tôi đã tính giai thừa của tất cả các số từ 0 đến 999, nhưng vì máy tính của tôi khá chậm nên mất một lúc. Số cuối cùng, 999!, có tới 2565 chữ số.

Bài tập 5   Nhiều kĩ thuật mã hóa phụ thuộc vào khả năng nâng các số nguyên lớn lên những lũy thừa nguyên. Sau đây là một phương thức thực hiện một kĩ thuật (tương đối) nhanh để tính lũy thừa số nguyên:

  public static int pow(int x, int n) { 
    if (n == 0) return 1; 

    // tính x mũ n/2 bằng cách đệ quy 
    int t = pow(x, n/2); 

    // nếu n chẵn, kết quả là t bình phương
    // nếu n lẻ, kết quả là t bình phương nhân với x
    if (n%2 == 0) { 
      return t*t; 
    } else { 
      return t*t*x; 
    } 
  }

Vấn đề với phương thức này là ở chỗ nó chỉ hoạt động được nếu kết quả nhỏ hơn 2 tỷ. Hãy viết lại phương thức để kết quả là một BigInteger. Tuy vậy các tham số vẫn là số nguyên.

Bạn có thể dùng các phương thức cho BigInteger là add và multiply, song đừng dùng pow, như vậy sẽ chẳng còn gì để làm.

Bài tập 6   Nếu bạn thích đồ họa, bây giờ đúng là lúc đọc đến Phụ lục A rồi làm các bài tập ở đó.

5 phản hồi

Filed under Think Java

Chương 8: Chuỗi kí tự

8.1  Kí tự

Trong Java cũng như các ngôn ngữ hướng đối tượng khác thì đối tượng là tập hợp những dữ liệu có liên quan, cùng với một tập các phương thức. Những phương thức nafyhoajt động trên đối tượng kể trên, thực hiện tính toán và đôi lúc thay đổi dữ liệu trong đối tượng đó.

String (chuỗi kí tự) là các đối tượng, bởi vậy bạn có thể hỏi “Có dữ liệu nào được chứa trong một đối tượng String?” và “Có những phương thức nào mà ta có thể kích hoạt được từ đối tượng String?” Những thành phần trong một đối tượng String là các chữ cái, hay tổng quát hơn, là những kí tự. Không phải mọi kí tự đều là chữ cái; còn những kí tự là chữ số, kí hiệu, và các thứ khác. Để đơn giản tôi sẽ gọi chúng đều là các chữ cái. Có nhiều phương thức khác nhau, nhưng trong sách này chỉ dùng một số ít. Các phương thức còn lại được chỉ dẫn ở http://download.oracle.com/javase/6/docs/api/java/lang/String.html.

Phương thức đầu tiên mà ta xét đến là charAt; phương thức này cho phép bạn kết xuất những chữ cái từ một Stringchar là kiểu biến dùng được để lưu trữ từng kí tự riêng lẻ (trái ngược lại với một chuỗi các kí tự).

char cũng hoạt động như các kiểu dữ liệu khác ta đã gặp:

    char ltr = 'c'; 
    if (ltr == 'c') { 
      System.out.println(ltr); 
    }

Những giá trị của kí tự đều xuất hiện trong cặp dấu nháy đơn, như ’c’. Khác với giá trị của chuỗi (xuất hiện giữa cặp dấu nháy kép), các giá trị kí tự chỉ có thể chứa một chữ cái hoặc một kí hiệu.

Sau đây là cách dùng phương thức charAt:

    String fruit = "banana"; 
    char letter = fruit.charAt(1); 
    System.out.println(letter);

fruit.charAt() có nghĩa rằng tôi đang kích hoạt phương thức charAt lên đối tượng có tên fruit. Tôi đang truyền đối số 1 vào phương thức này, tức là tôi đang muốn biết chữ cái đầu tiên của chuỗi là gì. Kết quả là một kí tự, và được lưu vào trong một char có tên letter. Khi tôi in ra giá trị của letter, tôi bị bất ngờ:

a

a không phải là chữ cái đầu tiên của "banana". Trừ khi bạn nghiên cứu khoa học máy tính. Vì những lí do kĩ thuật mà giới khoa học máy tính đều đếm từ số không. Chữ cái thứ 0 của "banana" là chữ b. Chữ cái thứ 1 là a và thứ 2 là n.

Nếu bạn muốn biết chữ cái thứ 0 của một chuỗi, bạn phải truyền tham số là 0:

    char letter = fruit.charAt(0);

8.2  Length

Phương thức tiếp theo đối với String mà ta xét đến là length, vốn trả lại số kí tự có trong chuỗi. Chẳng hạn:

    int length = fruit.length();

length không nhận đối số truyền vào, và trả lại một số nguyên, trong trường hợp này bằng 6. Lưu ý rằng việc có một biến trùng tên với phương thức là hoàn toàn hợp lệ (mặc dù điều này có thể gây nhầm lẫn đối với người đọc mã lệnh).

Để tìm chữ cái cuối cùng trong chuỗi, bạn có thể bị xui khiến để thử theo cách làm sau:

    int length = fruit.length(); 
    char last = fruit.charAt(length); // SAI!!

Cách này không có tác dụng. Lý do là không có chữ cái thứ 6 nào trong "banana". Vì ta đã bắt đầu đếm từ 0, nên sáu chữ cái trong chuỗi được đếm từ 0 tới 5. Để lấy chữ cái cuối cùng, ta phải trừ length đi một.

    int length = fruit.length(); 
    char last = fruit.charAt(length-1);

8.3  Duyệt chuỗi

Một công việc thường làm với một chuỗi là bắt đầu từ điểm đầu của chuỗi, lần lượt chọn từng kí tự, thực hiện một số thao tác đối với chữ cái đó, và công việc được tiếp diễn cho các chữ cái còn lại đến hết chuỗi. Kiểu xử lý như thế này được gọi là duyệt. Một cách tự nhiên để thực hiện việc duyệt là dùng vòng lặp while:

    int index = 0; 
    while (index < fruit.length()) { 
      char letter = fruit.charAt(index); 
      System.out.println(letter); 
      index = index + 1; 
    }

Vòng lặp này để duyệt chuỗi và hiển thị từng chữ cái trên một dòng riêng. Lưu ý điều kiện lặp là index < fruit.length(), nghĩa là khi index bằng với chiều dài của chuỗi, thì điều kiện bị vi phạm, và phần thân của vòng lặp không được thực hiện. Kí tự cuối cùng được truy cập đến sẽ tương ứng với chỉ số fruit.length()-1.

Tên của biến vòng lặp là index (có nghĩa là “chỉ số”). Một chỉ số là một biến hay giá trị được dùng để chỉ định một thành viên của một tập hợp được xếp thứ tự, trong trường hợp này là chuỗi các kí tự. Chỉ số có nhiệm vụ chỉ định thành viên nào bạn cần biết (vì vậy mà nó có tên “chỉ số”).

8.4  Lỗi thực thi

Trở về Mục 1.3.2 tôi đã nói tới các lỗi thực thi, những lỗi không xuất hiện đến tận khi chương trình bắt đầu chạn. Trong Java, những lỗi thực thi được gọi là các biệt lệ.

Có thể bạn không thấy nhiều lỗi thực thi, song vì ta chưa thực hiện nhiều thao tác có khả năng gây nên những lỗi loại này. Và bây giờ ta sẽ gây lỗi. Nếu bạn dùng phương thức charAt rồi cung cấp một chỉ số là số âm hoặc lớn hơn length-1, Java sẽ phát ra một biệt lệ. Bạn có thể hình dung việc “phát” biệt lệ cũng như phát ra một cơn giận dữ.

Khi điều này xảy đến, Java in ra một thông báo lỗi có ghi kiểu biệt lệ và một lần vết ngăn xếp, trong đó có biểu thị những phương thức đang hoạt động khi có biệt lệ xảy ra. Sau đây là một ví dụ:

public class BadString { 
  public static void main(String[] args) { 
    processWord("banana"); 
  } 
  public static void processWord(String s) { 
    char c = getLastLetter(s); 
    System.out.println(c); 
  } 
  public static char getLastLetter(String s) { 
    int index = s.length();    // SAI! 
    char c = s.charAt(index); 
    return c; 
  } 
}

Lưu ý rằng lỗi nằm trong getLastLetter: chỉ số của kí tự cuối cùng đáng ra phải là s.length()-1. Sau đây là kết quả bạn thu được:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
String index out of range: 6
        at java.lang.String.charAt(String.java:694)
        at BadString.getLastLetter(BadString.java:24)
        at BadString.processWord(BadString.java:18)
        at BadString.main(BadString.java:14)

Sau đó chương trình kết thúc. Lần vết ngăn xếp này có thể khó đọc, song nó chứa đựng rất nhiều thông tin.

8.5  Đọc tài liệu

Nếu bạn truy cập đến http://download.oracle.com/javase/6/docs/api/java/lang/String.html và kích chuột vào charAt, bạn sẽ xem được tài liệu sau đây (hoặc với nội dung tương tự):

public char charAt(int index)

Returns the char value at the specified index. An index ranges
from 0 to length() - 1. The first char value of the sequence is
at index 0, the next at index 1, and so on, as for array indexing.

Parameters: index - the index of the char value.

Returns: the char value at the specified index of this string.
  The first char value is at index 0.

Throws: IndexOutOfBoundsException - if the index argument is
  negative or not less than the length of this string.

Dòng đầu tiên là nguyên mẫu của phương thức, có nhiệm vụ quy định tên của phương thức, kiểu dữ liệu của các tham số cũng như kiểu trả lại.

Dòng tiếp theo miêu tả những công việc mà phương thức thực hiện. Các dòng sau đó giải thích các tham số và giá trị trả lại. Trong trường hợp này, việc giải thích là quá thừa, nhưng tài liệu luôn được thiết kế để phù hợp một dạng mẫu tiêu chuẩn. Còn dòng cuối cùng mô tả các biệt lệ mà phương thức này có thể phát ra.

Có lẽ bạn sẽ mất chút thời gian để làm quen với kiểu tài liệu thế này, nhưng thời gian công sức bỏ ra cũng đáng.

8.6  Phương thức indexOf

indexOf là phép nghịch đảo của charAtcharAt nhận vào một chỉ số rồi trả lại kí tự ở vị trí chỉ số đó; indexOf nhận một kí tự rồi tìm chỉ số mà kí tự đó xuất hiện.

charAt thất bại nếu chỉ số nằm ngoài phạm vi chuỗi, khi đó phương thức này sẽ phát biệt lệ. indexOf thất bại nếu kí tự không có mặt trong chuỗi, và trả lại giá trị -1.

    String fruit = "banana"; 
    int index = fruit.indexOf('a');

Đoạn mã lệnh này tìm chỉ số của chữ cái ’a’ trong chuỗi. Với trường hợp này, chữ cái nêu trên xuất hiện ba lần, nên ta chưa thấy ngay rằng indexOf nên làm gì. Nhưng theo tài liệu, thì phương thức này sẽ trả lại chỉ số của lần xuất hiện đầu tiên.

Để tìm các lần xuất hiện tiếp theo, còn có một dạng khác của indexOf. Nó nhận vào một đối số thứ hai quy định xem cần bắt đầu tìm kiếm từ vị trí nào trong chuỗi. Đây là một dạng quá tải toán tử, để biết thêm chi tiết, bạn hãy xem Mục 6.4.

Nếu ta kích hoạt:

   int index = fruit.indexOf('a', 2);

nó sẽ bắt đầu ở chữ cái số hai (chữ n đầu tiên) rồi tìm chữ a thứ hai, vốn có chỉ số là 3. Nếu tình cờ chữ cái đó xuất hiện ngay ở chỉ số khởi đầu, thì câu trả lời chính là chỉ số đầu này. Bởi vậy

    int index = fruit.indexOf('a', 5);

sẽ trả lại 5.

8.7  Lặp quay vòng và đếm

Chương trình dưới đây đếm số lần xuất hiện của chữ ’a’ trong một chuỗi:

    String fruit = "banana"; 
    int length = fruit.length(); 
    int count = 0; 
    int index = 0; 
    while (index < length) { 
      if (fruit.charAt(index) == 'a') { 
        count = count + 1; 
      } 
      index = index + 1; 
    } 
    System.out.println(count);

Chương trình này cho thấy một cách viết quen tay thông dụng, đó là một biến đếm. Biến count được khởi tạo bằng không và sau đó tăng thêm một ứng với mỗi lần ta tìm thấy một chữ ’a’. Việc tăng ở đây là chỉ tăng thêm một đơn vị; nó ngược lại với thao tác giảm. Khi ta thoát khỏi vòng lặp, count sẽ chứa kết quả, đó là tổng số các chữ a.

8.8  Các toán tử tăng và giảm

Tăng và giảm là những thao tác thông dụng đến nỗi Java có những toán tử riêng cho chúng. Toán tử ++ cộng thêm một vào giá trị hiện thời của một int hay char-- thì trừ đi một. Hai toán tử trên đều không có tác dụng đối với doubleboolean hay String.

Về khía cạnh kĩ thuật, sẽ hoàn toàn hợp lệ nếu ta tăng một biến rồi đồng thời sử dụng nó trong một biểu thức. Chẳng hạn, bạn có thể thấy lệnh kiểu như sau:

    System.out.println(i++);

Nhìn vào câu lệnh này, thật không rõ là liệu việc tăng sẽ tiến hành trước hay sau khi giá trị được in ra. Bởi vì những biểu thức thế này có xu hướng gây nhầm lẫn, tôi khuyên bạn nên hạn chế sử dụng chúng. Thậm chí, để hạn chế hơn nữa, tôi sẽ không nói cho bạn biết kết quả bằng bao nhiêu. Nếu thực sự muốn biết, bạn có thể thử xem.

Bằng cách dùng toán tử tăng, ta có thể viết lại mã lệnh đếm chữ:\

    int index = 0; 
    while (index < length) { 
      if (fruit.charAt(index) == 'a') { 
        count++; 
      } 
      index++; 
    }

Một lỗi sai thường gặp là viết lệnh kiểu như sau:

    index = index++; // SAI!!

Tuy nhiên, cách này lại hợp lệ về mặt cú pháp, nên trình biên dịch sẽ không cảnh báo bạn. Hiệu ứng của lệnh này là giữ nguyên giá trị của index. Đây thường là một lỗi khó tìm ra.

Hãy nhớ, bạn có thể viết index = index+1, hay index++, nhưng đừng trộn lẫn hai cách viết này.

8.9  String có tính không đổi

Như đã đọc tài liệu về các phương thức của String, có thể bạn phát hiện ra hai phương thức toUpperCase và toLowerCase. Hai phương thức này thường gây nhầm lẫn, vì chúng có tên gọi nghe như thể chúng có tác dụng thay đổi chuỗi hiện có. Song thực ra, chẳng có phương thức nào nói chung và hai phương thức này nói riêng, có thể thay đổi được chuỗi, vì chuỗi có tính không đổi.

Khi bạn kích hoạt toUpperCase đối với một String, bạn sẽ thu được một String mới làm kết quả trả lại. Chẳng hạn:

    String name = "Alan Turing"; 
    String upperName = name.toUpperCase();

Sau khi dòng lệnh thứ hai được thực thi, upperName sẽ chứa giá trị "ALAN TURING", còn name vẫn chứa "Alan Turing".

8.10  String có tính không so sánh được

Ta thường cần so sánh hai chuỗi để xem chúng có giống nhau không, hay chuỗi nào sẽ xếp trước theo thứ tự bảng chữ cái. Thật tuyệt nếu ta sử dụng được các toán tử so sánh như == và >, song ta không thể làm vậy.

Để so sánh các String, ta phải dùng các phương thức equals và compareTo. Chẳng hạn:

    String name1 = "Alan Turing"; 
    String name2 = "Ada Lovelace"; 
    if (name1.equals (name2)) { 
      System.out.println("hai tên này là một."); 
    } 
    int flag = name1.compareTo (name2); 
    if (flag == 0) { 
      System.out.println("Hai tên gọi này là một."); 
    } else if (flag < 0) { 
      System.out.println("tên 1 xếp trước tên 2."); 
    } else if (flag > 0) { 
      System.out.println("tên 2 xếp trước tên 1."); 
    }

Cú pháp ở đây hơi kì quặc. Để so sánh hai String, bạn phải kích hoạt một phương thức lên một chuỗi rồi truyền chuỗi còn lại làm tham số.

Giá trị trả về từ equals thật dễ hiểu; true nếu hai chuỗi có chứa cùng các kí tự, và false trong trường hợp còn lại.

Giá trị trả về từ compareTo lại kì quặc. Đó là khoảng cách giữa hai chữ cái đầu tiên có sự khác biệt ở hai chuỗi. Nếu hai chuỗi bằng nhau thì khoảng cách này bằng 0. Nếu chuỗi thứ nhất (chuỗi mà ta kích hoạt phương thức lên) đứng trước theo thứ tự bảng chữ cái, thì khoảng cách này có giá trị âm. Ngược lại, khoảng cách có giá trị dương. Trong trường hợp này, giá trị trả lại bằng 8, vì chữ cái thứ hai của “Ada” đi trước chữ cái thứ hai của “Alan” là 8 vị trí.

Để trọn vẹn, tôi cũng nói thật rằng việc dùng toán tử == đối với các Strings là hợp lệ nhưng ít khi đúng đắn. Tôi sẽ giải thích lí do trong Mục 13.4; song bây giờ thì chưa.

8.11  Thuật ngữ

đối tượng:
Một tập hợp các dữ liệu có liên quan cùng với một tập các phương thức hoạt động với nó. Các đối tượng mà ta dùng cho đến giờ gồm có String, Bug, Rock, và những đối tượng khác trong GridWorld.
chỉ số:
Một biến hay giá trị được dùng để chọn một trong các thành viên (phần tử) của một tập hợp được xếp thứ tự, như chọn kí tự từ một chuỗi.
biệt lệ:
Một lỗi khi thực thi chương trình.
phát:
Gây nên một biệt lệ.
lần vết ngăn xếp:
Một bản báo cáo cho thấy trạng thái chương trình khi có biệt lệ xảy ra.occurs.
nguyên mẫu:
Dòng đầu tiên của một phương thức, trong đó quy định tên, các tham số và kiểu trả lại.
duyệt:
Việc lặp qua tất cả mọi phần tử của một tập hợp nhằm thực hiện một công việc tương tự đối với từng phần tử.
biến đếm:
Một biến dùng để đếm thứ gì đó; biến này thường được khởi tạo bằng không sau đó tăng thêm.
tăng:
Việc tăng giá trị của biến thêm một đơn vị. Toán tử tăng trong Java là ++.
giảm:
Việc giảm giá trị của biến thêm đi đơn vị. Toán tử giảm trong Java là --.

8.12  Bài tập

Bài tập 1   Hãy viết một phương thức nhận vào một String làm đối số rồi in tất cả các chữ cái theo chiều ngược lại trên cùng một dòng.
Bài tập 2  Hãy đọc nội dung lần vết ngăn xếp ở Mục 8.4 rồi trả lời những câu hỏi sau:

  • Những loại biệt lệ nào đã xảy ra, và những biệt lệ này được định nghĩa trong các gói (package) nào?
  • Giá trị nào của chỉ số gây nên biệt lệ?
  • Phương thức nào phát ra biệt lệ, và phương thức đó được định nghĩa ở đâu?
  • Phương thức nào kích hoạt charAt?
  • Trong BadString.java, charAt được kích hoạt tại dòng số mấy?
Bài tập 3  Hãy bao bọc đoạn mã ở Mục 8.7 vào một phương thức có tên countLetters, sau đó khái quát hoá sao cho nó chấp nhận các đối số là chuỗi và chữ cái cần đếm. Tiếp theo, viết lại phương thức sao cho nó sử dụng indexOf để định vị các chữ a, thay vì kiểm tra từng chữ cái một.
Bài tập 4   Mục đích của bài tập này là ôn lại phép bao bọc và khái quát hoá.

  1. Hãy bao bọc đoạn mã lệnh sau, chuyển đổi nó thành một phương thức nhận vào đối số là một String rồi trả lại giá trị cuối cùng của count.
  2. Mô tả ngắn gọn công dụng của phương thức vừa lập nên (mà không đi vào chi tiết các bước thực hiện như thế nào).
  3. Bây giờ khi bạn đã khái quát hoá để mã lệnh hoạt động được với chuỗi bất kì rồi, bạn còn có thể khái quát hoá theo cách nào nữa?
    String s = "((3 + 7) * 2)"; 
    int len = s.length(); 
    int i = 0; 
    int count = 0; 
    while (i < len) { 
      char c = s.charAt(i); 
      if (c == '(') { 
        count = count + 1; 
      } else if (c == ')') { 
        count = count - 1; 
      } 
      i = i + 1; 
    } 
    System.out.println(count);
Bài tập 5   Mục đích của bài tập này là khám phá những kiểu dữ liệu trong Java và điền vào một số thông tin chi tiết chưa được đề cập đến trong chương này.

  1. Hãy tạo nên một chương trình mới có tên Test.java rồi viết một phương thức main có chứa những biểu thức có kết hợp nhiều kiểu dữ liệu bằng toán tử +. Chẳng hạn, điều gì sẽ xảy ra nếu bạn “cộng” một String và một char? Liệu nó có thực hiện tính tổng hay kết nối? Kiểu của kết quả sẽ là gì? (Bạn xác định được kiểu của kết quả như thế nào?)
  2. Hãy sao chép lại và mở rộng bảng dưới đây rồi điền vào nó. Trong từng ô giao cắt giữa hai kiểu dữ liệu, bạn cần phải xác định xem liệu có hợp lệ nếu dùng toán tử + với những kiểu này không, phép toán nào được thực hiện (cộng hay kết nối), và kiểu kết quả sẽ là gì.
    boolean char int String
    boolean
    char
    int
    String
  3. Hãy tưởng tượng xem các nhà thiết kế nên ngôn ngữ Java đã lựa chọn thế nào khi họ điền vào bảng trên. Trong số các ô điền, có bao nhiêu ô dường như là lựa chọn chắc chắn? Có bao nhiêu ô dường như là lựa chọn tuỳ ý mà có vài phương án tốt như nhau? Có bao nhiêu ô có vẻ còn chứa đựng vấn đề?
  4. Sau đây là một câu đố: thông thường, câu lệnh x++ đúng bằng x = x + 1. Nhưng nếu x là một char, thì nó sẽ không còn đúng! Trong trường hợp này, x++ là hợp lệ, nhưng x = x + 1 sẽ gây ra lỗi. Hãy thử lại và xem thông báo lỗi là gì, và sau đó xem liệu bạn có thể hình dung được điều gì đang diễn ra không.
Bài tập 6  Kết quả của chương trình dưới đây là gì? Bằng một câu, hãy mô tả xem mystery làm gì (chứ không phải các bước thực hiện ra sao).

public class Mystery { 
  public static String mystery(String s) { 
    int i = s.length() - 1; 
    String total = ""; 
    while (i >= 0 ) { 
      char ch = s.charAt(i); 
      System.out.println(i + " " + ch); 
      total = total + ch; 
      i--; 
    } 
    return total; 
  } 
  public static void main(String[] args) { 
    System.out.println(mystery("Allen")); 
  } 
}
Bài tập 7   Một người bạn cho bạn xem phương thức sau đây và diễn giải rằng nếu number là số có hai chữ số bất kì, thì chương trình sẽ in các chữ số theo chiều ngược lại. Người ấy khẳng định rằng nếu number là 17, thì phương thức sẽ cho ra kết quả bằng 71. Liệu người đó có đúng không? Nếu không, hãy giải thích chương trình thực sự làm gì và sửa chữa để nó cho kết quả đúng.

    int number = 17; 
    int lastDigit = number%10; 
    int firstDigit = number/10; 
    System.out.println(lastDigit + firstDigit);
Bài tập 8   Kết quả của chương trình sau là gì?

public class Enigma { 
  public static void enigma(int x) { 
    if (x == 0) { 
      return; 
    } else { 
      enigma(x/2); 
    } 
    System.out.print(x%2); 
  } 
  public static void main(String[] args) { 
    enigma(5); 
    System.out.println(""); 
  } 
}

Hãy giải thích ngắn gọn bằng 4-5 từ xem phương thức enigma thực sự làm điều gì.

Bài tập 9  

  1. Hãy lập một chương trình mới có tên Palindrome.java.
  2. Viết một phương thức có tên first nhận vào một String rồi trả lại chữ cái đầu tiên, và một phương thức last để trả lại chữ cái cuối cùng.
  3. Viết một phương thức có tên  middle nhận vào một String rồi trả lại một chuỗi con có chứa mọi thứ trừ hai chữ cái đầu và cuối. Gợi ý: hãy đọc tài liệu về phương thức substring trong lớp String. Hãy chạy một vài phép thử để chắc rằng bạn hiểu rõ cách hoạt động của substring trước khi thử viết middle. Điều gì sẽ xảy ra nếu bạn kích hoạt middle lên một chuỗi chỉ có hai chứ cái? Một chữ cái? Không có chữ cái nào?
  4. Cách định nghĩa thông thường của một palindrome là một từ mà đọc xuôi ngược đều giống nhau, chẳng hạn “otto” và “palindromeemordnilap.” Một cách khác để định nghĩa một thuộc tính như thế baft là quy định một cách kiểm tra thuộc tính đó. Chẳng hạn, ta có thể nói “một chữ cái là một palindrome, và một từ hai chữ là một palindrome nếu hai chữ cái của nó giống nhau, và một từ bất kì khác là một palindrome nếu chữ cái đầu giống chữ cái cuối và khúc giữa cũng là một palindrome.” Hãy viết một phương thức đệ quy có tên isPalindrome nhận vào một String và trả lại một boolean cho biết từ đó có phải là palindrome hay không.
  5. Một khi bạn đã có đoạn mã để kiểm tra palindrome, hãy tìm cách đơn giản hoá nó bằng cách giảm số điều kiện trong phép kiểm tra. Gợi ý: việc lấy định nghĩa chuỗi rỗng cũng là palindrome có thể giúp ích.
  6. Hãy viết ra trên giấy một chiến lược có tính lặp để kiểm tra palindrome. Có một số phương án khả dĩ, bởi vậy bạn hãy đảm bảo chắc chắn một kế hoạch rõ ràng trước khi bắt đầu viết mã lệnh.
  7. Hãy tạo lập chiến lược bạn chọn thành một phương thức có tên isPalindromeIter.
  8. Câu hỏi phụ: Phụ lục B có mã lệnh để đọc một danh sách các từ vựng từ một file. Hãy đọc một danh sách các từ rồi in ra những palindrome.
Bài tập 10  Một từ được gọi là “abecedarian” nếu các chữ cái trong từ đó xuất hiện theo thứ tự bảng chữ cái. Chẳng hạn, sau đây là tất cả những từ abecedarian gồm 6 chữ cái trong tiếng Anh.

abdest, acknow, acorsy, adempt, adipsy, agnosy, befist, behint, beknow, bijoux, biopsy, cestuy, chintz, deflux, dehors, dehort, deinos, diluvy, dimpsy

  1. Hãy miêu tả một quy trình kiểm tra xem một từ (String) cho trước là abecedarian hay không, nếu coi rằng từ đó chỉ gồm các chữ cái thường. Quy trình này có thể mang tính lặp hay đệ quy.
  2. Tạo dựng quy trình trên thành một phương thức mang tên isAbecedarian.
Bài tập 11   Một dupledrome là một từ chỉ chứa các chữ cái ghép đôi, chẳng hạn như “llaammaa” hay “ssaabb”. Tôi đề ra giả thiết ràng trong tiếng Anh thông dụng không hề có dupledrome nào. Để kiểm chứng giả thiết đó, tôi muốn có chương trình đọc lần lượt các từ vựng từ một cuốn từ điển rồi kiểm tra xem từ đó có phải là dupledrome hay không. Hãy viết một phương thức mang tên isDupledrome nhận vào một String rồi trả lại một boolean để cho biết từ đó có phải là dupledrome không.
Bài tập 12

  1. Vòng giải mã Captain Crunch hoạt động bằng cách lấy mỗi chữ cái trong một chuỗi rồi cộng 13 vào nó. Chẳng hạn, ’a’ trở thành ’n’ và ’b’ trở thành ’o’. Đến cuối, các chữ cái “quay vòng lại”, bởi vậy ’z’ trở thành ’m’. Hãy viết một phương thức nhận vào một String rồi trả lại một String mới có chứa chuỗi sau mã hoá. Bạn cần coi ràng String ban đầu chỉ chứa các chữ in, chữ thường, dấu cách, mà không có dấu chấm phẩy gì khác. Các chữ thường thì được mã hoá thành chữ thường, chữ in thành chữ in. Bạn không được mã hoá  các dấu cách.
  2. Hãy khái quát hoá phương thức Captain Crunch sao cho thay vì cộng 13 vào từng chữ cái, nó có thể cộng thêm bất kì số nào. Bây giờ bạn có thể mã hoá bằn cách cộng 13 rồi giải mã bằng cách cộng -13. Hãy thử làm điều này.
Bài tập 13    Nếu bạn đã giải các bài tập GridWorld trong Chương 5, có thể bạn sẽ thích bài tập này. Mục đích là dùng toán lượng giác để khiến các con bọ (Bug) đuổi bắt lẫn nhau. Hãy sao chép file BugRunner.java thành ChaseRunner.java rồi nhập nó vào môi trường phát triển của bạn. Trước khi thay đổi bất cứ điều gì, hãy kiểm tra đảm bảo rằng bạn biên dịch và chạy được chương trình.

  • Tạo nên hai Bug, một con màu đỏ và một màu xanh lam.
  • Viết một phương thức mang tên distance nhận vào hai Bug rồi tính khoảng cách giữa chúng. Hãy nhớ rằng bạn có thể lấy được toạ độ x của một Bug như sau:
    int x = bug.getLocation().getCol();
  • Viết một phương thức mang tên turnToward nhận vào hai Bug rồi quay mặt một con hướng đến con kia. GỢI Ý: dùng Math.atan2, nhưng hãy nhớ rằng kết quả theo đơn vị radian, bởi vậy bạn phải chuyển sang độ. Ngoài ra, đối với Bug, 0 độ là hướng Bắc chứ không phải hướng Đông.
  • Viết một phương thức mang tên moveToward nhận vào hai Bug, quay mặt con thứ nhất về phía con thứ hai, rồi di chuyển con thứ nhất, nếu có thể.
  • Viết một phương thức mang tên moveBugs nhận hai Bug và một số nguyên n, rồi di chuyển một con Bug về phía con kia n lần. Bạn có thể viết phương thức này theo cách đệ quy, hoặc dùng một vòng lặp while.
  • Kiểm tra từng phương thức vừa viết ở trên ngay khi bạn phát triển chúng. Khi chúng đều hoạt động được, hãy tìm mọi cơ hội cải thiện. Chẳng hạn, nếu bạn có mã lệnh dư thừa trong distance và turnToward, thì bạn có thể bao bọc đoạn mã lệnh lặp lại vào trong một phương thức.

5 phản hồi

Filed under Think Java

Chương 5: Grid World, phần 1

Trở về Mục lục cuốn sách

5.1  Khởi động

Bây giờ đã đến lúc ta bắt đầu làm Nghiên cứu cụ thể về kì thi Khoa học máy tính AP; nghiên cứu này xoay quanh một chương trình có tên GridWorld. Đầu tiên, hãy cài đặt GridWorld; bạn có thể tải chương trình này về từ Hội đồng tuyển sinh Hoa Kì: http://www.collegeboard.com/student/testing/ap/compsci_a/case.html.

Khi giải nén mã nguồn này, bạn sẽ thu được một thư mục mang tên GridWorldCode trong đó chứa projects/firstProject, và bản thân thư mục này lại chứa BugRunner.java. Tiếp tục đọc

22 phản hồi

Filed under Think Java