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.

Lời định nghĩa lớp sẽ trông như sau:

class Deck { 
  Card[] cards; 

  public Deck(int n) { 
    this.cards = new Card[n]; 
  } 
}

Ở đây, constructor khởi tạo biến thực thể là một mảng những lá bài, nhưng nó không tạo nên lá bài nào. Sau đây là sơ đồ trạng thái cho thấy Deck mà không có lá bài nào kèm theo:

Dưới đây là một constructor không có đối số để tạo nên một cỗ bài 52 lá rồi điền đầy những đối tượng Card vào nó:

  public Deck() { 
    this.cards = new Card[52]; 
    int index = 0; 
    for (int suit = 0; suit <= 3; suit++) { 
      for (int rank = 1; rank <= 13; rank++) { 
        cards[index] = new Card(suit, rank); 
        index++; 
      } 
    } 
  }

Phương thức này tương tự như makeDeck; ta chỉ việc thay đổi cú pháp để nó trở thành một constructor. Để kích hoạt nó, ta dùng new:

    Deck deck = new Deck();

Bây giờ việc đặt các phương thức thuộc về các đối tượng Deck vào trong lời định nghĩa lớp Deck là hợp lý. Khi xem xét những phương thức mà ta đã viết cho đến giờ, dễ thấy một ứng cử viên đó là printDeck (Mục 13.7). Sau đây là dáng vẻ của nó, được viết lại để hoạt động với Deck:

  public static void printDeck(Deck deck) { 
    for (int i = 0; i < deck.cards.length; i++) { 
      Card.printCard(deck.cards[i]); 
    } 
  }

Một sự thay đổi là kiểu của tham số, từ Card[] sang Deck.

Thay đổi thứ hai là ta không còn dùng được deck.length để lấy chiều dài của mảng, bởi giờ đây deck đã là một đối tượng Deck, chứ không phải một mảng. Nó chứa một mảng, nhưng nó không phải là mảng. Bởi v ậy ta phải viết deck.cards.length để kết xuất được mảng từ đối tượng Deck rồi lấy chiều dài của mảng này.

Với lý do tương tự, ta phải dùng deck.cards[i] để truy cập một phần tử của mảng, thay vì chỉ viết deck[i].

Sự thay đổi cuối cùng là việc kích hoạt printCard phải nói rõ rằng printCard được định nghĩa trong lớp Card.

14.2  Tráo bài

Trong phần lớn các trò chơi bài tây, bạn cần phải tráo cỗ bài; nghĩa là xếp bài theo một trật tự ngẫu nhiên. Ở Mục 12.6 ta đã thấy cách phát sinh số ngẫu nhiên, song thật không dễ thấy cách áp dụng để tráo cỗ bài.

Một khả năng là mô phỏng cách con người tráo bài, thường là chia cỗ bài làm đôi rồi chọn bài đan xen từ từng phần. Bởi người thường không thể tráo chính xác theo cách này được, nên sau chừng 7 lần lặp lại thao tác thì cỗ bài dường như đã hoàn toàn ngẫu nhiên. Song một chương trình máy tính thì lại có đặc điểm luôn trộn bài thật hoàn hảo nên kết quả sẽ không thật ngẫu nhiên. Thực tế là, sau 8 lần trộn, máy sẽ làm cho cỗ bài về nguyên trạng. Bạn có thể xem thông tin thêm ở http://en.wikipedia.org/wiki/Faro_shuffle.

Một thuật toán trộn bài hợp lý hơn là trong mỗi lần duyệt chỉ lật một lá bài, và mỗi lần lặp thì chọn lấy hai lá bài rồi đổi chỗ chúng.

Sau đây là phác thảo cách hoạt động của thuật toán này. Để phác họa chương trình, tôi kết hợp câu lệnh Java với ngôn ngữ nói, mà đôi khi được gọi là giả mã:

    for (int i = 0; i < deck.cards.length; i++) { 
      // chọn một số nằm giữa 1 và deck.cards.length-1 
      // đổi chỗ lá bài thứ i và lá bài ngẫu nhiên được chọn
    }

Điều hay ở giả mã là nó thường làm rõ những phương thức nào mà bạn sắp cần có. Trong trường hợp này, ta cần một thứ như randomInt, để chọn một số nguyên ngẫu nhiên giữa low và high, và swapCards để nhận vào hai chỉ số rồi đổi chỗ hai lá bài ở vị trí các chỉ số đó.

Quá trình này—viết giả mã trước rồi mới viết phương thức thực hiện sau—được gọi là phát triển từ trên xuống (xem http://en.wikipedia.org/wiki/Top-down_and_bottom-up_design).

14.3  Sắp xếp

Bây giờ khi đã làm cỗ bài lẫn lung tung lên, ta cần một cách khiến nó trở lại trật tự. Có một thuật toán sắp xếp giống với thuật toán trộn đến không ngờ. Nó được gọi là sắp xếp chọn bởi nó hoạt động dựa trên việc duyệt mảng lặp đi lặp lại và mỗi lần duyệt thì chọn lấy lá bài thấp nhất còn lại.

Trong lần lặp thứ nhất, ta tìm lấy lá bài thấp nhất rồi đổi chỗ cho lá bài ở vị trí thứ 0. Trong lần lặp thứ i, ta tìm lấy lá bài thấp nhất bên phải vị trí i rồi đổi chỗ nó cho lá bài thứ i.

Sau đây là giả mã cho cách sắp xếp chọn:

    for (int i = 0; i < deck.cards.length; i++) { 
      // tìm lấy lá bài thấp nhất tại vị trí i, hoặc bên phải chỗ đó
      // đổi chỗ lá bài thứ i với lá bài thấp nhất tìm được }

Một lần nữa, giả mã giúp cho việc thiết kế các phương thức trợ giúp. Trong trường hợp này, ta có thể dùng  lại swapCards, bởi vậy ta chỉ cần có một phương thức mới, có tên indexLowestCard, để nhận một mảng những lá bài và một chỉ số nơi cần bắt đầu tìm kiếm.

14.4  Cỗ bài con

Vậy ta nên biểu diễn một phần bài hay một dạng tập con của cỗ bài đủ như thế nào? Một khả năng là tạo nên một lớp mới có tên Hand, và nó có thể mở rộng Deck. Một khả năng khác, như tôi trình bày ở đây, là biểu diễn một phần bài bằng đối tượng Deck nhưng có ít hơn 52 lá bài.

Ta có thể muốn một phương thức, subdeck, để nhận một cỗ bài và một khoảng chỉ số, rồi trả lại một cỗ bài mới chứa tập con những lá bài đã chỉ định:

  public static Deck subdeck(Deck deck, int low, int high) { 
    Deck sub = new Deck(high-low+1); 
    for (int i = 0; i<sub.cards.length; i++) { 
      sub.cards[i] = deck.cards[low+i]; 
    } 
    return sub; 
  }

Chiều dài của cỗ bài con là high-low+1 bởi cả lá bài thấp (low) lẫn cao (high) đều được tính vào. Cách tính có thể gây nhầm lẫn, và dẫn đến lỗi “lệch một”. Cách tránh lỗi này tốt nhất thường là vẽ hình minh họa.

Vì ta đã cung cấp new vào một đối số, nên contructor được kích hoạt sẽ là cái đầu tiên, vốn chỉ huy động mảng mà không huy động bất kì lá bài nào. Bên trong vòng lặp for, cỗ bài con được điền đầy những bản sao tham chiếu từ cỗ bài lớn.

Dưới đây là sơ đồ trạng thái của cỗ bài con được tạo nên bằng những tham số low=3 và high=7. Kết quả là một phần bài gồm 5 lá được chung với cỗ bài ban đầu; nghĩa là theo cách đặt bí danh (alias).

Cách đặt bí danh này thường không phải ý tưởng hay, bởi những thay đổi trong một cỗ bài con lại được thể hiện ở những cỗ khác; đây không phải là động thái mà bạn trông đợi ở những bộ bài thật. Song nếu các lá bài là đối tượng không thay đổi được, thì việc đặt bí danh ít nguy hiểm hơn. Trong trường hợp này, có lẽ chẳng có lý do nào để thay đổi bậc hay chất của lá bài. Thay vì vậy, ta có thể mỗi lúc lại tạo ra một lá bài rồi coi nó như một đối tượng không thay đổi được. Bởi vậy, đối với Card, việc đặt bí danh là lựa chọn hợp lý.

14.5  Tráo bài và chia bài

Ở Mục 14.2, tôi đã viết giả mã cho thuật toán trộn bài. Coi như ta đã có một phương thức shuffleDeck nhận tham số là một cỗ bài rồi trộn nó lên, ta có thể sử dụng nó để chia thành nhiều phần bài:

    Deck deck = new Deck(); 
    shuffleDeck(deck); 
    Deck hand1 = subdeck(deck, 0, 4); 
    Deck hand2 = subdeck(deck, 5, 9); 
    Deck pack = subdeck(deck, 10, 51);

Mã lệnh này đặt 5 lá bài đầu tiên vào phần thứ nhất, 5 lá bài kế tiếp vào phần thứ hai, và phần còn lại giữ ở cỗ.

Khi bạn hình dung cách chia bài, bạn có nghĩ rằng ta nên chia vòng tròn như đánh bài thật không? Tôi cũng nghĩ về điều này, song nhận thấy rằng với chương trình máy tính thì như vậy không cần thiết. Quy tắc chia vòng tròn chỉ để giảm thiểu khả năng tráo bài chưa kĩ và để cho người chia khó chơi ăn gian hơn. Hai điều này không thành vấn đề đối với máy tính.

Ví dụ này là lời nhắc hở hữu ích về một trong những nguy hiểm của phép ẩn dụ trong kĩ thuật: đôi khi ta quy định những hạn chế không cần thiết lên máy tính, hoặc trông chờ những tính năng không có sẵn, bởi ta đã không suy nghĩ khi mở rộng một hình ảnh ẩn dụ vượt quá giới hạn của nó rồi.

14.6  Sắp xếp trộn

Ở Mục 14.3, ta đã thấy một thuật toán sắp xếp đơn giản nhưng hóa ra không hiệu quả. Để sắp xếp n phần tử, nó phải duyệt mảng n lần, và mỗi lần duyệt tốn một khoảng thời gian tỉ lệ với n. Do đó, thời gian tổng cộng sẽ tỉ lệ với n².

Trong mục này tôi phác thảo một thuật toán hiệu quả hơn, có tên gọi sắp xếp trộn. Để sắp xếp n phần tử, phương pháp này tốn một thời gian tỉ lệ với n logn. Như vậy có vẻ chưa ấn tượng lắm, song khi n lớn lên, hiệu số giữa n² và n logn có thể sẽ rất lớn. Hãy thử vài giá trị của n xem sao.

Ý tưởng cơ bản phía sau phép sắp xếp trộn là thế này: Nếu bạn có 2 phần bài, từng phần đã được sắp xếp rồi, thì rất dễ (và nhanh chóng) để trộn ghép chúng thành một cỗ bài duy nhất được sắp xếp đúng. Hãy thử làm điều này với một cỗ bài xem sao:

1. Hình thành hai phần bài với mỗi phần khoảng 10 lá rồi sắp xếp chúng để cho khi đặt ngửa mặt lên thì các lá bài thấp ở trên. Đặt hai phần bài này trước mặt bạn.
2. So sánh hai lá bài ở trên cùng của mỗi phần rồi chọn lá bài thấp hơn. Lật úp nó rồi đưa nó vào phần bài riêng được sắp xếp.
3. Lặp lại bước Hai đến khi một phần bài đã hết. Sau đó lấy những lá bài còn lại rồi thêm vào phần bài được sắp xếp.

Kết quả ta sẽ được một phần bài chung được xếp đúng. Sau đây là cách làm bằng giả mã:

  public static Deck merge(Deck d1, Deck d2) { 
    // tạo nên một cỗ bài đủ lớn chứa hết các quân bài  
    Deck result = new Deck(d1.cards.length + d2.cards.length); 
    // dùng chỉ số i để theo dõi vị trí hiện tại trên
    // phần bài thứ nhất, và chỉ số j cho phần bài thứ hai 
    int i = 0; 
    int j = 0; 
    // chỉ số k duyệt theo phần bài được xếp đúng 
    for (int k = 0; k < result.cards.length; k++) { 
      // nếu d1 rỗng thì d2 thắng; nếu d2 rỗng, d1 thắng;
      // nếu không, đi so sánh hai lá bài 
      // thêm lá bài thắng vào phần bài được xếp đúng 
    } 
    return result; 
}

Cách hay nhất để kiểm tra merge là lập nên và trộn một cỗ bài, dùng phương thức subdeck để hình thành nên hai phần bài (nhỏ), rồi dùng thủ tục sort từ chương trước để sắp xếp hai nửa. Sau đó bạn có thể truyền hai nửa này vào merge để xem phương thức mới này có hoạt động không.

Nếu bạn có thể làm cho mọi thứ như trên hoạt động được, hãy thử một phiên bản mergeSort đơn giản:

  public static Deck mergeSort(Deck deck) { 
    // tìm điểm giữa của cỗ bài 
    // chia cỗ bài thành hai phần nhỏ 
    // xếp phần nhỏ bằng sortDeck 
    // trộn hai nửa rồi trả lại kết quả 
  }

Sau đó, nếu như bạn làm cho phương thức hoạt động được, sẽ có cái hay! Điều kì diệu về sắp xếp trộn là nó có tính đệ quy. Ở lúc mà bạn bắt đầu sắp xếp các phần bài, tại sao phải kích hoạt phương thức sort cũ và chậm chạp? Sao không kích hoạt phương thức mergeSort mới toanh, đang được viết?

Đây không chỉ là một ý tưởng tốt, mà cần thiết phải đạt được ưu thế về hiệu năng của chương trình mà tôi đã hứa. Nhưng để chương trình hoạt động, bạn cần phải có một trường hợp cơ sở. Nếu không, đệ quy sẽ mãi mãi. Một trường hợp cơ sở đơn giản là một phần bài với 0 hoặc 1 lá bài. Nếu như mergesort nhận được một phần bài nhỏ như vậy, thì nó có thể trả lại kết quả y nguyên, bởi phần bài nhỏ này đã được sắp xếp.

Phiên bản đệ quy của mergesort có thể sẽ trông như sau:

  public static Deck mergeSort(Deck deck) { 
    // nếu cỗ bài chỉ gồm 0 hoặc 1 lá bài, thì trả lại nó 
    // tìm ra điểm giữa của cỗ bài 
    // chia cỗ bài thành hai phần bài
    // sắp xếp các phần bài này bằng mergesort 
    // trộn ghép lại hai nửa rồi trả lại kết quả 
  }

Như thường lệ, có hai cách nghĩ về chương trình đệ quy: Bạn có thể nghĩ qua toàn bộ luồng thực thi, hay bạn có thể dựa vào “niềm tin” (xem Mục 6.9). Tôi đã xây dựng ví dụ này để khuyến khích bạn tư duy theo niềm tin như vậy.

Khi dử dụng sortDeck để sắp xếp các phần bài, bạn không thấy bị thôi thúc phải theo luồng thực thi, phải không? Bạn chỉ việc giả sử rằng nó hoạt động được vì bạn đã gỡ lỗi cho nó rồi. Ồ, tất cả những điều mà bạn đã làm cho mergeSort trở nên đệ quy là thay thế một thuật toán sắp xếp này với thuật toán khác. Không có lý do gì để đọc chương trình khác đi cả.

Thực ra, bạn phải nghĩ một chút mới lập được trường hợp cơ sở đúng đắn và đảm bảo rằng cuối cùng bạn sẽ đạt đến trường hợp cơ sở này. Song ngoài điều đó ra, việc viết nên phiên bản đệ quy hẳn sẽ không còn vấn đề nữa. Chúc bạn may mắn!

14.7  Biến lớp

Đến giờ ta đã thấy những biến địa phương, vốn được khai báo bên trong phương thức, và biến thực thể, vốn được khai báo ở lời định nghĩa lớp, thường đi trước các định nghĩa phương thức.

Các biến địa phương được tạo nên khi một phương thức được kích hoạt và phá hủy khi phương thức kết thúc. Các biến thực thể được tạo nên khi bạn tạo nên một đối tượng; các biến này bị phá hủy khi đối tượng bị thu hồi rác bộ nhớ.

Bây giờ là lúc biết về biến lớp. Giống như biến thực thể, biến lớp được định nghĩa trong một lời định nghĩa lớp trước những định nghĩa phương thức, song chúng được nhận diện bằng từ khóa static. Chúng được tạo nên khi chương trình khởi đầu và còn tồn tại đến tận khi chương trình kết thúc.

Bạn có thể tham chiếu tới biên thực thể từ bất kì đâu bên trong lời khai báo lớp. Những biến lớp thường được dùng để lưu các giá trị hằng số cần thiết ở nhiều chỗ.

Lấy ví dụ, sau đây là một phiên bản của Card trong đó suits và ranks là những biến lớp:

class Card { 
  int suit, rank; 
  static String[] suits = { "Clubs", "Diamonds", "Hearts", "Spades" }; 
  static String[] ranks = { "narf", "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King" }; 

  public static void printCard(Card c) { 
    System.out.println(ranks[c.rank] + " of " + suits[c.suit]); 
  } 
}

Bên trong printCard ta có thể tham chiếu tới suits và ranks như thể chúng là các biến địa phương.

14.8  Thuật ngữ

giả mã:

Một cách thiết kế chương trình bằng cách viết các bản nháp kết hợp ngôn ngữ nói và Java.

phương thức trợ giúp:

Thường là một phương thức nhỏ chẳng làm nhiều điều có ích, song phương thức này trợ giúp một phương thức khác có ích hơn.

biến lớp:

Một biến được khai báo trong lớp theo dạng static; luôn chỉ có một bản sao của biến này tồn tại.

14.9  Bài tập

Bài tập 1   Mục đích của bài tập này là thi hành các thuật toán tráo bài và sắp xếp trong chương.

1. Hãy tải về mã lệnh cho chương này từ http://thinkapjava.com/code/Card2.java rồi nhập nó vào môi trường phát triển đang dùng. Tôi đã cung cấp phần khung của những phương thức mà bạn sẽ viết, do vậy mà chương trình sẽ được biên dịch thông suốt. Nhưng khi chạy, nó sẽ in các dòng thông báo cho biết rằng những phương thức rỗng chưa làm việc được. Khi bạn hoàn thành hết các phương thức này, những lời thông báo đó sẽ biến mất.
2. Nếu đã làm Bài tập 3 trong Chương 12, bạn đã viết randomInt. Nếu không, bây giờ hãy viết phương thức này rồi thêm vào mã lệnh để kiểm tra.
3. Hãy viết một phương thức có thên swapCards để nhận vào một cỗ bài (mảng chứa những quân bài) cùng hai chỉ số, rồi đổi chỗ hai lá bài ở những vị trí đó. GỢI Ý: phương thức này phải đổi chỗ tham chiếu, chứ không phải nội dung của các đối tượng. Việc này nhanh hơn; đồng thời cũng xử lý đúng trường hợp các lá bài cùng tham chiếu đến một đối tượng (tức “đặt bí danh”).
4. Viết một phương thức có tên shuffleDeck để dùng thuật toán trong Mục 14.2. Có thể bạn sẽ muốn dùng phương thức randomInt từ Bài tập 3 Chương 12.
5. Viết một phương thức có tên indexLowestCard để dùng phương thức compareCard nhằm tìm kiếm lá bài thấp nhất trong một khoảng cho trước của cỗ bài (từ lowIndex đến highIndex, kể cả hai đầu).
6. Viết một phương thức có tên sortDeck để sắp xếp cỗ bài từ thấp lên cao.
7. Dùng giả mã trong Mục 14.6, hãy viết phương thức có tên merge. Đảm bảo rằng bạn kiểm tra nó trước khi dùng nó làm một phần trong mergeSort.
8. Viết một dạng đơn giản của mergeSort, dạng chia cỗ bài làm đôi, rồi dùng sortDeck để sắp xếp hai nửa, và dùng merge để tạo nên cỗ bài mới, sắp xếp đúng.
9. Viết một dạng đệ quy hoàn chỉnh của mergeSort. Nhớ rằng sortDeck là một phương thức sửa đổi còn mergeSort là một hàm; như vậy chúng được kích hoạt theo cách khác nhau:

   sortDeck(deck); // sửa đổi cỗ bài sẵn có
   deck = mergeSort(deck); // thay thế cỗ bài cũ bằng cỗ mới