|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Всем привет. Допустим, есть набор точек (заданы координатами): Код: plaintext 1. 2. 3. 4. 5. 6. 7.
И по ним построена диаграмма (см в аттаче). Требуется найти такое подмножество смежных отрезков, для которого верны следующие утверждения: 1) сумма длин его отрезков не меньше N% от общей суммы длин всех отрезков; 2) число отрезков в этом множестве - минимальное (т.е. нет аналогичных других подмножеств, в которых число отрезков строго меньше, чем в найденном) Что-то не могу понять: что гуглить ? название алгоритма хотя бы или направление в математике для этого... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.08.2021, 13:22 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Голос из погреба, быстрее будет написать несколько циклов и найти минимум ... |
|||
:
Нравится:
Не нравится:
|
|||
14.08.2021, 13:43 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Один цикл чтобы посчитать общую сумму. Второй цикл чтобы найти все возможные группы отрезков. Третий цикл, вложенный во второй, чтобы посчитать количество отрезков в каждой группе. Вот и весь алгоритм. Лабораторная работа первокурсника. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.08.2021, 13:56 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Я тоже из погреба. Нужен наиболее узкий и непрерывный кусок спектра распределения? с интегралом больше заданного. Или непрерырвность не требуется? И кстати, мне кажется, что достаточно проскользить по накопительной кривой заданным окном (N% в высоту). Проскользить слева направо и выбрать эти наиболее узкие интервалы. Тогда вобще один цикл. На глаз вижу 2х претендентов. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2021, 13:49 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
exp98 Я тоже из погреба. Нужен наиболее узкий и непрерывный кусок спектра распределения? с интегралом больше заданного. Или непрерырвность не требуется? И кстати, мне кажется, что достаточно проскользить по накопительной кривой заданным окном (N% в высоту). Проскользить слева направо и выбрать эти наиболее узкие интервалы. Тогда вобще один цикл. На глаз вижу 2х претендентов. Постановка не особо сложная. Но слова могут быть слишком по разному интерпретированы. Я-бы предложил автору взять на бумажке вручную посчитать хотя-бы 1 вариант решения где в исходных данных будет всего 5-10 отрезков. И потом по этим данным сформировать следующее утверждение в таком формате. Input: Код: sql 1. 2. 3. 4. 5.
Output: Код: sql 1. 2.
Далее - по этому утверждению мы сможем написать модульный тест и код к нему. Если этого не сделать - то задача будет "заболтана". В топик зайдут эксперты которые будут задавать бесконечное число уточнений и мыслей и тема задачи будет просто похоронена под потоком деталей. Гуглить задачу - скорее всего бесполезно. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2021, 15:45 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Ну мимо одного цикла, в самом начале, считающего общую сумму, никуда, надо же знать, сколько это - N%. А дальше второй цикл. Держим два указателя, на начало и конец окна, и текущую сумму значений между ними. Если текущая сумма больше - сравниваем вариант с уже имеющимся. Если он лучше (или если имеющегося - ещё нет), запоминаем. Иначе - сдвигаем первый указатель и повторяем. Если сдвигать некуда - завершаем. Если проверяли, надо ли запоминать, проверяем, можно ли сдвинуть второй (останется ли сумма больше). Если можно - сдвигаем и повторяем. Оптимальный порядок действий (для уменьшения количества проверок и веток) искать лениво. Самостоятельно разберётесь. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2021, 16:05 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
накидал VBA-код в Excel: Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165.
Пока не вижу, можно ли сделать что-то существенно лучше или нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2021, 20:02 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
https://jsfiddle.net/cb9ga7qj/ в принципе, по описанию Akina расширяем окно вправо, а если оказалось больше или равно мин. сумме, то сужаем слева. Линейная сложность, без доп. памяти. Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 13:06 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
я ведь правильно понял, что все Y больше нуля? иначе придется немного по-другому решить, тоже линейно, но уже с O(N) памяти ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 13:15 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Я тот самый "эксперт": в универсальной проге надо помнить на всякий случ, что значения м.б. <0. mayton, вспомнился вопрос о выборе лучшей невесты оптимальным способом. Вот если бы добавить ещё совсем неможко данных, то выбор оказался бы третьим по росту. И теоретическая оценка матож 3/4 от макс была бы превышена. К сож в наборе этой длины скорее всего невеста будет ростом ~490, это ~в 1-й десятке , и от матож это уже дальше. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 13:22 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
2Имя пользователя1, можно положить let bestBegin = 0, bestEnd = arr.length; тогда проверка bestBegin < 0 уйдёт. в остальном, кажется, nice ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 14:41 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Матрица скользящих сумм. По горизонтали - отрезки. А по вертикали - скольящая сумма N соседей. По матрице - должна образоваться некая "область" решений которую удобно обозревать глазами. Как в транспортной задаче. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 14:53 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
И нервную сеть на на матрицу напустить, чтобы самому не программировать. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 15:26 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Кстати подобных экспериментов "непрограммирования" уже есть у нас. Тут и там появляются НС которые то играют в Супер-Марио а то и программируют PacMan без строчки кода. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 15:37 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
booby можно положить let bestBegin = 0, bestEnd = arr.length; тогда проверка bestBegin < 0 уйдёт. у меня с этими "крайними кейсами" всё время путаница ) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2021, 15:44 |
|
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
|
|||
---|---|---|---|
#18+
Голос из погреба, что-то очень ваш график на гаусианы наложенные смахивает Вы точно ищете то, что написали? Я честно говоря подумал, исходя из рисунка, что нужно найти параметры гаусиан, это делается различными модификациями EM-методов ... |
|||
:
Нравится:
Не нравится:
|
|||
18.08.2021, 10:00 |
|
|
start [/forum/topic.php?fid=16&msg=40091432&tid=1339640]: |
0ms |
get settings: |
10ms |
get forum list: |
11ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
79ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
55ms |
get tp. blocked users: |
1ms |
others: | 15ms |
total: | 193ms |
0 / 0 |