ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
25 сообщений из 339, страница 9 из 14
  9  все
Относительно простые задачки
    #39933079
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
у того, о чем я подумал, глубина рекурсии 6, а ходов 95

подразумевал вот что:
abcdefgk (a b c d e f g k)

меняем ближайшие символы (a b -> b a) кроме среднего при нечетном числе символов -> badcfekg
меняем затронутые пары -> dcbakgfe
меняем четверки -> kgfedcba

итог kgfedcba
------------------

2mayton - здесь по условию можно заменять только соседние подстроки
...
Рейтинг: 0 / 0
02.03.2020, 16:13
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933082
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
меняем ближайшие символы (a b -> b a) кроме среднего при нечетном числе символов -> badcfekg
меняем затронутые пары -> dcbakgfe
меняем четверки -> kgfedcba
ага, понял.

можно существенно меньше ходов
...
Рейтинг: 0 / 0
02.03.2020, 16:17
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933088
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
Давайте возьмем маленькую строку (не 99 а чуть меньше):

Код: sql
1.
The quick brown fox jumps over lazy dog

по условию в строке нет повторяющихся символов.

Я не знаю английскую панграмму которая имела бы смысл и при этом содержала бы все буквы
алвавита по 1 штуке. Для русского языка была тестовая фраза "в чащах юга жил бы цитрус..."

Но к чорту прозу. Давайте просто алвафиты. 99 букв - это 33 русских + 22 латиницы + 10 цифр.

Или просто упростим задачу до реверса массива байтов.
...
Рейтинг: 0 / 0
02.03.2020, 16:25
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933115
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Имя пользователя1
...

можно существенно меньше ходов

явные вращения как-то комбинируются?
...
Рейтинг: 0 / 0
02.03.2020, 16:51
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933121
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Напомнило одну задачку для начинающих из Haskell.
...
Рейтинг: 0 / 0
02.03.2020, 16:55
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933122
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
Имя пользователя1
...

можно существенно меньше ходов

явные вращения как-то комбинируются?
Сами подстроки переворачивать нельзя, только обменять местами, как в примере из условия.
...
Рейтинг: 0 / 0
02.03.2020, 16:56
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933132
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
вращение на 1 элемент представляется явным "обменом местами"
abcdefgk - abcdefg k -> kabcdefg
kabcdefg - kabcdef g -> gkabcdef

можно навращать полстроки...
но здесь может оказаться хитрая комбинация вращений с "простыми обменами".
...
Рейтинг: 0 / 0
02.03.2020, 17:17
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933136
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
На вращениях можно наковырять даже перестановки. Которых будет факториал от количества букв в строке.
...
Рейтинг: 0 / 0
02.03.2020, 17:22
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933160
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Вообще-то "вращение" 2-х соседей не запрещено. И уж это точно инверсия даже с т.зр. теоргрупп. А из инверсий любую перестановку можно собрать, правда не оптимально. "Пузырьком" будет.
...
Рейтинг: 0 / 0
02.03.2020, 18:06
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39933173
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
вращение на 1 элемент представляется явным "обменом местами"
abcdefgk - abcdefg k -> kabcdefg
kabcdefg - kabcdef g -> gkabcdef
понял.
да, такие можно, разумеется.
...
Рейтинг: 0 / 0
02.03.2020, 18:28
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934653
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
22090677 не зашло, попробуем другую, строго по сабжу.

Строка S1 содержит только буквы R, G, B, и больше никаких других символов.
Из неё делается строка S2, длиной на 1 меньше, по правилу: S2[i] = rgb(S1[i], S1[i+1]).
Из S2 аналогично делается S3, и т.д., пока не окажется строка S N длиной 1, с одним символом.
Надо по строке S1 определить этот символ в S N .

Упомянутая функция rgb(x, y) получает на вход два параметра - буквы из набора (R, G, B). Если x=y, то возвращается x, иначе возвращается третья буква из набора, та, которой не равны х и у.

Пример
Код: sql
1.
2.
3.
4.
5.
S1 = RGBBR
S2 = BRBG
S3 = GGR
S4 = GB
S5 = R



Итого из "RGBBR" получилось "R".

Паззл интересен тем, что тут можно хитро оптимизировать, и даже километровые строки будут обрабатываться быстро.
...
Рейтинг: 0 / 0
05.03.2020, 13:54
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934676
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Имя пользователя1,

здесь код конкретный ожидается, или как?

что касается не зашло.
Скажи пожалуйста,
а) за какое число обменов двух соседних строк задача решается для длины 99
б) с какой наименьшей длины работает ожидаемое решение эффективнее простого попарного обмена

а вообще, имхо, если считаешь, что время вышло, то прилично было бы дать ссылку на решение, если это общеизвестная задача,
или показать свое личное решение.
...
Рейтинг: 0 / 0
05.03.2020, 14:21
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934684
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
Имя пользователя1,

здесь код конкретный ожидается, или как?
достаточно идеи, а кодинга нам и по работе хватает )

booby
а) за какое число обменов двух соседних строк задача решается для длины 99
б) с какой наименьшей длины работает ожидаемое решение эффективнее простого попарного обмена

а вообще, имхо, если считаешь, что время вышло, то прилично было бы дать ссылку на решение, если это общеизвестная задача,
или показать свое личное решение.
время не вышло, вдруг кто-то порешать надумает.

99 решается за 50 обменов.
...
Рейтинг: 0 / 0
05.03.2020, 14:34
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934701
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Имя пользователя1,

там был еще один вопрос ... :))

то есть 9 решится по этой схеме за 5?
...
Рейтинг: 0 / 0
05.03.2020, 15:05
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934702
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1,
У меня идея в том, чтобы свести операцию rgb к арифметической.
Обозначим R=0, G=1, B=2
rgb(x,y)=(3-x-y) mod 3.
Дальше с телефона неудобно
...
Рейтинг: 0 / 0
05.03.2020, 15:06
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934710
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Обозначим R=0, G=1, B=2
rgb(x,y)=(3-x-y) mod 3.
можно и так) rgb верно считается.
...
Рейтинг: 0 / 0
05.03.2020, 15:14
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934713
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
там был еще один вопрос ... :))

то есть 9 решится по этой схеме за 5?
вопрос я видел, но подсказок больше давать нет смысла, и так уже теперь всё понятно
...
Рейтинг: 0 / 0
05.03.2020, 15:16
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934735
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
Соколинский Борис
Обозначим R=0, G=1, B=2
rgb(x,y)=(3-x-y) mod 3.
можно и так) rgb верно считается.
Дальше мы пользуемся тем, что остаток от деления суммы остатков от деления есть просто остаток от деления суммы.
И выясняем, что достаточно сложить все числа с правильными весами и взять остаток от деления.
...
Рейтинг: 0 / 0
05.03.2020, 15:44
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934747
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Имя пользователя1
22090677 не зашло, попробуем другую, строго по сабжу.

Строка S1 содержит только буквы R, G, B, и больше никаких других символов.
Из неё делается строка S2, длиной на 1 меньше, по правилу: S2[i] = rgb(S1[i], S1[i+1]).
Из S2 аналогично делается S3, и т.д., пока не окажется строка S N длиной 1, с одним символом.
Надо по строке S1 определить этот символ в S N .

Упомянутая функция rgb(x, y) получает на вход два параметра - буквы из набора (R, G, B). Если x=y, то возвращается x, иначе возвращается третья буква из набора, та, которой не равны х и у.

Пример
Код: sql
1.
2.
3.
4.
5.
S1 = RGBBR
S2 = BRBG
S3 = GGR
S4 = GB
S5 = R



Итого из "RGBBR" получилось "R".

Паззл интересен тем, что тут можно хитро оптимизировать, и даже километровые строки будут обрабатываться быстро.

Есть подозрение что достаточно посчитать rgb() от крайних, т.е. rgb(R, R)
...
Рейтинг: 0 / 0
05.03.2020, 15:55
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934752
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Dima T,

Даже из примера видно, что это не так - начинаем с S3
...
Рейтинг: 0 / 0
05.03.2020, 16:02
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934753
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
И выясняем, что достаточно сложить все числа с правильными весами и взять остаток от деления.
то есть решение за O(N)?
...
Рейтинг: 0 / 0
05.03.2020, 16:04
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934754
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1,
Ну да, вроде.
...
Рейтинг: 0 / 0
05.03.2020, 16:05
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934759
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Напомнило PPM сжатие. Там тоже брался текст. Выборка группы букв. И эти буквы вращались
и заносились в справочник. Потом эти карусели использовались как справочник.
...
Рейтинг: 0 / 0
05.03.2020, 16:08
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934762
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Имя пользователя1,
Ну да, вроде.
можно существенно ускорить.
...
Рейтинг: 0 / 0
05.03.2020, 16:10
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39934763
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Dima T
Имя пользователя1
22090677 не зашло, попробуем другую, строго по сабжу.

Строка S1 содержит только буквы R, G, B, и больше никаких других символов.
Из неё делается строка S2, длиной на 1 меньше, по правилу: S2[i] = rgb(S1[i], S1[i+1]).
Из S2 аналогично делается S3, и т.д., пока не окажется строка S N длиной 1, с одним символом.
Надо по строке S1 определить этот символ в S N .

Упомянутая функция rgb(x, y) получает на вход два параметра - буквы из набора (R, G, B). Если x=y, то возвращается x, иначе возвращается третья буква из набора, та, которой не равны х и у.

Пример
Код: sql
1.
2.
3.
4.
5.
S1 = RGBBR
S2 = BRBG
S3 = GGR
S4 = GB
S5 = R




Итого из "RGBBR" получилось "R".

Паззл интересен тем, что тут можно хитро оптимизировать, и даже километровые строки будут обрабатываться быстро.

Есть подозрение что достаточно посчитать rgb() от крайних, т.е. rgb(R, R)
совпадение )
...
Рейтинг: 0 / 0
05.03.2020, 16:11
| Ответить | Цитировать | Написать  
25 сообщений из 339, страница 9 из 14
  9  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39933115&tid=1339678]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 167ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 65ms
get tp. blocked users:
 1ms
others: 12ms
total:  289ms
созд. / загр.: 289ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]