Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

RFpro.ru: Алгоритмы и теория программирования


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

solowey
Статус: Специалист
Рейтинг: 529
∙ повысить рейтинг »
CradleA
Статус: Профессор
Рейтинг: 374
∙ повысить рейтинг »
SAW
Статус: 9-й класс
Рейтинг: 342
∙ повысить рейтинг »

∙ Алгоритмы и теория программирования

Номер выпуска:229
Дата выхода:22.03.2020, 19:15
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:30 / 13
Вопросов / ответов:3 / 5

Консультация # 144128: Помогите, пожалуйсто: Предполжим, что вам прислали программу про которую известно, что она детерменирована, и про кторую утверждается, что она работает правильно и использует число операций меньшее чем линейный поиск. Придумайте набор тестов, который определенно покажет, что программа работает не быстрее линейного поиска или ошибается...
Консультация # 183184: Здравствуйте, уважаемые эксперты! Прошу вас 1. Написать программу. Дана карта клетчатых ячеек, на которой есть исходная ячейка A, конечная ячейка B и некоторое количество запретных ячеек {Ci}. Есть робот, который может перемещаться из клетки в клетку, но не может попасть на клетки {Ci}. Требуется составить программу управления роботом, котор...
Консультация # 20722: зрасьсьсь... короче проблема такая: надо проверить все элементы матрицы на какое-либо условие. и для каждого элемента матрицы нодо проверить все соседние элементы (понятно? чёт я намутил!). ну например для элемента a[2][2] надо проверить элементы a[1][1],a[1][2],a[1][3],a[2][1],a[2][3],a[3][1],a[ 3][2],a[3][3] во! ну не могу я н...

Консультация # 144128:

Помогите, пожалуйсто:
Предполжим, что вам прислали программу про которую известно, что она детерменирована, и про кторую утверждается, что она
работает правильно и использует число операций меньшее чем линейный поиск. Придумайте набор тестов, который определенно покажет, что программа работает не быстрее линейного поиска или ошибается

Дата отправки: 16.09.2008, 20:15
Вопрос задал: Капранов Павел Павлович
Всего ответов: 1
Страница онлайн-консультации »


Консультирует Гнедов Андрей:

Здравствуйте, Капранов Павел Павлович!
В такой постановке задачу не решить. Если заменить проверку при всех возможных начальных условиях на конечный набор тестов, то легко построить программу, которая просто распознает тест из набора и выдает ответ, который "знает" заранее. Это будет очень быстро. Примерно так, как легко умножать по таблице умножения.

Консультировал: Гнедов Андрей
Дата отправки: 17.09.2008, 14:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 183184:

Здравствуйте, уважаемые эксперты! Прошу вас
1. Написать программу.
Дана карта клетчатых ячеек, на которой есть исходная ячейка A, конечная ячейка B и некоторое количество запретных ячеек {Ci}. Есть робот, который может перемещаться из клетки в клетку, но не может попасть на клетки {Ci}. Требуется составить программу управления роботом, который должен переместиться из клетки A в клетку B.
Переход между ячейками осуществляется либо через сторону клетки, либо через вершину, но запрещен переход через вершину, если этой вершины касается одна из запретных клеток {Ci}
Управляющая программа заранее имеет сведения о расположении и количестве клеток {Ci}
Цель управления: добраться из клетки A в клетку B за меньшее время.
Инструменты: Turbo-/ABC-Pascal, Delphi-7/CodeGear, qBasic, VBA, C/C++ без STL
2. Убедительно доказать (или привести ссылку на доказательство) то, что время минимально
Срок исполнения: 20 мая. Цена будет согласована с автором ответа.
Е сли кто-то готов взяться, дайте, пожалуйста, знать в мини-форум или в личную почту.
Спасибо.

Дата отправки: 16.05.2011, 14:57
Вопрос задал: lamed (Академик)
Всего ответов: 1
Страница онлайн-консультации »


Консультирует Зенченко Константин Николаевич (Старший модератор):

Здравствуйте, lamed!

В приложениии код волнового алгоритма под АВС 3,х.
Вопросы задавайте в мини-форум.
Удачи!

Приложение:

Консультировал: Зенченко Константин Николаевич (Старший модератор)
Дата отправки: 25.05.2011, 12:56

5
Блестящая работа! Большое спасибо. Удачи :)
-----
Дата оценки: 25.05.2011, 13:49

Рейтинг ответа:

НЕ одобряю +1 одобряю!

Консультация # 20722:

зрасьсьсь...
короче проблема такая:
надо проверить все элементы матрицы на какое-либо условие. и для каждого элемента матрицы нодо проверить все соседние элементы (понятно? чёт я намутил!). ну например для элемента a[2][2] надо проверить элементы
a[1][1],a[1][2],a[1][3],a[2][1],a[2][3],a[3][1],a[
3][2],a[3][3] во!
ну не могу я ничего умного придумать! ну ладно элементы которые в центре матрицы можно проверить в простом цикле. а вот как проверить те которые на границе матрицы?! (при том что матрица не 3x3).
была еще такая мысль (тока не смеяться!): можно каждый элемент матрицы представить в виде структуры. в этой структуре будет 2 поля. 1-е поле для данных, а 2-е для флага, в котором отмечается проверялся ли уже этот элемент. но тоже проблема - когда этот алгоритм натыкается на границу матрицы или на элемент который уже проверялся, как его по новой запустить?
заранее спасибо!

Дата отправки: 12.05.2005, 08:08
Вопрос задал: ОчХочуНаучиться
Всего ответов: 3
Страница онлайн-консультации »


Консультирует Boriss:

Здравствуйте, ОчХочуНаучиться!
В Вашем вопросе прозвучала очень важная полуфраза "которые уже проверялись"... - это зачем?
Может напишите, что за задача - тогда легче будет сформулировать решение
А так, можно посоветовать добавить лишние строки и столбцы на границах, заполненные нужными значениями (хммм, нужными ... - не ясно, но понятно)

Консультировал: Boriss
Дата отправки: 12.05.2005, 09:35
Рейтинг ответа:

НЕ одобряю 0 одобряю!


Консультирует DSota:

Здравствуйте, ОчХочуНаучиться!
Тут можно использовать 2 варианта:
1. добавить к матрице по краям столбики и столбцы (своего рода рамку). т.е.
пусть есть матрица S[1..10][1..10], мы преобразуем его к матрице
S\'[0..11][0..11]. Где S\'[i][j]=S[i][j]. Значения столбцов и строк S\'[0][i],
S\'[11][i],S\'[i][0],S\'[i][11] выбираем в зависимости от нужного условия, чтобы
они не мешали правильности рассчетов.
2. Обычное вычисление заданного условия для каждого элемента матрицы
(обозначим этот элемент как Z[x][y] для краткости, и пусть размерность матрицы
Z равна 5):
для всех i меняющихся от 1 до 3 выполняем (для всех j меняющихся от 1 до 3
выполняем (если i и j вместе не равны 2 выполняем (проверка заданного условия
для элемента матрицы Z[x-1+i][y-1+j])))
Расширим его для использования и на крайних столбцах и строках матрицы:
Найдем левый столбец для проверки:
Если x равен 1, то левого столбца нет и Хлев равен 2, иначе Хлев=1
Найдем правый столбец для проверки:
Если х равен 5, то правого столбца нет и Хправ=2, иначе Хправ=3
Аналогично для строк:
Если у=1, то Уверх=2, иначе Уверх=1
Если у=5, то Униз=2, иначе Униз=3
(Это мы нашли размерность маленького квадратика (соседей данного элемента)) И дальше используем алгоритм выше чуть изменив его:
Для всех i от Хлев до Хправ выполним (для всех j от Уверх до Уних выполним (
если i и j одновременно не равны 2 выполним (проверим заданное условие для
эелемента матрицы Z[x-1+i][y-1+j])))

Консультировал: DSota
Дата отправки: 12.05.2005, 09:52
Рейтинг ответа:

НЕ одобряю 0 одобряю!


Консультирует Jadd:

Здравствуйте, ОчХочуНаучиться!
Да все довольно просто. Получается, что, в большинстве случаев, текущий элемент с его соседями - матрица 3х3. Вот и все. Получается, что мы для каждого элемента делаем 2 вещи: 1) проверяем на пограничность элемента и в случае обнаружения оного, принимаем за точку отсчета (номер колноки и/или столбца) текущего элемента для соседей, которые лежат за пределами(например, для текущего a[0][1] очевидно, что соседей с индексами а[-1][0] не существует, иначе мы получим GPF) 2) применяем поиск как для обычных матриц, меняя начальный индекс и/или конечный индекс в зависимости от пограничных условий. Все. Можно наверное иначе, но это то, что первое пришло в голову.

Консультировал: Jadd
Дата отправки: 13.05.2005, 10:00
Рейтинг ответа:

НЕ одобряю 0 одобряю!


Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!


В избранное