Tuesday, July 14, 2015

Bài 9 - Lập trình hướng đối tượng (Object Oriented Programming)

Trong loạt bài trước mình đã hướng dẫn các bạn về các kỹ năng lập trình căn bản đối với ngôn ngữ Java . Tuy nhiênJava là ngôn ngữ lập trình hướng đối tượng rất mạnh mẽ . Và chúng ta sẽ dành nhiều thời gian hơn để nói về nó . Và đây cũng chiếm gần như chọn thời gian tìm hiểu của chúng ta.
I. Định nghĩa class của Object
1. Lập trình hướng đối tượng là gì :là ngôn ngữ mô tả các sự vật hiện tượng thông qua đối tượng.
Vậy đối tượng là gì : đối tượng là hiện tượng sự vật , được biểu hiện bằng các thuộc tính(data field) , và các hành động (behavior ) của nó được mô tả bằng các method hay event.
Trong Java người ta biểu diễn đối tượng thông qua class (template).
Ví dụ : class Nguoi có các field (name , age , salary...) và các behavior (nghe, nói , đọc ,viết ...)
Khi thiết kế hệ thống , chúng ta cần dùng các ngôn ngữ phân tích thiết kế khác . Ở đây tôi sẽ đề cập cho các bạn một dạng ngôn ngữ phân tích thiết kế thông thường hay sử dụng đó là UML(Unified Modeling Language) . Người ta dùng UML class diagram để thể hiện một class (hay template của đối tượng như sau)

Trong đó dữ liệu của thuộc tính được thể hiện ở dạng
dataFieldName: dataFieldType
Các contructor :
ClassName(parameterName: parameterType)
Các method :
methodName(parameterName: parameterType): returnType
Wao , chúng ta lại đề cập tới khái niệm contructor , vậy nó là gì.
Contructor được khai báo trùng với tên class , biểu diễn như một method nhưng lại không có kiểu dữ liệu trả về. Nó là một thể hiện của class .

Khi khai báo một class , thì nó sẽ tự động sinh ra một contructor rỗng (không có tham số).Mặc dù nó không thể hiện trên code.
Nếu một class viết một contructor có tham số (arguments) duy nhất cho class . Thì contructor này sẽ overload contructor default (không tham số) . Vì vậy nếu bạn gọi contructor(không tham số) nó sẽ báo lỗi .
Khi bạn muốn một thể hiện của class ở nhiều dạng , yêu cầu đầu vào cho class nhiều tham số thì bạn cũng có thể tạo rất nhiều contructor . Khi gọi tới contructor nào thì nó sẽ overload các contructor còn lại : Ví dụ:
public class DemoContructor {

       int a;
       String str ;
       float salary;
       public DemoContructor(){
              System.out.println("contructor rong");
       }
       public DemoContructor(int a){
              this.a = a;
              System.out.println("contructor co 1 tham so :" + a);
       }
      
       public DemoContructor(int a, String str, float salary) {
              super();
              this.a = a;
              this.str = str;
              this.salary = salary;
              System.out.println("contructor co 3 tham so:" + a + " " + str + " " + salary);
       }
       public static void main(String[] args) {
              // TODO Auto-generated method stub
              DemoContructor demo = new DemoContructor();
              DemoContructor demo2 = new DemoContructor(3);
              DemoContructor demo3 = new DemoContructor(4, "hello", 12);
       }

}
Đây cũng là một đặc tính đa hình trong Java .
Trong eclipse các bạn có thể tự generate các method contructor bằng các click vào Source trên thanh tabbar (Alt +S) hoặc chuột phải vào cửa sổ soạn thảo -->Source --> Generate Contructor using field
2. Biến static (static variables) , Constant (hằng số ) và method.
- Biến static và method static: Khi chúng ta muốn chia sẻ dữ liệu thì chúng ta dùng biến static . Biến static lưu trữ giá trị trong bộ nhớ dùng chung. Bởi vì vị trí ô nhớ dùng chung này , tất cả các đối tượng giống nhau trong class đều có thể thay đổi giá trị của biến static này. Java cũng support các method static để gọi tới các biến static. Ví dụ :
Các bạn chú ý : Chỉ có method static mới gọi được các biến static . Và chỉ có method static mới gọi được tới nhau.
Cách khai báo biến static và method static là :
static int numberOfObjects;

static int getNumberObjects() {
  return numberOfObjects;
}
- Hằng số và final method : Để chia sẻ dữ liệu cho toàn bộ project chúng ta dùng từ khóa final static để biểu diễn những giá trị không thể thay đổi . Hay đây chính là biểu diễn hằng số như trong toán học. (Những giá trị không bao giờ thay đổi ).Ví dụ
final static double PI = 3.14159265358979323846;
Tương tự như vậy final method cũng là một method không có bất kỳ method nào thay đổi giá trị của nó . Cũng không đươc kế thừa (cái này mình sẽ giới thiệu các bạn trong những bài học lần sau ).
public class DemoFinal {

       final static double PI = 3.14159265358979323846;
       final /*static*/ void show(){
              System.out.println("show :" + PI);
             
       }
       public static void main(String[] args) {
              DemoFinal fn = new DemoFinal();
              fn.show();
//            show();
       }
}
- Cách gọi tới method hoặc variable từ hàm main.
Thông thường chúng ta có 2 cách gọi method hay variable từ hàm main . Một là gọi trực tiếp , hai là gọi thông qua đối tượng.
* Cách 1 : gọi trực tiếp
Vì hàm main là một hàm static nên tất cả các variable và method của nó khi gọi tới phải là static
static int a = 23;
static void show(){
     System.out.println("ket qua show :" + a);
}
public static void main(String[] args) {
     show();
     System.out.println("ket qua show 2 :" + a);
}
*Cách 2 : gọi thông qua đối tượng. Ta dựa vào contructor như đã nói ở trên . Sau đó nhờ đối tượng để gọi tới.
public class DemoObject {

       String name = "Khai";
       int age = 24;
      
       public DemoObject() {
              super();
       }

       public DemoObject(String name, int age) {
              super();
              this.name = name;
              this.age = age;
       }

       void show(){
              System.out.println("name :" + name + "\nage" + age);
       }
       public static void main(String[] args) {
              DemoObject obj = new DemoObject();
              obj.show();
             
              DemoObject obj2 = new DemoObject("nosoft", 30);
              obj2.show();
       }
}
3. Khả năng truy nhập (Visibility Modifiers)
Java cung cấp các khả năng truy nhập dữ liệu như sau :
- public : Các biến dữ liệu hoặc method có thể sẽ được tất cả các lớp khác , hoặc method khác gọi tới ở bất kỳ nơi đâu trong project
- protected : Các biến dữ liệu hoặc method chỉ cho các lớp hoặc method khác gọi tới nếu cùng chung một package.
- private : Các biến dữ liệu hoặc method chỉ cho các method khác hoặc lớp nội hàm truy nhập nếu chung một class.
- default : truy nhập được trong class và trong package nhưng lại không truy nhập được từ class con
Đây cũng chính là tính bảo mật dữ liệu trong Java
Để tăng tính bảo mật project của bạn thì chúng ta nên dùng private cho các field . Và truy xuất dữ liệu thông quá các method getter và setter .
Thông qua các method getter và setter này để hạn chế khả năng truy nhập dữ liệu như thế nào tới từng loại user một. Tùy vào mục đích sử dụng.
public class Student {
  private int id;
  private BirthDate birthDate;

  public Student(int ssn, int year, int month, int day) {
    id = ssn;
    birthDate = new BirthDate(year, month, day);
    }

    public int getId() {
      if(id >1)
      return id;
      return 0;
    }

    public BirthDate getBirthDate() {
      return birthDate;
    }
}

public class BirthDate {
   private int year;
   private int month;
   private int day;

   public BirthDate(int newYear, int newMonth, int newDay) {
     year = newYear;
     month = newMonth;
     day = newDay;
   }

   public void setYear(int newYear) {
     year = newYear;
   }
}
public class Test {
  public static void main(String[] args) {
    Student student = new Student(111223333, 1970, 5, 3);
    BirthDate date = student.getBirthDate();
    date.setYear(2010); //Now the student birth year is changed!
  }
}
Muốn lấy dữ liệu của class Student thì ta dùng phương thức getter (getId , getBirthDate)
Muốn gán dữ liệu ta dùng phương thức setter (setYear)
Các bạn cũng có thể generate trong eclipse giống như generate contructor bằng phím tắt Alt+ S.
*Mở rộng : Cũng như với variable thì Array cũng là một object chứa các object khác là các phần tử .
Circle[] circleArray = new Circle[10];
for (int i = 0; i < circleArray.length; i++) {
  circleArray[i] = new Circle();
}
4. Lớp DateTime và Random
Trong Java hỗ trợ 2 thư viện rất hữu dụng đó là lớp Date và Random.
a . Date
Thuộc gói java.util.Date để thể hiện các toán tử current second , minute , hour . Có câu lệnh System.currentTimeMillis() để tính toán thời gian tại thời điểm hiện tại chính xác tới minisecond .
java.util.Date date =  new jave.util.Date();
System.out.println("The elapsed time since Jan 1, 1970 is " +
 date.getTime() + " milliseconds");
System.out.println(date.toString());
Result
The elapse time since Jan 1, 1970 is 1100547210284 milliseconds
Mon Nov 15 14:33:30 EST 2004
b. Random.
Thuộc gói java.util.Random generate ra các toán tử ngẫu nhiên . Trong phạm vi nào đó.
Ví dụ :
Random random1 = new Random(3);
System.out.print("From random1: ");
for (int i = 0; i < 10; i++)
  System.out.print(random1.nextInt(1000) + " ");
Random random2 = new Random(3);
System.out.print("\nFrom random2: ");
  for (int i = 0; i < 10; i++)
  System.out.print(random2.nextInt(1000) + " ");
Result
From random1: 734 660 210 581 128 202 549 564 459 961
From random2: 734 660 210 581 128 202 549 564 459 961
II. Tính đóng gói dữ liệu.
Hãy xem xét việc xây dựng một hệ thống máy tính, ví dụ. Máy tính cá nhân của bạn được tạo thành từ nhiều thành phần, chẳng hạn như một CPU, CD-ROM, ổ đĩa mềm, bo mạch chủ, quạt, và như vậy. Mỗi thành phần có thể được xem như là một đối tượng có các thuộc tính và phương thức. Để có được các thành phần để làm việc cùng nhau, tất cả chúng cần biết là mỗi thành phần được sử dụng và làm thế nào nó tương tác với những thành phần khác. Nó không cần phải biết làm thế nào nó hoạt động trong nội bộ. Việc thực hiện các thành phần với nhau phải được đóng gói và ẩn từ riêng chúng. Bạn có thể xây dựng một máy tính mà không biết làm thế nào thành phần được thực hiện như thế nào.
Vì vậy chúng ta có thể dùng các project này để làm library cho các project kia.
OK. Hôm nay hãn tạm dừng tại đây .
Mình sẽ không nêu ví dụ trong bài hướng dẫn này .
Nhưng vẫn có bài tập cho các bạn luyện tập về nó .
Bài 1: Tạo chương trình nhập và in ra thông tin một sinh viên (tên , tuổi , quê quán , học lực (điểm trung bình của ba môn : toán , văn , anh)) . Phải sử dụng contructor và getter setter để thực hiện.
Bài 2 : Tạo một chương trình nhập và in thông tin nhân viên (id , tên , tuổi , chức vụ , phòng ban (id phòng ban , loai phòng) , số lương) . Trong đó nếu chức vụ là trưởng phòng thì lương không được dưới 10 triệu. Nếu là giám đốc thì lương không dưới 20 tr
Source code : here
(Code khung)
pass extract : https://coderandtutorial.blogspot.com

Thursday, July 9, 2015

Bài 8 - Mảng (Array) (3)

Sau hai bài hướng dẫn về mảng một chiều và mảng nhiều chiều . Các bạn đã có những cái nhìn tổng quan hơn về Mảng. Hôm nay mình sẽ giới thiệu cho các bạn giải thuật cơ bản về sử dụng mảng .
Đó là sắp xếp và tìm kiếm đối với mảng . Bởi vì sau này các bạn có thể dùng một list (danh sách) các đối tượng , thực hiện tìm kiếm hay sắp xếp theo thứ tự . ... Sau loạt bài này các bạn sẽ có cách tuy duy rất căn bản đối với các giải thuật cơ bản về danh sách các đối tượng.
I. Tìm kiếm
Có rất nhiều phương pháp cũng như thuật toán tìm kiếm . Nhưng ở đây mình sẽ giới thiệu cho các bạn 2 phương pháp căn bản.
1. Tìm kiếm tuyến tính(Linear Search Approach).
Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi x¹a1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi x¹a2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0 .
Kết quả:
int[] list = {1, 4, 4, 2, 5, -3, 6, 2};
int i = linearSearch(list, 4);  // returns 1
int j = linearSearch(list, -4); // returns -1
int k = linearSearch(list, -3); // returns 5
2. Tìm kiếm nhị phân(Binary Search Approach)
Thuật toán này có thể được dùng khi bảng liệt kê có các số hạng được sắp theo thứ tự tăng dần. Chẳng hạn, nếu các số hạng là các số thì chúng được sắp từ số nhỏ nhất đến số lớn nhất hoặc nếu chúng là các từ hay xâu ký tự thì chúng được sắp theo thứ tự từ điển. Thuật toán thứ hai này gọi là thuật toán tìm kiếm nhị phân. Nó được tiến hành bằng cách so sánh phần tử cần xác định vị trí với số hạng ở giữa bảng liệt kê. Sau đó bảng này được tách làm hai bảng kê con nhỏ hơn có kích thước như nhau, hoặc một trong hai bảng con ít hơn bảng con kia một số hạng. Sự tìm kiếm tiếp tục bằng cách hạn chế tìm kiếm ở một bảng kê con thích hợp dựa trên việc so sánh phần tử cần xác định vị trí với số hạng giữa bảng kê. Ta sẽ  thấy rằng thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm tuyến tính.Các bạn để ý vào hình vẽ dưới sẽ hiểu tường minh hơn
Giải thuật :
public class BinarySearch {
 /** Use binary search to find the key in the list */
 public static int binarySearch(int[] list, int key) {
  int low = 0;
  int high = list.length - 1;

  while (high >= low) {
   int mid = (low + high) / 2;
   if (key < list[mid])
    high = mid - 1;
   else if (key == list[mid])
    return mid;
   else
    low = mid + 1;
  }
  return -low - 1;
 }

 public static void main(String[] args) {
  int array[] = { 1, 2, 3, 5, 7, 4, 6 };
  Scanner in = new Scanner(System.in);
  System.out.println("nhap key:");
  int key = in.nextInt();  
  System.out.println("Key vi tri " + (binarySearch(array, key) + 1));
 }
}
II. Sắp sếp (sort)
Mình sẽ giới thiệu cho các bạn những thuật toán sắp xếp cơ bản . Để sau này các bạn có thể trả lời phỏng vấn một cách nguy hiểm hơn . Có thể các bạn biết nhưng thuật toán này . Tuy nhiên khi hỏi tới các bạn lại không biết tên nó , hoặc không diễn đạt được nổi nó.
1.Selection Sort
Định nghĩa giải thuật :
Lần lượt chọn phần tửnhỏnhất trong dãy chỉsố k1, k2,. . ., kn với i = 0, 1, . .,n; ki< k i+1< . . ., kn và đổi chỗ cho phần tử thứ ki. Như vậy, sau j =n-1 lần chọn, chúng ta sẽ só dãy khoá được sắp xếp theo thứ tự tăng dần. Đối với dãy số trên, 
chúng ta sẽ thực hiện như sau: 
* Lần chọn thứ 0: Tìm trong khoảng từ 0 đến n-1bằng cách thực hiện n- 1 lần so 
sánh để xác định phần tử min0 và đổi chỗ cho phần tử ở vị trí 0.
* Lần chọn thứ 1: Tìm trong khoảng từ 1 đến n-1 bằng cách thực hiện n- 2 lần so sánh để xác định phần tử min1 và đổi chỗ cho phần tử ở vị trí 1. 
.....................................................................................................................................
Lần chọn thứ i: Tìm trong khoảng từ i đến n-1 bằng cách thực hiện n- i lần so sánh để xác định phần tử mini và đổi chỗ cho phần tử ở vị trí i. 
Lần chọn thứ n-2: Tìm trong khoảng từ n-2 đến n-1 bằng cách thực hiện 1 lần so 
sánh để xác định phần tử min n-2 và đổi chỗ cho phần tử ở vị trí n-2. 
Cụ thể sẽ được mô tả dưới hình sau :
Giải thuật :
public static void selectionSort(double[] list) {
 double currentMax;
 currentMax = list[0];
 int currentMaxIndex = 0;
 for (int i = list.length - 1; i >= 1; i--)
 // Find the maximum in the list[0..i]
 {
  for (int j = 1; j <= i; j++) {
   if (currentMax < list[j]) {
    currentMax = list[j];
    currentMaxIndex = j;
   }
  }
  // Swap list[i] with list[currentMaxIndex] if necessary;
  if (currentMaxIndex != i) {
   list[currentMaxIndex] = list[i];
   list[i] = currentMax;
  }
 }
}
2. Insertion Sort
Insert Sort được thực hiện dựa trên kinh nghiệm của những người chơi bài. Khi có i-1 lá bài đã được sắp xếp đang ở trên tay, nay ta thêm lá bài thứ i thì lá bài đó được so sánh với lá bài i-1, i-2, . . để tìm được vị trí thích hợp và chèn vào quân bài thứ i.
Nguyên tắc thực hiện như sau :
Lấy phần tử đầu tiên i0, đương nhiên tập một phần tử là tập đã được sắp xếp. 
* Lấy tiếp phần tử thứ i1 chọn vị trí thích hợp của phần tử thứ i1 trong tập hai phần tử và thực hiện đổi chỗ.
* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
* Lấy tiếp phần tử thứ ik chọn vị trí thích hợp của phần tử thứ ik trong tập hai ik-1 phần tử và thực hiện đổi chỗ, dãy sẽ được sắp xếp hoàn toàn sau n-1 lần chèn phần tử vào vị trí thích hợp. 
Cụ thể như hình vẽ sau :
Giải thuật :
public static void insertionSort(double[] list) {
 for (int i = 1; i < list.length; i++) {
  /**
   * insert list[i] into a sorted sublist list[0..i-1] so that
   * list[0..i] is sorted.
   */
  double currentElement = list[i];
  int k;
  for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
   list[k + 1] = list[k];
  }
  // Insert the current element into list[k+1]
  list[k + 1] = currentElement;
 }
}
3 . Sắp xếp nổi bọt (Bubble Sort)
Bubble Sort được thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế cận khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh. Như vậy, sau lần duyệt thứ nhất,phần tử lớn nhất sẽ được xếp đúng ở vị trí thứ n-1, ở lần duyệt thứ k thì k phần tử lớn nhất đã được xếp đúng vị trí n-1, n-2, . ., n-k+1. Sau lần duyệt thứ n-1, toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này, các phần tử có giá trị nhỏ được nổi dần lên như nước sủi bọt nhờ đó nó có tên gọi “phương pháp sủi bọt”.
Giải thuật :
public void bubbleSort(int [] array){
 for(int i = 0; i< array.length; i++){
            for (int j = array.length - 1; j > 0; j--) {
               if(array[j] < array[j-1]){
                   int temp = array[j];
                   array[j] = array[j-1];
                   array[j-1] = temp;
               }
           }    
       }
}
4. Quick Sort
Quick Sort là chọn ngẫu nhiên một phần tử nào đó của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá phải được xếp vào trước chốt (đầu dãy), mọi phần tử sau chốt được xếp vào sau chốt (cuối dãy). Để làm được việc đó, các phần tử trong dãy sẽ được so sánh với khoá chốt và tráo đổi vị trí cho nhau, hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhỏ hơn chốt nhưng lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên đã thực hiện xong thì dãy hình thành hai đoạn: một đoạn bao gồm các phần tử nhỏ hơn chốt, một đoạn gồm các phần tử lớn hơn chốt, còn chốt chính là vị trí của phần tử trong dãy được sắp xếp.
Áp dụng cho mỗi đoạn trước chốt và sau chốt cho tới khi các đoạn còn lại hai phần tử thì việc ghi nhớ không còn cần thiết nữa. Dãy sẽ được sắp xếp khi tất cả các đoạn được xử lý xong. Ví dụ với dãy:
42  23 74 11 65 58 94 36 99 87
Ta chọn chốt đầu tiên là 42. Để phát hiện ra hai khoá cần đổi chỗ cho nhau, ta dùng hai biến i, j với giá trị ban đầu i=2, j=10. Nếu ki< 42 thì tiếp tục tăng i và lặp lại cho tới khi 
gặp phần tử thứ  ki>42. Duyệt các phần tử thứ kj với 42 nếu kj> 42 thì j giảm đi một, cho 
tới khi gặp phần tử thứ kj<42 thì phần tử thứ ki và kj được đổi chỗ cho nhau. Quá trình sẽ
được lặp lại với ki và kj  cho tới khi i=j chính là vị trí dành cho khoá 42. Cuối cùng chúng ta 
đổi chỗ 42 cho khoá cho kj.
Các bạn có thể tham khảo hình ảnh tại đây để có thể hiểu rõ hơn về nguyên lý của thuật toán quick sort
Giải thuật :
// Tìm chốt
 public int findPivot(int i, int j, int[] array) {
         if (array.length == 1) {
             return -1;
         }
         int k = i + 1;
         int pivot = array[i];

         while ((k <= j) && (array[k] == pivot)) {
             k++;
         }
         if (k > j) {
             return -1;
         }
         if (array[k] > pivot) {
             return k;
         } else {
             return i;
         }
     }

 // Tìm partition
 public int pointPartition(int i, int j, int pivotKey, int[] array) {
       int partition = -1;
         int L = i;
         int R = j;
         while (L <= R) {
             while (array[L] < pivotKey)
                 L++;
             while (array[R] >= pivotKey)
                 R--;
             if (L < R) {
                 int temp = array[L]; 
                 array[L] = array[R];
                 array[R] = temp;
             }
         }
         partition = L;
         return partition;  
     }

    // Sắp xếp
     public void quickSort(int i, int j, int[] array) {
         int pivot = findPivot(i, j, array);
         if (pivot == -1)
             return;
         int partition = pointPartition(i, j, array[pivot], array);
         quickSort(i, partition - 1, array);
         quickSort(partition, j, array);
    }
OK như vậy là cũng ổn rồi . Bây giờ là bài tập vận dụng của các bạn . Hãy chăm chỉ lên nào các chiến binh.
Bài 1 :Viết chương trình nhập vào vào mảng A có n phần tử, các phần tử là những số nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức năng sau
a)      Tìm phần tử lớn nhất và lớn thứ 2 trong mảng cùng chỉ số của các số đó.
b)      Sắp xếp mảng theo thứ tự giảm dần (Sử dụng một trong các thuật toán sắp xếp ở trên).
c)Nhập một số nguyên x và chèn x vào mảng A sao cho vẫn đảm bảo tính sắp xếp giảm dần
Note : Trong source code mình làm theo hướng khác để các bạn hiểu thêm về cách làm.
Bài 2 : Nhập số n và dãy các số thực  a0 , a1 ,..., an-1. Không đổi chỗ các phần tử và không dùng thêm mảng số thực nào khác (có thể dùng mảng số nguyên nếu cần) hãy cho hiện trên màn hình dãy trên theo thứ tự tăng dần
Bài 3Viết chương trình thử nghiệm các thuật toán trên một dãy n số nguyên ngẫu nhiên (10<n<100)
a)      Sắp xếp chọn
b)      Sắp xếp chèn
c)      Sắp xếp nổi bọt
d)     Sắp xếp nhanh
e)      Sắp xếp trộn (bổ sung)
f)       Sắp xếp vun đống (Heap Sort) (bố sung)
Source code : here
Pass extract : https://coderandtutorial.blogspot.com

Tuesday, July 7, 2015

Bài 8 - Mảng( Array) (2)

Sau loạt bài trước mình đã hướng dẫn các bạn về mảng 2 chiều . Hôm nay mình sẽ hướng dẫn các bạn tiếp về cách sử dụng mảng 2 chiều và mảng nhiều chiều .
Mảng 2 chiều là mảng của mảng 1 chiều . Nghe có vẻ lủng củng , nhưng thực chất nó chính là như vậy.
I. Cú pháp
dataType[][] arrayRefVar;
hoặc :
dataType arrayRefVar[][];
ví dụ :
int[][] matrix;
or
int matrix[][];
Cách tạo một mảng mới nó như thế nào : matrix = new int[5][5];
Mảng vừa tạo có 25 phần tử.
Gán giá trị cho mảng 2 chiều cũng phức tạp hơn mảng 1 chiều . Cụ thể 
Đôi khi các bạn thường hay nhầm lẫn hay lúng túng mỗi khi nhập mảng . Thì thứ tự nó sẽ được thực hiện cụ thể như sau :
Ví dụ tôi nhập một mảng 2 chiều có 3 hàng và 4 cột :
Cứ nhập theo tuần tự Hàng hết xong tới cột
Ngoài ra chúng ta có thể khai báo mảng khuyết như sau :
Thực chất mảng khuyết trên nó là dạng này:
int[][] triangleArray = new int[5][];
triangleArray[0] = new int[5];
triangleArray[1] = new int[4];
triangleArray[2] = new int[3];
triangleArray[3] = new int[2];
triangleArray[4] = new int[1];
II. Một số cách sử dụng mảng 2 chiều
* khởi tạo mảng 2 chiều với n giá trị
for(int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    matrix[row][column] = (int)(Math.random() * 100);
  }
}
* Cách hiển thị mảng 2 chiều
for (int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    System.out.print(matrix[row][column] + " ");
  }

  System.out.println();
}
* Tổng các phần tử
int total = 0;
for (int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    total += matrix[row][column];
  }
}
* Tổng các phần tử của cột
 for (int column = 0; column < matrix[0].length; column++) {
  int total = 0;
  for (int row = 0; row < matrix.length; row++)
    total += matrix[row][column];
  System.out.println("Sum for column " + column + " is " + total);
}
* Số lớn nhất của hàng
int maxRow = 0;
int indexOfMaxRow = 0;

// Get sum of the first row in maxRow
for (int column = 0; column < matrix[0].length; column++) {
  maxRow += matrix[0][column];
}

for (int row = 1; row < matrix.length; row++) {
  int totalOfThisRow = 0;
  for (int column = 0; column < matrix[row].length; column++) {
    totalOfThisRow += matrix[row][column];
    if (totalOfThisRow > maxRow) {
      maxRow = totalOfThisRow;
      indexOfMaxRow = row;
    }
  }
}

System.out.println("Row " + indexOfMaxRow 
   + " has the maximum sum" + " of " + maxRow); 
Chú ý : Đối với mảng 2 chiều thì như vậy . Tương tự với mảng 3 chiều , 4 chiều ,... n chiều cũng chỉ là dạng mảng của mảng của mảng mà thôi . Các bạn nắm chắc mảng 2 chiều thì có vạn chiều các bạn cũng hoàn toàn có thể làm được
Sau đây là các ví dụ cụ thể và hoàn chỉnh hơn về cách sử dụng mảng nhiều chiều .
III. Ví dụ vận dụng
Ví dụ  :
Viết chương trình nhập vào vào ma trận A có n dòng, m cột, các phần tử là những số nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức năng sau:
a)Tìm phần tử lớn nhất của ma trận cùng chỉ số của số đó.
b)      Tìm và in ra các phần tử là số nguyên tố của ma trận (các phần tử không nguyên tố thì thay bằng số 0).
c)      Sắp xếp tất cả các cột của ma trận theo thứ tự tăng dần và in kết quả ra màn hình.
public class Ex1_UseArray2 {
 public static int nhap() {
  Scanner input = new Scanner(System.in);
  boolean check = false;
  int n = 0;
  while (!check) {
   System.out.print(" ");
   try {
    n = input.nextInt();
    check = true;
   } catch (Exception e) {
    System.out.println("Ban phai nhap so! hay nhap lai...");
    input.nextLine();
   }
  }
  return (n);
 }
 public static boolean checkSNT(int n) {
  if (n > 1) {
   for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0)
     return false;
   }
   return true;
  } else
   return false;
 }
 public static void inMT(int[][] A, int n, int m) {
  int i, j;
  for (i = 0; i < n; i++) {
   System.out.print("\n");
   for (j = 0; j < m; j++)
    System.out.print(" " + A[i][j]);
  }
 }
 public static int findMaxMT(int[][] A, int n, int m) {
  int Max = A[0][0];
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < m; j++) {
    if (Max < A[i][j])
     Max = A[i][j];
   }
  }
  return (Max);
 }
 // Tim nhung phan tu la SNT
 public static void phanTuSNT(int[][] A, int n, int m) {
  int count = 0, i, j;
  System.out.println("\nCac phan tu la SNT (nhung phan tu ko la SNT =0): ");
  for (i = 0; i < n; i++) {
   System.out.print("\n");
   for (j = 0; j < m; j++) {
    if (checkSNT(A[i][j])) {
     count++;
     System.out.print(" " + A[i][j]);
    } else
     System.out.print(" " + 0);
   }
  }
  System.out.println("\n Co " + count + " phan tu la so nguyen to");
 }
 // Sap xep cac cot theo thu tang dan
 public static void sortColum(int[][] A, int n, int m) {
  int i, j, temp;
  for (j = 0; j < m; j++) {
   for (i = 1; i < n; i++) {
    if (A[i - 1][j] > A[i][j]) {
     temp = A[i - 1][j];
     A[i - 1][j] = A[i][j];
     A[i][j] = temp;
    }
   }
  }
  inMT(A, n, m);
 }
 public static void main(String[] args) {
  System.out.print("Nhap so hang n=");
  int n = nhap();
  System.out.print("Nhap so cot m=");
  int m = nhap();
  int[][] A = new int[n][m];
  int i, j;
  for (i = 0; i < n; i++) {
   for (j = 0; j < m; j++) {
   System.out.println("Nhap phan tu thu A[" + (i + 1) + "]["
      + (j + 1) + "]= ");
    A[i][j] = nhap();
   }
  }
  System.out.println("Ma tran nhap vao: ");
  inMT(A, n, m);
  for (i = 0; i < n; i++) {
   for (j = 0; j < m; j++) {
   if (A[i][j] == findMaxMT(A, n, m))
  System.out.println("\nPhan tu o hang " + i + " cot " + j
   + " dat Max: A[" + i + "][" + j + "]= " + A[i][j]);
   }
  }

  phanTuSNT(A, n, m);
  sortColum(A, n, m);
 }
}

Sau đây là bài tập để các bạn luyện tập . Hãy nhỡ luyện tập thường xuyên để có được kết quả ngọt ngào nhất nhé.
Bài 1 :Viết chương trình nhập vào vào ma trận A có n dòng, m cột, các phần tử là những số
nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức
năng sau:
a)     Tìm phần tử lớn nhất của ma trận cùng chỉ số của số đó.
b)     Tìm và in ra các phần tử là số nguyên tố của ma trận
(các phần tử không nguyên tố thì thay bằng số 0).
c )Tìm hàng trong ma trận có nhiều số nguyên tố nhất
Bài 2 :Viết chương trình nhập các hệ số của đa thức P bậc n (0<n<20). Thực hiện các chức năng sau:
a)      Tính giá trị của đa thức P theo công thức Horner:
 P(x)=((((anx+ an-1)x+ an-2... + a1)x+ a0
b)      Tính đạo hàm của đa thức P. In ra các hệ số của đa thức kết quả.
c)      Nhập thêm đa thức Q bậc m. Tính tổng hai đa thức P và Q. 
Source code : here
pass extract : https://coderandtutorial.blogspot.com