IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Окружения элемента в матрице
Merhaba
сообщение 19.04.2011 18:31
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Добрый вечер!
Помогите Пожалуйста написать программу:
Назовем k-окружением элементa a_ij (целочисленного) двумерного массива А такие
элементы a_pq , у которых по крайней мере один из индексов (p или q) отличается по
абсолютной величине от соответствующего ему индекса (i или j) ровно на k , а другой -
не более, чем на k . Напишите программу, которая подсчитывает в массиве А количество элементов, которые больше любого элемента из своего 1-окружения, но при этом меньше любого элемента из своего 2-окружения.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 19.04.2011 20:35
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


можно сделать функию с аргументами i,j и ответом boolean.
потом
OK(i,j:integer):boolean;

OK:=True;
for p:=1 to N do
for q:=1 to M do
if (((p=i-k) or (p=i+k)) and ((q>=j-k) and (q<=j+k))) or (((q=j-k) or (q=j+k)) and ((p>=i-k) and ((p<=i+k)))
then if a[p,q]>a[i,j] then begin
OK:=False; //нашли элемент который больше
exit; //выходим из функции так как смысла нету продолжать цикл
end;


Я так понял индекс K это окружение, значит изменяем немного функцию т.е добовляем ещё K как аргумент, и там где if a[p,q]>a[i,j] меняем на if k=1 then оставляем как есть, if k=2 then if a[p,q]<a[i,j] ....
Потом поочередно смотрим все элементы:
for i:=1 to n do
for j:=1 to m do
if Ok(i,j,1) and Ok(i,j,2) then Count:=Count+1;

Тут только на счет условия не уверен.

Сообщение отредактировано: DarkWishmaster - 19.04.2011 20:52
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 7.05.2011 21:41
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(DarkWishmaster @ 19.04.2011 21:35) *

можно сделать функию с аргументами i,j и ответом boolean.
потом
OK(i,j:integer):boolean;

OK:=True;
for p:=1 to N do
for q:=1 to M do
if (((p=i-k) or (p=i+k)) and ((q>=j-k) and (q<=j+k))) or (((q=j-k) or (q=j+k)) and ((p>=i-k) and ((p<=i+k)))
then if a[p,q]>a[i,j] then begin
OK:=False; //нашли элемент который больше
exit; //выходим из функции так как смысла нету продолжать цикл
end;


Я так понял индекс K это окружение, значит изменяем немного функцию т.е добовляем ещё K как аргумент, и там где if a[p,q]>a[i,j] меняем на if k=1 then оставляем как есть, if k=2 then if a[p,q]<a[i,j] ....
Потом поочередно смотрим все элементы:
for i:=1 to n do
for j:=1 to m do
if Ok(i,j,1) and Ok(i,j,2) then Count:=Count+1;

Тут только на счет условия не уверен.

Окружение - "рамочка" вокруг элемента. Если 1 - окружение, то одинарная рамочка, Если 2 - окружение, то двойная рамочка
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Unconnected
сообщение 8.05.2011 0:07
Сообщение #4


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Может быть и не совсем двойная, по условию одна из размерностей <=2. То есть, прямоугольная..


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 8.05.2011 6:36
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Unconnected @ 8.05.2011 1:07) *

Может быть и не совсем двойная, по условию одна из размерностей <=2. То есть, прямоугольная..

А условие в этом случае такое?
"Тут только на счет условия не уверен." - DarkWishmaster
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 8.05.2011 12:05
Сообщение #6


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Unconnected @ 8.05.2011 1:07) *
Может быть и не совсем двойная, по условию одна из размерностей <=2. То есть, прямоугольная..
Я бы сказал, что совсем не двойная, но и не совсем прямоугольная, а квадратная smile.gif (или неполный квадрат, если скраю).

2 DarkWishMaster:
идея функции по большому счету неплоха, но есть проблема.. Как передавать в эту функцию условие? В первой проверке должно быть больше, во второй - меньше. Выход, конечно, есть, и не один - либо закодировать условие символом и потом использовать case для распознования, либо делать параметр-функцию. Последнее, на мой взгляд, предпочтительнее, но явно медленнее. И вообще, мне кажется, что нечего огород городить из-за двух вызовов, так что я просто сделал БЕЗ функции )).

И второе: да, DarkWishMaster, ты прав в своих сомнениях насчет условия - оно у тебя неправильно реализовано.

Короче - Merhaba, вот код:
function Min(a,b: integer): integer;
begin
if a<b then Min:= a else Min:= b
end;

function Max(a,b: integer): integer;
begin
if a>b then Max:= a else Max:= b
end;


const
n= 30;
m= 20;

var
a: array [1..n,1..m] of integer;
i,j,k,l,p,q: integer;
Ok: boolean;

begin
Randomize;
for i:=1 to n do for j:=1 to m do a[i,j]:= Random(100);
for i:=1 to n do begin
for j:=1 to m do Write(a[i,j]:3);
WriteLn
end;

l:=0;
for i:=3 to n-2 do for j:=3 to m-2 do begin
Ok:= true;
k:= 1;
for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do
if (Abs(i-p)=k) or (Abs(j-q)=k) then Ok:= Ok and (a[i,j]>a[p,q]);
k:= 2;
for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do
if (Abs(i-p)=k) or (Abs(j-q)=k) then Ok:= Ok and (a[i,j]<a[p,q]);
if Ok then Inc(l)
end;

WriteLn('found ',l,' of wanted elements');
ReadLn
end.


Если все же хочется сделать через функцию - говори, могу показать, как. Кстати, DarkWishMaster - попробуй сделать с параметром-функцией.

И небольшое лирическое отступление на правах шутки.. smile.gif
Вообще, программа, которая при небольших n и m (то есть, порядка 100) с подавляющей вероятностью дает правильный ответ, может быть написана примерно так:
begin
WriteLn(0)
end.

Потому что при случайном распределении вероятность нахождения элемента, удовлетворяющего условиям практически нулевая.. smile.gif))

Я прогнал при размере массива 20000х20000 и получил всего 25 случаев. Из них 15 - на краях (там вероятность выше несколько). То есть вероятность на 1 элемент массива в объеме равна примерно (25-15)/400000000, то есть 2.5*10-8. Это ниже, чем вероятность выиграть миллион в лотерею.. ))

Слова, выделенные курсивом, добавлены позже

Сообщение отредактировано: Lapp - 8.05.2011 12:25


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 19.05.2011 22:59
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 8.05.2011 13:05) *

Я бы сказал, что совсем не двойная, но и не совсем прямоугольная, а квадратная smile.gif (или неполный квадрат, если скраю).

2 DarkWishMaster:
идея функции по большому счету неплоха, но есть проблема.. Как передавать в эту функцию условие? В первой проверке должно быть больше, во второй - меньше. Выход, конечно, есть, и не один - либо закодировать условие символом и потом использовать case для распознования, либо делать параметр-функцию. Последнее, на мой взгляд, предпочтительнее, но явно медленнее. И вообще, мне кажется, что нечего огород городить из-за двух вызовов, так что я просто сделал БЕЗ функции )).

И второе: да, DarkWishMaster, ты прав в своих сомнениях насчет условия - оно у тебя неправильно реализовано.

Короче - Merhaba, вот код:
function Min(a,b: integer): integer;
begin
if a<b then Min:= a else Min:= b
end;

function Max(a,b: integer): integer;
begin
if a>b then Max:= a else Max:= b
end;
const
n= 30;
m= 20;

var
a: array [1..n,1..m] of integer;
i,j,k,l,p,q: integer;
Ok: boolean;

begin
Randomize;
for i:=1 to n do for j:=1 to m do a[i,j]:= Random(100);
for i:=1 to n do begin
for j:=1 to m do Write(a[i,j]:3);
WriteLn
end;

l:=0;
for i:=3 to n-2 do for j:=3 to m-2 do begin
Ok:= true;
k:= 1;
for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do
if (Abs(i-p)=k) or (Abs(j-q)=k) then Ok:= Ok and (a[i,j]>a[p,q]);
k:= 2;
for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do
if (Abs(i-p)=k) or (Abs(j-q)=k) then Ok:= Ok and (a[i,j]<a[p,q]);
if Ok then Inc(l)
end;

WriteLn('found ',l,' of wanted elements');
ReadLn
end.


Если все же хочется сделать через функцию - говори, могу показать, как. Кстати, DarkWishMaster - попробуй сделать с параметром-функцией.

И небольшое лирическое отступление на правах шутки.. smile.gif
Вообще, программа, которая при небольших n и m (то есть, порядка 100) с подавляющей вероятностью дает правильный ответ, может быть написана примерно так:
begin
WriteLn(0)
end.

Потому что при случайном распределении вероятность нахождения элемента, удовлетворяющего условиям практически нулевая.. smile.gif))

Я прогнал при размере массива 20000х20000 и получил всего 25 случаев. Из них 15 - на краях (там вероятность выше несколько). То есть вероятность на 1 элемент массива в объеме равна примерно (25-15)/400000000, то есть 2.5*10-8. Это ниже, чем вероятность выиграть миллион в лотерею.. ))

Слова, выделенные курсивом, добавлены позже


Не знаете случайно, как это на Java написать: for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do ?

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 19.05.2011 23:36
Сообщение #8


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Merhaba @ 19.05.2011 23:59) *
Не знаете случайно, как это на Java написать: for p:= Max(i-k,1) to Min(i+k,n) do
for q:= Max(j-k,1) to Min(j+k,m) do ?

1. Для Java есть раздел "Другие языки".
2. Мы много, чего знаем. А ты знаешь, как по-русски звучит слово, выражающее благодарность?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 20.05.2011 6:24
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 20.05.2011 0:36) *

1. Для Java есть раздел "Другие языки".
2. Мы много, чего знаем. А ты знаешь, как по-русски звучит слово, выражающее благодарность?

Спасибо Вам Большое за помощь!!! give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 20.05.2011 20:27
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 20.05.2011 0:36) *

1. Для Java есть раздел "Другие языки".
2. Мы много, чего знаем. А ты знаешь, как по-русски звучит слово, выражающее благодарность?

Если Вас не затруднит smile.gif , объясните Пожалуйста алгоритм, который вы использовали)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 21.05.2011 5:35
Сообщение #11


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Merhaba @ 20.05.2011 21:27) *
Если Вас не затруднит smile.gif , объясните Пожалуйста алгоритм, который вы использовали)
А что ты тут называешь громким словом "алгоритм"? blink.gif
Нет тут никакого алгоритма. Тупой подсчет в лоб по условию задачи. Внешний двойной цикл по всем клеткам и два внутренних (тоже двойных) для подсчета сумм 1 (при k=1) и 2 (при k=2) окружений.

Кстати, тот вариант, который я запостил, обсчитывает только внутренние точки. Чтобы пройтись по всем элементам, убери смещения на концах, то есть строку
  for i:=3 to n-2 do for j:=3 to m-2 do begin
замени на
  for i:=1 to n do for j:=1 to m do begin


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 21.05.2011 20:47
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 21.05.2011 6:35) *

А что ты тут называешь громким словом "алгоритм"? blink.gif
Нет тут никакого алгоритма. Тупой подсчет в лоб по условию задачи. Внешний двойной цикл по всем клеткам и два внутренних (тоже двойных) для подсчета сумм 1 (при k=1) и 2 (при k=2) окружений.

Кстати, тот вариант, который я запостил, обсчитывает только внутренние точки. Чтобы пройтись по всем элементам, убери смещения на концах, то есть строку
  for i:=3 to n-2 do for j:=3 to m-2 do begin
замени на
  for i:=1 to n do for j:=1 to m do begin


Спасибо Большое!!!
Если Вас не затруднит, объясните Пожалуйста, а для чего искали минимум и максимум!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 22.05.2011 3:08
Сообщение #13


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Merhaba @ 21.05.2011 21:47) *
Если Вас не затруднит, объясните Пожалуйста, а для чего искали минимум и максимум!

Окружения тех точек, которые находятся скраю (на первой и второй линиях от края), обрезаны. Если этого не учитывать, при подсчете выйдешь за пределы матрицы. Чтобы этого не произошло, пределы внутренних циклов проверяются на выход за границу массива. Например, если считается сумма по 2-окружению для элемента [1,5], то левая граница цикла по i должна быть -1, что лежит за пределами. Ее нужно насильно привести к 1. Для этого я и считаю максимум: max(-1,1)=1.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 22.05.2011 8:14
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 22.05.2011 4:08) *

Окружения тех точек, которые находятся скраю (на первой и второй линиях от края), обрезаны. Если этого не учитывать, при подсчете выйдешь за пределы матрицы. Чтобы этого не произошло, пределы внутренних циклов проверяются на выход за границу массива. Например, если считается сумма по 2-окружению для элемента [1,5], то левая граница цикла по i должна быть -1, что лежит за пределами. Ее нужно насильно привести к 1. Для этого я и считаю максимум: max(-1,1)=1.

А вот так получится: "добавить"к матрице "двойную рамку заполненную нулями" ?
Тогда мы не будем вылетать за матрицу, когда будет считать окружение крайних элементов
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 23.05.2011 0:11
Сообщение #15


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Merhaba @ 22.05.2011 9:14) *
А вот так получится: "добавить"к матрице "двойную рамку заполненную нулями" ?
Тогда мы не будем вылетать за матрицу, когда будет считать окружение крайних элементов
Да, можно.
Это будет стоить тебе больше, чем 4*(n+m)*SizeOf(element) Для описанного выше случая 20тыс на 20тыс это составит 320KB. Время также будет больше, поскольку надо складывать несуществующие элементы. Я понимаю, что такие мелочи по нынешним временам не считаются.. Потому 90% современного софта и тормозит немеряно, что такой стиль программирования.. ))


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 23.05.2011 8:07
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 23.05.2011 1:11) *

Да, можно.
Это будет стоить тебе больше, чем 4*(n+m)*SizeOf(element) Для описанного выше случая 20тыс на 20тыс это составит 320KB. Время также будет больше, поскольку надо складывать несуществующие элементы. Я понимаю, что такие мелочи по нынешним временам не считаются.. Потому 90% современного софта и тормозит немеряно, что такой стиль программирования.. ))

Если Вам не сложно, напишите Пожалуйста код, который будет использовать такой случай (с добавлением двойной рамки заполненной нулями) rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 23.05.2011 9:50
Сообщение #17


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Merhaba @ 23.05.2011 9:07) *
Если Вам не сложно, напишите Пожалуйста код, который будет использовать такой случай (с добавлением двойной рамки заполненной нулями) rolleyes.gif
Мне несложно. А тебе?
Послушай, Merhaba, я пишу тебе ответы не для того, чтоб ты сдавал свои задания (мне плевать на твои несдачи), а чтоб помочь тебе чему-то научиться. Попробуй хоть что-то сделать сам.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 29.03.2024 1:04
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"