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

А у этой задачи точно есть решение? Просто я не слышал чтобы кто-то сильно переживал
по поводу o(n) reverse.

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

PS
конечно, известно, что за три реверса выполняется произвольный циклический сдвиг.
Значит, какая-то последовательность циклических сдвигов должна формировать реверс.
Но в этом месте я продолжаю верить в первую часть своей гипотезы.
Т.е. почти наверно, такая последовательность, да еще если она даёт число действий,
по сути равное числу свопов для разворота массива, использовалась бы как стандартный алгоритм
разворота односвязного списка.
...
Рейтинг: 0 / 0
17.03.2020, 18:18
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938406
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
пропущено...

А у этой задачи точно есть решение? Просто я не слышал чтобы кто-то сильно переживал
по поводу o(n) reverse.
эту задачу не надо рассматривать как реализацию reverse. Никто в здравом уме не будет реверсить строку или массив подобным образом. Просто головоломка, на подумать, размять мозг, отвлечься от кодерской рутины.

А у тебя есть твоё предложение по решению?

Я почему спрашиваю. Обидно знаешь-ли. Делать что-то "просто так". А ты - как ловкий тролль.
Забросил. И сидишь себе.
...
Рейтинг: 0 / 0
17.03.2020, 18:25
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938414
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Имя пользователя1
что-то не очень. Линия разреза очевидно должна быть меньше стороны треугольника. Даже если просто разрезать по высоте, длина разреза будет a*sqrt(3)/2, а это далеко не минимум.
Н-да, там поспешил, пересчитал. Последнее слово a*sqrt(2)/2 , всяко меньше, м.б. и не так далеко, но хотел назвать именно это (если снова не ошибся).
...
Рейтинг: 0 / 0
17.03.2020, 18:37
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938428
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
booby
я так скромно думаю:
если бы у этой задачи было решение, да еще универсальное, его, почти наверно, можно было бы использовать
для разворота односвязного списка быстрее, чем за n-1 шагов
нет, решение не подойдёт для списка, там доступ к произвольным элементам
...
Рейтинг: 0 / 0
17.03.2020, 19:01
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938455
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Имя пользователя1
пропущено...
эту задачу не надо рассматривать как реализацию reverse. Никто в здравом уме не будет реверсить строку или массив подобным образом. Просто головоломка, на подумать, размять мозг, отвлечься от кодерской рутины.

А у тебя есть твоё предложение по решению?

Я почему спрашиваю. Обидно знаешь-ли. Делать что-то "просто так". А ты - как ловкий тролль.
Забросил. И сидишь себе.
решение есть. Когда нет решения, то я об этом сразу говорю.

Если кто сомневается в наличии, могу выслать персональным сообщением.
...
Рейтинг: 0 / 0
17.03.2020, 20:38
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938456
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98
Имя пользователя1
что-то не очень. Линия разреза очевидно должна быть меньше стороны треугольника. Даже если просто разрезать по высоте, длина разреза будет a*sqrt(3)/2, а это далеко не минимум.
Н-да, там поспешил, пересчитал. Последнее слово a*sqrt(2)/2 , всяко меньше, м.б. и не так далеко, но хотел назвать именно это (если снова не ошибся).
ага, понял. Разрез параллельно стороне. Но это не минимум
...
Рейтинг: 0 / 0
17.03.2020, 20:39
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938460
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
пропущено...

А у тебя есть твоё предложение по решению?

Я почему спрашиваю. Обидно знаешь-ли. Делать что-то "просто так". А ты - как ловкий тролль.
Забросил. И сидишь себе.
решение есть. Когда нет решения, то я об этом сразу говорю.

Если кто сомневается в наличии, могу выслать персональным сообщением.

Нет уж. Давай в этот топик. Мне секретов не надо. Иначеб я тут не сидел.
...
Рейтинг: 0 / 0
17.03.2020, 21:07
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938464
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Имя пользователя1
Разрез параллельно стороне. Но это не минимум
Ну значит один из ближайших наклонных меньше, возможно, даже что с изломом или с 2-мя даже. Неохота смотреть на движение точек по сторонам. Они там с разной скоростью.
Народ! налетай, задел сделан.
...
Рейтинг: 0 / 0
17.03.2020, 21:38
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938466
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
mayton
Нет уж. Давай в этот топик.
Нет уж, нет уж, ещё не все притрагивались. Попарно 2-х соседей ведь можно ж поменять. А нет ли ощущения, что битиё яиц было бы разминкой к этой? зря что ли продукт изводили ...
...
Рейтинг: 0 / 0
17.03.2020, 21:48
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938486
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
exp98
Нет уж, нет уж, ещё не все притрагивались.

Согласен, хочется подумать. А когда решение уже выложено, то желание пропадает.
...
Рейтинг: 0 / 0
18.03.2020, 02:58
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938487
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98
А нет ли ощущения, что битиё яиц было бы разминкой к этой? зря что ли продукт изводили ...
ничего общего, совсем разные идеи
...
Рейтинг: 0 / 0
18.03.2020, 03:01
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938488
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
Имя пользователя1
ничего общего, совсем разные идеи

А какой лучший результат для строки в 99 символов?

N получить довольно просто:
1. подстрока а - последний символ, подстрока b - с первого до предпоследнего символа
2. подстрока а - последний символ, подстрока b - со второго до предпоследнего символа
и т.д. пока все символы не встанут на свои места.

Т.е. каждый раз последний символ ставим на должное ему место:

012345678 9 - 012345678 и 9
9 01234567 8 - 01234567 и 8
98 0123456 7 - 0123456 и 7
987 012345 6 - 012345 и 6
9876 01234 5 - 01234 и 5
98765 0123 4 - 0123 и 4
987654 012 3 - 012 и 3
9876543 01 2 - 01 и 2
98765432 0 1 - 0 и 1
98765432 1 0 - done
...
Рейтинг: 0 / 0
18.03.2020, 03:18
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938489
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
labarad
А какой лучший результат для строки в 99 символов?
50 действий
...
Рейтинг: 0 / 0
18.03.2020, 03:38
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938622
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я в задачах оптимизации исхожу из некого физико-механического принципа. Если
представлять символы - ящиками а позиции - стеллажами то задача сводится
к некому оптимальному маршруту авто-погрузчика который может их очень
быстро перевернуть. Причем авто-погрузчик может захватывать группу ящиков.

Я думал и так и эдак и лучше чем классический реверс - ничего не выходит.

Но поскольку автор говорит - что это "разогрев" аудитории - тогда я жду что
будет следующее. Сама по себе задача реверса уже не интересна.
...
Рейтинг: 0 / 0
18.03.2020, 11:35
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938653
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Из курса инженерной графики (AutoCad e.t.c) я помню что такое линейное преобразование.
Вобщем суть такова. Если у вас есть объект в 3D пространстве (множество трехмерных точек)
и вам его надо часто и много двигать и вращать и масштабировать (наподобие 3д шутера)
то вы принимаете решение закрепить на ним матрицу линейных преобразований (4х4)
и меняя ее коэффициенты можно деформировать и масштабировать вращать и двигать
этот объект.

В неком гипотетическом случае строка может быть представлена стационарным
иммутабельным вектором. И набором линейных преобразований. Сдвиг. И масштабирование.
Но в данном случае масштабирование будет единичкой со знаком + или -. И эти коэффициенты -
частный случай матрицы 2х2 для данного одномерного вектора символов.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
class ReversAbleString(val string : String) {

   var int offset; 
   var int scale; // +1,-1   
 
   def getTransformedString() : String = ???

   def reverse() {
      ... invert scale and change offset to be correct
   }
}



Здесь реверс будет иметь сложность o(1). Хотя билдер строки будет иметь какую-то линейную
комплексность но нам пофиг. Предполагаем что есть некое lazy поведение. Вдруг строка вообще
не понадобится (типичный случай для логгеров) а преобразование зря делалось.
...
Рейтинг: 0 / 0
18.03.2020, 12:11
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39938817
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Я думал и так и эдак и лучше чем классический реверс - ничего не выходит.
классический реверс дает 49 обменов символами (первый с последним, второй с предпоследним и тд), он по любому быстрее. Здесь прикол именно в ограничениях - можно обменивать местами только соседние подстроки
...
Рейтинг: 0 / 0
18.03.2020, 16:42
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939334
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Имя пользователя1,
хватит издеваться над животными,
треугольник режется дугой окружности,
режем радиусом t= a*sqr( sqr(27)/4/pi), L~0,673387*a >2/3
(если прямой,то только a*sqr(2)/2, L~0,7*a)
...
Рейтинг: 0 / 0
19.03.2020, 22:16
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939349
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98,

что за дуга, где центр, и главное, почему это минимум? )
...
Рейтинг: 0 / 0
20.03.2020, 00:53
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939712
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Имя пользователя1,
будете маскироваться до победного? имеете меньшее значение -- предъявите + алгоритм.
Окр. центром в вершине тр-ка, радиус t указан выше.
Ну, 2pi*R/6 же. Доказывать не требовалось по ТЗ. Хотя можно и обсудить, но только после вас. И ... я ведь не свободен от ошибок, да и допускаю возможность нескольких вариантов непрерывной линии одной длины.
...
Рейтинг: 0 / 0
20.03.2020, 20:11
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939832
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98
Доказывать не требовалось по ТЗ. Хотя можно и обсудить, но только после вас.
доказательство тут - самая интересная деталь.

Пусть у нас линия разреза между точками А и В на сторонах. Соединим 6 треугольников одноимёнными точками. Линии разреза станут замкнутым контуром, площадь внутри которого равна 3 треугольниками. Как известно, минимальная длина будет, если этот контур - окружность, что получается, если разрез делать по дуге.
...
Рейтинг: 0 / 0
21.03.2020, 12:20
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939891
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Это безусловно интересно тем, кто не брался за задачу. Только вы умело обходите суть вопроса.
1) Вопрос был про значение. Значение см. выше в моём посте. Откуда же я его взял?
2) Док-во. я вроде и намекал на это самое док-во и эту теорему минимальности, см. выше в моём посте. И даже в явном виде упомянул ещё ранее (п.3)
3) Отдельного объяснения требует, почему круг, вырезанный внутри тр-ка, будет длиннее разомкнутой линии. Та же самая теорема + вычисление её периметра и сравнение. Эти значения я приводил ранее при первых попытках решения.
(далее удалил ...)
...
Рейтинг: 0 / 0
21.03.2020, 16:37
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39939898
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Собсно, хотел спорсить: кто-нибудь брался за вопрос с бисектириссами треугольника? Что-то пока ничего простого не проглядывает. Если рисовать граф, то он уж очень быстро растёт с каждым разрезом, чтобы использовать подбор комбинаций углов А/2, В/2 и (180-А-В/2).
Маячат впереди какие-то суммы 2^k (если в обратном направлении) - не более того. Где-то должны появиться циклические послед-сти.
Если отталкиваться от соотношения сторон при разрезании, то формулы кажутся ещё громоздче.

Короче говоря, какие будут подходы к решению?
...
Рейтинг: 0 / 0
21.03.2020, 16:54
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39940178
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Собсно, хотел спорсить: кто-нибудь брался за вопрос с бисектириссами треугольника? Что-то пока ничего простого не проглядывает. Если рисовать граф, то он уж очень быстро растёт с каждым разрезом, чтобы использовать подбор комбинаций углов А/2, В/2 и (180-А-В/2).
Маячат впереди какие-то суммы 2^k (если в обратном направлении) - не более того. Где-то должны появиться циклические послед-сти.
Если отталкиваться от соотношения сторон при разрезании, то формулы кажутся ещё громоздче.

Короче говоря, какие будут подходы к решению?


можно попробовать решать в обратную сторону:
рекурсивно из какого треугольника мог бы получиться заданный
и доказать, что там все зациклено
...
Рейтинг: 0 / 0
23.03.2020, 10:43
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39940307
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aleksandr Sharahov, так хорошо в надежде, что не все варианты нужно перебрать. Но умозрительно кажется, что придётся рассматривать фиктивные варианты. Т.к. если обратный вывод, то мы не знаем заранее, какой угол получен на пересечении бисектриссы со стороной, а какой делением угла и т.д.
Ну т.е. кроме равенства А+В+С=180 и нечем воспользоваться, выходит.
...
Рейтинг: 0 / 0
23.03.2020, 16:50
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39940309
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
exp98
...3) Отдельного объяснения требует, почему круг, вырезанный внутри тр-ка, будет длиннее разомкнутой линии.
4) И ещё доказать, почему не получится резать дугой (либо ломанной), имеющей ровно 2 тт пересечения с одно стороной?
...
Рейтинг: 0 / 0
23.03.2020, 16:54
| Ответить | Цитировать | Написать  
25 сообщений из 339, страница 12 из 14
  12  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39939712&tid=1339678]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 159ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 73ms
get tp. blocked users:
 2ms
others: 13ms
total:  289ms
созд. / загр.: 289ms
x
x
Закрыть


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