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

Đề tài: [ Solved ]Tổng đường chéo lớn nhất

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

    Mặc định [ Solved ]Tổng đường chéo lớn nhất

    Cho một bảng A gồm N x N số nguyên (N <= 100), các dòng được đánh số từ trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối 2 ô (1,1) và (N,N). Như vậy trên bảng có 2N-1 đường chéo song song với đường chéo chính.

    Bài toán : Hãy tìm đường chéo song song với đường chéo chính có tổng các phần tử trên đường chéo đó là lớn nhất.

    Nhập vào :
    Dòng đầu chứa số N
    Dòng thứ i trong N dòng tiếp theo chứa N số nguyên lần lượt ứng với các phần tử nằm trên dòng i của bảng A.

    Xuất ra :
    In ra tổng các phần tử nằm trên đường chéo có tổng lớn nhất.

    VD :


    Với bảng A như hình vẽ, đường chéo chính chính là đường chéo có tổng lớn nhất (bằng 14).
    Nhập :
    4 4
    1 2 4 3
    3 4 2 5
    2 5 4 3
    4 3 2 5

    Xuất : 14

    Mời các pác cùng giải thuật bài này (kèm theo code càng tốt)

  2. #2
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Dễ mà, chỉ cần biết tính chất trong đg` chéo chính là các ptử a[i][j] có i-j bằng nhau sau đó xài vòng lặp là đc.
    VD a[0][0],a[1][1],a[2][2],... i-j=0
    a[1][0],a[2][1],a[3][2],... i-j=1
    Hoặc chạy cái vòng lặp theo cột 0, và vòng lặp theo hàng 0 rồi tăng chỉ số theo đg` chéo chính cũng đc.
    code ra gió bão

  3. #3
    Ngày gia nhập
    09 2007
    Bài viết
    724

    dùng 2 vòng lặp và tính chất j-i là một số không đổi + 1 flagMax chứa giá trị max hiện thời là ok.

    cách cải tiến hơn thì hiện giờ chưa nghĩ ra.

    mà không biết nếu dùng 1 vòng lặp có ra không nhỉ.

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

    Phân tích như các bạn ở trên.
    Code này tính toán hơi rườm rà tí nhưng dễ hiểu, cậu ktra lại xem vì tớ ko có compiler
    C++ Code:
    1. #include <cstdlib>
    2. #include <iostream>
    3. #include <memory.h>
    4.  
    5. using namespace std;
    6.  
    7. const int N = 4;
    8. const int A[N][N] = {
    9.   {1, 2, 4, 3},
    10.   {3, 4, 2, 5},
    11.   {2, 5, 4, 3},
    12.   {4, 3, 2, 5}
    13. }; //ma trận (input)
    14.  
    15. int _B[N*N]; //Mảng tạm để chứa tổng N*2-1 đường chéo
    16. int *B = _B + N - 1; //Dịch đi 1 đoạn để xài chỉ số âm từ -N+1 đến N-1
    17.  
    18. int main(){
    19.   memset(_B, 0, sizeof(_B)); //Khởi tạo cho các tổng các đường chéo = 0
    20.  
    21.   //Tính tổng
    22.   for (short i = 0; i<N; i++)
    23.     for (short j = 0; j<N; j++)
    24.       B[i-j] += A[i][j]; // A[i][j] nằm trên đường chéo i-j
    25.  
    26.   //Tìm tổng lớn nhất
    27.   int Max = _B[0];
    28.   for (int i = 1; i<N*2; i++)
    29.     if (Max < _B[i]) Max = _B[i];
    30.  
    31.   //Xuất kq
    32.   cout << Max <<endl;
    33.  
    34.   system("pause");
    35.   return EXIT_SUCCESS; 
    36. }
    Đã được chỉnh sửa lần cuối bởi Berberin : 01-09-2008 lúc 01:51 PM.

  5. #5
    Ngày gia nhập
    08 2008
    Bài viết
    5

    Code chạy ngon, nhưng nếu code mở rộng ra N là số nguyên bất kỳ nữa thì càng tốt , code của bạn chỉ đặt N=4 thui

  6. #6
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Mặc định [ Solved ]Tổng đường chéo lớn nhất

    code này viết cho trg` hợp N số đó, ko lẽ bạn ko biết cách chuyển lại hả ?
    code ra gió bão

  7. #7
    Ngày gia nhập
    08 2008
    Bài viết
    22

    Ngon bug tè le tớ sửa lại ngay giờ , cái vụ N bất kì bạn tự làm đi.

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

  1. [ Solved ]Kiểm tra kí tự nhập vào
    Gửi bởi hahonga3 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 26
    Bài viết cuối: 15-11-2008, 04:31 PM
  2. [ Solved ]Nhập thông tin cho 1 lớp từ tệp dữ liệu ?
    Gửi bởi khanhtungx7 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 04-11-2008, 10:32 AM
  3. [ Solved ]Xét giá trị của 1 số khi nhập
    Gửi bởi lovedtn trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 20-10-2008, 01:21 AM
  4. [ Solved ]Lỗi nhập nhằng trong chuyển kiểu
    Gửi bởi demontaihack trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 10
    Bài viết cuối: 08-09-2008, 10:17 PM
  5. [ Solved ]Xuất nhập tập tin!!
    Gửi bởi yentin3 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 12-04-2008, 09:49 AM

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