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

Đề tài: Tìm ma trận con có tổng lớn nhất

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

    Mặc định Tìm ma trận con có tổng lớn nhất

    Ai giải được bài này , giúp với

  2. #2
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    hê, trên lớp vừa học bài tìm dãy con có tổng lớn nhất trong dãy cho trước, dùng quy hoạch động, độ phức tạp On. Xem ở đây:
    http://d.violet.vn/uploads/resources/336/373220/sco234.htm

    chỉ cần đọc phần cuối thôi.

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

    Cái mình cần là ma trận , mảng 1 chiều thi code được lâu rùi , thank bạn

  4. #4
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    không có ai thả sung vào miệng bạn đâu, nếu không tự mở rộng từ mảng lên ma trận được thì làm chay đi, O(n^4) ráng chịu.

  5. #5
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    ma trận 2 chìu chuyển thành 1 chìu cũng được thôi chứ có j đâu.còn tính kiểu 2 chìu như pn nói thì pải ttính thôi.
    vdu mà trận 9x9 sẽ có 9 cục 3x3 xem như từ 0-8 mình pải tính tổng của từng cục.bây giờ là suy ngĩ cách tính tổng cùa 9 cục đó.nên nhớ mỗi cục sẽ có ô trung tâm
    HT117-5277

  6. #6
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    140

    Cool Tìm ma trận con có tổng lớn nhất

    Đây là bài quy hoạch động mình viết cho mảng con.
    C++ Code:
    1. #include <iostream>
    2. #include <conio.h>
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7.     /* mảng ví dụ có 10 phần tử */
    8.     int p[] = {1, 3, 4, 2, 5, 7, 9, 10, 0, 2};
    9.     int n = 10;
    10.  
    11.     /* biến m lưu kích thước mảng con */
    12.     int m = 3;
    13.  
    14.     /* biến trongluong lưu trọng lượng các mảng con:
    15.      * với: trongluong[i] là tổng giá trị của mảng con với phần tử kết thúc là i,
    16.      * theo ví dụ thì:
    17.      * trongluong[2] = p[0] + p[1] + p[2]
    18.      * trongluong[3] = p[1] + p[2] + p[3]
    19.      */
    20.     int trongluong[10];
    21.  
    22.     trongluong[0] = p[0];
    23.     for (int i=1; i<m; i++)
    24.         trongluong[i] = trongluong[i-1] + p[i];
    25.  
    26.     /* biến dapan lưu vị trí cuối của mảng con có trọng lượng lớn nhất */
    27.     int dapan = m-1; /* m-1 là vị trí của mảng con đầu tiên */
    28.     for (int i=m; i<n; i++)
    29.     {
    30.         trongluong[i] = trongluong[i-1] + p[i] - p[i-m]; /* kể từ mảng con thứ 2 trở đi,
    31.                                                           * cách tính trọng lượng là ta thêm
    32.                                                           * phần tử của dãy mới và bớt
    33.                                                           * phần tử đầu dãy cũ
    34.                                                           */
    35.         if (trongluong[i] > trongluong[dapan]) /* xét xem trọng lượng của mảng con vừa tính
    36.                                                 * có lớn hơn cái đã lưu không? Nếu có thì
    37.                                                 * cập nhật đáp án
    38.                                                 */
    39.             dapan = i;
    40.     }
    41.  
    42.     cout << "Mang con co " << m << " phan tu co trong luong lon nhat la:" << endl;
    43.     for (int i=dapan-m+1; i<=dapan; i++)
    44.         cout << p[i] << " ";
    45.     getch();
    46.     return 0;
    47. }
    Rẹt rẹt..

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

  1. Tin tuổi trẻ - cập nhật thông tin giới trẻ hot và nóng
    Gửi bởi apolo1512 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: 13-12-2013, 10:15 AM
  2. căn hộ N05 trần duy hưng, chung cư N05 trần duy hưng, chênh thấp nhất thị trường
    Gửi bởi ephat_tt86 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: 13-01-2012, 10:36 AM
  3. Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 AM
  4. website cập nhật nhiều laptop mới và hot nhất, bán trả góp thủ tục đơn giản
    Gửi bởi diemnt 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: 02-07-2010, 03:23 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