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

[Masterwin]

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)

[6220119]

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.

[zkday2686]

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ỉ.

[Berberin]

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

#include <cstdlib>#include <iostream>#include <memory.h> using namespace std; const int N = 4;const int A[N][N] = {  {1, 2, 4, 3},   {3, 4, 2, 5},   {2, 5, 4, 3},   {4, 3, 2, 5}}; //ma trận (input) int _B[N*N]; //Mảng tạm để chứa tổng N*2-1 đường chéoint *B = _B + N - 1; //Dịch đi 1 đoạn để xài chỉ số âm từ -N+1 đến N-1 int main(){  memset(_B, 0, sizeof(_B)); //Khởi tạo cho các tổng các đường chéo = 0   //Tính tổng  for (short i = 0; i<N; i++)    for (short j = 0; j<N; j++)       B[i-j] += A[i][j]; // A[i][j] nằm trên đường chéo i-j    //Tìm tổng lớn nhất  int Max = _B[0];  for (int i = 1; i<N*2; i++)     if (Max < _B[i]) Max = _B[i];    //Xuất kq  cout << Max <<endl;   system("pause");  return EXIT_SUCCESS;  }

[Masterwin]

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

[6220119]

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ả ?

[Berberin]

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