 Длина кольцевого буфера., Программирование? |
Рейтинг
 |
 |
Добро пожаловать, гость ( Вход | Регистрация )
Правила раздела
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
  |
| nik_vic |
 10.5.2013, 9:52
Сообщение
#1
|
|
Активный участник  Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125  |
Для кольцевого битового буфера реализуемы пошаговые команды вперёд/назад и чтение/запись.
Как бы побыстее найти его длину? ==== Но можно и иначе. ММ - в кольцевой тюряге, может переходить из камеры в камеру, зажигать/гасить свет. Узнает, сколько камер - выйдет на свободу  -------------------- Где это видано?
|
   |
 
|
| idler_ |
10.5.2013, 10:03
Сообщение
#2
|
 Лентяй Группа: Администраторы Braingames Сообщений: 8 665 Регистрация: 22.4.2007 Пользователь №: 211 |
QUOTE(nik_vic @ 10.5.2013, 10:52)  Для кольцевого битового буфера реализуемы пошаговые команды вперёд/назад и чтение/запись. Как бы побыстее найти его длину? ==== Но можно и иначе. ММ - в кольцевой тюряге, может переходить из камеры в камеру, зажигать/гасить свет. Узнает, сколько камер - выйдет на свободу Я так понимаю всё-таки задача не выйти на свободу/найти длину (т. к. такая задача есть на сайте), а сделать это оптимальный способом? Есть ли у вас доказательство оптимальности? -------------------- Я - человек-простой
|
|
|
|
| nik_vic |
10.5.2013, 11:07
Сообщение
#3
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(idler_ @ 10.5.2013, 11:03) такая задача есть на сайте О, ткните носом - не знал. -------------------- Где это видано?
|
|
|
|
| idler_ |
10.5.2013, 11:31
Сообщение
#4
|
|
Лентяй Группа: Администраторы Braingames Сообщений: 8 665 Регистрация: 22.4.2007 Пользователь №: 211 |
-------------------- Я - человек-простой
|
|
|
|
| nik_vic |
10.5.2013, 11:47
Сообщение
#5
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(idler_ @ 10.5.2013, 12:31) Ну да, детский вариант "моей". В ней разумная формулировка оптимальности - отдельная задача. -------------------- Где это видано?
|
|
|
|
| nik_vic |
11.5.2013, 16:21
Сообщение
#6
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(idler_ @ 10.5.2013, 11:03) Есть ли у вас доказательство оптимальности? Есть. -------------------- Где это видано?
|
|
|
|
| nik_vic |
11.5.2013, 22:08
Сообщение
#7
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Прошла первая попытка, далёкая от оптимума.
-------------------- Где это видано?
|
|
|
|
| panda-pandus |
12.5.2013, 13:48
Сообщение
#8
|
|
Участник Группа: Пользователи Braingames Сообщений: 199 Регистрация: 9.4.2010 Пользователь №: 20 180 |
На выполнение каждой команды затрачивается одинаковое время? Время шага равно времени записи, времени чтения? После чтения на обработку прочитанного значения (сравнения его с какими-то другими значениями) время не тратится?
|
|
|
|
| nik_vic |
12.5.2013, 14:02
Сообщение
#9
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(panda-pandus @ 12.5.2013, 14:48) На выполнение каждой команды затрачивается одинаковое время? Время шага равно времени записи, времени чтения? После чтения на обработку прочитанного значения (сравнения его с какими-то другими значениями) время не тратится? Время шага грандиозно по сравнению с остальными операциями. Так что речь идёт о количестве шагов - как в "вагонной" постановке. -------------------- Где это видано?
|
|
|
|
| panda-pandus |
12.5.2013, 15:07
Сообщение
#10
|
|
Участник Группа: Пользователи Braingames Сообщений: 199 Регистрация: 9.4.2010 Пользователь №: 20 180 |
А что должен минимизировать оптимальный алгоритм: матожидание количества шагов, или матожидание отношения количества шагов к длине буфера?
В первом случае оптимальный алгоритм определенно будет зависеть от распределения вероятностей возможных длин буфера (не говоря о том, что это матожидание можно гарантированно загнать в бесконечность, и все алгоритмы станут равными по такой оценке эффективности). Во втором, думаю, то же самое. Во всяком случае, какой бы алгоритм мне не предъявили, я запросто придумаю особое распределение вероятностей длин буфера и особый алгоритм под это распределение, который окажется лучше предъявленного. |
|
|
|
| nik_vic |
12.5.2013, 16:44
Сообщение
#11
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(panda-pandus @ 12.5.2013, 16:07) А что должен минимизировать оптимальный алгоритм: матожидание количества шагов, или матожидание отношения количества шагов к длине буфера? Никаких матожиданий и вероятностей. Длина поезда неизвестна, состояние ламп в вагонах - тоже. "Алгоритму" могут подсунуть любой "поезд", он обязан без ошибки выдать его длину, а мы можем сравнить её с показаниями одометра/шагомера. Я бы сказал больше, но не хочу "мешать" решающим детский вариант. -------------------- Где это видано?
|
|
|
|
| panda-pandus |
12.5.2013, 22:02
Сообщение
#12
|
|
Участник Группа: Пользователи Braingames Сообщений: 199 Регистрация: 9.4.2010 Пользователь №: 20 180 |
QUOTE(nik_vic @ 12.5.2013, 17:44) Длина поезда неизвестна, состояние ламп в вагонах - тоже. "Алгоритму" могут подсунуть любой "поезд", он обязан без ошибки выдать его длину, а мы можем сравнить её с показаниями одометра/шагомера. Но по каким критериям тогда оценивается, действительно ли алгоритм самый быстрый? Если у нас есть два алгоритма, то на одном поезде может быстрее сработать первый, на другом поезде второй. Какой же из них считать более быстрым? Каков критерий оптимальности? Алгоритм, который на любом поезде победит другие алгоритмы, точно не существует. |
|
|
|
| nik_vic |
13.5.2013, 10:13
Сообщение
#13
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(panda-pandus @ 12.5.2013, 23:02) Но по каким критериям тогда оценивается, действительно ли алгоритм самый быстрый? Факт - оптимальность штука тонкая Если у нас есть два алгоритма, то на одном поезде может быстрее сработать первый, на другом поезде второй. Какой же из них считать более быстрым? Каков критерий оптимальности? Алгоритм, который на любом поезде победит другие алгоритмы, точно не существует.  В нашем случае достаточно такого определения оптимальности, что у "лидера" минимален верхний предел отношения числа шагов к длине поезда. -------------------- Где это видано?
|
|
|
|
| 0 |
13.5.2013, 13:02
Сообщение
#14
|
 Охгдеж Группа: Пользователи Braingames Сообщений: 1 335 Регистрация: 26.3.2009 Пользователь №: 13 618 |
QUOTE(nik_vic @ 13.5.2013, 11:13) Факт - оптимальность штука тонкая В нашем случае достаточно такого определения оптимальности, что у "лидера" минимален верхний предел отношения числа шагов к длине поезда. ... при длине поезда стремящемся к бесконечности? Разве он не бесконечен? |
|
|
|
| Mouse |
13.5.2013, 13:17
Сообщение
#15
|
 и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
QUOTE . при длине поезда стремящемся к бесконечности? Разве он не бесконечен? в данном случае нет. хотя большинство реализуют алгоритм где он бесконечен. |
|
|
|
| nik_vic |
15.5.2013, 10:59
Сообщение
#16
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Получил ещё один алгоритм, на сей раз оптимальный.
-------------------- Где это видано?
|
|
|
|
| Mouse |
15.5.2013, 12:40
Сообщение
#17
|
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
QUOTE Есть ли у вас доказательство оптимальности? QUOTE Есть. и QUOTE Получил ещё один алгоритм, на сей раз оптимальный. это как? |
|
|
|
| nik_vic |
15.5.2013, 13:01
Сообщение
#18
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(Mouse @ 15.5.2013, 13:40) это как? Один из пользователей прислал. Без доказательства оптимальности пятёрки (в определённом классе), но это - дело наживное. В классе "алгоритмов с монеткой" и использованием мат. ожидания в качестве функции сложности вычислений можно достигнуть и неулучшаемой двойки. ===== Итак, Панда - на пандусе с ковровой дорожкой  -------------------- Где это видано?
|
|
|
|
| nik_vic |
20.5.2013, 13:32
Сообщение
#19
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(Mouse @ 15.5.2013, 13:40) и это как? Есть алгоритм со средним числом шагов на вагон не более 2+2*корень(2). И серьёзные подозрения, что лучше нельзя - хотя полное доказательство только для двойки в качестве нижней оценки. -------------------- Где это видано?
|
|
|
|
| 0 |
20.5.2013, 14:39
Сообщение
#20
|
|
Охгдеж Группа: Пользователи Braingames Сообщений: 1 335 Регистрация: 26.3.2009 Пользователь №: 13 618 |
QUOTE(nik_vic @ 20.5.2013, 14:32) Есть алгоритм со средним числом шагов на вагон не более 2+2*корень(2). И серьёзные подозрения, что лучше нельзя - хотя полное доказательство только для двойки в качестве нижней оценки. Что такое "шаг"? только вперед/назад или чтение/запись тоже шаг? |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -
|
Упрощённая версия | Сейчас: 20.7.2025, 9:49 |
Invision Power Board
v2.1.4 © 2025 IPS, Inc.