Chương 12: Mảng

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

Mảng là một tập hợp các giá trị trong đó mỗi giá trị được xác định bởi một chỉ số. Bạn có thể lập nên các mảng int, mảng double, hay mảng chứa bất kì kiểu dữ liệu nào khác, nhưng các giá trị trong cùng một mảng phải có kiểu giống nhau.

Về mặt cú pháp, các kiểu mảng trông giống như các kiểu dữ liệu khác trong Java chỉ trừ đặc điểm: theo sau là []. Chẳng hạn, int[] là kiểu “mảng các số nguyên” còn double[] là kiểu “mảng các số phẩy động.”

Bạn có thể khai báo các biến với những kiểu như vậy theo cách thông thường:

    int[] count; 
    double[] values;

Trước khi bạn khởi tạo các biến này, chúng được đặt về null. Để tự tay tạo các mảng, hãy dùng new.

    count = new int[4]; 
    values = new double[size];

Lệnh gán thứ nhất khiến cho count tham chiếu đến một mảng gồm 4 số nguyên; lệnh thứ hai tham chiếu khiến values tham chiếu đến một mảng các double. Số phần tử trong values phụ thuộc vào size. Bạn có thể dùng bất kì biểu thức nguyên nào để làm kích thước mảng.

Hình vẽ sau cho thấy cách biểu diễn mảng trong sơ đồ trạng thái:

Các số lớn ghi bên trong các ô là những phần tử của mảng. Các con số nhỏ bên ngoài hộp là những chỉ số dùng để xác định từng ô. Khi bạn huy động một mảng các int, những phần tử của chúng đều được khởi tạo bằng không.

12.1  Truy cập các phần tử

Để lưu các giá trị trong mảng, hãy dùng toán tử [] operator. Chẳng hạn, count[0] tham chiếu đến phần tử “thứ không” của mảng, còn count[1] tham chiếu đến phần tử “thứ một”. Bạn có thể dùng toán tử [] bất cứ đâu trong một biểu thức:

    count[0] = 7; 
    count[1] = count[0] * 2; 
    count[2]++; 
    count[3] -= 60;

Tất cả đó đều là những phép gán hợp lệ. Sau đây là kết quả của đoạn mã trên:

Những phần tử của mảng được đánh số từ 0 tới 3, nghĩa là không có phần tử nào mang chỉ số 4. Điều này rất quen thuộc, bởi ta đã thấy điều tương tự trong chỉ số của String. Dù vậy, việc vượt quá phạm vi của mảng vẫn là kiểu lỗi thường gặp, bằng cách đó phát ra biệt lệ ArrayOutOfBoundsException.

Bạn có thể dùng bất kì biểu thức nào làm chỉ số cũng được, miễn là nó có kiểu int. Một trong những cách thông dụng nhất để đánh chỉ số của mảng là dùng biến vòng lặp. Chẳng hạn:

    int i = 0; 
    while (i < 4) { 
      System.out.println(count[i]); i++; 
    }

Đây là một vòng lặp while tiêu chuẩn để đếm từ 0 lên 4, và khi biến lặp i bằng 4, điều kiện lặp sẽ không thỏa mãn và vòng lặp kết thúc. Như vậy, phần thân vòng lặp chỉ được thực thi khi i là 0, 1, 2 và 3.

Mỗi lần qua vòng lặp ta dùng i làm chỉ số trong mảng, để in ra phần tử thứ i. Hình thức duyệt mảng này rất thông dụng.

12.2  Sao chép mảng

Khi bạn sao chép một biến mảng, hãy nhớ rằng bạn đang sao chép tham chiếu tới mảng. Ví dụ:

    double[] a = new double [3]; 
    double[] b = a;

Đoạn mã lệnh này tạo nên một mảng ba số double, rồi đặt hai biến khác nhau để tham chiếu tới nó. Trường hợp này cũng là một dạng trùng tên (aliasing).

Bất kì thay đổi nào đối với một trong hai mảng đều được phản ánh trên mảng còn lại. Thường thì đây không phải là điều bạn muốn; mà bạn muốn huy động một mảng mới rồi sao chép các phần tử từ mảng này sang mảng kia.

    double[] b = new double [3]; 
    int i = 0; 
    while (i < 4) { 
      b[i] = a[i]; i++; 
    }

12.3  Mảng và đối tượng

Mảng giống với đối tượng ở nhiều điểm:

  • Khi khai báo một biến mảng, bạn nhận được tham chiếu đến mảng.
  • Bạn phải dùng new để tự tạo ra mảng.
  • Khi truyền mảng làm đối số, bạn truyền một tham chiếu, nghĩa là phương thức được kích hoạt có thể thay đổi nội dung của mảng.

Một số đối tượng mà ta đã xét, như Rectangle, tương đồng với mảng ở chỗ chúng cũng là tập hợp các giá trị. Vậy nảy sinh câu hỏi, “Mảng bốn số nguyên thì khác một đối tượng Rectangle ở chỗ nào?”

Nếu bạn quay về định nghĩa của “mảng” từ đầu chương, bạn sẽ thấy một khác biệt: các phần tử của mảng được xác định bằng chỉ số, còn các phần tử của đối tượng xác định bằng tên.

Một khác biệt nữa là các phần tử trong mảng phải có cùng kiểu. Còn đối tượng có thể chứa những biến thực thể khác kiểu nhau.

12.4 Vòng lặp for

Các vòng lặp mà ta đã dùng đều có một số điểm chung. Chúng đều bắt đầu bằng việc khởi tạo một biến; chúng đều có một phép kiểm tra, hay điều kiện, phụ thuộc vào biến đó; và bên trong vòng lặp thì chúng thực hiện tác động nhất định đến biến đó, như tăng giá trị.

Dạng vòng lặp này thông dụng đến nỗi còn một lệnh lặp khác, gọi là for, để diễn đạt một cách gọn gàng hơn. Cú pháp chung của nó như sau:

    for (KHỞI TẠO; ĐIỀU KIỆN; GIA TĂNG) { 
      PHẦN THÂN 
    }

Lệnh này tương đương với

    KHỞI TẠO; 
    while (ĐIỀU KIỆN) { 
      PHẦN THÂN 
      GIA TĂNG 
    }

ngoại trừ nó gọn gàng hơn vì đã đặt tất cả những câu lệnh liên quan đến lặp vào một chỗ, và do đó dễ đọc hơn. Chẳng hạn:

    for (int i = 0; i < 4; i++) { 
      System.out.println(count[i]); 
    }

thì tương đương với

    int i = 0; 
    while (i < 4) { 
      System.out.println(count[i]); 
      i++; 
    }

12.5  Chiều dài của mảng

Tất cả mảng đều có một biến thực thể tên là length. Chẳng cần nói thì bạn cũng biết, biến này chứa chiều dài của mảng (số phần tử). Nên lấy giá trị này làm giới hạn trên của vòng lặp thay vì một giá trị cố định. Làm như vậy, nếu như kích thước của mảng thay đổi thì bạn sẽ không phải dò lại cả chương trình để thay đổi các vòng lặp; chương trình sẽ chạy được đúng với mọi kích cỡ mảng khác nhau.

    for (int i = 0; i < a.length; i++) { 
      b[i] = a[i]; 
    }

Lần cuối cùng mà phần thân của vòng lặp được thực thi, i sẽ là a.length - 1, chỉ số của phần tử cuối. Khi i bằng với a.length, điều kiện sẽ không thỏa mãn và phần thần sẽ không được thực thi. Đây là điều tốt, vì sẽ có biệt lệ được phát ra. Đoạn mã này giả thiết rằng mảng b phải có bằng số phần tử, hoặc nhiều hơn so với a.

12.6  Số ngẫu nhiên

Đa số các chương trình máy tính đều làm cùng một công việc mỗi khi nó được thực thi; chương trình như vậy được gọi là có tính tất định. Thông thường, tất định là tính chất tốt, vì ta luôn trông đợi cùng một phép tính sẽ chỉ cho một kết quả. Song có những chương trình ứng dụng mà ta muốn kết quả phải không đoán trước được. Một ví dụ hiển nhiên là các trò chơi điện tử, song cũng có những ứng dụng khác nữa.

Để một chương trình thực sự phi tất định hóa ra lại không dễ chút nào, song ít nhất vẫn có những cách làm chương trình có vẻ như phi tất định. Một cách làm trong số đó là việc phát sinh những số ngẫu nhiên và dùng nó để quy định kết quả của chương trình. Java có một phương thức để phát sinh ra các số giả ngẫu nhiên, vốn không thực sự ngẫu nhiên, nhưng sẽ dùng được cho mục đích ta cần.

Hãy đọc tài liệu về phương thức random trong lớp Math. Giá trị trả lại là một doublenằm giữa 0.0 và 1.0. Chính xác là, nó lớn hơn hoặc bằng 0.0 và nhỏ hơn 1.0. Mỗi lần kích hoạt random bạn sẽ nhận được con số tiếp theo trong dãy số giả ngẫu nhiên. Để thấy được một mẫu của dãy ngẫu nhiên, hãy chạy vòng lặp sau:

    for (int i = 0; i < 10; i++) { 
      double x = Math.random(); 
      System.out.println(x); 
    }

Để phát sinh một số double giữa 0.0 và một giới hạn trên như high, bạn có thể nhân x với high.

12.7  Mảng các số ngẫu nhiên

Bằng cách nào để phát sinh một số nguyên ngẫu nhiên giữa low và high? Nếu phương thức randomInt bạn viết đã chính xác, thì mỗi giá trị trong khoảng từ low lên đến high-1 phải có cùng xác suất xuất hiện. Nếu bạn phát sinh một dãy số rất dài, thì mỗi giá trị phải xuất hiện ít nhất là có số lần xấp xỉ nhau.

Một cách kiểm tra phương thức vừa viết là phát inh rất nhiều số ngẫu nhiên, lưu trữ chúng vào một mảng, rồi đếm số lần từng giá trị xuất hiện.

Phương thức sau nhận một đối số duy nhất là kích thước của mảng. Phương thức có nhiệm vụ huy động một mảng số nguyên mới, điền vào những giá trị ngẫu nhiên, rồi trả lại tham chiếu đến mảng mới điền.

  public static int[] randomArray(int n) { 
    int[] a = new int[n]; 
    for (int i = 0; i<a.length; i++) { 
      a[i] = randomInt(0, 100); 
    } 
    return a; 
  }

Kiểu trả lại là int[], nghĩa là phương thức này trả lại một mảng các số nguyên. Để kiểm tra phương thức này, thật tiện nếu có một phương thức để in ra nội dung của mảng.

  public static void printArray(int[] a) { 
    for (int i = 0; i<a.length; i++) { 
      System.out.println(a[i]); 
    } 
  }

Đoạn mã sau đây phát sinh một mảng rồi in nó ra:

  int numValues = 8; 
  int[] array = randomArray(numValues); 
  printArray(array);

Trên máy tính của tôi, kết quả là

27
6
54
62
54
2
44
81

trông thật là ngẫu nhiên. Kết quả của bạn có thể sẽ khác đi.

Nếu đây là những điểm thi (và nếu vậy thì điểm thật tệ), giáo viên có thể biểu diễn kết quả trước lớp dưới dạng một histogram, vốn là một tập hợp những biến đếm để theo dõi số lần mỗi giá trị xuất hiện.

Với điểm thi, có thể ta dành ra 10 biến đếm để theo dõi bao nhiêu học sinh đạt điểm đầu 9 (90 – 99), bao nhiêu đạt điểm đầu 8, v.v. Một số mục tiếp theo sẽ dành cho việc phát triển mã lệnh tạo ra histogram.

12.8  Đếm

Một cách tiếp cận hay đến những bài toán như thế này là nghĩ về những phương thức đơn giản, dễ viết, rồi kết hợp chúng lại thành lời giải. Quá trình này được gọi là phát triển từ dưới lên. Xem http://en.wikipedia.org/wiki/Top-down_and_bottom-up_design.

Thật không dễ thấy điểm khởi đầu của quá trình, nhưng một cách hợp lý là tìm kiếm những bài toán nhỏ khớp với một dạng mẫu mà bạn đã biết trước.

Ở Mục 8.7 ta đã thấy một vòng lặp duyệt qua một chuỗi rồi đếm số lần xuất hiện một chữ cái cho trước. Bạn có thể coi chương trình này như một ví dụ về một mẫu có tên gọi “duyệt và đếm.” Những yếu tố tạo nên dạng mẫu này là:

  • Một tập hợp hoặc tập dữ liệu có thể duyệt được, như một mảng hoặc chuỗi.
  • Một phép thử mà bạn có thể áp dụng cho từng phần tử trong tập đó.
  • Một con trỏ để theo dõi xem có bao nhiêu phần tử đạt được phép thử này.

Trong trường hợp đang xét, tập hợp là một mảng các số nguyên. Phép thử là liệu rằng một điểm số cho trước có rơi vào một khoảng giá trị cho trước hay không.

Sau đây là một phương thức có tên inRange để đếm số phần tử trong mảng rơi vào một khoảng cho trước. Các tham số bao gồm mảng và hai số nguyên để quy định giới hạn dưới và trên của khoảng này.

  public static int inRange(int[] a, int low, int high) { 
    int count = 0; 
    for (int i = 0; i < a.length; i++) { 
      if (a[i] >= low && a[i] < high) 
        count++; 
    } 
    return count; 
  }

Tôi đã không cụ thể hóa rằng liệu việc giá trị nào đó đúng bằng low hoặc high thì sẽ được coi là rơi vào khoảng hay không, nhưng từ mã lệnh bạn có thể thấy rằng low được coi là rơi vào trong còn high thì không. Điều này giúp ta tránh được việc đếm phần tử hai lần.

Bây giờ ta có thể đếm số điểm trong những khoảng cần quan tâm:

    int[] scores = randomArray(30); 
    int a = inRange(scores, 90, 100); 
    int b = inRange(scores, 80, 90); 
    int c = inRange(scores, 70, 80); 
    int d = inRange(scores, 60, 70); 
    int f = inRange(scores, 0, 60);

12.9  Histogram

Mã lệnh này có sự lặp lại, nhưng cũng chấp nhận được khi có ít khoảng khác nhau. Nhưng thử tưởng tượng nếu ta muốn theo dõi số lần xuất hiện của từng điểm số, nghĩa là 100 giá trị có thể. Lúc đó liệu bạn còn muốn viết mã lệnh nữa không?

    int count0 = inRange(scores, 0, 1); 
    int count1 = inRange(scores, 1, 2); 
    int count2 = inRange(scores, 2, 3); 
    ... 
    int count3 = inRange(scores, 99, 100);

Tôi không nghĩ vậy. Điều mà ta thực sự mong muốn là cách để lưu trữ 100 số nguyên, tốt nhất là cách mà ta dùng được chỉ số để truy cập đến từng giá trị. Gợi ý: dùng mảng.

Dạng mẫu đếm cũng tương tự bất kể việc ta dùng một biến đếm hay một mảng các biến đếm. Trong trường hợp sau này, ta khởi tạo mảng bên ngoài vòng lặp. Sau đó, trong vòng lặp, ta kích hoạt inRange và lưu lại giá trị:

    int[] counts = new int[100]; 
    for (int i = 0; i < counts.length; i++) { 
      counts[i] = inRange(scores, i, i+1); 
    }

Ở đây chỉ có một điều mẹo mực: chúng ta dùng biến lặp với hai tác dụng: làm chỉ số bên trong mảng, và làm tham số cho inRange.

12.10  Lời giải “một lượt”

Mã lệnh nói trên hoạt động được, song không hiệu quả như khả năng mà lẽ ra nó phải làm được. Mỗi lần đoạn chương trình kích hoạt inRange, nó duyệt toàn bộ mảng. Khi số các khoảng giá trị nhiều lên, sẽ có rất nhiều lần duyệt.

Sẽ tốt hơn nếu chỉ chạy một lượt qua mảng, và với mỗi giá trị, ta đi tính xem nó rơi vào khoảng nào. Tiếp theo ta có thể tăng biến đếm thích hợp. Ở ví dụ này, phép tính đó là nhỏ nhặt, bởi vì ta có thể dùng bản thân giá trị đó làm chỉ số cho mảng các biến đếm.

Sau đây là đoạn mã để duyệt một mảng các điểm số và phát sinh ra histogram.

    int[] counts = new int[100]; 
    for (int i = 0; i < scores.length; i++) { 
      int index = scores[i]; 
      counts[index]++; 
    }

12.11  Thuật ngữ

mảng:
Một tập hợp các giá trị, trong đó những giá trị này phải cùng kiểu, và mỗi giá trị được xác định bằng một chỉ số.
phần tử:
Một trong số các giá trị thuộc mảng. Toán tử [] được dùng để lựa chọn phần tử.
chỉ số:
Một biến nguyên hoặc giá trị nguyên để chỉ định một phần tử của mảng.
tất định:
Một chương trình thực hiện đúng một công việc mỗi khi nó được kích hoạt.
giả ngẫu nhiên:
Một dãy con số trông có vẻ ngẫu nhiên, song thực ra là sản phẩm của những phép tính tất định.
histogram:
Một mảng các số nguyên trong đó từng số nguyên để đếm số các giá trị rơi vào một khoảng nhất định.

12.12  Bài tập

Bài tập 1   Hãy viết một phương thức có tên cloneArray để nhận vào tham số là một mảng các số nguyên, tạo ra một mảng mới cùng kích thước, sao chép các phần tử từ mảng đầu sang mảng mới tạo, rồi trả lại một tham chiếu đến mảng mới.
Bài tập 2   Viết một phương thức có tên randomDouble nhận vào hai số phẩy động, low và high, rồi trả lại một số phẩy động ngẫu nhiên, x, sao cho low ≤ x < high.
Bài tập 3   Viết một phương thức có tên randomInt nhận vào hai đối số, low và high, rồi trả lại một số nguyên ngẫu nhiên từ low đến high, nhưng không kể high.
Bài tập 4   Bao bọc mã lệnh trong Mục 12.10 vào một phương thức có tên makeHist để nhận một mảng các điểm số rồi trả lại một histogram các giá trị trong mảng.
Bài tập 5   Viết một phương thức có tên areFactors để nhận vào một số nguyên, n, và một mảng các số nguyên, và trả lại true nếu các số trong mảng đều là ước số của n (nghĩa là n chia hết cho tất cả những phần tử này). GỢI Ý: Xem bài tập 8.1.
Bài tập 6   Viết một phương thức nhận tham số gồm một mảng những số nguyên và một số nguyên tên là target, rồi trả lại chỉ số đầu tiên nơi mà target xuất hiện trong mảng, nếu có, hoặc -1 nếu không.
Bài tập 7   Có những lập trình viên phản đối quy tắc chung rằng các biến và phương thức phải được đặt tên có nghĩa. Thay vào đó, họ nghĩ rằng các biến và phương thức phải đặt tên là các loại hoa quả. Với từng phương thức sau đây, hãy viết một câu mô tả ý tưởng, nhiệm vụ của phương thức. Với mỗi biến, hãy xác định vai trò của nó.

  public static int banana(int[] a) { 
    int grape = 0; 
    int i = 0; 
    while (i < a.length) { 
      grape = grape + a[i]; 
      i++; 
    } 
    return grape; 
  } 
  public static int apple(int[] a, int p) { 
    int i = 0; 
    int pear = 0; 
    while (i < a.length) { 
      if (a[i] == p) 
        pear++; 
      i++; 
    } 
    return pear; 
  } 
  public static int grapefruit(int[] a, int p) { 
    for (int i = 0; i<a.length; i++) { 
      if (a[i] == p) 
        return i; 
      } 
    return -1; 
  }

Mục đích của bài tập này là thực hành đọc mã lệnh và nhận ra những dạng mẫu tính toán mà ta đã gặp.

Bài tập 8

  1. Kết quả của chương trình sau là gì?
  2. Hãy vẽ biểu đồ ngăn xếp để cho thấy trạng thái chương trình ngay trước khi mus trả về.
  3. Diễn đạt bằng lời một cách ngắn gọn nhiệm vụ của mus.
  public static int[] make(int n) { 
    int[] a = new int[n]; 
    for (int i = 0; i < n; i++) { 
      a[i] = i+1; 
    } 
    return a; 
  } 
  public static void dub(int[] jub) { 
    for (int i = 0; i < jub.length; i++) { 
      jub[i] *= 2; 
    } 
  } 
  public static int mus(int[] zoo) { 
    int fus = 0; 
    for (int i = 0; i < zoo.length; i++) { 
      fus = fus + zoo[i]; 
    } 
    return fus; 
  } 
  public static void main(String[] args) { 
    int[] bob = make(5); 
    dub(bob); 
    System.out.println(mus(bob)); 
  }
Bài tập 9   Nhiều dạng mẫu để duyệt mảng mà ta đã gặp cũng có thể được viết theo cách đệ quy. Đó không phải là cách thường dùng, nhưng là một bài tập hữu ích.

  1. Hãy viết một phương thức có tên maxInRange, nhận vào một mảng số nguyên mà một khoảng chỉ số (lowIndex và highIndex), rồi tìm giá trị lớn nhất trong mảng, nhưng chỉ xét những phần tử giữa lowIndex và highIndex, kể cả hai đầu này. Phương thức phải được viết theo cách đệ quy. Nếu chiều dài của khoảng bằng 1, nghĩa là nếu lowIndex == highIndex, thì ta biết ngay rằng phần tử duy nhất trong khoảng phải là giá trị lớn nhất. Do đó đây là trường hợp cơ sở. Nếu có nhiều phần tử trong khoảng, thì ta có thể chia mảng làm đôi, tìm cực đại trên mỗi phần, rồi sau đó lấy giá trị lớn hơn trong số hai cực đại tìm được.
  2. Các phương thức như maxInRange có thể gây lúng túng khi dùng. Để tìm phần tử lớn nhất trong mảng, ta phải cung cấp một khoảng bao gồm toàn bộ mảng đó.
    double max = maxInRange(array, 0, a.length-1);

    Hãy viết một phương thức có tên max nhận tham số là một mảng rồi dùng maxInRange để tìm và trả lại giá trị lớn nhất. Các phương thức như max đôi khi còn được gọi là phương thức gói bọc vì chúng cung cấp một lớp khái niệm xung quanh một phương thức lủng củng và giúp nó dễ dùng. Phương thức mà thực sự thực hiện tính toán được gọi là phương thức trợ giúp.

  3. Hãy viết một phiên bản find theo cách đệ quy và dùng đến dạng mẫu gói bọc-trợ giúp. find cần phải nhận một mảng các số nguyên và một số nguyên mục tiêu. Nó cần phải trả lại chỉ số của vị trí đầu tiên tại đó xuất hiện số nguyên mục tiêu, hoặc trả lại -1 nếu không xuất hiện.
Bài tập 10   Một cách không hiệu quả lắm để sắp xếp các phần tử trong mảng là tìm phần tử lớn nhất rồi đổi chỗ nó cho phần tử thứ nhất, sau đó tìm phần tử lớn thứ hai rồi đổi chỗ với phần tử thứ hai, và cứ như vậy. Cách này gọi là sắp xếp chọn (xem http://vi.wikipedia.org/wiki/Sắp_xếp_chọn).

  1. Hãy viết một phương thức mang tên indexOfMaxInRange nhận vào một mảng số nguyên, tìm phần tử lớn nhất trong khoảng cho trước, rồi trả lại chỉ số của nó. Bạn có thể sửa lại phiên bản maxInRange hay bạn có thể viết từ đầu một phiên bản tương tác với máy.
  2. Viết một phương thức có tên swapElement nhận một mảng số nguyên cùng hai chỉ số, rồi đổi chỗ hai phần tử tại các chỉ số đó.
  3. Viết một phương thức có tên selectionSort nhận vào một mảng các số nguyên và trong đó dùng indexOfMaxInRange cùng swapElement để xếp mảng từ nhỏ đến lớn.
Bài tập 11   Viết một phương thức có tên letterHist nhận một chuỗi làm tham số rồi trả lại histogram của các chữ cái trong chuỗi. Phần tử thứ không của histogram cần phải chứa số chữ a trong chuỗi (cả chữ in và thường); phần tử thứ 25 cần phải chứa số chữ z. Lời giải của bạn chỉ được duyệt chuỗi này đúng một lần.
Bài tập 12   Một từ được gọi là “doubloon” nếu trong từ đó, mỗi chữ cái xuất hiện đúng hai lần. Chẳng hạn, các từ sau đây là doubloon mà tôi đã tìm thấy trong cuốn từ điển.

Abba, Anna, appall, appearer, appeases, arraigning, beriberi, bilabial, boob, Caucasus, coco, Dada, deed, Emmett, Hannah, horseshoer, intestines, Isis, mama, Mimi, murmur, noon, Otto, papa, peep, reappear, redder, sees, Shanghaiings, Toto

Hãy viết một phương thức có tên isDoubloon để trả lại true nếu từ đã cho là một doubloon và false nếu không phải.

Bài tập 13   Hai từ là từ đảo (anagram) nếu như chúng có chứa cùng những chữ cái (đồng thời cùng số lượng từng chữ). Chẳng hạn, “stop” là từ đảo của “pots” còn “allen downey” là cụm từ đảo của “well annoyed.” Hãy viết một phương thức nhận vào hai String rồi trả lại true nếu như các String là từ đảo của nhau. Thêm phần thử thách: bạn chỉ được đọc các chữ cái của những String này đúng một lần.
Bài tập 14   Trong trò chơi Scrabble, mỗi người chơi có một tập hợp các miếng vuông với các chữ cái ghi trên đó, và mục tiêu của chò trơi là dùng những chữ cái đó ghép thành từ có nghĩa. Hệ thống tính điểm khá phức tạp, song thường thì các từ dài có giá trị cao hơn các từ ngắn. Giả dụ rằng bạn được cho trước các chữ cái dưới dạng một chuỗi, như "quijibo" và bạn nhận được một chuỗi khác để kiểm tra, như "jib". Hãy viết một phương thức có tên canSpell nhận vào hai chuỗi rồi trả lại true nếu tập hợp các miếng vuông xếp được thành từ có nghĩa. Bạn có thể có nhiều miếng ghi chữ giống nhau, nhưng chỉ được dùng mỗi miếng một lần. Thêm phần thử thách: bạn chỉ được đọc các chữ cái của những String này đúng một lần.
Bài tập 15   Thực ra trong Scrabble, còn những miếng vuông trắng có thể được dùng để biểu diễn chữ cái tùy ý. Hãy suy nghĩ một thuật toán cho canSpell xử lý được trường hợp chữ tùy ý như vậy. Đừng bận tâm đến những chi tiết thực hiện như bằng cách nào có thể biểu diễn những chữ tùy ý đó. Chỉ cần diễn đạt thuật toán bằng lời, bằng giả mã, hoặc bằng Java.

24 phản hồi

Filed under Think Java

24 responses to “Chương 12: Mảng

  1. Pingback: Think Java: Cách suy nghĩ như nhà khoa học máy tính | Blog của Chiến

  2. ko hiểu phần này,chẳng khai báo mảng gì cả tự yên cho cái đoạn code cộc lốc vào ức chế ko tả nổi :
    int i = 0;
    while (i < 4) {
    System.out.println(count[i]); i++;
    }

  3. mình ko biết phương thức randomInt là gìsao randomInt lại có 2 đối số

  4. viet randomInt như thế nào bạn ơi

    • Mặc định trong Java, hàm Math.random() không nhận đối số nào, và trả lại một double trong khoảng từ 0.0 đến 1.0. Như vậy ví dụ tôi muốn viết randomInt(0,10) thì sẽ rất muốn gắn đối số 0 với giá trị 0.0 và số 10 với 1.0. Như vậy khi định nghĩa randomInt, ở phần thân hàm bạn phải đặt, chẳng hạn, x = Math.random() rồi lấy x*10 để ra số thực sau đó cast (int) (x*10) thì ra kết quả cần có. Bạn tự phát triển trường hợp chung randomInt(0, b) và tổng quát là randomInt(a,b).

      • Khách

        mình thực sự chỉ biết viết randomInt(0,b) thôi chứ cho 2 đối số vào thì mình ko biết làm ntn,nhu nay co dung ko :

        public static int RandomInt(int b){
        double x=Math.random()*b;
        int N=(int)x;
        return N;
        }

      • Trong trường hợp có số a, bạn phải nghĩ ra cách trừ đi a trước khi nhân tỉ lệ với b chứ.

      • Khách

        bạn gợi ý thêm đi lấy cái gì trừ đi a chứ

    • Khách

      i can’t do it

  5. sao mình đọc đầu bài bài 9 ý 1 nó cứ kiểu gì ấy sao đang truyền tham số là 1 mảng thì lại xét các phần tử từ lowIndex đến highIndex là sao xong lại bắt tìm Giá trị max ở mảng ???!!!!!

  6. cả bài 11 nữa thực sự ko hiểu gì @@ như kiểu đọc tiếng campuchia

  7. bạn ơi cho mình hỏi ứng dụng của mảng trong lập trình để làm gì vậy ? để vẽ biểu đồ à

  8. Khách

    bạn ơi cái phần lời giải 1 lượt ấy thì lại phải truyền đối số là 100 vào randomArray à (ý mình là ntn int[] scores=randomArray(100);

  9. Khách

    mình làm được rồi

  10. Khách

    bạn ơi giúp mình bài 10 ý 3 với mình có ý tưởng như này tìm được số lớn nhất xong đổi chỗ cho phần tử array.length-1 trong mảng xong tìm số lớn thứ 2 đổi chỗ cho phần tử array.length-2 dần dần như thế đến hết có được ko nhưng ko biết làm thế nào .

  11. Khách

    gợi ý bài 12 đi bạn ơi

  12. Khách

    thôi k ocan đâu bạn mình tìm đc code trên google rồi

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s