Zadaci

[CrniĐavo]

Једино што у рекурзивном позиву кошта више је отварање простора за нови позив. Административни обим је исти.

Ја те наводим да напишеш рекурзију, па је размотај на итеративно ако ти се игра. Ако нећеш, можеш да прескочиш тај корак.

Али појави се са кодом који ради.

Izgleda da radi

<?php

$arr = array(1, 2, 4, 2, 1, -5, 6, 2, 2, 3);

function solve($arr) {		
	$sum = 0;
		
	for ($i = 0; $i < count($arr); $i++) {				 	
		$maxLeft = ($i > 0) ? max(array_slice($arr, 0, $i)) : $arr[$i];				
		$maxRight = max(array_slice($arr, $i));									
		
		if ($arr[$i] < $maxLeft && $arr[$i] < $maxRight)
			$sum +=  min($maxLeft, $maxRight) - $arr[$i];			
	}	
	echo $sum;	
}
solve($arr);
?>

 

[Миша]

Aj' postavi svoj primer sa rekurzijom, posto sam slab sa njom totalno?

Није (вам) занимљиво ако дам код који се извршава. Рецимо да се ово већ довољно дуго вуче да би могао да иде опис. Џиз, дође ми да вас више не гњавим...

Основна идеја са врховима је да се нађу два највиша у целом низу (O(n)). Онда се обради све између њих (O(n)). Након тога се преостали делови низа (лево и десно од обрађеног дела) обраде на исти начин. У рекурзивној верзији то изгледа овако:

1. Метода добија низ (arr) и опсег индекса на којем треба да га обради (start / end, start <= end). На почетку важи start = 0, end = arr.len - 1. Метода такође на почетку игнорише случајеве када се одмах види да добијени опсег не може да има запремину. Нпр. start == end, start +1 == end.
2. Запремина volume за тај позив се поставља на нулу.
3. Нађу се прва два максимума himax и lomax. Сваки од њих може бити леви или десни. Нека је индекс левог lmaxi, а индекс десног rmaxi.
4. Сабере се сва запремина између њих и смести се у volume.
5. На променљиву volume се онда додају резултати позива solve(arr, start, lmaxi) и solve(arr, rmaxi, end).
6. Врати се вредност volume.

И меморијска и временска сложеност су O(n),

Итеративна варијанта ради исто, само што не користи рекурзију како би "паковала" оно што јој је преостало да обради, већ партиционише низ тако што одржава ред интервала које још није обишла и врши обраду све док је ред непразан. Измена није радикална, али претпоставио сам да је лакше прво написати рекурзивно па прерадити у итеративно решење.

Отворено питање је да ли алгоритам може да се унапреди тако да му треба мање од O(n) меморије...

 

[CrniĐavo]

Док чекамо да се неко јави на тај задатак, имам и следећи. Овако нешто бих можда дао на интервјуу. Требало би да је тривијалан за све који су радили са рачунарском графиком, али шта знам...

Дат је објекат геометријске фигуре, који садржи њене дужи. Транслација фигуре за вектор v је реализована тако што се итерира по дужима и за сваку дуж се обе њене тачке транслирају за вектор v, који није нула-вектор. Но, након обављене трансформације фигура није била транслирана за вектор v у границама разумних толеранција. Шта може бити грешка?

O kakvoj grešci je reč, ne kapiram?

 

[Миша]

Ето сада не морам да понављам питање. Хвала.

Ко је радио како треба са 3D графиком, знаће. Изгледа да је ипак добро питање за интервју (управо ниси прош`о).

 

[CrniĐavo]

Ето сада не морам да понављам питање. Хвала.

Ко је радио како треба са 3D графиком, знаће. Изгледа да је ипак добро питање за интервју (управо ниси прош`о).

Jedino ako greška nastaje usled rada sa floating-point brojevima.
Ne vidim šta bi drugo moglo biti problem.

 

[Миша]

Jedino ako greška nastaje usled rada sa floating-point brojevima.

Није то. Причаћемо овде за недељу дана.

 

[Миша]

Објашњење:
Низови дужи могу да се снимају тако што се одвојено сниме скуп тачака и скуп веза (дужи) међу њима. Дужи које деле исту крајњу тачку референцирају исти објекат у меморији. Ако се та тачка транслира једанпут за једну дуж и други пут за другу дуж, биће транслирана за дупло већи интензитет вектора од жељеног.

 

[CrniĐavo]

Дужи које деле исту крајњу тачку референцирају исти објекат у меморији.

Ovo uopšte ne mora da bude tako kako kažeš, već može svaka duž da ima svoju tačku, kao zaseban objekat.

 

[Миша]

Ovo uopšte ne mora da bude tako kako kažeš, već može svaka duž da ima svoju tačku, kao zaseban objekat.

Мора да буде када је премиса да то како би ти хтео да буде није тако.

Објашњење:
Низови дужи могу да се снимају тако што се одвојено сниме скуп тачака и скуп веза (дужи) међу њима.

 

[CrniĐavo]

Мора да буде када је премиса да то како би ти хтео да буде није тако.

Zašto?

 

[Миша]

Zašto?

Зато што не можеш да заобилазиш премису када негираш резултат. Прочитај опет текст задатка те решење и видећеш да се они уопште не баве другим решењима за снимање геометрије, већ траже једно на којем специфичан алгоритам неће радити.

 

[Wrong Turn]

Ma retko ko bi ti dao tacan odgovor na to, da se ne lazemo.

Pitanje je "Google Style"

 

[Миша]

Pitanje je "Google Style"

Хм, за гугл се спреми на питања о стратегијама аутоматског груписања (clustering) милијарди интернет чланака према њиховом садржају и осталим јавним метаподацима.

Без зеза.