|
|
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#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 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
без этой хрени получаются хреновые алгоритмы) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 23:16 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
без этой хрени получаются хреновые алгоритмы) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2014, 23:19 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
У меня такой вопрос. Я дал вам площадку 10^6 на 10^6. Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ? Первые алгоритмы в целом понятны, вы модифицировали предложенною мной сумму как разность площадей, так действительно лучше. Сегодня вновь ничего не смогу проверить. Только завтра ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2014, 05:35 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Вчера решил попробовать решить этого "Вини-пуха" и сделать это наиболее эффективно, и начал с того что самой лучшей попыткой решения является реализация на BASIC (VB6) IDДатаАвторЯзыкВремяПамятьРазмер104.07.2009 19:35:38Антон ЛунёвBasic0.207218 Кб123 Во-первых, код который просто читает в переменные из файла и записывает решение заняло у меня около ~101 байт (без учетов пробелов, переносов) Код: vbnet 1. 2. 3. 4. 5. 6. 7. Остаётся 123 - 101 = 22 байта на формулу (тут циклом боюсь не запишешь) которая даст решение. Но во-вторых, самое странное, что даже программа которая ничего не делает и не считывает требует около 1,5 Мб памяти, но у решившего получается всего использовано 218 Кб. Я так чую или подвох какой-то (возможно раньше был компилятор у системы), либо фейковый результат... Может есть какое-то объяснение этому? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2014, 09:53 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryУ меня такой вопрос. Я дал вам площадку 10^6 на 10^6. Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ? Оно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит. SashaMercuryПервые алгоритмы в целом понятны, вы модифицировали предложенною мной сумму как разность площадей, так действительно лучше. Последний самый интересный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2014, 10:15 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
А можно подробнее про операцию "произведения по модулю". Я не понял как вы перемножили большие числа без длинной арифметики и Integer Promotion, в вашем коде я также не заметил специфических операций. Может быть вы предложите одну формулу для получения нужного результата ?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 02:37 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
VSVLAD , скорее всего товарищ использовал препроцессорную обработку для сокращения объёма кода ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 02:39 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryА можно подробнее про операцию "произведения по модулю". Я не понял как вы перемножили большие числа без длинной арифметики и Integer Promotion, в вашем коде я также не заметил специфических операций. Вот такие объявления Код: pascal 1. как раз и являются специфическими операторами. Они определяют сколько бит будет выделено для хранения и работы с переменной, т.е. количество ее возможных значений. Процессору ничего другого не остается, кроме как "крутиться" (здесь это очень точное слово) внутри этого множества значений. Это довольно большая тема, читайте книги или заводите отдельную ветку - поговорим. SashaMercuryМожет быть вы предложите одну формулу для получения нужного результата ?) Запросто ) Однако думаю вам это гораздо интереснее будет сделать самостоятельно. В данной задаче это не особенно актуально, но иногда бывает нужно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 08:17 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, мне показалось что вы не ответили на мой вопрос SSУ меня такой вопрос. Я дал вам площадку 10^6 на 10^6. Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ? Aleksandr Sharahov,Оно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит. а в тра-та-та:T ничего специфического я не вижу ;) Хотя в коде я не встретил у вас m*n - , потому вполне возможно что переполнения не будет, но тогда почему вы стали говорить про выполнение операций по модулю ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 08:32 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Если можно получить результат прямой формулой, то это всегда актуально ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 08:33 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryЕсли можно получить результат прямой формулой, то это всегда актуально ) Гаусс решал задачу о восьми ферзях. Он искал аналитическое решение вида формулы. И не нашёл. Для шахматных задач (комбинаторный класс задач) иногда и нет аналитического решения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 09:27 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryа в тра-та-та: ничего специфического я не вижу ;) А суслик есть, и от него зависит сгенерированный компилятором код. SashaMercuryХотя в коде я не встретил у вас m*n - , потому вполне возможно что переполнения не будет, но тогда почему вы стали говорить про выполнение операций по модулю ? Совершенно неважно есть там это умножение или нет. Код, используя целочисленную 32-битную арифметику, каким-то образом считает площадь, превышающую 2^31. Переполнения обязаны быть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 10:40 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
VSVLAD, а откуда взялась цифра 218 кб? Это что размер исходника? Бинарника? Или выделяемая память при работе приложения? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 15:35 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Это затрачиваемая программой память, размер кода 123 ) Объясните мне кто-нибудь пожалуйста, каким образом его программа работает с длинной арифметикой, и будет ли она у него на моих примерах ?) Кстати, Aleksandr Sharahov , зачем вы так усложнили поиск минимального отступа ? Простите, этот код весь ваш, я правильно понимаю ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 15:44 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton, вы полностью правы в вашем предыдущем рассуждении ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 15:46 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahov, зачем вы так усложнили поиск минимального отступа? Специально ничего не усложнял, а проще не сумел ) SashaMercuryПростите, этот код весь ваш, я правильно понимаю ? Разумеется, весь код, который я здесь привел, написан мной. В противном случае я сослался бы на автора кода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 17:16 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercury, про Гаусса? Или про прямоугольники? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2014, 17:16 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
По сути, и там и там, но я больше комментировал эту фразу ) mayton Для шахматных задач (комбинаторный класс задач) иногда и нет аналитического решения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 02:00 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?) Раскройте тайну для особо одарённых :D (nolocky, надеюсь вам понятно что это самоирония) Aleksandr SharahovCellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника. где эта формула в вашем коде ? Я вижу несколько другую ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 02:05 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Выделил немного времени на изменение предложенного алгоритма. итак, ваш код. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. по строчке Result:=2*(M+N-2*LoopCount)*LoopCount пока не буду говорить. Дальше, мы имеем матрицу со столбцами Result x y LC M N a Если записать ваш switch одной формулой, мы получим следующее F(k) числа Фибоначчи 1 1 2 3 ...(нас только первые 4 числа интересуют на самом деле) [k=4] используется классическая нотация Айверсона (программисты Си знают, а другие могут встретить хорошие разъяснений у Кнута) В первую очередь мне не нравится тот факт что я использую эту нотацию, так сразу формулу не получил, и сейчас не смогу сидеть и рассуждать, если у вас есть идеи, то пишите. И конечно хочется уйти от F(k) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 07:02 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SSВ первую очередь мне не нравится тот факт что я использую эту нотацию Нотация то мне нравится, даже очень :) Мне не нравится, что по факту в программе это ещё один if ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 07:05 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Мне не нравится что ты синус используешь для углов кратных четверти. В этой задаче - он вырожденный и заменяется на более примитивную функцию. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 09:46 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryAleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?) Боюсь, у меня получится хуже, чем пишут в книжках. Возьмите любую хорошую книжку (если не найдете, можно взять почти любую по ассемблеру) и прочитайте про представление чисел в памяти и операции с ними. Сразу все встанет на место. SashaMercuryAleksandr SharahovCellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника. где эта формула в вашем коде ? Я вижу несколько другую Попробуйте выполнить вычитание и разложить на множители. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 10:37 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovSashaMercuryAleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?) Боюсь, у меня получится хуже, чем пишут в книжках. Возьмите любую хорошую книжку (если не найдете, можно взять почти любую по ассемблеру) и прочитайте про представление чисел в памяти и операции с ними. Сразу все встанет на место. SashaMercuryпропущено... где эта формула в вашем коде ? Я вижу несколько другую Попробуйте выполнить вычитание и разложить на множители. 1. Не морочьте голову. Ответ на вопрос вы мне так и не дали, на вполне конкретный и обоснованный вопрос. Если я не прав, то пусть меня поправит кто-нибудь другой. Вопрос по переполнению не был раскрыт. 2. Уже давно сделал, и прекрасно вижу различия, только вы говорите одно, в коде пишите совершенно другое. Я вам про это говорю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 14:40 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
maytonМне не нравится что ты синус используешь для углов кратных четверти. В этой задаче - он вырожденный и заменяется на более примитивную функцию. крайне рад критике, может быть кто-нибудь ещё подскажет альтернативу лучше ?) А также подскажет как уйти от нотации Айверсона и чисел Фибоначчи ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 14:43 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SSУже давно сделал, и прекрасно вижу различия, только вы говорите одно, в коде пишите совершенно другое. Я вам про это говорю. Это к тому, что в коде не видно того что вы отнимаете, и потому не видно алгоритма. Если было бы чётко M*N-() , то ничего бы не спросил ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 14:46 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercurymaytonМне не нравится что ты синус используешь для углов кратных четверти. В этой задаче - он вырожденный и заменяется на более примитивную функцию. крайне рад критике, может быть кто-нибудь ещё подскажет альтернативу лучше ?) А также подскажет как уйти от нотации Айверсона и чисел Фибоначчи ? Саш я тоже поднаторел в научных дискурсах и могу кидать софизмы и парадоксы. Скажи пожалуйста. Это ты у Кнута прочитал про нотацию Айверсона? Ты уверен что она ДЕЙСТВИТЕЛЬНО необходима для решения задачи Вини-Пуха. Или это уже новая ветка дискурса с новой задачей? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 14:48 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Нет, про нее я узнал у своего наставника. 8 лет назад. А когда начал изучать Си понял, что вот же она тут :) А у Кнута недавно встретил, он хорошо объясняет. Интернет я не очень люблю, потому не стал рекомендовать гуглить, как это любит Анатолий. Мне захотелось оптимизировать его код, уйти от ветвлений, потому я предложил такую формулу, но тем не менее в ней ещё есть два ветвления. Разве это не интересно ? Разве задача про ферзей не кажется на первый взгляд такой-же простой как задача про медвежонка ?;) Меня гонят.. доброго времени суток ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 15:51 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton, 218 кб - выделяемая память приложению. 123 байта - размер исходного кода файла ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 18:15 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
VSVLADmayton, 218 кб - выделяемая память приложению. 123 байта - размер исходного кода файла Как они меряют? Так точно. Не реально мне интересно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 18:17 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton, Для меня это останется большой загадкой... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2014, 19:51 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton, Количество символов (кроме пробелов и переносов строк) и есть размер исходного кода. Вот так меряют. А объём памяти получается исходя из операций аллоцирования(исходя из моих личных наблюдений). Sharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос, и перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности. авторОно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит. Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ? Вы мне должны были ответить -эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую. И я практически уверен что код не ваш. Вы плаваете в элементарных вопросах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 03:14 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 07:28 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Более понятный код после рефакторинга Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. Единственное что мне тут не нравится, это использование вспомогательной переменной Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 07:30 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Я-бы не стал так писать. Код: plaintext 1. Лучше-бы так. Код: plaintext 1. или Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 09:34 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Почему так писать не стоит? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 10:07 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Ну... в случае если (k>1) дает FALSE - будет (int)0. Для значения true думаю что возможны варианты ненулевых констант. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 10:22 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Да, вы правы, согласен. Спасибо :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 10:23 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
mayton Код: plaintext 1. зачем хвост после вопроса? Чем тебе так не нравится: Код: sql 1. в переменную логического типа сохраняем результат логического выражения. Глазами читается нормально. Если кто-то захочет переменную в арифметический расчет засунуть - это его проблемы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 10:26 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercurySharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос, Возможно, другие участники, как, впрочем, и я, не собираются учить Вас программированию за 21 день? Как-то не хочется всерьез объяснять, что термин "разность" служит для обозначения результата, а сама соответствующая операция называется вычитанием. Устройство ЭВМ, системы счисления, битовые операции и т.п. базовые вещи обязан знать назубок любой начинающий программист. Начните с этого, и, может быть, тогда найдется больше желающих вас поправить. И еще одно. На форуме вы можете задавать сколько угодно вопросов, но требовать на них ответа вы не можете. Какие задачи мне решать и на какие вопросы мне отвечать, решаете не вы. SashaMercuryи перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности. Где именно вы увидели личные оскорбления в ваш адрес? Ссылку. Вы параноик? SashaMercuryавторОно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит. Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ? Вы мне должны были ответить-эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую. Не совсем так. Даже ребенку очевидно, что ваши исходные данные заставляют программу считать площадь квадрата со стороной 10^5. Правильный ответ, как вам должно быть известно равен 10^10. И само собой разумеется, ни одна программа в мире не сможет поместить его в результат типа integer. Результат вычислений получен в полном соответствии с известным принципом "мякину заложишь - мякину получишь". Правильный ли он? Вы этот вопрос не задавали, и я на него не отвечал. Я отметил лишь, что при вычислениях обязательно было переполнение. Если вы программист, то должны понимать, что в данном случае это означает неверный результат. SashaMercuryИ я практически уверен что код не ваш. Вы плаваете в элементарных вопросах. Дайте угадаю. Наверно, он ваш? Теперь уже похоже на то, что вы успешно окончили курсы "Жизнь за 21 день". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 10:26 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Давайте.... в конструктивное русло. Без личностей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 12:53 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Dima Tmayton Код: plaintext 1. зачем хвост после вопроса? Чем тебе так не нравится: Код: sql 1. в переменную логического типа сохраняем результат логического выражения. Глазами читается нормально. Если кто-то захочет переменную в арифметический расчет засунуть - это его проблемы. bool не нравится. Нету у нас общего понимания что такое этот бул. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2014, 16:26 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovSashaMercurySharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос, Возможно, другие участники, как, впрочем, и я, не собираются учить Вас программированию за 21 день? очевидно не собираются. Aleksandr SharahovКак-то не хочется всерьез объяснять, что термин "разность" служит для обозначения результата, а сама соответствующая операция называется вычитанием. Устройство ЭВМ, системы счисления, битовые операции и т.п. базовые вещи обязан знать назубок любой начинающий программист. Начните с этого, и, может быть, тогда найдется больше желающих вас поправить. И еще одно. На форуме вы можете задавать сколько угодно вопросов, но требовать на них ответа вы не можете. Какие задачи мне решать и на какие вопросы мне отвечать, решаете не вы. в этой теме, получалось, что решал я. Правда отвечали вы хреново. Aleksandr Sharahov SashaMercuryи перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности. Где именно вы увидели личные оскорбления в ваш адрес? Ссылку. Вы параноик? вы прекрасно понимаете о чём я . ваше сообщение видимо уже удалено. Aleksandr Sharahov SashaMercuryпропущено... Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ? Вы мне должны были ответить-эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую. Не совсем так. Даже ребенку очевидно, что ваши исходные данные заставляют программу считать площадь квадрата со стороной 10^5. Правильный ответ, как вам должно быть известно равен 10^10. И само собой разумеется, ни одна программа в мире не сможет поместить его в результат типа integer. Результат вычислений получен в полном соответствии с известным принципом "мякину заложишь - мякину получишь". Правильный ли он? Вы этот вопрос не задавали, и я на него не отвечал. Я отметил лишь, что при вычислениях обязательно было переполнение. Если вы программист, то должны понимать, что в данном случае это означает неверный результат. Когда я давал вам пример, я не подумал что он выйдет за пределы 4Б. Когда прочитал от вас якобы правильный ответ, мне показалось странным, и я решил проверить, корректные ли входные данные я дал.( В целом они были бы корректные, если бы точка находилась ближе к краю, ибо вы не используете M*N в коде.) Оказалось что не корректные. Но ответ вы мне дали ! И я просто пытался узнать откуда он. Вам нужно было написать что он неверный. и всё. Aleksandr Sharahov SashaMercuryИ я практически уверен что код не ваш. Вы плаваете в элементарных вопросах. Дайте угадаю. Наверно, он ваш? Теперь уже похоже на то, что вы успешно окончили курсы "Жизнь за 21 день". нет. не мой, но автору спасибо. PS Крайне не люблю с кем то ругаться по таким глупым и пустым поводам, вы даже не представляете насколько мне это неприятно. Вы меня не понимаете или я вас не понимаю, в общем-то я сомневаюсь что мы друг другу что-то докажем.(и у меня нет желания). Потому я не буду больше вам отвечать и читать ваши сообщения. Слишком много нехороших настроений. Со своей стороны я себя так не вел по отношению к вам. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 01:59 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#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. Изменил массив shift ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 02:20 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Подумал, что если кто-нибудь не до конца понял алгоритм, лучше добавить рисунок ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 04:27 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 04:28 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Сейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 06:33 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
[quot SashaMercury]в этой теме, получалось, что решал я. Правда отвечали вы хреново./quot] У меня совершенно противоположное мнение. Не умеете ни решать, ни вести себя. SashaMercuryКогда я давал вам пример, я не подумал что он выйдет за пределы 4Б пропущено... Но ответ вы мне дали ! И я просто пытался узнать откуда он. Вам нужно было написать что он неверный. и всё. Зачем давать тестовый пример, не зная ответа? Я рассуждал как программист. То что вы дали 2 теста, причем второе значение находится явно вне области допустимых значений параметра меня нисколько не смутило. Вы спросили, что выдает программа в обоих случаях. Я ответил. Какие тут претензии? Или каждый раз, когда у вас в программе возникает переполнение, вы ищете виновника на стороне? SashaMercuryнет. не мой, но автору спасибо. Не стоит благодарности. Код писал больше для себя. Надо же иногда немного расслабиться. SashaMercuryя не буду больше вам отвечать и читать ваши сообщения. Правильно, берите только код! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 10:29 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
SashaMercuryСейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется). Саш. А как ты себе понимаешь площадь прямоугольника на дискретной поверхности? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2014, 17:20 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
maytonSashaMercuryСейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется). Саш. А как ты себе понимаешь площадь прямоугольника на дискретной поверхности? Как мощность элементов принадлежащих данному прямоугольнику ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 04:47 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Ну... ты ответил умно, но ниочём. Я не то имел в виду. Представь себе дискретную поверхность пикселов (ячеек, квадратиков e.t.c) Как ты думаешь, какую площадь должен иметь следующий прямоугольник? Код: plaintext 1. Конструктор задаёт левый верхний и правый нижний угол. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 12:23 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Можешь нарисовать на клеточной бумаге. Так нагляднее будет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:29 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
В данном прямоугольнике будет 7*11 элементов, потому 77 :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:31 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Только я исходил из того что это левый нижний и правый верхний. Рисовать не нужно, я просто только пришёл домой, так бы раньше ответил )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:33 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Я думаю что его площадь равна 60 квадратикам. Мне так кааатся... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:40 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Если брать за основу точки, то должно быть 77, а если квадратиков, то 60 :) Разве нет ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:48 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Точки (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) 7 в одной строке и таких строк 11 А квадратиков будет 6 в строке, 10 строк ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:51 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Хотя конечно может быть я ошибаюсь, это только мои предположения о том, как можно рассуждать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:52 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Парадокс заключается в последней фразе Конструктор задаёт левый верхний и правый нижний угол. Это вопрос договорённостей. Как мы договоримся задавать ректенжл - так и будет. Будем ли мы привязывать. Это как договорённости о право-сторонней (правило буравчика) или лево-сторонней системе координат (x,y,z) в 3-d графике. Это как наша договорённость о том как считать subsring(begin, end). Вот мне моё техническое чутьё подсказывает что over 50% графических библиотек 2D графики используют мой вариант толкования прямоугольника. Код: java 1. Здесь прямоугольник включает в себя x1,y1 но не включает точку x2,y2. Она лежит ВНЕ прямоугольника в том силе и правый и нижний отрезок прямоугольника. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 15:55 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Это может показаться странным но если мы переходим к непрерывности на плоскости (координаты - дробные) то всё становиться на смои места. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 16:01 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Это интересно. Хотя некоторые моменты мне не до конца понятны, но скорее это связано с тем что уже слишком поздно. Спасибо, я обязательно учту всё это :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 16:12 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Кстати в задаче о блуждающем Винни-пухе можно использовать подсчёт отрезков как прямоугольников с единичным измерением или делать вычитание площадей если это оптимизирует задачу по скорости и не противоречит смыслу. Мне кажется что на восточном направлении обхода сада ВинниПух может учитывать площадь по более простой формуле. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 16:18 |
|
||
|
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
|
|||
|---|---|---|---|
|
#18+
Буду рад любым предложениям по оптимизации ) У меня в голове крутится другой метод, хочу привести его путь к уравнению архимедовой спирали, и вычислять длину её дуги. Общая идея мне понятна, а возможно ли это сделать и как, пока не решил. Думаю что так решить можно. Меня гонят. Доброго времени суток C: ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2014, 16:40 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1341199]: |
0ms |
get settings: |
8ms |
get forum list: |
17ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
149ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
112ms |
get tp. blocked users: |
1ms |
| others: | 204ms |
| total: | 509ms |

| 0 / 0 |
