• Thứ Sáu, 17/03/2006 14:16 (GMT+7)

    Lập trình ma trận

    Câu hỏi :
    Có 1 ma trận 3*3 như sau:

    | 1 | 2 | 3 |
    | 4 | 5 | 6 |
    | 7 | 8 | 9 |

    Xin hướng dẫn cách tạo 1 ma trận số ngẫu nhiên từ 1 đến 9. Điều kiện: 1 số đã có không được lặp lại trên 1 dòng và cột.


    Trả lời :

    Bạn không yêu cầu miêu tả giải thuật trên ngôn ngữ cụ thể nên chúng tôi dùng ngôn ngữ VB, nếu cần bạn hãy chuyển nó về ngôn ngữ mình cần dùng. Chúng tôi phân tích bài toán của bạn ra 2 bài toán khác nhau:

    1. Bài toán tạo ma trận ngẫu nhiên 3*3 dùng 9 giá trị khác nhau từ 1 tới 9, giá trị được dùng cho ô (i,j) là duy nhất trong hàng i và duy nhất trong cột j. Đây là điều kiện mà bạn yêu cầu. Ý tưởng là duyệt từng hàng theo thứ tự từ trên xuống, mỗi hàng duyệt từng cột. Ứng với ô (i,j) ta lấy 1 số ngẫu nhiên từ 1 tới 9 rồi kiểm tra xem giá trị này đã được dùng cho ô nào trong hàng i hay cột j chưa, nếu chưa ta dùng giá trị này, còn nếu đã dùng rồi thì bỏ và lặp lại qui trình lấy số ngẫu nhiên khác và kiểm tra... Cụ thể đoạn chương trình VB miêu tả thuật toán trên được viết như sau:

    Sub TaoRand3x3()
    Dim i As Integer
    Dim j As Integer
    Dim cot As Integer
    Dim hang As Integer
       ‘khởi động các giá trị ban đầu của các ô về 0
       For i = 0 To 2
          For j = 0 To 2
             matran(i, j) = 0
          Next j
       Next i
       ‘ duyệt từng ô và tạo số ngẫu nhiên cho ô đó
       For i = 0 To 2
          For j = 0 To 2
             Do
                ‘lấy 1 số ngẫu nhiên từ 0 đến 9
                gtri = Round(Rnd() * 9, 0)
                ‘nếu = 0 thì bỏ rồi lặp lại tìm số khác
                If gtri = 0 Then GoTo tieptuc
                ‘so sánh với các ô cùng hàng i
                For cot = 0 To j - 1
                   If gtri = matran(i, cot) Then GoTo tieptuc
                Next cot
                ‘so sánh với các ô cùng cột j
                For hang = 0 To i - 1
                   If gtri = matran(hang, j) Then GoTo tieptuc
                Next hang
                ‘nếu chưa có thì dùng giá trị vừa tìm được
                matran(i, j) = gtri
                Exit Do
              tieptuc:
              Loop While True
          Next j
       Next i
    End Sub

    2. Bài toán tổng quát hơn là tạo ma trận ngẫu nhiên 3*3 dùng 9 giá trị khác nhau từ 1 tới 9, mỗi giá trị chỉ được dùng bởi 1 ô trong ma trận. Ý tưởng là đưa 9 giá trị (từ 1 tới 9) vào 1 danh sách rồi gọi hàm lấy số ngẫu nhiên tên là Rnd() để lấy chỉ số ngẫu nhiên (từ 1 đến 9), chỉ số này sẽ xác định phần tử trong danh sách. Sau khi lấy phần tử đầu, danh sách còn 8 giá trị, ta lấy 1 chỉ số ngẫu nhiên từ 1 tới 8 để xác định chỉ số phần tử thứ 2 cần dùng trong danh sách. Sau khi lấy phần tử thứ 2, danh sách còn 7 giá trị, ta tiếp tục lặp lại công việc trên để xác định lần lượt các giá trị cần dùng. Cụ thể đoạn chương trình VB miêu tả thuật toán trên được viết như sau:

    Sub TaoRand3x3()
    Dim i As Integer
    Dim j As Integer
    Dim idx As Integer
    Dim max As Integer
    Dim dsach(0 To 8) As Integer
       ‘ khởi động danh sách chứa các số cần dùng
       For i = 0 To 8
           dsach(i) = i
       Next i
       max = 8
       ‘ duyệt từng ô và tạo số ngẫu nhiên cho ô đó
       For i = 0 To 2
          For j = 0 To 2
              ‘lấy 1 số ngẫu nhiên từ 0 đến max
              idx = Round(Rnd() * max, 0)
              ‘dùng giá trị nằm ở chỉ số idx
              matran(i, j) = dsach(idx)
              ‘bỏ giá trị vừa dùng ra khỏi danh sách
              While idx < max
                 dsach(idx) = dsach(idx + 1)
                 idx = idx + 1
              Wend
              ‘thiết lập lại cận trên của danh sách chứa giá trị
              max = max - 1
           Next j
       Next i
    End Sub

    Chuyên mục: Lập trình