|
|
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 разрезать равносторонний треугольник на 2 куска равной площади, так чтобы длина линии разреза была минимальной ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.03.2020, 16:21 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Имя пользователя1 разрезать равносторонний треугольник на 2 куска равной площади, так чтобы длина линии разреза была минимальной ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.03.2020, 16:22 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 labarad, В худших случаях по прежнему 5*N, хотя таких кейсов намного меньше Если решать задачу практически в виде алгоритма для стандартного компа, то подсчитать количество вагонов можно за N, т.е. всего за один проход: 1. Запомнить состояние нулевого вагона. 2.а Если состояние следующего вагона НЕ совпадает со значением п.1 (нулевой вагон), то - идти дальше в следующий вагон. 2.б Если состояние следующего вагона совпадает со значением п.1 (нулевой вагон), то - изменить состояние текущего вагона и - проверить состояние нулевого вагона: если состояние нулевого вагона изменилось (не совпадает с п.1), то круг замкнулся ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 00:39 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
это labarad можно за N противоречит этому labarad проверить состояние нулевого вагона т.к. "проверить состояние нулевого вагона" = вернутся в нулевой вагон, и так много раз. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 10:06 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
msLex это labarad можно за N противоречит этому labarad проверить состояние нулевого вагона т.к. "проверить состояние нулевого вагона" = вернутся в нулевой вагон, и так много раз. "для стандартного компа", у нас тут двусвязный кольцевой список с булевскими значениями, и всего один указатель на элемент, примерно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 10:57 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 msLex ... т.к. "проверить состояние нулевого вагона" = вернутся в нулевой вагон, и так много раз. "для стандартного компа", у нас тут двусвязный кольцевой список с булевскими значениями, и всего один указатель на элемент, примерно так. Друзья, Нисколько не спорю, что, например, при ограничении функционала железа невозможно оптимизировать алгоритм. Однако, на компе, где можно программно иметь не один, а два указателя (в поезде находится два человека, а не один) производительность можно повысить аж в 5 раз. Что, согласитесь, на больших объёмах весьма существенно - час будет прога считать данные или пять часов? И цена этому ускорению - условные 4 или 8 байт. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 13:55 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
labarad, решение чем-то напоминает "я же не отдам некту яблоко, хоть он дерись" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 15:35 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov labarad, решение чем-то напоминает "я же не отдам некту яблоко, хоть он дерись" Могу только повторить: эффективность реализации алгоритма объективно зависит от платформы, на которой он будет исполняться. Например, если проектируете железо, то добавление простенькой функции хранения дополнительного указателя позволит увеличить скорость обработки данных в пять раз. Стоит ли учитывать возможность такой оптимизации, думаю, вопрос риторический. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 16:58 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
labarad, теперь уже больше похоже на "как пройти на Дерибасовскую" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2020, 20:06 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
iOracleDev Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет. а если всего будет 2 вагона (но мы этого не знаем) и в обоих свет выключен? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 11:20 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
DmitryKn iOracleDev Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет. а если всего будет 2 вагона (но мы этого не знаем) и в обоих свет выключен? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 12:33 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
задачи пока без решений: 22090677 Есть строка длиной 99 символов, причем все символы в строке разные. За одно действие можно взять 2 соседние подстроки и обменять местами (например, было "...abcdefg...", стало "...aefbcdg...", поменяли красную и синюю подстроки). Сколько минимум действий понадобится, чтобы развернуть строку задом наперед? ---- 22095992 Множество А изначально содержит 2 элемента - числа 1 и 4. За одно действие можно добавить туда число (a+b+ab), где a и b - любые два числа из А, возможно, одинаковые. Получится ли на каком-то шаге добавить туда какое-нибудь число вида 2*10 k , где k - натуральное (то есть число 200...0), и если да, то как? ---- 22096932 разрезать равносторонний треугольник на 2 куска равной площади, так чтобы длина линии разреза была минимальной ---- 22096932 дан треугольник с углами 20 гр., 60 гр., 100 гр. Его разрезают по биссектрисе. Потом любой из полученных кусков тоже разрезается по биссектрисе. И так далее. Можно ли на каком-то этапе получить треугольник, подобный исходному? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 12:40 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, с двумя вагонами, при условии их идентичности и замкнутости и свет может быть включен или не включен, и если свет выключен в обоих, при указанных выше действиях получим включенный свет в обоих и безконечный бег по кругу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 13:25 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
DmitryKn при указанных выше действиях получим включенный свет в обоих и безконечный бег по кругу при каждом включении света мы возвращаемся к вагону А (при возврате считаем вагоны в обратную сторону, и зная сколько прошли вагонов "вперед", легко можем вернуться в указанный) и проверяем в нем свет, который оставили выключенным. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 13:32 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, согласен, зря это я ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 14:14 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
DmitryKn зря это я ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 14:25 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Имя пользователя1 разрезать равносторонний треугольник на 2 куска равной площади, так чтобы длина линии разреза была минимальной Открывая страницу для ответа, я собирался доказать, что достаточно срезать верхушку самого маленького угла параллельно противоп-й стороне. Отсечь ~sqr(3)/2-ую часть этой высоты. И тогда длина среза~sqr(3)*a. Для произвольного тр-ка. Т.к. любая незамкнутая спрямляемая и непрерывная кривая обязательно пересечёт этот срез ==> её длина будет больше. Конечно и в цифрах тоже я могу ошибаться, проверять не буду. Но пока ждал открытия страницы, подумал, зачем обязательно открытую кривую? Тем более, в условии равносторонний тр-к. А вдруг окружность или квадрат внутри? Да вроде при одинаковой площади (а площадь мы знаем) наименьший периметр имеет окружность. Вот не помню в каком это классе замкнутых кривых. ПОлучатся R ~ a/2/sqr(2pi). Тогда длина = a*sqr(pi/2). Если снова не ошибся. Добавил для полноты: это меньше вписанной окр. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 14:57 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 22096932 дан треугольник с углами 20 гр., 60 гр., 100 гр. Его разрезают по биссектрисе. Потом любой из полученных кусков тоже разрезается по биссектрисе. И так далее. Можно ли на каком-то этапе получить треугольник, подобный исходному? Получается, что резать можно только всё время через одну и ту же вершину? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 15:02 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 Соколинский Борис пропущено... Куски односвязные? Открывая страницу для ответа, я собирался доказать, что достаточно срезать верхушку самого маленького угла параллельно противоп-й стороне. Отсечь ~sqr(3)/2-ую часть этой высоты. И тогда длина среза~sqr(3)*a. Для произвольного тр-ка. Т.к. любая незамкнутая спрямляемая и непрерывная кривая обязательно пересечёт этот срез ==> её длина будет больше. Конечно и в цифрах тоже я могу ошибаться, проверять не буду. Но пока ждал открытия страницы, подумал, зачем обязательно открытую кривую? Тем более, в условии равносторонний тр-к. А вдруг окружность или квадрат внутри? Да вроде при одинаковой площади (а площадь мы знаем) наименьший периметр имеет окружность. Вот не помню в каком это классе замкнутых кривых. ПОлучатся R ~ a/2/sqr(2pi). Тогда длина = a*sqr(pi/2). Если снова не ошибся. Добавил для полноты: это меньше вписанной окр. Линия разреза очевидно должна быть меньше стороны треугольника. Даже если просто разрезать по высоте, длина разреза будет a*sqrt(3)/2, а это далеко не минимум. exp98 Имя пользователя1 22096932 дан треугольник с углами 20 гр., 60 гр., 100 гр. Его разрезают по биссектрисе. Потом любой из полученных кусков тоже разрезается по биссектрисе. И так далее. Можно ли на каком-то этапе получить треугольник, подобный исходному? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 15:51 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 задачи пока без решений: 22095992 Множество А изначально содержит 2 элемента - числа 1 и 4. За одно действие можно добавить туда число (a+b+ab), где a и b - любые два числа из А, возможно, одинаковые. Получится ли на каком-то шаге добавить туда какое-нибудь число вида 2*10 k , где k - натуральное (то есть число 200...0), и если да, то как? Возьмем множество B, такое что B k =A k +1. Тогда любой B k =B i *B j , т.е все элементы B в разложении на простые множители должны иметь только 2 и 5. 2*10 k +1 всегда будет иметь 3, т.е. не входит в B. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 16:37 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Имя пользователя1 задачи пока без решений: 22095992 Множество А изначально содержит 2 элемента - числа 1 и 4. За одно действие можно добавить туда число (a+b+ab), где a и b - любые два числа из А, возможно, одинаковые. Получится ли на каком-то шаге добавить туда какое-нибудь число вида 2*10 k , где k - натуральное (то есть число 200...0), и если да, то как? Возьмем множество B, такое что B k =A k +1. Тогда любой B k =B i *B j , т.е все элементы B в разложении на простые множители должны иметь только 2 и 5. 2*10 k +1 всегда будет иметь 3, т.е. не входит в B. я чуть по другому решил: все элементы из А при делении на 3 дают остаток 0 или 1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 16:55 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 22090677 Есть строка длиной 99 символов, причем все символы в строке разные. За одно действие можно взять 2 соседние подстроки и обменять местами (например, было "...abcdefg...", стало "...aefbcdg...", поменяли красную и синюю подстроки). Сколько минимум действий понадобится, чтобы развернуть строку задом наперед? Я взял короткую строку abcd. Для простоты пускай ее размер будет кратным 2^n. Тогда чтобы ее перевернуть можно сделать дерево действий. 1. abcd => (ab)(cd) => swap => (cd)(ab) 2. Повторить рекурсивно для каждой группы до тех пор пока в группе не будет 1 символ. (d)(c)(b)(a) Тоесть за 3 свопа мы перевернули 4 символьную строку. Для 99 символов будет логарифм2 высоты дерево свопов. Но беря во внимание что на последнем уровне количество листьев будет ]99/2[ = 50 То моё древо-видное решение будет ничем не лучше чем стандартная функция реверса строки. Которая делает тоже самое за гарантированное число 50 а для древо-видного свопа нужно еще посчитать порядка 7 уровне дерева сверху. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 17:06 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton а для древо-видного свопа нужно еще посчитать порядка 7 уровне дерева сверху. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 17:18 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 mayton а для древо-видного свопа нужно еще посчитать порядка 7 уровне дерева сверху. А у этой задачи точно есть решение? Просто я не слышал чтобы кто-то сильно переживал по поводу o(n) reverse. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 17:43 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton Имя пользователя1 пропущено... там будет ещё примерно столько же обменов ) А у этой задачи точно есть решение? Просто я не слышал чтобы кто-то сильно переживал по поводу o(n) reverse. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2020, 18:01 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39938299&tid=1339678]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
157ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
63ms |
get tp. blocked users: |
2ms |
| others: | 13ms |
| total: | 276ms |
| 0 / 0 |
