04:08 21-03-2005 Программистское
Дан двухмерный квадратны массив short'ов (src). Нужно получить второй двухмерный квадратный массив short'ов (dst), так что dst[i][j] = average(src[i-1][j-1]...src[i+1][j+1]). Реально составить такой алгоритм, чтоб он делал это за один проход каждого элемента в src? (т.е. O(n) с константой 1)
Комментарии:
14:57 21-03-2005
В случае src[0][0] считать src[i-1][j-1] за src[0][0] или за src[max(i)][max(j)]?
21:55 21-03-2005
А что означает в average(src[i-1][j-1]...src[i+1][j+1]) многоточие?
23:41 21-03-2005
cpcat
Если в углу, то усреднять 4 поля. Т.е. это доска, а не глобус
MIK
означает усреднять все поля вокруг (всего 9)
Если в углу, то усреднять 4 поля. Т.е. это доска, а не глобус
MIK
означает усреднять все поля вокруг (всего 9)
Anafay
05:36 22-03-2005
Э... Вообще-то, что бы ты ни делал, будет O(n^2).
Задача стоит в том, чтобы любой ценой обойтись единственным обращением к каждому элементу, или в том, чтобы посчитать быстрее?
Задача стоит в том, чтобы любой ценой обойтись единственным обращением к каждому элементу, или в том, чтобы посчитать быстрее?
06:14 22-03-2005
Anafay
Well, I consider the total number of elements to be n, not the size of the square.
To count faster. Actually we are already done with it
But the only thing we came up with was that for each element in the destination array we only needed to access 3 elements in the source array, while data for 6 other elements is available from the previous calcucation.
So for element (25,25) we already found the sum of elements (24,24), (24,25), (24,26) , (25,24), (25,25), (25,26) and we only need (26,24) , (26,25) and (26,26). So the total time is in general case would be 3*n.
Well, I consider the total number of elements to be n, not the size of the square.
To count faster. Actually we are already done with it
But the only thing we came up with was that for each element in the destination array we only needed to access 3 elements in the source array, while data for 6 other elements is available from the previous calcucation.So for element (25,25) we already found the sum of elements (24,24), (24,25), (24,26) , (25,24), (25,25), (25,26) and we only need (26,24) , (26,25) and (26,26). So the total time is in general case would be 3*n.
Anafay
08:19 22-03-2005
Xirax
А тебе надо, чтобы еще меньше было обращений к src? IMHO, с запретом на чтение dst и с запретом на явные или завуалированные хранилища не выйдет.
А тебе надо, чтобы еще меньше было обращений к src? IMHO, с запретом на чтение dst и с запретом на явные или завуалированные хранилища не выйдет.
08:28 22-03-2005
Anafay
Нету таких запретов :-/
Только src нельзя менять
Нету таких запретов :-/
Только src нельзя менять
Anafay
21:42 22-03-2005
Xirax
Тогда просто помести dst[i,j]=avg(src[i-1,j],src[i,j],src[i+1,j]) - это один проход по каждому src[i,j]
А потом сделай то же самое внутри dst, по j и без всяких ограничений на количество обращений, которое будет опять же по одному к каждому dst[i,j] на чтение
Вариант ( издевательский) - сделай временный массив tmp, скопируй в него src и обращайся, сколько угодно к tmp 
Тогда просто помести dst[i,j]=avg(src[i-1,j],src[i,j],src[i+1,j]) - это один проход по каждому src[i,j]
А потом сделай то же самое внутри dst, по j и без всяких ограничений на количество обращений, которое будет опять же по одному к каждому dst[i,j] на чтение
Вариант ( издевательский
) - сделай временный массив tmp, скопируй в него src и обращайся, сколько угодно к tmp