тази задачка е доста проста, ама като ти виси потенциалния бъдещ шеф на главата и очаква да отговориш не сега ами веднага и става доста сложна :(


Двама души играят игра. Има (крайна) кръгла маса и безкраен брой бутилки. Двамата се редуват да поставят по една бутилка на масата. Победител е този който постави последната бутилка. Бутилките се поставят винаги по един и същ начин, без да се изместват вече поставените бутилки.

Ако ти си пръв на ход, как можеш да гарантираш че ще си победител?

ако масата побира нечетен брой бутилки.

-----------------------
гърбавия, ковчег ще го изправи

хм. предвид че масата е кръгла, ако първият постави бутилка точно в центъра й, това означава, че където и да постави бутилка вторият играч, първият ще може да постави бутилка "централно симетрично" (тоест симетрично спрямо центъра на окръжността (масата)).

"ако първият постави бутилка точно в центъра й" - ama ti ot kade znaesh kade e To4no centara i :) Na pove4eto masi ne e beljazan, pak i sled tolko izprazneni butilki ste e trudno da se uceli ..

maitapat na strana, no vie mislite li 4e podobni zada4i sa podhodjasti za vhodjast test za rabota? Ne e li malko na kasmet i osven tova mnogo logi4eski zada4i sa tipizirani i njakoi prosto mogat da si znajat otgovorite.
Tova ima li go na testovete v serioznite kompanii (bjah 4uval za MS)?

ako postavim edna v centara, do neja ste mojem da doprem oste 6 (zastoto sa s ednakav diamera). Posle e po slojno no vse ste sa 4eten broi, + centara = ne4eten
ako simetri4no dublirame hodovete bez da zapalvame na max masata ne e jasno kolko ste postavim no otnovo ste sa 4eten broi (+ centara = ne4eten)

В отговор на:

---

maitapat na strana, no vie mislite li 4e podobni zada4i sa podhodjasti za vhodjast test za rabota?

---

ами не можеш да гарантираш - пример масата е широка колкото едната страна или диаметъра на една бутилка а масата събира между 2.5 и 3 бутилки - каквото и да правиш втория ще си постави бутилката и няма да има място за трета. В смисъл трябва обезателно да се дефинира и съотношението между площта на бутилките и масата както и някаква минимална площ.

pravilno! zatova vupreki che ne ia reshih me vzeha ;)

Хващам бутилка и я чупя в главата на опонента. Хващам бутилка и я чупя в главата на опонента. Хващам бутилка и я чупя в главата на опонента... И така докато не остана единствен претендент за победител. Бутилките не могат да свършат, щото са безкраен брой по условие.

Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

Честито! Утре те хващам на ICQ-то да се похвалиш повече .

--
"Agile is a mindset, not a set of practices, rules, or tools."
Tom Poppendieck

Chakai malko (izwini me za latinicata - pod Windows sum), no...

безкраен брой бутилки. i Победител е този който постави последната бутилка. nekaksi ne se wurzwat... (ne sum chel drugite otgovori, tuj kato zadachata mozhe da se okazhe interesna).

Bravo Purist, pozdravlenia zqa uspeha! Kakvi drugi zadachi ti dadoha?

потърсих из архивите, но не открих мрънкане по тема като "ако аз наемам хора, какви конкретни задачи ще им дам, какво конкретно бих ги питал и какво бих искал да узная за тях"; (най-близкото до това ми се стори не по-малко задълбочената отколкото интригуваща дискусия по отношение на запетайките).
мнения?

Не съм съгласен... нима не могат да съществуват маси които да побират само (точно) 1, 2, 3, 4 и т.н. бутилки? За всяко цяло, неотрицателно число (без значение дали е четно или нечетно) съществуват кръгли маси, които да поберат толкова, но не повече на брой бутилки! Или може и да не важи за всяко такова число, но важното е, че съществуват и четни, и нечетни такива... (егати! звуча като математик!)

Ако от това, дали ще решиш тази задача, определят дали ще те вземат на работа... хммм ... струва ми се меко казано несериозно.. Ама може би целта на задачата е да те видят как ще реагираш в такава ситуация?!

Сега ще почвам да си търся работа, та да видим на какво ще попадам...:))

накратко: още мисля, че най-важното е да се опознае кандидата за работа - и технически и като човек колкото се може повече. Техническата част не трябва да превъзхожда другата. Бих искал да видя код. Не глупава задача в стил "напишете функция дето да обхожда свързан списък" ами нещо по-голямо, където да се види как човека се справя със сложността.

Защо не пуснеш нова тема сигурно и другите ще се включат?

--
"Agile is a mindset, not a set of practices, rules, or tools."
Tom Poppendieck

Впрочем разсъжденията ми не са съвсем правилни, ама няма значение... все пак не можеш да си гарантираш победа, освен в някои много частни случаи...

Безкраен брой бутилки са го казали само за да дефинират че победител не може да се излъчи като "свършат" бутилките и затова някой е оставил последната, а може да се излъчи победител само като се "запълни" масата.

А и отговора вече го дадоха -
започващия 1-ви поставя бутилка в центъра, като след това "повтаря" всеки ход на противника като поставя бутилката симпетрично на масата спрямо центъра. Това гарантира че ако 2-рия има къде да постави бутилка - че има и 1-вия къде, и тъй като масата е крайна, "запълването" на масата че завърши когато 1-вя постави н-тата бутилка, в отговор на 2рия, и няма повече нясто.

Estestveno che mozesh !!! Simple Math !!!!

1. Slagash v centyra - ako masata sybira pone edna butilka mozesh !!!
2. Toi slaga niakude
3. Ti slagash simetrichno spriamo centyra

sys elementarna indukcia mozesh da vidish che ako toi moze da slozi niakude butilka to simetrichnoto miasto e free.

i ne zabraviai che masata e krygla vypreki che tova vazi i za masa koiato e pravoygylnik
Toest za vsiaka figura koiato e simetrichnia spriamo edna tochka toest centyra si !!!

Обръщаш кръглата маса на една страна, като я придържаш ако се налага.
Поставяш една бутилка точно отгоре, в точката в която има водоравна допирателна.
Това е първата и последна бутилка.

неможе да се каже какво значи "побира". Колко бутилки ще се поберат зависи от това как играят опонентите.

И аз предполагах че става дума не за "свършване на бутилките" а за запълване на "масата". 10-15 минути които си дадох да реша задачата не се сетих, и я казах на един колега - и той ми даде същия отговор като твоя. Хитро ;)

първо, що за задача ще е, ако става дума за свършване на бутиликте?
и второ - като я реших за 2 минути - какво следва - че съм гениален ли?????
айде си заврете тъпите задачи да не казвам къде

Tova beshe prosto otgovor na kokretnia vapros, 4e s butilka v centara, edna masa napalnena na max pobira ne4eten broi butilki
a pobeda se garantira kakto njakade ve4e go bjaha objasnili

Да предположим, че сложа първата бутилка в центъра. Масата побира общо 7 бутилки... Слагаме още 4, той е на ред. Ясно е, че по принцип ще има място за още две. Но защо той да слага бутилката така, че да има място и за теб накрая. Ако си сложи бутилката посредата на свободното място, ти няма да можеш да сложиш нищо после (без да разместваш)

a ako masata ima kraka ;)

Abe az da si te tresna s edna butilka za vseki sluchai, pyk da vidim...

Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

Поставяш първата в центъра и след това играеш симетрично (централна симетрия).

Е, ако промениш формата на масата, то задачата се превръща в адски трудна

Здрасти, ето ви и един brainteaser от мойто интервю:

Имате array of integers - всякакви положителни, отрицателни и най-важното - много големи по стойност (близо до границите на INT_MAX и INT_MIN за 32- и 64- или 128- битови и всякакви други машини. Задачата е да се намери средната стойност на масива от числа. Звучи просто, да, ама не - като тръгнеш да събираш числата и да делиш на броя им - надвишаваш границите и няма къде да побереш резултата от сумирането.... Всяка логика за работа с големи числа, включително представяне на числата със string и писане на алгоритми за събиране - отпадат - не се приемат. Като първа стъпка може да се подскаже: сортиране на масива. Ами после? Как да намерим средната стойност на неговите числа?

Ами... логическо погледнато в общия случай на масиви би трябвало да е в средата на масива, макар че много ме съмнява да е толкова елементарно.

Съдържаниет е скрито
Влезте за да го видите

броиш колко са еднаквите бройки от всеки различен елемент и си преобразуваш леко формулата за ср. аритм.

а за Лупи - това твойто се нарича медиана и е друго нещо.

Да - можем да приемем, че стойността на средата на масива след сортиране е най-близка до действителната средна стойност. Ами сега - посоката на мисли е правилна, но се иска да намерим действителната средна стойност. Обърнете внимание - самите числа в масива не надхвърлят минималния/максималния обхват - проблема се появява, когато започнат да се сумират...(ощв едно подсказване). Задачата е много приложима там където се изчисляват контролни CRS суми на пакети данни, които се предават по някаква мрежа.

Примерни масиви:
(6678912, 678965, 7958439, 8698548, 9877765)
(-100000, 1, 3, 999999)

Премахването на повтарящите се е много добра идея, още повече, че след сортиране те са един до друг и с едно минаване ще се свърши работа. Но това все още не решава проблема със overflow/underflow на сумата на останалите елементи от масива. Да речем, чв масива няма повтарящи се елементи...

ако щете вярвайте , ако щете недейте. това наистина е задача за 4-ти клас. падала се е на конкурс/олимпиада използва се централна симетрия като първата бутилна се поставя в пресечната точка на диагоналите.

niama li da stane ako normalizirame dannite - naprimer ot vsichki izvadim polovinata na nai-goliamoto chislo - po-tozi nachin kato sumirame niama da ima overflow i kato poluchim srednata stoinost kam neia shte dobavim chisloto, koeto sme izvadili i shte poluchim realnoto goliamo chislo za srednata stoinost.

I kyde sa diagonalite na kryglata masa?

Ето едно решение

За примера нека общият брой е 3

Avr(a,b,c)=(a+b+c)/3=a/3+b/3+c/3

Нека а= 3m+s
b=3n+q
c=3k+r
s,q,r са остатъците при делението на броя елементи в случая 3, а m,n,k са целите части при делението

Avr(a,b,c) = (m+n+k)+ (s+q+r)/3

Ако не бъркам програмно ще е нещо от сорта на:

Avr (a,b,c)= a div 3+ b div 3 +c div 3 + (a mod 3 + b mod 3 + c mod3)/3

Като сбора (m+n+k) < MAX_INT, както и (s+q+r)<MAX_INT

Това решение няма да работи, ако размера на масива също е около MAX_INT

Поздрави

Т-о-п-л-о! Ама направо горещо!!! Браво прякор!!! Какво ще кажеш ако вместо половината на най-голямото извадим стойността на средното (медиума) на масива?

Ami primerno za masiva:
{32765, 32764,0,0,-32765}

Njama da ti svyrshi nikakva rabota

ми първо отрицателните няма ли да се оплескат.
и след това защо да няма оверфлов?
ако имаш MAX_INT, MAX_INT, MAX_INT,
ще събираш 3* (МАX_INT/2), което пак отива при коня...

Да, прав си - от изваждане на 0 няма файда. Да, но ако нулата е в краищата ситуацията е аналогична. Виж например масива: (-32765, -32764, -1, 0, 0) - изобщо простата задача за намиране на средна стойност на масив от числа се оказва доста сложно нещо !

Mojem da go napravim kakto se pravi po uchebnik - istinska normalizacia, koiato zapazva statisticheskite harakteristiki na dannite.

Eto edna formula, koiato preobrazuva vhodnite danni v interval -1, 1 , kato se zapazvat statisticheskite harakteristiki na chislovia red(otnosheniata mejdu goleminite im). pn = 2*(p-minp)/(maxp-minp) - 1; tyk minp e minimalnoto chislo, maxp e maximalnoto , pn e rezultatnia normaliziran vector. Tova sam go vzel ot MATLAB. Eto podrobno opisanie kakvo pravi

PREMNMX Preprocesses data so that minimum is -1 and maximum is 1.

PREMNMX(P,T) takes these inputs,
P - RxQ matrix of input (column) vectors.
T - SxQ matrix of target vectors.
and returns,
PN - RxQ matrix of normalized input vectors
MINP- Rx1 vector containing minimums for each P
MAXP- Rx1 vector containing maximums for each P
TN - SxQ matrix of normalized target vectors
MINT- Sx1 vector containing minimums for each T
MAXT- Sx1 vector containing maximums for each T

sled kato go normalizirame po tozi nachin si pravim suma i delim na vsichki i namirame srednata stoinost. No tova e srednata stoinost na normaliziranite(namalenite) chisla - za da ia preobrazuvame obratno v goliamo chislo triabva da izvarshim obratnia proces - denormalizacia sas dannnite polucheni ot normalizaciata. Eto formulata p = 0.5(pn+1)*(maxp-minp) + minp;

POSTMNMX Postprocesses data which has been preprocessed by PREMNMX.

POSTMNMX takes these inputs,
PN - RxQ matrix of normalized input vectors
MINP- Rx1 vector containing minimums for each P
MAXP- Rx1 vector containing maximums for each P
TN - SxQ matrix of normalized target vectors
MINT- Sx1 vector containing minimums for each T
MAXT- Sx1 vector containing maximums for each T
and returns,
P - RxQ matrix of input (column) vectors.
T - SxQ matrix of target vectors.


Sled kato izvarshim denormalizacia poluchavame tova, koeto ni triabva - srednata stoinost v goliamo chislo.

Първо - сортираме масива. После: ако от най-големият елемент извадим единица и я прибавим към най-малкия, средното остава същото. Използваме тази идея за да получим масив от еднакви или различаващи сe с единица числа, т.е. от вида {k,...,k} или {k,...,k,k+1,...,k+1}.

В първият случай средното е k, а във втория - цяла част k и дробна част (ако k се повтаря n пъти, а k+1 се повтаря m пъти) - m/(n+m).

Значи, правим цикъл, като на всяка стъпка: първо - сортираме масива; второ - проверяваме дали е от вида, който ни трябва и ако не е - от първия елемент вадим 1 и прибавяме към последния, от втория вадим 1 и прибавяме към предпоследния и т.н.

Проверката за края на вложения цикъл е: ако трябва от х да извадим едно, а към у да прибавим едно, правим това само ако х-1 е по-голямо от у, иначе прекратяваме вложения цикъл и се връщаме към първия - сортиране и т.н.

Не знам дали го обясних разбираемо ...

О-о-о-оранжеви китари оранжево звънят!

<<
Първо - сортираме масива. После: ако от най-големият елемент извадим единица и я прибавим към най-малкия, средното остава същото. Използваме тази идея за да получим масив от еднакви или различаващи сe с единица числа, т.е. от вида {k,...,k} или {k,...,k,k+1,...,k+1}.

В първият случай средното е k, а във втория - цяла част k и дробна част (ако k се повтаря n пъти, а k+1 се повтаря m пъти) - m/(n+m).
>>

Bravo Zipreks!!! Mnogo dobro reshenie! Bi li obiasnil kak stigash do nego. Po - podrobno me interesuva kak stigash do izvoda che drobnata chiast triabva da e m/(n+m)

То лекар-програмист е почти като жена програмист.
Ама психоложка програмистка ?
:))))))))
Дип че не се връзва на простотийки :)))))

Bеer? Moooorrre?

Не знам за вас но ако на мен ми се наложи да пиша подобно нещо вместо да пиша вложени цикли и на всяка стъпка да сортирам масива да взимам едно от първия да го прибавям към последния , от втория към предпоследния и т.н. бих постъпил по следния начин :

#include "stafx.h"
int (int argc,char*argv[])

{
const int EL_COUNT = 11 ;
short Arr[EL_COUNT] = {31355,152,-8794,6374,0,-24878,5422,147,4,29387,7765} ;
double AvgRes = 0.0 ;
const double factor = 1000.0 ;

for (int I = 0 ; I < EL_COUNT ;I++)
AvgRes += Arr / factor ;
AvgRes = (AvgRes / EL_COUNT) * factor ;
printf("Srednata stoinost e - %f\n"AvgRes);
return 0 ;
}

Това работи и с __int64 масиви , освен това можете да си поиграете и с фактора за деление.

Малка поправка на цикъла - заменям I с II (познайте защо)

for (int II = 0 ; II < EL_COUNT ;II++)
AvgRes += Arr[II] / factor ;

Това е все едно да ти поставят задача да намериш средно аритметично на числата 250 и 200 като използваш 8 битова аритметика:
1.(250+200)/2=250/2+200/2=125+100=225
или
2. (250+200)/2= (250-128 +128 +200 -128+128)/2= (122+72)/2 +128=97+128=225

Или опростено за по бърза обработка се намират всички числа >MAX/2 от
тях се вади MAX/2 и след осредняването им се прибавя МАX/2. За отрицателни числа действията са аналогични.

Та както по-горе попитах, какво ще стане, ако числата са не 2, а примерно 4?

(пак препълване)

kato sa 4 delish na 4

и после?

После нещата са прости и вече ги обясниха. След сортиране на n числа:
An,An-1...A0, където Аn e най-голямото А0 най-малкото число, започва
осредняване на числата по двойки за по-голяма скорост на изпълнение :
Аn=A0=(Аn+A0)/2 ; An-1=A1=(An-1 + A1)/2 и т.н. където има препълване при сумиране на две числа, се използа описания алгоритъм за избягването му.
Всичко се повтаря докато разликата между най-голямото осреднено (Амax ) и най-малкото осреднено (Амin) число стане Аmax-Amin<MAXNUMBER/n .
Изваждаме от всички числа Аmin и с остатъците Оi пресмятаме :
RES=Amin+(Оn + ...О1)/n .
Възможно е да се доведе и до Аmax-Amin=1, както споменаха по-горе.
Ako се получи Аmax-Amin=0 още по добре

аа аз помислих, че ще се осредняват по повече от 2 числа едновременно по същия начин (с - 128)...

за какви диагонали в окръжност става въпрос?! пресечна точка на диагонали в окръжност :) 11 клас съм вече в математическа гимназия и досега пресечна точка на диагонали в окръжност не съм чувал :) центъра на окръжността и от там централна симетрия :)

biro, ti pa kato nema kvo da kajesh i toku iztrysish nqkoiq glupost, are da ne kazvam tuka mujete kvi izcepki sa napravili, da ne kazvam i kyv kolaga programist imam i kvi gi drynka toim, shtoto ne iskam da vi zaboli korema ot smqh ;)

Абе идеята много си я бива и е доста универсална! Браво SIR!!!
Идеята на Зимпрекса също е много хитра, но това сортиране на масива в цикъла, докато изравняваш с +1/-1 елементите яде много - О(n2) не ти мърда!

Абе изобщо много ме кефи факта, че в тая държава има такива умни глави (на фона на мизерията и простотията навсякъде). Може малко да са, ама ги има! Дано да дочакаме времето, когато ще дават луди пари за такива идеи и още повече, някой наистина да се възползва от тях. То и оня до нас 'вратото' може да си купи идеята и определвно да му върши работа в бизнеса с тировете, ама кат' нема акъл кво да прави с тва дет си го е купил...е-е-е-х, успех колеги ! и честит Национален празник!!!

Eto kakwo me pitaha mene:

"Suppose you're locked in a building and can't leave. How many ways can you think of to measure the exterior temperature? "

Waprosa se zadawa s cel da si widi kolko kandidata e problem solwer i kolkoto poweche idei se dadat, tolkowa poweche raste shansa da go wzemat na rabota.
Waprosa e ot realno interwiew za progammers. Postoqnno se stesnqwat iziskwaniata, dokato nakraia kandidata kaje 'give up'. Towa obache ne triabwa da se sluchwa. Naprimer, wednaga nqkoi kazwa - ami s termomer, da ama te ti wikat - ami nqmash nikakwi phisical devices wytre (shtoto nqkoi moje i po internet da prochete ;-)), ta, haide da zapochwame...

>>Абе изобщо много ме кефи факта, че в тая държава има такива умни глави
Решаването на тази задачка не те прави "умна глава". Умната глава ще е този, който вземе решението на тази иначе съвсем безсмислена задачка и я продаде за $1М, купи си къща с басейн и ебе манекенки.

>>Дано да дочакаме времето, когато ще дават луди пари за такива идеи
Ето, това е българския манталитет. "Да дочакаме", "Ще даде пари" ... Да ти кажа ли нещо много изненадващо? Няма да дочакаш някой да ти даде пари. Между другото това важи не само за България.

Може би сам трябва да се опиташ да си ги заработиш?

Един от най-добрите програмисти които познавам е философ :-)


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

мога да се обадя по gsm-а :) това брои ли си?!

...или да се изпикая в чашка, за да знам приблизително каква е температурата на течността. и после да засека за колко време ще замръзне :)

poglajdam prez prozoreca, obasho vzeto moga da precenq dali e nad 0 ili pod 0 temperaturata. ako e nad 0 slagam v hladilnika chasha voda s opredelena vmestimost i q 4akam da znamryzne /ako ima hladilnik efstefstfeno/, izvajdam leda otvyn i zasicham za kolko vreme shte se raztopi /ako imam s kakvo da zaseka/, vadq uchebnika po fizika i smqtam po formula za otdavane na toplina ili neshto takova. Ako temperaturata e pod 0, pravq obratnoto, izvajdam chasha s nagrqta do kipene voda i gledam za kolko vreme shte zamryzne. ako nqmam nagrevatel moga da probvam da q zagreq do telesna temperatura, koqto obshto vzeto e izvestna, oba4e ako nqmam hladilnik... variant dve pak s chashata voda na koqto i znam temperaturata, izvajdam q navyn i merq kolko se e razshirila/svila pod vyzdeistvie na vynshnata temperatura i pak vadq uchebnika po fizika za da smetna. ;)

ee izprevari me, az dokato pisha ti ve4e si go izmislil ;) ama ne znaesh kakva e temperaturata na tova deto si go izpikal ;) pyk i zashto trqbva da zamryzne moje da e toplo navyn ;)

Questor, ами може и гол да се съблечеш по между другото. Ето каква ми е идеята:
Значи събличаш се. Усещането за конфортност е да речем 18 градуса стайна температура. Ако усещаш топло/топлина, значи темперарурата е по-висока. Ако усещаш, че ти е студено - значи температурата в стаята е под 18 градуса. Така-а-а. Обаче въпроса е за температурата навън. Значи това дотука беше за да си направя един вид скала - откъде накъде да започна меренето, като зная, че температурата в стаята е обикновено по-висока от тази навън. (при голяма жега е обратното). Има и други видове скали - например ако вънка има сняг - скалата се прави около 0-та. Така - дотук: Гол съм и съм сам в стаята. Ако ми е студено трябва да измеря 'колко' ми е студено, ако ми е топло - пак. Имам идеи: 1) да се потопя във вода (топла и студена) и като изляза да измеря какво усещам. Още, мога да се покажа навън през прозореца и пак да измеря - колко по-топло или колко по-студено е навън от стаята. Ако отворя прозореца мога да видя накъде ще стане течение - и какъв въздух ще влезе и т.н. Отивам да си мисля, но междувременно ще се облека , за да не настина !

Abe iz4etoh celia thread za tazi zada4ka i ne moga da poviarvam 4e nikoi ne vijda o4evidnoto re6enie

Avr = (a1+a2+....+an)/n = a1/n + a2/n + ....+ an/n
znaem n - broia na elementite
prepolagam 4e broiat n e ot sa6tia tip kakto elementite ako ne prosto 6te se re6i na 4asti i predpolagam 4e elementite sa ot tip int (32, 64, 128, 256, ....ili kakvito i da sa)

Avr = 0;
for(int i = 0; i < n; i++) Avr = Avr + arr/n;
i tova e
srednata stoinost e vinagi v intervala m/u nai-goliamto i nai-malkoto 4islo v masiva za tova i Avr = Avr + arr/n; nikoga niama da izlezne ot nego

Sury, be6e nai-blizo do tova re6enie ne razbrah samo za kakvo mu biaha tia Factor-i

Ти пробва ли го?!? Говорим за ЦЕЛИ числа. Вероятността да получиш отговор 0 нараства с n. 1/3 е 0, не знаеш ли?


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

double Avr=0;
for (int i=0; i<n; i++) Avr+=(double)arr/n;


______________

Ако искаш изненада, защо просто не се влюбиш?

How to Measure a Building with a Barometer:

Take the barometer to the top of the building, attach a long rope to it, lower the
barometer to the street and then bring it up, measuring the length of the rope.
The length of the rope is the height of the building.

Take the barometer and begin to walk up the stairs. As you climb the stairs, mark
off the length of the barometer along the wall. Then count the number of marks,
and this will give you the height of the building in barometer units.

The Pressure Method: Measure the air pressure at the bottom and top of the building, then compute the height of the building from the pressure difference. This is the only method that actually uses the barometer for its designed purpose of measuring air pressure. Although aircraft altimeters often work by this principle, it is one of the least accurate methods for measuring a building's height.

The Pendulum Method: Go onto the building's roof, and lower the barometer on a string until it almost reaches the ground. Swing the barometer and measure the pendulum's period of oscillation. From this the length of the pendulum, and hence the building, can be calculated.

The Avarice Method: Pawn the barometer to raise seed money for a chain letter campaign. Then stack the currency thus obtained against the building, measuring it in units of currency thickness. No comment on how to stay ahead of the police long enough to measure the building.

The Mafia Method: Extort the building's height from the superintendent, using the barometer as a weapon. The Ballistic Method: Fire the barometer from ground level with a mortar, just high enough to reach the top of the building. You may need to take some ranging shots to get the explosive charge and firing elevation just right. A table of standard ballistic calculations will then yield the height reached
by the projectile.

The Paperweight Method: Use the barometer as a paperweight while looking over the building plans.

The Sonic Method: Drop the barometer from the top of the building, and time the interval between seeing the barometer hit the ground and hearing it. For practical distances, the sight will be instantaneous, and the sound will travel at the speed of sound (1150 feet/second at standard temperature-pressure and mean sea level), giving the height.

The Reflective Method: Use the glass face of the barometer as a mirror and time the interval it takes light to traverse the round trip between the top of the building and the ground. Since the speed of light is a known quantity, the distance can be calculated.

The Mercantile Method: Sell the barometer, and buy some proper equipment.
The Analog Method: Attach the barometer to a string, wind the string around the shaft of a small generator, and measure the amount of electrical energy produced as the barometer falls from the top of the building to the ground. The generated energy is proportionate to the number of revolutions of the shaft, and hence the distance to the ground.

The Trigonometric Method: Pick a spot on the ground a known distance from the building, go to the top of the building with the barometer and a protractor level, and wait for the sun to reach the horizon. Then, using the barometer as a mirror, aim a spot of sunlight at the place you previously picked and measure the angle of the mirror with the level. Use trigonometry to calculate the building's height.

The Proportion Method: Measure the height of the barometer. Bring a friend and a tape measure. Stand at a known distance from the building and sight past the barometer to the building. Move the barometer toward or away from you until the top and bottom of the barometer line up with the top and bottom of the building. Then have your friend measure the distance from the barometer to your eye.
Compute the building height by proportion.

The Photographic Method: Set up a tripod with a camera at a known distance from the building. Hold the barometer a known distance from the camera and take a picture. From the relative heights of the barometer and the building in the picture, you can compute the height of the building.

The Gravitational Method I: Suspend the barometer from a yard of string. Measure the oscillation period of the pendulum thus formed at the top and bottom of the building. Compute the building's height from the difference in gravitational acceleration.

The Gravitational Method II: Weigh the barometer at the top and bottom of the building with a spring balance (a beam balance won't work for this!). Differences in the readings will be due to the different gravitational acceleration, due to the differing distances from Earth. (A reader tells me that the Lacoste Romberg gravimeter provides a practical way of getting the required accuracy.) Compute the
building's height from the two measurements.

Циничното отношение не ти отива. Пък и няма смисъл да се опитваш да образоваш хората. Много хора, тук, на този форум, сме по-цинични и от тебе, ама не е учтиво да се демонстрира.
Дали някой ще даде, или няма да даде пари на някого не е твоя работа. И няма нищо общо с интелигентност и т.н.т. Ако човек се справя с такива проблеми значи е вероятно да има нещо в главата. Това е. А за тези дето ебат манекенки -- незнам. Манекенките на са добра база за сравнение за "умност".

Я вземи прочети малко теорийка, стига с това писане на HTML! Какви са тези double?! Няма да получиш точен отговор! Освен това, решението ти противоречи на условието на задачата (иначе що да ползваме double, а не long long (или както го наричат в БГ: __int64)).

И като имаш double що не така:

double Avr=0; 

for (int j=0; j<n; j++)

   Avr+=arr[j];

Avr /= n;

Така не е точно, защото когато сумата ти стане прекалено голяма, ще започнеш да губиш от ниските разреди.
С Arr+=(double)arr/n; натрупаната грешка ще е пренебрежимо малка, защото започва след нулата и става по-сериозна доста много знака след нея, особено в double. Отгоре на това при аритметиката няма грешка - има при преобразуването на дробната част.
Ако не ми вярваш - пробвай. Когато в книгата за 3D графика пише мъгляво, че числата с плаваща запетая водят до натрупване на грешка, това си има своите параметри. Ако искаш да разбереш какви са параметрите - учи асемблер.

Отговорът ми е и за двамата.
Вие може би си мислите, че числата с плаваща запетая са били измислени само за да се затруднят учениците и нямат никаква практическа стойност?

Отделен въпрос е, че моето решение на задачката би се базирало на сумиране на числата по байтове и изчисляване на средно аритметично от тях, което би дало overflow при масив с повече от 16000000 стойности (ако е 32 битов int) и ако се стигне до там, винаги може да се направи и по тетради. Бих го предпочел точно за да избегна плаващите запетаи, но не защото ще има грешка, а защото като използвам само целочислена аритметика, ще работи по-бързо.

Между другото - в условието на задачата се забранява аритметика с големи числа, не се забранява плаваща запетая - прочетете пак.


______________

Ако искаш изненада, защо просто не се влюбиш?

Редактирано от Labrett на 05.03.04 19:51.

Прочете е бавно въпроса като начало.
после уринирайте в чашки и хвърляйте барометри наляво надясно...

Как може да се очаква да се даде правилен отговор на въпрос, след като той не може да се прочете правилно....
--------------------------------------------

kvo shte reche kakto go narichat v bg : __int64, tva samo v bg li e ?

Moje i da imash neshto v glavata, obache romantichni prikazki za
tova kak niakoi shte ni otkrie i shte ni dava pari sa si smeshni, taka
che Guru e prav za tva neshto.

Mi to e blizo do akala, 4e Ave ne e ot tip int. Pak i misleh da napi6a (ama za6to li ne go napisah), 4e tova ne e kod na c/c++/c# ili kakavto i da e tam ezik. Tova e prosto opisane na tova kak da se smetne
*/* e operacia delene a ne CELO4ISLENO delene.
Kak o4akva6 srednoto aritmeti4no da e cialo 4islo. V ob6tia slu4ai to e realno.
Pak i ne vijdam nikade v uslovieto da ne moje da se izpolzva double ili float ili drug tip s plava6ta zapetetaia.
Ako ne moje6e viarvam 4e biha kazali da se polu4i cialata 4ast na sredno aritmeti4noto na......

Я вземи прочети малко теорийка... Какви са тези double?! Няма да получиш точен отговор!

Tova pak v koia teoriika go pi6e? V kakvo v celo4islen tip li 6te polu4i6 po-to4no srednoto aritmeti4no?
aide mi nameri srednoto aritmeti4no na {1,1,3} i go zapi6i v integer s po-goliama to4nost ot kolkoto az 6te go sapi6a v double

Имате array of integers - всякакви положителни, отрицателни и най-важното - много големи по стойност (близо до границите на INT_MAX и INT_MIN за 32- и 64- или 128- битови и всякакви други машини. Задачата е да се намери средната стойност на масива от числа. Звучи просто, да, ама не - като тръгнеш да събираш числата и да делиш на броя им - надвишаваш границите и няма къде да побереш резултата от сумирането.... Всяка логика за работа с големи числа, включително представяне на числата със string и писане на алгоритми за събиране - отпадат - не се приемат.

Eto ti i uslovieto da si go pripomni6. Kade pi6e 4e rezultata ne moje da e v double?
Naprotiv na vseki normalno misle6t 4ovek 6te mu mine prez uma 4e 6tom se tarsi sredno aritmeti4no to ne moje da e celo4islen tip.
Ako iska Foksa da si promeni uslovieto ili da hvarli malko svetlina po vaprosa dali se tarsi sredno aritmeti4noto ili samo cialata mu 4as. I za vtoroto ima ne trudno re6enie (e vse pak malko po-dalgi4ko ot tova)

Sury, be6e nai-blizo do tova re6enie ne razbrah samo za kakvo mu biaha tia Factor-i
Радвам се че поне някой е прочел поста ми :)
Идеята на факторите беше най-общо да емулирам (double) преобразуването без което резултата е неточен и да си местя запетаята в междинните резултати , най-общо бях решил да пиша алгоритъм за повишаване на точността особено когато става дума за огромни __int64-ки които превишават double по разряди.
После се отказах но фактора оцеля

"Suppose you're locked in a building and can't leave. How many ways can you think of to measure the exterior temperature? "

Tuk pishe "Predpolojete che ste zakliucheni v sgrada i ne mojete da izlezete. Kolko nachina shte izmislite da izmerite vynshnata temperatura"

ne vijdam kakvo prechi da se pikae v chashka? pyk i da imash nqkakva druga ideq? moje bi trqbva da se ogledam dali nqma nablizo hotel hemus s termometyr na nego ili da tyrsq binokyl da gledam termometrite na sysedite?

Всъщност отговорът на този въпрос би трябвало да е число.


______________

Ако искаш изненада, защо просто не се влюбиш?

kakyv e smisyla na vselenata? 42!

Imenno no te sa tolkova zaeti da misliat slojni re6enia 4e ne vijdat prostoto.
kakto kzah za da se uslojni zada4kata moje da se kaje da se izpolzvat samo celo4isleni tipove i da se polu4i cialata 4ast na srednoto aritmeti4no.

Srednoto aritmeti4no v ob6tia slu4ai e realno 4islo. Mislia 4e vseki znae kakvo sa realnite 4isla. Razradnata re6etka ot druga strana e kraina i diskretna taka 4e ne moje da da o4akva6 bezkraino goliama to4nost.

Taka 4e az viarvam 4e to4nosta na double e dostata4no dobra

double Avr=0;
for (int j=0; j<n; j++)
Avr+=arr[j];
Avr /= n;


?
Некак си по-бързо и по-точно е
E da samo deto lo6oto e 4e ne ti e daden nito kolko ti e bitov celo4islenia tip nito razmernostta na masiva.
Taka 4e teoreti4no ima opasnost ot prepalvane.
Drugia moje da prepalne pri niakakvo nenormalno goliama razraidnost na celo4islenia tip.

Za to4nostta sa6to ne sam saglasen. Ti gubi6 to4nost pri samato preobrazuvane ot int v double. Dori i celo4islenite 4isla ne se predstaviat s 100% to4nost v double

Първо да уточня какво се иска в задачата: търси се целочислено решение в рамките на същата разрядна решетка. Не се приема решение с по-големи типове, или с емулацията им. Ясно е, че с по-големи типове няма проблем и никой не би го задавал като специална задача. Просто щяха да кажат 'намерете средното аритметично'. Защо му трябва на човек подобно нещо е предмет на друг разговор.
Сега да ви обясня на вас двамата умници за double.
Нека за определеност int е 32 бита със знак. В double имаме 53 бита за мантиса( 52+1 от нормализация ). За да го препълниш с MAXINT-ове ( 31 бита ) ще ти трябват 2^22 числа ( към 4М, или общо 16М памет ). Възможно, но малко вероятно. Но щом имаш double ще имаш и long double, който се ползва тъкмо за контейнер. Той има 64 бита мантиса ( ненормализирана ). За да препълниш него ще ти трябват 2^33 MAXINT-а, което вече е невъзможно на 32 битови процесори, а на по-големи сигурно би имало и по-големи FP типове.
Пробиването на сумата Arr[j]/n е също толкова трудна работа - пак ще разполагаме с 31 бита, но в друг диапазон. Но така написан кодът има два недостатъка:
1. По-бавен е, защото на всяка стъпка се извършва по едно допълнително деление.
2. По-неточен е, защото на всяка стъпка се внася малка неточност. Вярно е, че тази неточност е много малка и статистически почти винаги ще остане в последните 2-3 бита, но тя би могла да е много досадна понякога, знам го от опит.
Пример 1: Имаш числата 3, 2, 1 и вместо 2.0 получаваш 1.9...98.
Пример 2: Имаш 100K числа, в първите 1К слагаш числата MAXINT-j, в останалите - числата n-j. Получаваш десетично число 61975.186479..9 вместо 61975.186478 т.е. грешка в 11-тата цифра. А типът ти гарантира 15 минимум. Загубил си цели 4 десетични цифри, или около 1/4 от мантисата.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Всъщност за втория пример съм изтърсил голяма глупост, добре че пръв я видях :-) Грешката пак е в последните битове, а не в 1/4 от мантисата. Много ми се искаше да наглася пример с голяма грешка, ама явно не е тривиално - например да се подберат само числа, които при делене на n се закръглят само в една и съща посока. И n да е малко по-къдраво :-)


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Няма шанс да стане голяма грешка - иначе нямаше да седя и да споря сега :)
Между другото, твърде малко хора наистина разбират какво става в един double, макар че повечето добре знаят за мантиси и експоненти. Грешката става не там обаче, а в представянето на дробната част в двоична бройна система, което не може да стане точно по чисто математически причини - когато умножаваш по 10, 100 и т.н можеш да го представиш същото и с умножение по 2, 4,8 .., обаче като делиш на 10, 100, 1000, не става същото с деление на 2, 4 и 8. Само че грешката при това представяне е едва в последното битче, което записваш. Става натрупване на грешка когато умножаваш реалното число и когато събираш, само че във втория случай натрупването става изключително бавно.

А казвам, че може да се препълни ако ги сумираш в double, просто защото може - в условието е написано, че целочисленото е с неопределен размер.
За да стане номерът с делението на всеки ход, което много добре зная,че е бавно и би могъл да го видиш, ако беше прочел и другата част от постинга ми, е необходимо да разполагаме с double, чиято мантиса е с няколко бита по-голяма от целочисления тип и нищо повече - изчислението ще е точно. При същото положение, обаче, сумирането на целочислените в double ще го препълни много бързо.

Освен това, деление на всеки ход, е просто светкавично в сравнение с решенията, които могат да се прочетат нагоре.



Да добавя, че в условието на задачата се иска да се намери средно аритметично на масив от цели числа, близки до INTMAX и INTMIN, без да се ползват алгоритми за аритметика с големи числа.
При така написано условие, решението с double отговаря - никъде не се споменава нищо за реални числа.
Друг е въпросът, ако условието е подадено грешно, но това не е проблем на решаващия.


______________

Ако искаш изненада, защо просто не се влюбиш?

Редактирано от Labrett на 07.03.04 15:34.

Не си прочела книгата.

Какъв е отговорът на въпроса за вселената? 42.

И след това построяват още по-велик компютър във вид на цяла планета, по-точно - Земята, за да отговори - Какъв е въпросът за вселената?

Абе изобщо четете ли като пише нещо пред вас, бе хора, или поглеждате текста и си измисляте всичко сами?


______________

Ако искаш изненада, защо просто не се влюбиш?

Ami ami ne si mnogo naiasno zza6to se polu4ava gre6kata. Tia idva ot dvoi4noto predstaviane na realnoto 4islo a ne ot razriadnosta na mantisata.

Posle vzemi i pro4eti po-dobre uslovieto. Moje pak celta na zada4ata (nezabraviai 4e e davana na interview za rabota)e da to4no da vodiat dali 6te tragne6 da si izmizlia6 sam uslojnenia

Ако не ме разбираш повярвай ми на честна дума, или някой друг дето по-добре от мен обяснява да ти каже. Ще направя последен опит да ти обясня.

В отговор на:

---

Няма шанс да стане голяма грешка - иначе нямаше да седя и да споря сега :)

---

В отговор на:

---

Между другото, твърде малко хора наистина разбират какво става в един double, макар че повечето добре знаят за мантиси и експоненти.

---

В отговор на:

---

При същото положение, обаче, сумирането на целочислените в double ще го препълни много бързо.

---

Научи се да пишеш на български като начало, после давай акъл.
Няма двоично представяне на реални числа, има представяне на рационални, които са приближение на реалните. Наясно съм защо се получава грешката, не съм наясно защо е нужно да се получава, като целите числа имат точно представяне в двоичен вид при числа с плаваща запетая.
Ами рядко това е целта. По-често в тоя форум хората не са запомнили добре условията, или ги е домързяло да ги напишат прецизно, така както теб те мързи да пишеш на български.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ама че нерви те друсат :)
Това джавистите много лесно се палите

Първото нещо, което ти казах, е че при твоя метод не е точно, защото ще губиш от ниските разреди. Приятел, ходи го прочети пак и докато не прочетеш внимателно и не разбереш какво ти говоря, не се връщай да ми спориш, щото повторяш дословно точно каквото ти казах от началото до края и наричаш това аргумент срещу моето изказване ?!
Препълване на double е това - да ти стане прекалено голямо числото и мантисата да не го побира, така че при умножаване с 10^E да ти се получат нулички в дясно, в ниските разреди. Тогава започват ГРАМАДНИ грешки при следващо сумиране, както сам си обяснил. И ако не се търсеше средно аритметично, щеше да бъдеш прав, защото тогава тези нулички нямаше да са важни при толкова голямо число, обаче като го разделим на броя на елементите, става пак малко - с такъв размер, че може да има и по-малко цифри от колкото са били нуличките, а това е толкова далеч от точно, че е минало от другата страна на Земята и настига точното с обиколка - може да се получи грешка още в целочислената част.

`при твоя метод се получава грешка още при 6та - 7ма цифра` .. добре, забравяш обаче `след нулата`, а аз през цялото време ти говоря за пренебрежимо малка грешка.
Факт е, че никой, по никакъв начин не може да намери точното средно аритметично, защото няма с какво да го запише, така че някъде ще трябва да удари кепенците и да каже - закръгляваме до тук.

Хайде сега ти, четейки условието, ми кажи кое е достатъчно точно? Без да си измисляш `какво са искали да кажат` ?

да напомня, че при `моя метод`, който изрично посочих, че не е мой и аз бих го решил по друг начин (ходи прочети още няколко пъти и _разбери_ какво пиша най-накрая), грешката ще остане в същия порядък.


______________

Ако искаш изненада, защо просто не се влюбиш?

Аз пиша на Жаба от няколко месеца и съм си сложил вкъщи да тренирам :-) Нервите ме друсат щото мразя Жаба :-) Стига си говорил за условието на задачата, отдавна не спорим за него. В момента с теб спорим как се смята средно аритметично.
Аз твърдя, че числата просто се сумират и накрая се делят. Така през цялото време работим с цели числа и нямаме загуба на точност. Чак накрая делим и получаваме възможно най-доброто приближение. Ако резултатът е цяло число получаваме пак цяло число.
Ти твърдиш, е по-добре първо да делим всяко число за да не се получи препълване. ( Разбира се и двамата говорим за препълване на мантисата, не на характеристиката, която има 12 бита и значи с нея можем да представяме числа от порядъка на 2^2^11 степен, което е твърде голямо число за нашия случай. ) Аз твърдя, че и по двата начина ще настъпи приблизително по едно и също време препълване на мантисата, следователно има само вреда и никаква полза от делението почленно.
За да си го представиш по-добре ще ти дам още един пример:
Нека n = 2^20. т.е около 1М. Тогава ти ще имаш точно толкова точен резултат колкото и аз. Какво мислиш, че ще стане като разделиш на 2^20? Ще стане, че тези 12 бита в които се представя характеристиката ще се намалят с 20 в смисъла на цели положителни числа. Но ти имаш 2048 стойности за числата>1 и 20 е нищо. Тогава цялото сумиране ще ти е също като да не си делил, просто ще имаш друго число записано в характеристиката. Следователно ще получиш същия отговор като мен. Ако щеш смятай 2^30 броя числа ( около 1G ), делението ще намали с 30 характеристиката. Това с нищо няма да подобри сумата в мантисата. Каква е разликата когато имаш и когато нямаш точно деление? Само в това, че ще смяташ с приближени числа, а не с точните иначе принципът е същият - делението/умножението касае характеристиката. Просто променя мащаба. Но аритметичните действия не зависят от мащаба като цяло, а от съотношението на мащабите на двете числа. Ако успееш да си представиш как работят числата ще ме разбереш.
Иначе съм съгласен, че се работи с приближения, но не съм съгласен по изкуствен начин да се внася грешка без от това да има поне малко полза.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ama toi problema ne ti bil s double a s balgarskia. Sega zacepih.

Проблем имаш ти с балгарския, аз нямам. Нямам и с double, пак ти имаш. Не че имаш проблем де, просто не знаеш как работи. Сума хора не знаят как работи и нямат проблем.
Ей, аман от мозъчни донори в тоя форум. Пък нямаш и смелост да се подпишеш. Аз поне ако ръся глупости си нося последствията, щото едно 10% от хората дето четат тук ме познават лично.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Значи, досега установихме, че ти знаеш как работи double и аз знам.
Освен това установихме, че спорим по кой начин като се сметне средно аритметично, ще има по-голяма грешка - дали с делене на всеки ход, или накрая.
Като погледна ефективността на спора - все едно сме го писали на .NET, ама карай :)

Та поначало съм съгласен с горе-долу с всичко, което казваш, с изключение единствено на тази част за грешката - по принцип спорът ни е почти безсмислен, защото в общия случай би трябвало да се получи една и съща грешка и при двата варианта.
Аз споря само за един граничен случай, когато грешката става голяма - мантисата е с няколко бита по-голяма от цялото число. В този случай си мисля, че с делене на всеки ход ще има по-малка грешка, защото ще сме изгубили по-малко значещи битове - твърдение, което всъщност не мога да докажа, но ако се стигне до там - можем да пробваме.

А може и двамата да говорим глупости и разлика в грешката да няма, в който случай твоят вариант е по-добър, защото е по-бърз.


______________

Ако искаш изненада, защо просто не се влюбиш?

В отговор на:

---

с делене на всеки ход ще има по-малка грешка, защото ще сме изгубили по-малко значещи битове - твърдение, което всъщност не мога да докажа

---

dobre be ebasi, ne moga da razbera kakvo iskash, da kaja kolko a ne kak taka li? ne mislia che onia tam deto sa zadali vyprosa sa iskali chislo za otgovor, shtoto interview-to shteshe da se prevyrne v naddavane...
are kaji si nai-nakraia kakyv ti e problema s nasheto chetene

не му се карай - потърси с гуугле за задачата и се намира един сайт с още такива задачи от MS поне да се позабавлява човек :)

10x :)

mi kak da ne se karam :) toi pyk ne moje li da ne povtaria samo edno i syshto "vie ne chetete vyprosa", "vie ne chetete vyprosa", "abe prochetete si vyprosa"...

Mnogo si nerven ne6to . Iavno kompleksi ima6 da izbiva6. I 6tom ima6 goliamata smelost da se podpisva6 6to ne go napravi6 ili imeto naistina ti e colombino. I tova li v kraia na krai6tata e nai-vajnoto. Pak i znania po double ne si pokazal koi znae kakvi. Tova deto go rasi6 tuka sigurno vseki go znae ot universiteta.
Kakvo kato si darjal izpit ili pisal kursova zada4a sigurno polovinata v toia forum sme go pravili.

Idi piini edna rakia i se uspokoi malko.
Aide i ia karai po-spokoino. Zapazi si nervite za drugade.

Когато пиша - пиша с nick-а си, а ти пак не си допрочела, щом ме слагаш на едно място с този, който каза, че не четете условията.
Освен това - той е прав, защото в условието наистина те питат колко метода можеш да измислиш, а не какви. Ако са имали предвид какви - значи са подали грешно условие. Аз лично мисля, че е грешен превода в случая, но това не променя факта, че всякакви хора му отговориха без да прочетат внимателно какво пише.

Абе много сте забавни всичките тука :) Човек да не каже нещо различно от вас - ще го набиете на кол, без дори да се запитате дали пък не е прав.


______________

Ако искаш изненада, защо просто не се влюбиш?

ти обаче не спираш да ме броиш за първокласник :)
ок, ще си търся да споря с някой, който проявява уважението поне да гледа какво пиша


______________

Ако искаш изненада, защо просто не се влюбиш?