|
|
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Решал сегодня достаточно простую задачу, но решил её не оптимально. Привожу ссылку на саму задачу . Вот как я её решаю Код: plaintext 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. Очевидно что алгоритм не оптимален. Мне в голову пришёл другой способ решения данной задачи, Элементы суммы есть количество элементов прямоугольников окружающих прямоугольник содержащий нужную координату, дельта-сдвиг внутри прямоугольника содержащего нужный элемент. Мне кажется что данный алгоритм вполне можно реализовать. Так ли это ? Приходят ли вам в голову ещё какие-либо способы решения данной задачи ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 08:31 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Кстати, мой код можно оптимизировать, только пока я не решил как, и стоит ли это делать. Возможно вы реализовали бы по-другому уже реализованный алгоритм ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 08:34 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Память забыл освободить. Прошу прощение (это все после перелета((( ). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 08:37 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
помню, в 1990-ом писал змею в лабиринте очень интересно было :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 10:39 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryПамять забыл освободить. Прошу прощение (это все после перелета((( ). Саш ты как всегда наколбасил тучу ненужного кода. У тебя в функции move_on_square_spiral идёт сплошная копи-паста одного и того-же расчётного блока с небольшими изменениями вектора движения который ты прибавляешь к cur_i, cur_j. Не нужно быть Фаулером чтобы сказать что это код "смердит" и срочно требует рефакторингов. Кстати почитай про Аффинные преобразования на плоскости и в частности Поворот вектора на 90 градусов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 12:50 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton, спасибо :) Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно. Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 14:57 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercurymayton, спасибо :) Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно. Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ? Конкретное? Вечером я допью чай. И как покромсаю твой сорц. Ожидаю чуть более чем наполовину сокращение количества ненужных символов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 15:04 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercurymayton, спасибо :) Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно. Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ? вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. когда вы уже отучитись от "стиля" их 70-х годов? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 15:52 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
nolockyвообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. По вашему... можно-ли взять за правило - переписывать любой I/O на mmap? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 16:18 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
maytonnolockyвообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. По вашему... можно-ли взять за правило - переписывать любой I/O на mmap? В современном мире - да. Есть только одна задача, где это не нужно делать - это syslog Для сети же есть splice и sendfile, там тоже, внезапно, все вокруг mmap ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2014, 18:57 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
nolockySashaMercurymayton, спасибо :) Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно. Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ? вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. когда вы уже отучитись от "стиля" их 70-х годов? Я уверен в том, что не вы определяете правила приличного общества ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 06:18 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercury, не отлаживал, тест прошла - и ладно ) Код: pascal 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 13:08 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercurynolockyпропущено... вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. когда вы уже отучитись от "стиля" их 70-х годов? Я уверен в том, что не вы определяете правила приличного общества Конечно не я, разве я где-то говорил, что использовать mmap - это правило, придуманное лично мною? Ты неудачно решил показаться умным. У тебя это не получилось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 13:14 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, вкралась пара неточностей с обратным ходом, исправил Код: pascal 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. или эквивалентная версия через case Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 14:00 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
nolockySashaMercuryпропущено... Я уверен в том, что не вы определяете правила приличного общества Конечно не я, разве я где-то говорил, что использовать mmap - это правило, придуманное лично мною? Ты неудачно решил показаться умным. У тебя это не получилось. Вы вообще адекватный человек ? В каком месте я решил показаться умным, тут половина форума умнее меня, и я это говорил всегда, и именно поэтому я обращаюсь к этому форуму за советом. Администрация, уберите его отсюда, очевидно что этот идиот меня провоцирует. Хватает идиотов в жизни, я минимизировал свое появление в интернете только до этого сайта, и никак не ожидал встретить такого кретина тут. Администрация, я ещё раз отмечаю, его сообщение выше очевидная провокация. Примите меры к этому пользователю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 14:52 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovAleksandr Sharahov, вкралась пара неточностей с обратным ходом, исправил Код: pascal 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. или эквивалентная версия через case Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. Спасибо :) Скоро займусь вашей реализацией ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 14:53 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, а можно услышать ваши комментарии по вашей реализации ?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 15:04 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercury, вот это еще посмотрите: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 15:29 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahov, а можно услышать ваши комментарии по вашей реализации ?) CellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника. CellCount3 в цикле срезает верхний слой прямоугольника и поворачивает прямоугольник на 90 до тех пор пока точка не окажется в этом слое, а затем прибавляет расстояние до нее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 15:37 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Проверьте пожалуйста прямоугольник 10 3 , точка 5 2, и прямоугольник 100 000 100 000, точка 50000 50000 Сейчас сам не могу этого сделать, пишу не с того компьютера где это возможно, и меня уже заставляют его выключать( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 16:03 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryПроверьте пожалуйста прямоугольник 10 3 , точка 5 2, и прямоугольник 100 000 100 000, точка 50000 50000 Сейчас сам не могу этого сделать, пишу не с того компьютера где это возможно, и меня уже заставляют его выключать( 26 1410065405 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 16:10 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
В данной задаче я проглядел одно важное условие - в каждой клетке растёт по ягоде. Вобщем уравнение движения Медведя в динамике никому не нужно. Мы заранее знаем сколько он соберёт ягод исходя геометрии на плоскости. Формула упрощается до разности площадей двух прямоугольников. Последний (финальный) круг медведя решается требует двух-трех проверок условий и коррекции площади. Циклы и рекурсии для решения данной задачи не нужны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 18:01 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
а это комбинация идей из CellCount1 и CellCount3: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 21:40 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
nolockySashaMercurymayton, спасибо :) Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно. Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ? вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи. когда вы уже отучитись от "стиля" их 70-х годов? нахрена mmap? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 23:04 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=38766176&tid=1341199]: |
0ms |
get settings: |
6ms |
get forum list: |
18ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
133ms |
get topic data: |
7ms |
get forum data: |
1ms |
get page messages: |
36ms |
get tp. blocked users: |
1ms |
| others: | 213ms |
| total: | 419ms |

| 0 / 0 |
