Окружения элемента в матрице Опции

[Merhaba]

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

[Lapp]

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

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

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 - попробуй сделать с параметром-функцией.

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

begin
  WriteLn(0)
end.

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

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

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

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

[Merhaba]

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

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 - попробуй сделать с параметром-функцией.

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

begin
  WriteLn(0)
end.

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

Я прогнал при размере массива 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]

Не знаете случайно, как это на 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]

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

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

[Lapp]

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

А что ты тут называешь громким словом "алгоритм"?
Нет тут никакого алгоритма. Тупой подсчет в лоб по условию задачи. Внешний двойной цикл по всем клеткам и два внутренних (тоже двойных) для подсчета сумм 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