Как стать автором
Обновить
365
0
Андрей @Mrrl

Заводчик кардиганов

Отправить сообщение
Разные бывают ситуации. Иногда этих 20 строк приходится ждать два года, а то и больше. Другое дело, что значит, без них можно было обойтись, и были дела поважнее.
В условии не сказано, что дерево сбалансированно.
Комментарий был изменён.
Неограниченна.
Тогда при чём здесь вообще программирование? Рисуем на бумажке карту и кодируем:
  int dx=abs(targetX-sourceX);  
  int dy=abs(targetY-sourceY);
  int p=max((dx+1)/2,max((dy+1)/2,(dx+dy+2)/3);
  if((p+dx+dy)%2!=0) p++;
  if(dx+dy==1 || (dx==2 && dy==2)) p+=2;
  return p;
А доска ограничена или бесконечна?
Лучше сразу число ходов для достижения клетки.
Зачем? В кратчайшем маршруте циклов не будет.
Мне тоже стыдно, что не заметил сразу. Хотя на рисунке чётко видно, что из очередной строчки можно получить следующую.
Без рекурсии и за О(1) дополнительной памяти:
void Connect(Node x){
    while(x!=null){
        Node newStart=null,y=null;
        while(x!=null){
            if(x.left!=null) y=addNode(x.left,y,ref newStart);
            if(x.right!=null) y=addNode(x.right,y,ref newStart);
            x=x.neighbour;
        }
        x=newStart;
    }
}
Node addNode(Node x,Node y,ref Node start){
    return start==null ? start=x : y.neighbour=x; 
}
Чем-то похоже на первое решение:
static void Connect(Node x){
    Connect(x,new List<Node>(),0);
}
static void Connect(Node x,List<Node> rightLine,int level){
    if(x==null) return;
    if(level==rightLine.Count){
        rightLine.Add(x);
    }else{
        rightLine[level].neighbor=x;
        rightLine[level]=x;
    }
    Connect(x.left,rightLine,level+1);
    Connect(x.right,rightLine,level+1);
}

Сложность O(size), память O(depth).
Смысла в задаче определённо стало бы меньше. Если надо просто что-то сделать с этими диаметрами, можно было бы спросить площадь кольца, ограниченного окружностями, или объём усечённого конуса, нижнее основание которого описано вокруг нижнего основания призмы, а верхнее — вписано в верхнее основание.
А факт обнаружили бы просто. Зачем-нибудь получив диаметр вписанной окружности a+b-sqrt(a^2+b^2), заметили бы, что sqrt(a^2+b^2) — это как раз диаметр описанного, а значит, их сумма равна a+b.
То есть, нужны четыре факта:
— гипотенуза является диаметром описанной окружности;
— отрезки касательных, опущенных из одной точки, равны;
— касательная перпендикулярна радиусу;
— у квадрата стороны равны.
И вообще никаких формул. Красиво!
Если бы учителя делали как вы предлагаете — сначала давали задачу, а потом бы объясняли, что в ней надо делать, отвечая на вопросы ученика (причем где гарантия-то, что эти вопросы у него вообще возникнут?) — да, была бы каша, но ведь никто так не делает, все делают наоборот, сначала дают всю информацию, а потом уже на задачах ее обкатывают. Я побывал как-то раз на астрономических сборах перед всероссийской олимпиадой по астрономии и физике космоса, где пытались решать олимпиадные задачи, используя их точно таким образом, как вы предлагаете...

Для подготовки к олимпиадам высокого уровня это совершенно естественный подход. Чтобы сначала ученик примерил задачу к своей картине мира, обнаружил, что для решения чего-то не хватает — и после этого объяснить ему, каким может быть это «что-то». Или чтобы он сумел найти нужный приём — а потом объяснить его более системно. В конце концов, больше половины мастерства олимпиадника — суметь увидеть способ решения совершенно незнакомой задачи.
Кажется, это называется «кроссовер». hpmor.ru/book/1/64, самый конец.
Как спирт в бочке мог остаться 100-процентным? Разве он не впитает тут же 2% влаги?
Они бы отлично знали многомерную геометрию (как и мы) — она бы использовалась при анализе звуковых сигналов, что для них жизненно важно. И при анализе данных — PCA и прочие прелести работают в многомерном пространстве, и им плевать на число геометрических измерений Вселенной.
Например, чтобы сделать компьютеры компактнее, быстрее, мощнее. Кто знает, к чему приведёт какое новое открытие.
Примерно так.
	.global find12
find12:
	AND	.L2	B4,3,B2
||	SHR	.S1X	B4,2,A2
||	ADD	.D2XA4,4,B4
||	ZERO	.L1	A0
||	ZERO	.S2	B0
||	MV	.D1	A6,A8

	ZERO	.L2	B2
||	SUB	.L1	A2,2,A2
||	MV	.D2XA6,B8
||	MVC             CSR,B9
	AND             B9,-2,B1
	MVC             B1,CSR
||	LDW	.D1	*A4++[2],A5  ;; [0@0]
||	LDW	.D2	*B4++[2],B5  ;; [0@0]

	NOP	2

	LDW	.D1	*A4++[2],A5  ;; [0@3]
||	LDW	.D2	*B4++[2],B5  ;; [0@3]

	NOP

	CMPEQ	.L1	A5,A8,A1	 ;; [5@0]
||	SHR	.S1	A5,16,A7	 ;; [5@0]

	LDW	.D1	*A4++[2],A5  ;; [0@6]
||	LDW	.D2	*B4++[2],B5  ;; [0@6]
||	ADD	.S1	A0,A1,A0     ;; [6@0]
||	B	.S2	_F12LOOP

	SUB	.D2	B5,B8,B1	 ;; [7@0]
||	SHL	.S1X	B5,16,A6	 ;; [7@0]
||	SHR	.S2	B5,16,B7	 ;; [7@0]
||	ZERO	.L2	B6			 ;; [7@0]
|| [A2]	SUB	.D1	A2,1,A2		 ;; [7@0]

	CMPEQ	.L1	A5,A8,A1	 ;; [5]
||	SHL	.S2X	A5,16,B6	 ;; [5]
||	SHR	.S1	A5,16,A7	 ;; [5]
|| [!B1] ADD	.L2	B0,1,B0	 	 ;; [8]
||	ADD	.D1	A6,A7,A6	 ;; [8]
||	ADD	.D2	B2,B6,B2	 ;; [8]

_F12LOOP:
	LDW	.D1	*A4++[2],A5  ;; [0]
||	LDW	.D2	*B4++[2],B5  ;; [0]
||	ADD	.S1	A0,A1,A0     ;; [6]
||	ADD	.L2	B6,B7,B6     ;; [6]
|| 	CMPEQ	.L1	A6,A8,A1	 ;; [9]
|| [A2]	B	.S2	_F12LOOP	 ;; [9]

	SUB	.D2	B5,B8,B1	 ;; [7]
||	SHL	.S1X	B5,16,A6	 ;; [7]
||	SHR	.S2	B5,16,B7	 ;; [7]
||	CMPEQ	.L2	B6,B8,B6	 ;; [7]
|| [A2]	SUB	.D1	A2,1,A2		 ;; [7]
||	ADD	.L1	A0,A1,A0	 ;; [10]

	CMPEQ	.L1	A5,A8,A1	 ;; [5]
||	SHL	.S2X	A5,16,B6	 ;; [5]
||	SHR	.S1	A5,16,A7	 ;; [5]
|| [!B1] ADD	.L2	B0,1,B0	 	 ;; [8]
||	ADD	.D1	A6,A7,A6	 ;; [8]
||	ADD	.D2	B2,B6,B2	 ;; [8]

	;; end loop

	B	.S2	B3
   	CMPEQ	.L1	A6,A8,A1	 ;; [9]
	ADD	.L2	B0,B2,B0
  	ADD	.L1	A0,A1,A0	 ;; [10]
	ADD	.L1X	A0,B0,A4
	MVC	.S2	B9,CSR


3 такта на 4 полуслова.
Правда, этот код работает только для массивов длиной, кратной 4 и не меньше 12, но добавить дополнительную обработку для коротких массивов — дело техники.
Серьёзная задача. Похоже, что можно упаковать обработку 8 элементов в 6 тактов. Но это будет очень непросто.
МОРФЕУС: А где ты ходил в школу, Нео?
(Пауза)
НЕО: …В Матрице.
МОРФЕУС: Машины придумали изящную ложь.
(Пауза)
НЕО (робко): А могу я где-нибудь взять учебник по настоящей физике?
МОРФЕУС: Такой вещи не существует, Нео. Вселенная не подчиняется математическим законам.

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Дата рождения
Зарегистрирован
Активность