Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Окружения элемента в матрице

Автор: Merhaba 19.04.2011 22:31

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

Автор: DarkWishmaster 20.04.2011 0: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;

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

Автор: Merhaba 8.05.2011 1:41

Цитата(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 - окружение, то двойная рамочка

Автор: Unconnected 8.05.2011 4:07

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

Автор: Merhaba 8.05.2011 10:36

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

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

А условие в этом случае такое?
"Тут только на счет условия не уверен." - DarkWishmaster

Автор: Lapp 8.05.2011 16:05

Цитата(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. Это ниже, чем вероятность выиграть миллион в лотерею.. ))

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

Автор: Merhaba 20.05.2011 2:59

Цитата(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 ?


Автор: Lapp 20.05.2011 3:36

Цитата(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. Мы много, чего знаем. А ты знаешь, как по-русски звучит слово, выражающее благодарность?

Автор: Merhaba 20.05.2011 10:24

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

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

Спасибо Вам Большое за помощь!!! give_rose.gif

Автор: Merhaba 21.05.2011 0:27

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

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

Если Вас не затруднит smile.gif , объясните Пожалуйста алгоритм, который вы использовали)

Автор: Lapp 21.05.2011 9:35

Цитата(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

Автор: Merhaba 22.05.2011 0:47

Цитата(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


Спасибо Большое!!!
Если Вас не затруднит, объясните Пожалуйста, а для чего искали минимум и максимум!

Автор: Lapp 22.05.2011 7:08

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

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

Автор: Merhaba 22.05.2011 12:14

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

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

А вот так получится: "добавить"к матрице "двойную рамку заполненную нулями" ?
Тогда мы не будем вылетать за матрицу, когда будет считать окружение крайних элементов

Автор: Lapp 23.05.2011 4:11

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

Автор: Merhaba 23.05.2011 12:07

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

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

Если Вам не сложно, напишите Пожалуйста код, который будет использовать такой случай (с добавлением двойной рамки заполненной нулями) rolleyes.gif

Автор: Lapp 23.05.2011 13:50

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