Буду выкладывать наработки в народ
Соревнование на быстроту алгоритмов
Уже есть подобная тема http://www.flasher.ru/forum/blog.php?bt=5651 , тут задание будет немного другим :
Дается задача связанная с алгоритмом, несколько людей(ну или хотя бы 1) выкладывает код решения и мы проверяем чей алгоритм работает быстрее. Призов соответственно нет, только эстетический интерес. После того как будут решения, ну или хотя-бы одно решение - задание меняется. Предлагаю задавать не сложные задания связанные с одномерными-двумерными массивами как в этом примере http://www.flasher.ru/forum/showthread.php?t=170199
Ну что-же первое задание :
Цитата:
Есть карта NxN (N%2 = 1), есть ее центр (N/2 , N/2 - соответственно , с идентификатором 0). Необходимо зная идентификатор index, найти координаты на карте. Идентификаторы на карте расставлены в спиралевидном порядке - по часовой стрелке,спираль начинает движение вверх , т.е. пример карты 3х3:
Y\X| 0 | 1 | 2 |
0 _| 8 ^ 1 > 2
1 _| 7 ^ 0 v 3
2 _| 6 ^ 5 < 4
Y\X| 0 | 1 | 2 |
0 _| 8 ^ 1 > 2
1 _| 7 ^ 0 v 3
2 _| 6 ^ 5 < 4
Всего комментариев 10
Комментарии
20.10.2011 23:04 | |
Как эта спираль будет выглядеть не с квадратом а прямоугольником?
|
20.10.2011 23:42 | |
А судьи кто?
Какой бенчмарк? |
21.10.2011 01:11 | |
А на практике такая задача встречалась?
Предлагаю такую: есть битмапа, на ней есть одна непрозрачная область. Надо обойти её по часовой стрелке. Т.е. на входе битмапДата, на выходе вектор/массив точек, принадлежащих обходу. Если непрозрачные куски касаются "углом", то это считается касанием и они считаются одним куском. Где первая точка обхода - не важно (но естессно рядом с непрозрачной областью). Задачка тоже в принципе школьная, но встречается в практике. private var sideBasesX:Array = [-1, 1, 1, -1]; private var sideBasesY:Array = [1, 1, -1, -1]; private var sideDirX:Array = [1, 0, -1, 0]; private var sideDirY:Array = [0, -1, 0, 1]; public function calcPos(N:int, num:int):Point { if (num == 0) return new Point((N-1)/2, (N-1)/2); var ring:int = int( ( Math.sqrt(num) - 1) / 2 ); var sideSize:int = 2 * (ring + 1); var sideNum:Number = int( (num - (2 * ring + 1) * (2 * ring + 1)) / sideSize ); var sideDiff:int = num - (2 * ring + 1) * (2 * ring + 1) - sideNum * sideSize; //trace(ring, sideSize, sideNum, sideDiff); return new Point((N-1)/2 + sideBasesX[sideNum] * (ring + 1) + sideDirX[sideNum] * (1 + sideDiff), (N-1)/2 - sideBasesY[sideNum]*(ring + 1) - sideDirY[sideNum] * (1 + sideDiff)); } |
|
Обновил(-а) -De- 21.10.2011 в 02:17
|
21.10.2011 03:09 | |
/2 надо менять на *0.5
|
21.10.2011 08:00 | |
По моему, условие задачи не до конца продуманно. Как будет проходить спираль, если размер области будет 5 на 11?
|
21.10.2011 10:16 | |
/2 надо менять [x] На >> 1 Но только, если положительное.
|
Последние записи от Genzo
- Поиск файлов в системе.[AIR] (23.12.2011)
- Соревнование на быстроту алгоритмов (20.10.2011)
- Хранение Graphics (05.08.2011)