Окружения элемента в матрице |
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-окружения. |
DarkWishmaster |
19.04.2011 20:35
Сообщение
#2
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
можно сделать функию с аргументами i,j и ответом boolean.
потом OK(i,j:integer):boolean;
Я так понял индекс 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 Тут только на счет условия не уверен. Сообщение отредактировано: DarkWishmaster - 19.04.2011 20:52 |
Merhaba |
7.05.2011 21:41
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
можно сделать функию с аргументами i,j и ответом boolean. потом OK(i,j:integer):boolean;
Я так понял индекс 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 Тут только на счет условия не уверен. Окружение - "рамочка" вокруг элемента. Если 1 - окружение, то одинарная рамочка, Если 2 - окружение, то двойная рамочка |
Unconnected |
8.05.2011 0:07
Сообщение
#4
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Может быть и не совсем двойная, по условию одна из размерностей <=2. То есть, прямоугольная..
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Merhaba |
8.05.2011 6:36
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Lapp |
8.05.2011 12:05
Сообщение
#6
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Может быть и не совсем двойная, по условию одна из размерностей <=2. То есть, прямоугольная.. Я бы сказал, что совсем не двойная, но и не совсем прямоугольная, а квадратная (или неполный квадрат, если скраю).2 DarkWishMaster: идея функции по большому счету неплоха, но есть проблема.. Как передавать в эту функцию условие? В первой проверке должно быть больше, во второй - меньше. Выход, конечно, есть, и не один - либо закодировать условие символом и потом использовать case для распознования, либо делать параметр-функцию. Последнее, на мой взгляд, предпочтительнее, но явно медленнее. И вообще, мне кажется, что нечего огород городить из-за двух вызовов, так что я просто сделал БЕЗ функции )). И второе: да, DarkWishMaster, ты прав в своих сомнениях насчет условия - оно у тебя неправильно реализовано. Короче - Merhaba, вот код: function Min(a,b: integer): integer; Если все же хочется сделать через функцию - говори, могу показать, как. Кстати, DarkWishMaster - попробуй сделать с параметром-функцией. И небольшое лирическое отступление на правах шутки.. Вообще, программа, которая при небольших n и m (то есть, порядка 100) с подавляющей вероятностью дает правильный ответ, может быть написана примерно так: begin Потому что при случайном распределении вероятность нахождения элемента, удовлетворяющего условиям практически нулевая.. )) Я прогнал при размере массива 20000х20000 и получил всего 25 случаев. Из них 15 - на краях (там вероятность выше несколько). То есть вероятность на 1 элемент массива в объеме равна примерно (25-15)/400000000, то есть 2.5*10-8. Это ниже, чем вероятность выиграть миллион в лотерею.. )) Слова, выделенные курсивом, добавлены позже Сообщение отредактировано: Lapp - 8.05.2011 12:25 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Merhaba |
19.05.2011 22:59
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Я бы сказал, что совсем не двойная, но и не совсем прямоугольная, а квадратная (или неполный квадрат, если скраю). 2 DarkWishMaster: идея функции по большому счету неплоха, но есть проблема.. Как передавать в эту функцию условие? В первой проверке должно быть больше, во второй - меньше. Выход, конечно, есть, и не один - либо закодировать условие символом и потом использовать case для распознования, либо делать параметр-функцию. Последнее, на мой взгляд, предпочтительнее, но явно медленнее. И вообще, мне кажется, что нечего огород городить из-за двух вызовов, так что я просто сделал БЕЗ функции )). И второе: да, DarkWishMaster, ты прав в своих сомнениях насчет условия - оно у тебя неправильно реализовано. Короче - Merhaba, вот код: function Min(a,b: integer): integer; Если все же хочется сделать через функцию - говори, могу показать, как. Кстати, DarkWishMaster - попробуй сделать с параметром-функцией. И небольшое лирическое отступление на правах шутки.. Вообще, программа, которая при небольших n и m (то есть, порядка 100) с подавляющей вероятностью дает правильный ответ, может быть написана примерно так: begin Потому что при случайном распределении вероятность нахождения элемента, удовлетворяющего условиям практически нулевая.. )) Я прогнал при размере массива 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 |
19.05.2011 23:36
Сообщение
#8
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Не знаете случайно, как это на 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 6:24
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Merhaba |
20.05.2011 20:27
Сообщение
#10
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
|
Lapp |
21.05.2011 5:35
Сообщение
#11
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Если Вас не затруднит , объясните Пожалуйста алгоритм, который вы использовали) А что ты тут называешь громким словом "алгоритм"? Нет тут никакого алгоритма. Тупой подсчет в лоб по условию задачи. Внешний двойной цикл по всем клеткам и два внутренних (тоже двойных) для подсчета сумм 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 |
21.05.2011 20:47
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
А что ты тут называешь громким словом "алгоритм"? Нет тут никакого алгоритма. Тупой подсчет в лоб по условию задачи. Внешний двойной цикл по всем клеткам и два внутренних (тоже двойных) для подсчета сумм 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 3:08
Сообщение
#13
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Если Вас не затруднит, объясните Пожалуйста, а для чего искали минимум и максимум! Окружения тех точек, которые находятся скраю (на первой и второй линиях от края), обрезаны. Если этого не учитывать, при подсчете выйдешь за пределы матрицы. Чтобы этого не произошло, пределы внутренних циклов проверяются на выход за границу массива. Например, если считается сумма по 2-окружению для элемента [1,5], то левая граница цикла по i должна быть -1, что лежит за пределами. Ее нужно насильно привести к 1. Для этого я и считаю максимум: max(-1,1)=1. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Merhaba |
22.05.2011 8:14
Сообщение
#14
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Окружения тех точек, которые находятся скраю (на первой и второй линиях от края), обрезаны. Если этого не учитывать, при подсчете выйдешь за пределы матрицы. Чтобы этого не произошло, пределы внутренних циклов проверяются на выход за границу массива. Например, если считается сумма по 2-окружению для элемента [1,5], то левая граница цикла по i должна быть -1, что лежит за пределами. Ее нужно насильно привести к 1. Для этого я и считаю максимум: max(-1,1)=1. А вот так получится: "добавить"к матрице "двойную рамку заполненную нулями" ? Тогда мы не будем вылетать за матрицу, когда будет считать окружение крайних элементов |
Lapp |
23.05.2011 0:11
Сообщение
#15
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
А вот так получится: "добавить"к матрице "двойную рамку заполненную нулями" ? Да, можно.Тогда мы не будем вылетать за матрицу, когда будет считать окружение крайних элементов Это будет стоить тебе больше, чем 4*(n+m)*SizeOf(element) Для описанного выше случая 20тыс на 20тыс это составит 320KB. Время также будет больше, поскольку надо складывать несуществующие элементы. Я понимаю, что такие мелочи по нынешним временам не считаются.. Потому 90% современного софта и тормозит немеряно, что такой стиль программирования.. )) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Merhaba |
23.05.2011 8:07
Сообщение
#16
|
Пионер Группа: Пользователи Сообщений: 57 Пол: Мужской Репутация: 0 |
Да, можно. Это будет стоить тебе больше, чем 4*(n+m)*SizeOf(element) Для описанного выше случая 20тыс на 20тыс это составит 320KB. Время также будет больше, поскольку надо складывать несуществующие элементы. Я понимаю, что такие мелочи по нынешним временам не считаются.. Потому 90% современного софта и тормозит немеряно, что такой стиль программирования.. )) Если Вам не сложно, напишите Пожалуйста код, который будет использовать такой случай (с добавлением двойной рамки заполненной нулями) |
Lapp |
23.05.2011 9:50
Сообщение
#17
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Если Вам не сложно, напишите Пожалуйста код, который будет использовать такой случай (с добавлением двойной рамки заполненной нулями) Мне несложно. А тебе?Послушай, Merhaba, я пишу тебе ответы не для того, чтоб ты сдавал свои задания (мне плевать на твои несдачи), а чтоб помочь тебе чему-то научиться. Попробуй хоть что-то сделать сам. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 21.05.2024 17:24 |