Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Оптимизация угадывания положения фигур
СообщениеДобавлено: 20 сен 2013, 12:42 
Не в сети
Начинающий
Зарегистрирован:
26 сен 2011, 12:37
Сообщений: 19
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
На шахматной доске расположены 8 ладей (других фигур нет) так, что ни одна не бьет другую (на каждой вертикали и на каждой горизонтали - по одной ладье), но расположение нам неизвестно. Можно задавать вопрос о занятости той или иной клетки. Наша цель - узнать точное расположение всех ладей как можно быстрее. Символом А0 обозначим алгоритм, состоящий в проверке каждого столбца (клетка за клеткой) до обнаружения занятой клетки и последующим переходом к следующему столбцу. Как доказать, что в среднем (усредняя по всем возможным начальным расположениям ладей) А0 будет давать ответ быстрее (точнее - не медленнее), чем любой другой алгоритм?

Пока что я пробовал просматривать другие алгоритмы (например, после каждой проверки клетки переходить к следующему столбцу независимо от результата) и действительно (проверял программно) другие алгоритмы в среднем работают дольше чем (или так же как) А0, но вот как доказать, что ни один алгоритм не будет лучше (в среднем смысле) чем А0?.. Ведь разных алгоритмов может быть оооочень много...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Вероятность угадывания ответов

в форуме Теория вероятностей

Veronika34939

2

204

30 дек 2020, 20:01

Положения Равновесия на сфере

в форуме Дифференциальные и Интегральные уравнения

Roloroma

0

192

28 май 2020, 13:45

Найти положения равновесия системы

в форуме Дифференциальное исчисление

lllulll

0

275

15 июн 2015, 08:12

Исследование положения равновесия на устойчивость

в форуме Дифференциальные и Интегральные уравнения

vlad24

18

736

01 июл 2017, 16:14

Прямые и плоскости общего положения

в форуме Комбинаторика и Теория вероятностей

silversurficus

9

597

24 июл 2021, 19:12

Уравнение геометрического положения точек

в форуме Аналитическая геометрия и Векторная алгебра

karawella

2

398

26 дек 2015, 20:19

Опр-ть мат. ожидание и дисп. ошибки опр-ия положения объекта

в форуме Математическая статистика и Эконометрика

Knyazhe

2

182

20 дек 2019, 13:45

Модель популяции, устойчивость положения равновесия

в форуме Векторный анализ и Теория поля

crazymadman18

1

265

21 дек 2021, 13:55

Функция изменения положения Призмы в пространстве

в форуме Аналитическая геометрия и Векторная алгебра

Vektor

4

241

01 мар 2020, 19:29

Найти положения равновесия, характер, фазовые траектории

в форуме Дифференциальные и Интегральные уравнения

JohnnyGru

0

204

19 ноя 2019, 05:55


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved