Tổng láng giềng!

[Nemo]

Hôm qua nhóm 2 của CD đi thực hành tin.Thầy giáo cho một bài toán khá hay:
+đề bài: Nhập một ma trận n*m.Tìm điểm có tổng các láng giềng là lớn nhất.(Tổng các láng giềng của điểm (i,j) là tổng các số ở các ô có điểm chung với điểm (i,j) trong ma trận.Số láng giềng lớn nhất của một điểm dễ thấy là 8 láng giềng).

Bài này nếu không có giải pháp hợp lý thì sẽ phải đi theo cách trâu bò.Nhưng thầy giáo đưa cho một giải pháp rất hay.Mọi người thử suy nghĩ,tối tôi sẽ post lên (lúc đi quên mang USB).

[lang tu IT]

độ phức tạp tối đa là 8*m*n, mà m,n thì có giới hạn. Vậy làm sao mà chạy lâu. Bạn làm chạy trong bao lâu thì mình chạy trong bấy lâu với cách duyệt trâu bò

[Hận Đời Không Đối Thủ]

chính xác độ phức tạp của thuật toán lớn nhất chỉ là 8*m*n ~> rất bé.Chúng ta chỉ cần 1 viền bao quanh toàn 0.Khi đó tất cả các phần tử đều có 8 láng giềng.Xét tổng các láng giềng của từng phần tử một.Nếu nó là lớn nhất thì lưu lại (thử với từng phần tử của ma trận một).Code tối post sau,giờ đang có phim :21:

[Nemo]

tôi không nói về tốc độ,mà nói về cài đặt.

[Hận Đời Không Đối Thủ]

#include <stdio.h>
#include <conio.h>
define cot[8]=(-1,0,1,1,-1,1,0,1) , hang[8]=(-1,-1,-1,0,0,1,1,1); //cái này để cộng nhanh các láng giềng thôi ~lý giải sau
int i , j , m , n , max , luuh , luuc , t ;
int a[101][101]; // mảng a(m,n)
void nhap()
{
cái nhập này tự viết nhé.Nhớ là chỉ nhập a[i,j] từ [1,1] đến [m,n] nhé
}
void chuanbi()
{
for (i = 0 , i <= m , i++)
for (j=0 , j <= n , j++) a[ i ][ j ] = 0 ;
//tạo viền bao để đảm bảo khi cộng tất cả cá phần tử của mảng đều có 8 láng giềng,khi cộng có viền bao quanh sẽ không phải xét trường hợp bị tràn ngoài như ô (1,1)
max = 0 ;
}
void luucauhinh()
{
max = t ; luuh = i ; luuc = j;
}
void xuly()
{
int k ;
for (i=1 , i < m , i++)
for (j=1 , j < n , j++)
{
t = 0;
for (k=1 , k < 8 , k++)
t = t + a [ i + cot[k] ][ j + hang[k] ] ;
if ( t > max ) luucauhinh() ;
}
}
void main()
{
nhap();
chuanbi();
xuly();
printf ("phan tu co tong lang gieng lon nhat la: a[ %d ][ %d ]", luuh , luuc);
printf ("tong la :%d ",max);
getch();
}
lý giải nhé,khởi tạo cái mảng hang[8] và cot[8] là để cộng nhanh các láng giềng của a[i,j].Để ý là nếu muốn cộng các phần tử láng giềng của a[i,j] thì sẽ phải cộng a[ i-1 , j-1 ] ; a[ i - 1 , j ] ;.. chính vì thế ta làm 2 cái mảng này cộng cho khỏe :)) ,Hiểu rồi chứ :-?
Còn nữa nói trước là code này chỉ mang tính tham khảo thuật toán thôi nhé,viết không test mà :))

[Nemo]

+code của ông MA tôi sẽ test lại,nhưng chắc là chính xác rồi.
+còn đây là code của tôi,tôi chưa tối ưu lại cài đặt,lúc khác sẽ cài đặt lại:

//Tong lang gieng
#include<iostream.h>
#include<conio.h>
int a[100][100],s[100][100],n;
int di[8]={-1,-1,-1,0,0,1,1,1};
int dj[8]={-1,0,1,-1,1,-1,0,1};
void enter(){ //Ham nhap ma tran
int i,j;
cout<<"\nNhap cac gia tri cua ma tran:";
for(i=0;i<n;++i)
for(j=0;j<n;++j) {
cout<<"\na["<<i+1<<","<<j+1<<"]=";cin>>a[i][j];
}
}
int sumij(int i,int j){
int sum=0,k;
for(k=0;k<8;++k) {
if(((i+di[k])>=0)&&((i+di[k])<=n-1)&&((j+dj[k])>=0)&&((j+dj[k])<=n-1))
sum+=a[i+di[k]][j+dj[k]];
}
s[i][j]=sum;
return sum;
}
void search() {
int i,j,d,hi,cj;
d=0;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(s[i][j]>d){
d=s[i][j];
hi=i;
cj=j;
}
else {
hi=0;
cj=0;
}
cout<<"\nPhan tu co tong lang gieng lon nhat la a["<<hi+1<<","<<cj+1<<"]="<<a[hi][cj];
}
main() {
int i,j;
cout<<"\nNhap cap cua ma tran:";cin>>n;
cout<<"\nNhap ma tran:\n";
enter();
for(i=0;i<n;++i)
for(j=0;j<n;++j)
sumij(i,j);
search();
getch();
}

[Hận Đời Không Đối Thủ]

code của nemo hơi dài mới đọc qua nhưng cách này hơi dài,đâu cần 2 mảng để lưu trữ làm gì,tốt nhất là làm đến đâu so sánh đến đó như cách của tôi ~> vừa đỡ tốn dữ liệu lại không mất thêm 1 vòng for m*n lần để kiểm tra

[Nemo]

+Thì tôi chưa tối ưu lại mà.
+Nói chung cả 2 cách phần quan trong nhất của thuật toán cũng thể hiện được rồi (mảng đánh dấu láng giềng).Chỉ khác nhau chút xíu thôi

[Nemo]

Hôm trươc code tôi đưa lên hơi lăng nhằng,thậm chí còn sai.Tôi đã sửa,xin được đưa lên:

//Tong lang gieng
#include<iostream.h>
#include<conio.h>
int a[100][100],s[100][100],n;
int di[8]={-1,-1,-1,0,0,1,1,1};
int dj[8]={-1,0,1,-1,1,-1,0,1};
void enter(){ //Ham nhap ma tran
int i,j;
cout<<"\nNhap cac gia tri cua ma tran:";
for(i=0;i<n;++i)
for(j=0;j<n;++j) {
cout<<"\na["<<i+1<<","<<j+1<<"]=";cin>>a[i][j];
}
}
int sumij(int i,int j){
int sum=0,k;
for(k=0;k<8;++k) {
if(((i+di[k])>=0)&&((i+di[k])<=n-1)&&((j+dj[k])>=0)&&((j+dj[k])<=n-1))
sum+=a[i+di[k]][j+dj[k]];
}
s[i][j]=sum;
return sum;
}
void search() {
int i,j,d,hi,cj;
d=0;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(s[i][j]>d){
d=s[i][j];
hi=i;
cj=j;
}
else {
hi=0;
cj=0;
}
cout<<"\nPhan tu co tong lang gieng lon nhat la a["<<hi+1<<","<<cj+1<<"]="<<a[hi][cj];
}
main() {
int i,j;
cout<<"\nNhap cap cua ma tran:";cin>>n;
cout<<"\nNhap ma tran:\n";
enter();
for(i=0;i<n;++i)
for(j=0;j<n;++j)
sumij(i,j);
search();
getch();
}

[Hận Đời Không Đối Thủ]

xin được đưa ra 1 số nhận xét về thuật toán của nemo :
-không cần mảng s để lưu lại tất cả các tổng láng giềng đối với mỗi phần tử làm gì.Như thế dữ liệu của bạn sẽ tăng lên một cách không cần thiết.Ở đây chúng ta chỉ cần 1 biến max,và 1 biến luu để sau mỗi lần tìm được tổng láng giềng chúng ta lại so với cái max này.Nếu lớn hơn thì lại lưu tổng đó làm max và vị trí của phần tử có tổng max đó ~> thay vì 1 mảng 2 chiều chỉ còn lại 2 biến ~> tiết kiệm dữ liệu
-Đoạn này sẽ trở nên dài và tốn thời gian chạy
if(((i+di[k])>=0)&&((i+di[k])<=n-1)&&((j+dj[k])>=0)&&((j+dj[k])<=n-1)) (nếu có 100*100 phần tử thì bạn sẽ phải xét thêm tất cả là 4*100*100 lần ~> thử với 1000 hoặc lớn hơn xem :;)):.
Ở đây chúng ta chỉ cần rào lính canh xung quanh là không cần xét điều kiện nữa.
VD mảng :
1 2 3
4 5 6
7 8 9
thì chúng ta sẽ rào lính canh như sau:
0 0 0 0 0
0 1 2 3 0
0 4 5 6 0
0 7 8 9 0
0 0 0 0 0
như vậy sẽ đảm bảo khi cộng các láng giềng tổng luôn không đổi mà lại không phải xét điều kiện

[Hận Đời Không Đối Thủ]

oài lần trước đưa lên chỉ với mục đích anh em biết thuật toán,bây giờ post code đầy đủ lên vậy :-(
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int a[100][100],i,j,n;
int dx[]={-1,0,1,-1,1,-1,0,1},dy[]={-1,-1,-1,0,0,1,1,1};
void nhap()
{
cout <<"n = "; scanf("%d",&n);
for (i = 1 ; i <= n ; i++)
for (j = 1 ; j <= n ; j++)
{
printf("\na[%d][%d] = ",i,j);scanf("%d",&a[i][j]);
}
}
void cbi()
{
for (i = 0 ; i <= n+1 ; i++)
{
a[0][i] = 0 ; a[n+1][i] = 0 ;
a[i][0] = 0 ; a[i][n+1] = 0 ;
}
}
void xuly()
{
int max=0,k,t,cot,hang;
for (i = 1 ; i <= n ; i++)
for (j = 1 ; j <= n ; j++)
{
t = 0 ;
for (k = 0 ; k < 7 ; k++) t+=a[i+dx[k]][j+dy[k]];
if (t > max)
{
max = t ; hang = i ; cot = j ;
}
}
cout << "a["<<hang<<"][" << cot <<"]";
}
void main()
{
clrscr();
nhap();
cbi();
xuly();
getch();
}