Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > The way of improve

Буду выкладывать наработки в народ
Оценить эту запись

Соревнование на быстроту алгоритмов

Запись от Genzo размещена 20.10.2011 в 19:05
Обновил(-а) Genzo 21.10.2011 в 11:16

Уже есть подобная тема 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
Всего комментариев 10

Комментарии

Старый 20.10.2011 23:04 Dukobpa3 вне форума
Dukobpa3
 
Аватар для Dukobpa3
Как эта спираль будет выглядеть не с квадратом а прямоугольником?
Старый 20.10.2011 23:42 Котяра вне форума
Котяра
 
Аватар для Котяра
А судьи кто?
Какой бенчмарк?
Старый 21.10.2011 01:11 -De- вне форума
-De-
 
Аватар для -De-
А на практике такая задача встречалась?
Предлагаю такую: есть битмапа, на ней есть одна непрозрачная область. Надо обойти её по часовой стрелке. Т.е. на входе битмапДата, на выходе вектор/массив точек, принадлежащих обходу. Если непрозрачные куски касаются "углом", то это считается касанием и они считаются одним куском. Где первая точка обхода - не важно (но естессно рядом с непрозрачной областью).
Задачка тоже в принципе школьная, но встречается в практике.
Код AS3:
		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 01:21 AtomicFlasher вне форума
AtomicFlasher
Код AS3:
public function f(N:int, n:int):Point
{
	var p:Point = new Point((N-1)/2, (N-1)/2);
 
	var x:int = Math.floor(Math.sqrt(n + 1 / 4) - 1 / 2);
	p.x += (x%2) ? (x+1)/2 : -x/2
	p.y += (x%2) ? -(x+1)/2 : x/2;
 
	var d:int = n - x*(1+x);
	p.x += ((x%2) ? -1:1) * ((d < 1+x) ? 0:(d - (1+x)));
	p.y += ((x%2) ? 1:-1) * ((d < 1+x) ? d:(1+x));
 
	return p;
}
Старый 21.10.2011 03:09 Котяра вне форума
Котяра
 
Аватар для Котяра
/2 надо менять на *0.5
Старый 21.10.2011 08:00 iNils вне форума
iNils
 
Аватар для iNils
По моему, условие задачи не до конца продуманно. Как будет проходить спираль, если размер области будет 5 на 11?
Старый 21.10.2011 10:16 dimarik вне форума
dimarik
 
Аватар для dimarik
/2 надо менять [x] На >> 1 Но только, если положительное.
Старый 21.10.2011 10:49 crazyone вне форума
crazyone
 
Аватар для crazyone
Ага, а проверять на нечетность надо через (x&1), сразу посчитать (x+1), если оно столько раз используется, да и new Point(x,y) использовать дороже, чем {x,y} или [x,y].

А вобще - нужен судья с большим и толстым бенчмарком.
Старый 21.10.2011 11:16 Genzo вне форума
Genzo
 
Аватар для Genzo
Действительно извиняюсь, в торопяx задание накидывал, область соответственно NxN , N%2 = 1.
Судить не будем, просто время выполнения проверим и все - победит тот, чье время меньше.Естественно это будет зависеть и от машины на которой будет выполняться, но тут все таки главное креативность решения.
Старый 23.10.2011 00:36 Vektor вне форума
Vektor
 
Аватар для Vektor
А так, не быстрей будет?
Взял код AtomicFlasher.
Код AS3:
public function f(N:int, n:int):Point
{
        var nN=(N-1)*0.5
	var p:Point = new Point(nN, nN);
 
	var x:int = Math.floor(Math.sqrt(n + 0.25) - 0.5);
        var xX1 =(x+1)*0.5
        var xX =x*0.5
	p.x += (x%2) ? xX1 : -xX;
	p.y += (x%2) ? -xX1 : xX;
 
        var X1 = 1+x
	var d:int = n - x*X1;
	p.x += ((x%2) ? -1:1) * ((d < X1) ? 0:(d - X1));
	p.y += ((x%2) ? 1:-1) * ((d < X1) ? d:X1);
 
	return p;
}
 

 


Часовой пояс GMT +4, время: 20:11.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.