Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Tìm số lun xuất hiện trong mỗi hàng của mảng 2chiều

  1. #1
    Ngày gia nhập
    05 2010
    Bài viết
    27

    Mặc định Tìm số lun xuất hiện trong mỗi hàng của mảng 2chiều

    Ví dụ mình cho 1 mảng 2 chiều với mỗi hàng được sắp xếp tăng dần
    int a[][]={{1,2,4},{2,4,6},{0,1,2}};
    Hỏi tìm xuất hiện lặp lại trong mỗi hàng : ở đây là số 2.
    Ý tưởng của mình là lấy hàng đầu tiên {1,2,4} rồi dùng a[0][j] (i chạy từ 0 đến 3) . Ví dụ với a[0][0]=1 thì duyệt hàng thứ a[1][j] xem số 1 có xuất hiện ko nếu có thì duyệt tiếp hàng thứ 2 ko có thì tăng lên a[0][j+1].ở đây mình chưa sử dụng ý tưởng mỗi hàng đã được sắp xếp tăng dần.
    Vậy bạn nào có ý tưởng nào không. giúp mình với, mình đang rất cần code theo cách khác ý tưởng trên

  2. #2
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Ý tưởng của mình cũng tương tự:
    - Duyệt từng phần tử của hàng đầu tiên
    - Kiểm tra các hàng tiếp theo có phần tử đó không bằng tìm kiếm nhị phân (do được sắp xếp)
    - Nếu có ở tất cả các hàng thì đó là kết quả cần tìm.

  3. #3
    Ngày gia nhập
    03 2010
    Nơi ở
    My Home
    Bài viết
    772

  4. #4
    Ngày gia nhập
    03 2012
    Nơi ở
    Bình Thuận(đang học ở HCM)
    Bài viết
    2

    Nếu không tìm theo hàng thì tìm theo cột!
    Để lak nữa tui code cho giờ bận đi học rồi!@@

  5. #5
    Ngày gia nhập
    05 2010
    Nơi ở
    Tp. HCM
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi hoangtukhung Xem bài viết
    Ví dụ mình cho 1 mảng 2 chiều với mỗi hàng được sắp xếp tăng dần
    int a[][]={{1,2,4},{2,4,6},{0,1,2}};
    Hỏi tìm xuất hiện lặp lại trong mỗi hàng : ở đây là số 2.
    Ý tưởng của mình là lấy hàng đầu tiên {1,2,4} rồi dùng a[0][j] (i chạy từ 0 đến 3) . Ví dụ với a[0][0]=1 thì duyệt hàng thứ a[1][j] xem số 1 có xuất hiện ko nếu có thì duyệt tiếp hàng thứ 2 ko có thì tăng lên a[0][j+1].ở đây mình chưa sử dụng ý tưởng mỗi hàng đã được sắp xếp tăng dần.
    Vậy bạn nào có ý tưởng nào không. giúp mình với, mình đang rất cần code theo cách khác ý tưởng trên
    //////////////////////////////////////////////////////

    Mình có một ý tưởng thế này:
    Cho ma trận A[3][3]
    1 2 4
    2 4 6
    0 1 2
    Giờ để ý sẽ thấy rằng: Giả sử nếu có một phần tử x nào đó đều xuất hiện trong tất cả các dòng thì suy ra nó sẽ phải xuất hiện trong dòng đầu (dòng thứ 0), điều này luôn đúng . Do đó ta chỉ cần xét tới các phần tử trong dòng đầu thôi. Vì sao ? vì những phần tử không có trong dòng đầu sẽ ko xuất hiện trong tất cả các dòng. Như vậy, thay vì xét tất cả các phần tử, ta chỉ xét các phần tử dòng đầu để tìm phần tử thỏa yêu cầu.
    Bây giờ, trong khi xét tới từng phần tử x trong dòng đầu thì ta lại áp dùng tính chất như trên, thấy rằng chỉ cần x không nằm trong dòng tiếp theo (dòng thứ 1) thì x không thỏa yêu cầu, và ta lại xét sang phần tử kế tiếp. Làm như thế sẽ tiết kiệm được thời gian xử lý của chương trình

    Đó là ý tưởng của mình
    Kẻ hành khất
    Du xuân
    Hoa quả đầy túi


  6. #6
    Ngày gia nhập
    05 2010
    Bài viết
    27

    Mặc định Tìm số lun xuất hiện trong mỗi hàng của mảng 2chiều

    Trích dẫn Nguyên bản được gửi bởi cvhau.tt Xem bài viết
    //////////////////////////////////////////////////////

    Mình có một ý tưởng thế này:
    Cho ma trận A[3][3]
    1 2 4
    2 4 6
    0 1 2
    Giờ để ý sẽ thấy rằng: Giả sử nếu có một phần tử x nào đó đều xuất hiện trong tất cả các dòng thì suy ra nó sẽ phải xuất hiện trong dòng đầu (dòng thứ 0), điều này luôn đúng . Do đó ta chỉ cần xét tới các phần tử trong dòng đầu thôi. Vì sao ? vì những phần tử không có trong dòng đầu sẽ ko xuất hiện trong tất cả các dòng. Như vậy, thay vì xét tất cả các phần tử, ta chỉ xét các phần tử dòng đầu để tìm phần tử thỏa yêu cầu.
    Bây giờ, trong khi xét tới từng phần tử x trong dòng đầu thì ta lại áp dùng tính chất như trên, thấy rằng chỉ cần x không nằm trong dòng tiếp theo (dòng thứ 1) thì x không thỏa yêu cầu, và ta lại xét sang phần tử kế tiếp. Làm như thế sẽ tiết kiệm được thời gian xử lý của chương trình

    Đó là ý tưởng của mình
    Hình như giống ý tưởng trên, ý tưởng trên cũng đem phần tử dòng dầu ra để làm lính canh để tìm các hàng kế tiếp mà . Hay ý bạn khác

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

    Trích dẫn Nguyên bản được gửi bởi hoangtukhung Xem bài viết
    Ví dụ mình cho 1 mảng 2 chiều với mỗi hàng được sắp xếp tăng dần
    int a[][]={{1,2,4},{2,4,6},{0,1,2}};
    Hỏi tìm xuất hiện lặp lại trong mỗi hàng : ở đây là số 2.
    Ý tưởng của mình là lấy hàng đầu tiên {1,2,4} rồi dùng a[0][j] (i chạy từ 0 đến 3) . Ví dụ với a[0][0]=1 thì duyệt hàng thứ a[1][j] xem số 1 có xuất hiện ko nếu có thì duyệt tiếp hàng thứ 2 ko có thì tăng lên a[0][j+1].ở đây mình chưa sử dụng ý tưởng mỗi hàng đã được sắp xếp tăng dần.
    Vậy bạn nào có ý tưởng nào không. giúp mình với, mình đang rất cần code theo cách khác ý tưởng trên
    Giả sử mảng 2 chiều kích thước n*n
    Cách này của bạn, với mỗi số thuộc dòng đầu (n số), để tìm xem số đó xuất hiện trong dòng 2 không, bạn cần n phép so sánh. Có n - 1 dòng sau dòng 1, nên độ phức tạp của thuật toán sẽ là O(n*n*(n-1)) = O(n^3)

    Nếu dựa trên tính chất tăng dần của dãy để tìm kiếm nhị phân như cách của boss14420, thì độ phức tạp giảm được 1 chút thành O(n^2*logn). Cài đặt tìm kiếm nhị phân phức tạp hơn so với việc for để so sánh.

    Cách 3: (cũng dựa vào tính tăng dần của dãy)
    -Lưu mảng p[n] là n chỉ số cột hiện tại của mỗi dòng (lưu bằng con trỏ đến phần tử trong dòng, mình dùng từ chỉ số cho dễ hiểu), ban đầu gán bằng p[i] = &a[i][0] (trỏ đến vị trí đầu tiên của dòng ==> cột 0).
    -Nếu tồn tại i, j sao cho *p[i] < *p[j] => tăng p[i] (trỏ đến vị trí kế tiếp trong dòng)
    -Nếu không: tất cả các con trỏ đang trỏ đến phần tử bằng nhau, đó là kết quả cần tìm.

    Cách này, với mỗi p[i] sẽ chỉ cần tăng tối đa n lần, vậy độ phức tạp là O(n^2)

    Code giả:
    Code:
    int* p[n]; 
    for (i=0..n-1) p[i] = &a[i][0];
    for (i=0..n-1) a[i][n] = số cực lớn; // đặt "lính canh" tại cuối mỗi dòng
    int x = a[0][0];
    while(x < số cực lớn lính canh) {
      for (i=0..n-1) {
        while (*p[i] < x) ++p[i];
        if (*p[i] > x) {x = p[i]; break;}
      }
      if (i == n) // tất cả các con trỏ trỏ đến số bằng nhau
        --> in nghiệm;
    }

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

  1. Lập trình C++ Mình muốn hỏi về bài toán tìm số lần xuất hiện của ký tự nhiều nhất trong chuỗi và số lần xuất hiện
    Gửi bởi ducky trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 06-09-2013, 11:17 AM
  2. Lập trình C Xuất nhập file trong C kết quả xuất ra không đúng?
    Gửi bởi lamhoang100 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 05-06-2013, 05:38 PM
  3. Đếm các xâu thuận nghịch xuất hiện trong file và số lần xuất hiện của các xâu đó
    Gửi bởi orchidshl1 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 19-09-2012, 10:47 AM
  4. Trả lời: 1
    Bài viết cuối: 27-04-2011, 09:30 PM
  5. bài toán tìm số lần xuất hiện các phần tử xuất hiện trong 1 chuỗi
    Gửi bởi tuan_anhhhh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 11-03-2008, 09:30 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