Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: Tìm điểm yên ngựa trong ma trận

  1. #1
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Mặc định Tìm điểm yên ngựa trong ma trận

    Vì chức năng tìm kiếm có vẻ không hiệu quả lắm nên mình không biết là đã bị trùng chủ đề chưa nên nếu bị trùng mong mọi người thông cảm và giúp đỡ

    Đề bài như sau: Trong một ma trận 2 chiều m x n 1 phần tử a[i][j] được gọi là điểm yên ngựa của ma trận nếu như nó là phần tử nhỏ nhất trên hàng i và lớn nhất trên hàng j của ma trận. Hãy tìm tất cả các điểm yên ngựa của một ma trận và đưa ra độ phức tạp của thuật toán

    Mình suy nghĩ như này: mình sẽ duyệt các phần tử theo hàng, tìm tất cả các phần tử có giá trị min trong từng hàng cho vào 1 mảng là mảng min_h, sau đó tương tự tìm tất cả các phần tử có giá trị max trong từng cột cho vào 1 mảng là mảng max_c. Tiếp đó là duyệt tất cả các phần tử của ma trận, nếu phần tử nào bằng vs phần tử trong min_h và max_c thì đó là 1 điểm yên ngựa if (a[i][j] == min_h[i] == max_c[j]). Mình nghĩ là thuật toán này đúng(kể cả khi trong hàng hay cột có các phần tử nhỏ nhất hay lớn nhất bị trùng nhau). Nhưng mình nghĩ là cách này hơi dài dòng, vậy bạn nào có thuật toán nào tối ưu không hãy cùng bàn luận và chia sẻ. Thanks 4 reading!

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    3

    Trích dẫn Nguyên bản được gửi bởi Pop Xem bài viết
    Vì chức năng tìm kiếm có vẻ không hiệu quả lắm nên mình không biết là đã bị trùng chủ đề chưa nên nếu bị trùng mong mọi người thông cảm và giúp đỡ

    Đề bài như sau: Trong một ma trận 2 chiều m x n 1 phần tử a[i][j] được gọi là điểm yên ngựa của ma trận nếu như nó là phần tử nhỏ nhất trên hàng i và lớn nhất trên hàng j của ma trận. Hãy tìm tất cả các điểm yên ngựa của một ma trận và đưa ra độ phức tạp của thuật toán

    Mình suy nghĩ như này: mình sẽ duyệt các phần tử theo hàng, tìm tất cả các phần tử có giá trị min trong từng hàng cho vào 1 mảng là mảng min_h, sau đó tương tự tìm tất cả các phần tử có giá trị max trong từng cột cho vào 1 mảng là mảng max_c. Tiếp đó là duyệt tất cả các phần tử của ma trận, nếu phần tử nào bằng vs phần tử trong min_h và max_c thì đó là 1 điểm yên ngựa if (a[i][j] == min_h[i] == max_c[j]). Mình nghĩ là thuật toán này đúng(kể cả khi trong hàng hay cột có các phần tử nhỏ nhất hay lớn nhất bị trùng nhau). Nhưng mình nghĩ là cách này hơi dài dòng, vậy bạn nào có thuật toán nào tối ưu không hãy cùng bàn luận và chia sẻ. Thanks 4 reading!
    Chuẩn bị một ma trận B cùng kích thước với ma trận A. Ban đầu đặt các B[i][j] = 0. Duyệt từng hàng thứ k của A để tìm min, nếu A[k][j] đạt min thì đặt B[k][j] = 1. Sau đó duyệt từng cột thứ j của A để tìm max, nếu A[p][j] đạt max thì kiểm tra, nếu B[p][j] = 1 thì A[p][j] là điểm yên ngựa theo nghĩa của bạn. Độ phức tạp là O(n^2).

  3. #3
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi emngat31 Xem bài viết
    Chuẩn bị một ma trận B cùng kích thước với ma trận A. Ban đầu đặt các B[i][j] = 0. Duyệt từng hàng thứ k của A để tìm min, nếu A[k][j] đạt min thì đặt B[k][j] = 1. Sau đó duyệt từng cột thứ j của A để tìm max, nếu A[p][j] đạt max thì kiểm tra, nếu B[p][j] = 1 thì A[p][j] là điểm yên ngựa theo nghĩa của bạn. Độ phức tạp là O(n^2).
    Nếu như mà trong 1 hàng có 2 giá trị nhỏ nhất thì cũng phải có 2 giá trị tương ứng vào một ma trận phụ nghĩa là công việc tiếp tục là phải xét max của 2 cột tương ứng vs 2 giá trị nhỏ nhất trong hàng vừa tìm đc. Đúng là như của bạn thì thay vì xét cả ma trận thì chỉ xét theo số cột bằng số lượng phần tử min trong hàng. Thanks!

  4. #4
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi emngat31 Xem bài viết
    Chuẩn bị một ma trận B cùng kích thước với ma trận A. Ban đầu đặt các B[i][j] = 0. Duyệt từng hàng thứ k của A để tìm min, nếu A[k][j] đạt min thì đặt B[k][j] = 1. Sau đó duyệt từng cột thứ j của A để tìm max, nếu A[p][j] đạt max thì kiểm tra, nếu B[p][j] = 1 thì A[p][j] là điểm yên ngựa theo nghĩa của bạn. Độ phức tạp là O(n^2).
    Hôm này mình mới code và trong quá trình làm mình nhận ra không cần tới một mảng phụ gì cả. Vì mình đang học PTTK và đánh giá thuật toán nên tất cả mọi thứ phải tối ưu, không còn chút sai sót. Và đây là code của mình, mong mọi người đóng góp ý kiến xem nó đã tối ưu chưa

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    int timmin(int a[20][20], int sh, int sc)
    {
        int k, min=a[sh][0];
        for (k=1;k<sc;k++)  if (a[sh][k]<min)   min = a[sh][k];
        return min;
    }
    int timmax(int a[20][20], int sh, int sc)
    {
        int k, max=a[0][sc];
        for (k=1;k<sh;k++)  if (a[k][sc]>max)   max = a[k][sc];
        return max;
    }
    int main()
    {
        int i,j,n,m,a[20][20],kt=0;
        nhaplai:
        printf ("Nhap so hang va so cot cua ma tran :  ");
        scanf ("%d%d", &n,&m);
        if (n<0||m<0) goto nhaplai;
        for (i=0;i<n;i++)
        for (j=0;j<m;j++)
        {
            printf ("A[%d][%d] = ", i,j);
            scanf ("%d", &a[i][j]);
        }
        for (i=0;i<n;i++)
        {    
             for (j=0;j<m;j++)
             if (a[i][j]==timmin(a,i,m) && a[i][j] == timmax(a,n,j))  
                {
                   printf ("A[%d][%d] = %d la mot diem yen ngua \n", i,j,a[i][j]);
                   kt++;
                }
        }
        if (kt==0) printf ("\n Khong co diem yen ngua nao ");
        getch();
        return 0;
    }

  5. #5
    Ngày gia nhập
    01 2010
    Nơi ở
    Hà Nội
    Bài viết
    128

    Tớ cũng chưa xem xem độ phức tạp của thuật toán bạn đưa ra là bao nhiêu . Nên bạn hãy thử tìm xem độ phức tạp ra sao nhé ? Rồi mình cùng thảo luận xem ,mình tính thì thấy độ phức tạp của bạn là O(max(m,n)^3)thì phải .

  6. #6
    Ngày gia nhập
    08 2011
    Nơi ở
    Trà Vinh
    Bài viết
    20

    Mặc định Tìm điểm yên ngựa trong ma trận

    Code:
    if (a[i][j]==timmin(a,i,m) && a[i][j] == timmax(a,n,j))  
                {
                   printf ("A[%d][%d] = %d la mot diem yen ngua \n", i,j,a[i][j]);
                   kt++;
                }
    Theo mình thì trong điều kiện chỉ cần if(timmin(a,i,m)==timmax(a,n,j)) là được rồi
    Vì min dòng == max cột là được
    Đã được chỉnh sửa lần cuối bởi nguyenphuongcntv : 21-08-2011 lúc 09:10 PM. Lý do: chỉnh sửa tí
    Nó là con của thằng nào ? Con của thằng nào ? Nói mau!!!!!!!!!!!!!!!

  7. #7
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Hòi tôi đi học không có đặt nặng vấn đề độ phức tạp cho nên tôi hoàn toàn mù tịt về con tóan O(x) O(y) gì gì đó.

    Tuy nhiên, nhìn sơ qua cách tính của Pop thì thấy cứ mỗi a[i][j] lại phải tìm min, và nếu thỏa thì lại phải tìm max.

    Thực sự ra, nếu dùng thuật toán duyệt từng phần từ thì hàm timmin và timmax không cần. Dùng hàm IsMin và IsMax sẽ nhanh được hơn một chút (IsMin = xét xem trị ấy có phải là min của dòng hay không. Hàm này nhanh hơn vì theo trung bình, nó chỉ phải duyệt 1/2 dòng thay vì trọn dòng)

    C Code:
    1. // hàm duyệt dòng i của mảng a[m][n] để xét xem trị x có phải là nhỏ nhất
    2. int NhoNhatDong(int a[][SOCOT], int m, int n, int i, int x)
    3. {
    4.   for (int j=0; j < m; j++)
    5.     if (a[i][j] < x) return 0; // không phải min
    6.   return 1;
    7. }
    8.  
    9. // hàm duyệt cột j của mảng a[m][n] để xét xem trị x có phải là lớn nhất
    10. int LonNhatCot(int a[][SOCOT], int m, int n, int j, int x)
    11. {
    12.   for (int i=0; i < m; i++)
    13.     if (a[i][j] > x) return 0; // không phải max
    14.   return 1;
    15. }
    16.  
    17. // code trong main
    18. ...
    19.  
    20. for (i=0; i<m; i++)
    21. {
    22.   for (j=0; j<n; j++)
    23.   {
    24.     if (NhoNhatDong(a, m, n, i, a[i][j]) && LonNhatCot(a, m, n, j, a[i][j]))
    25.        printf ("A[%d][%d] = %d la mot diem yen ngua \n", i,j,a[i][j]);
    26.   }
    27. }
    28. // chỉnh sửa để tính cho trường hợp không có điểm yên ngựa

    tb tôi không hề nói thuật toán này hay hơn thuật toán dùng 1 mảng khác để ánh xạ (map) pt min/max

  8. #8
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Trích dẫn Nguyên bản được gửi bởi nguyenphuongcntv Xem bài viết
    Code:
    if (a[i][j]==timmin(a,i,m) && a[i][j] == timmax(a,n,j))  
                {
                   printf ("A[%d][%d] = %d la mot diem yen ngua \n", i,j,a[i][j]);
                   kt++;
                }
    Theo mình thì trong điều kiện chỉ cần if(timmin(a,i,m)==timmax(a,n,j)) là được rồi
    Vì min dòng == max cột là được
    Trông thì gọn hơn nhưng đối với ngôn ngữ C thì làm như vậy tính cực hơn.
    Code của Pop gọi hàm timmin, so sánh thấy ổn rồi mới gọi hàm timmax tiếp, nếu không ổn thì khỏi phải gọi timmax.
    Theo đề nghị của bạn thì lúc nào cũng phải chạy đủ hai hàm.

  9. #9
    Ngày gia nhập
    01 2010
    Nơi ở
    Hà Nội
    Bài viết
    128

    Bài này các bạn chỉ cần để ý 1 điều một ma trận chỉ có tối đa min(n,m) phần tử đạt yêu cầu .
    Nên ta sẽ làm như sau :
    tìm phần tử min của từng dòng sau đó với phần tử min đó kiểm tra xem có là max cột ko ?
    Ta ko cần phải kiểm tra với từng phần tử của ma trận rồi xem có max cột hay min dòng hay ko
    Cách này thì với O(n^2) thì phải . Thân !

  10. #10
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi kids301090 Xem bài viết
    Bài này các bạn chỉ cần để ý 1 điều một ma trận chỉ có tối đa min(n,m) phần tử đạt yêu cầu .
    Nên ta sẽ làm như sau :
    tìm phần tử min của từng dòng sau đó với phần tử min đó kiểm tra xem có là max cột ko ?
    Ta ko cần phải kiểm tra với từng phần tử của ma trận rồi xem có max cột hay min dòng hay ko
    Cách này thì với O(n^2) thì phải . Thân !
    Việc tìm min của từng dòng thì cũng sẽ phải duyệt qua n x m phần tử của mảng mới biết được min của từng dòng. Code của e riêng phần giải thuật thì nó cũng duyệt qua n x m phần tử mà.

    @@ VoTichSu: Em không hiểu tại sao: "IsMin = xét xem trị ấy có phải là min của dòng hay không. Hàm này nhanh hơn vì theo trung bình, nó chỉ phải duyệt 1/2 dòng thay vì trọn dòng" bởi vì sau vòng for anh cũng gọi hàm con và hàm con kia cũng duyệt tới m mà . Em nhận thấy phần chỉnh sửa của anh rút bớt được 2 biến, tuy không tìm max và min nhưng đều phải thực hiện phép duyệt n x m phần tử, nên code của anh gọn hơn được của em (n x m x 2) phép so sánh. Vậy anh có thuật toán nào mà không phải duyệt qua tất cả các phần tử không? . Quả thực e cũng đang mù tịt về mấy con số O(x) O(y) gì gì đó, đọc sách không hiểu nổi cho nên cũng chẳng biết tính toán xem độ phức tạp thuật toán của mình là bao nhiêu cả
    Code:
    Sờ tu pít :(

Các đề tài tương tự

  1. Cho thuê chung cư Cầu Giấy: Trung yên 1, làng quốc tế TL, Yên Hòa, Dịch Vọng (J.VCV)
    Gửi bởi janpibk trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 30-05-2013, 04:44 PM
  2. Lập trình C++ tìm điểm yên ngựa trong ma trận nhập vào từ file input
    Gửi bởi xuandao trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 12-04-2013, 03:34 AM
  3. Bán chung cư Trung Yên Plaza Trần Duy Hưng, sắp vào ở, giá 33,5tr
    Gửi bởi dongocduy294 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 07-01-2013, 05:43 PM
  4. tìm điểm yên ngựa trong ma trận
    Gửi bởi longvp trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 20-05-2010, 06:33 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn