И защо излизаш на 15-тия ?Първоначално публикувано от Bibi
Защото преди теб е имало един друг затворник който е изхабил един ден. (15=14+1)
Само че сега при тройната килия преди теб има двама затворника и всеки от тях е изхабил по един ден. (10=8+1+1)
ПП. Малко със закъснение, но все пак разбрах какво имаш предвид - да правим разлика между "излизане при точна тарифа" и "научаване на точна тарифа". Е, аз всичко което съм писал досега и било за "излизане при точна тарифа".
Така е. Аз броя на кой ден научавам точната тарифа.
А за 37 си прав.
Изглежда за 9 дена можем да научим точната измежду 130 стойности.
При тройната килия, на мен най-интересно ми беше как точно ще стане "рекурсията" - бая напъване му дръпнах за да го "видя", пък макар и с грешки в детайлите.
Обаче в момента колкото и да се напъвам, не мога да видя рекурсията при четворна килия ... проклета деменция
Според мен става така: След 7 въпроса можем да сме сигурни в тарифата, ако е имало 105 възможности за нея.
4-тия казва: 43, 70, 86, 95, 100, 103
Ако излезе още при 43, 3-тия казва: 16, 27, 34, 38, 40
и т.н.
P.S.
Междувременно схванах от къде ми е хрумнало за логаритъм.
Ако разполагаме с достатъчно много затворници, ще успеем с двоично деление да научим точната тарифа.
Което дава за броя дни логаритъм при основа 2 от броя възможни стойности.
Абсолютно прав си! За разлика от мен.
За сега "измислих" някаква рекурсивна зависимост за определяне на стъпките на питанията на затворниците в зависимост от броя им. Разсъжденията ми са малко в обратен ред и неподредени, но съм сигурен, че ще схванете идеята ми.
Най-лесно ми е да го илюстрирам с таблица:
1 2 3 4 5 6
1 1
2 1 2
3 1 3 4
4 1 4 7 8
5 1 5 11 15 16
6 1 6 16 26 31 32
7 1 7 22 42 57 63
8 1 8 29 64 99 120
9 1 9 37 93 163 219
10 1 10 46 130 256 382
11 1 11 56 176 386 638
12 1 12 67 232 562 1024
13 1 13 79 299 794 1586
14 1 14 92 378 1093 2380
В таблицата са стъпките на съответния затворник в зависимост от броя им и необходимите дни (въпроси). По абсцисата е броят на затворниците, а по ординатата дните. Стъпката на първия е винаги 1 (по вертикалата има винаги единички). Вторият има минимална стъпка 2, а всяка следваща се получава като съберем предходната по ветикала със съседната отляво по хоризонтала, т.е. съответната стъпка на затворника с No с едно по-малък. По този начин смятам рекурсивно стъпките на всички затворници (в случая до 6 и до 14 дни за определяне на тарифата).
За да сметна колко е максималната тарифа, която мога да определя с точност при зададен брой затворници събирам минималните стъпки на всички затворници и следващите стъпки на този с най-голям номер. Примерно, за 4 затворника се получава
1 - затворник No1
2 - затворник No2
4 - затворник No3
8 - затворник No4
15 - затворник No4, II-ра стъпка
26 - затворник No4, III-ра стъпка
42 - затворник No4, IV-ра стъпка
______________________________
98 - седем дни (въпроса) <- Това е максималната тарифа, която можем да определим със сигурност за толкова дни.
Визуално това събиране започва от първата стъпка на първия затворник, продължава по диагонал надолу до затворника с най-старши номер и продължава вертикално надолу докато се изравним или надминем максималната сума на потенциалната тарифа.
Това ме инспирира да предположа, че Bibi не е права за достатъчността от само седем въпроса при определяне на тарифа от 105 жълтици.
От табличката се вижда и че при зададена максимална тарифа, има една граница на "необходимия" брой затворници, надминаването на която не води до подобрение на резултата (намаляване на необходимия брой дни/въпроси).
От тук натам могат да се изведат и необходимите формули, както и начините за смятане на различни задачи видове задачи (права, обратна и т.н.), но ме мързи.По-скоро ще помисля дали има някакъв начин за оптимизиране при непълна, т.е. не максимална възможна тарифа. Имам предвид примерно при 5 затворника и тарифа пак от 100 жълтици дали може да се намали броя дни при някакво различно от горното разпределение на стъпките, тъй като то е валидно за пълната тарифа при даден брой дни.
Но ще почакам първо да мине MitkoS и да ми разбие детските мечти като ми намери очеизвадна грешка или недоглеждане в сметките.
Хм....а защо и другият да не може после да си предложи париците? Нещо не ми се връзва.
Би трябвало всеки да може да предлага - това не е колективна, килийна услуга!
Ясно, че ако някой се измъкне не може да го чакаш на другия ден пред портата, но според мен е логично
всеки ден да може всеки да се пробва. И след като са в една килия, да знае какво е предложил другият!
Това си е друго условие и води до други резултати! Но в първичното условие нямаше такова ограничение!
А тогава става друга задачата.............
@pimpirlit,
съвсем не съм сигурна, че съм права. Нямах време да проверя хубаво. Но и аз си правя табличка, много подобна на твоята, така че разсъжденията са същите. Успях да изведа формулите за до 3 участника, но от това не виждам особен смисъл.
@Wise,
Да, задачите са различни. Но и в двете има с какво да се заиграе човек, така че смятай тая, която ти харесва.
Ми сподели някоя формула де. Аз съм с малко по-инженерен начин на мислене и формулите са ми вторична функция, първо трябва да осмисля нещата на малко по-емпирично ниво. Лошото е, че не мога да го правя на сън - в това творческо състояние на духа, мозъкът ми генерира ексклузивно не съвсем математически диспути с разни каки. Не знам дали това е вследствие на факта, че ме е духал сливенският вятър няколко години или е повсеместно явление сред мъжката част от населението по принцип. Мистерия...
Добре. След като си огледам и поправя табличката. Но не днес.
Иначе не е нещо сложно. За сумата на 1+2+3+... Гаус е видял формулката още като е бил на около 7 години.
Аз я ползвам, както и още една за сумата от квадратите им.
А защо не си говоря с каки насън, това не знам. Дефект някакъв
„Видях” го най-после. Но пък сега ме е яд, че ми отне толкова време … проклета деменция.
Да се пробвам на едно обобщение на написаното за рекурсията, а ? С формулка.
Досега никой не го е описал по начина по който възнамерявам сега да го опиша тук. Става въпрос за случая, при който надзирателя приема само едно предложение дневно. (Както ще се види по-надолу, за момента е без значение дали говорим за подслучая „научаване на точна тарифа” или за подслучая „излизане при точна тарифа”)
Нека с ‘d’ да означаваме брой дни, а с ‘k’ да означаваме брой затворници.
Нека с M(d,k) да означим функцията която ни дава максималната тарифа, която можем да проверим за d дни с k на брой затворници.
Нека за момент предположим, че за фиксирано d знаем стойностите на M(d1,k) за всяко k и за всяко d1 по-малко или равно на d.
И сега въпроса е как да направим рекурсията за d+1. Т.е., ако имаме на разположение още един допълнителен ден, как да намерим новата максимална тарифа, т.е. как ще изглежда стойността M(d+1,k)
Разсъжденията са такива:
На първия ден, първия затворник ще предлага оферта. Той ще ‘излиза’ ако е предложил достатъчно, или ще ‘остане’ ако е предложил малко. И в двата случая, след неговия опит вече ще имаме на разположение един ден по-малко, т.е. остават d на брой дни.
Ако той излиза, ще имаме k-1 на брой затворници и оттук нататък, максималния интервал който можем да проверим е M(d, k-1) (по-нагоре предположихме, че тая стойност ни е известна някак си в момента). И затова, първия затворник в първия ден трябва да предложи именно тая стойност, защото ако излезе, да можем с останалите к-1 затворници и останалите d дни да проверим интервала от 1 до M(d, k-1).
Ако той не излезе, ние вече знаем, че тарифата е по-голяма от M(d, k-1) и също така вече имаме гарантирано проверен тарифи от 1 до M(d, k-1). А с останалите d дни и k на брой затворници, можем да проверим още M(d,k) на брой тарифи.
==> Общия брой тарифи които можем да проверим за d+1 дни и k на брой затворници е:
[size=10pt][size=10pt]M(d+1,k)=M(d,k-1)+M(d,k)[/size][/size]
Именно това е формулката за рекурсията, като разбира се, трябва да решим как да дефинираме:
M(1,i) за i=1,2,3,4,5,6,7,8 …
M(j,1) за j=1,2,3,4,5,6,7,8, …
При случая „излизане при точна тарифа” е естествено да дефинираме
M(1,i)=1 за i=1,2,3,4,5,6,7,8 …
M(j,1)=j за j=1,2,3,4,5,6,7,8, …
А при случая „научаване на точна тарифа” е естествено да дефинираме
M(1,i)=2 за i=1,2,3,4,5,6,7,8 …
M(j,1)=j+1 за j=1,2,3,4,5,6,7,8, …
При тоя случай „научаване на точна тарифа”, можем даже да се направим на тарикати и да допуснем нулеви стойности за d и k и съответно да дефинираме
M(0,i)=1 за i=1,2,3,4,5,6,7,8 …
M(j,0)=1 за j=1,2,3,4,5,6,7,8, …
Защото лесно се вижда, че при тази нова дефиниция и при горната формула за рекурсия пак се стига до същите стойности за d=1 и k=1
M(1,i)=2 за i=1,2,3,4,5,6,7,8 …
M(j,1)=j+1 за j=1,2,3,4,5,6,7,8, …
Как изглежда това във вид на таблица ?
Ще я нарисувам за случая „научаване на точна тарифа” като ще взема втората дефиниция с нулеви стойности за d и k. За другия случай - „излизане при точна тарифа”, стойностите в таблицата изглеждат по същия начин, само дето има едно отместване с един ред и една колона
0 1 2 3 4 5 6 7 8 9 - брой затворници
0 дни – 1 1 1 1 1 1 1 1 1 1
1 ден – 1 2 2 2 2 2 2 2 2 2
2 дни – 1 3 4 4 4 4 4 4 4 4
3 дни – 1 4 7 8 8 8 8 8 8 8
4 дни – 1 5 11 12 16 16 16 16 16 16
5 дни – 1 6 16 26 31 32 32 32 32 32
6 дни – 1 7 22 42 57 63 64 64 64 64
7 дни – 1 8 29 64 99 120 127 128 128 128
8 дни – 1 9 37 93 163 219 247 255 256 256
И т.н.
И нещо последно:
Без да намирам точната причина (не съм я и търсил де), забелязах, че ако направим нова таблица където в клетка с координати (i,j) разположим числото M(i,j+1)-M(i,j), то получаваме триъгълника на Паскал
Wise,
В предишния пост съм въвел едно означение d. Приел съм, че с това d означавам броя дни. Но всъщност, това е броя опити за подкуп необходими за да се провери даден интервал от тарифи.
(разгледал съм варианта при който надзирателя приема само една оферта дневно и затова в моя случай брой дни и брой опити съвпада).
И сега за твоя вариант:
Намираме първо необходимия броя опити (който е един и същ за всички варианти) и след това сравнително лесно преминаваме към броя дни за твоя вариант.
Новини
Форум
Актуално
сървър
Отговор с цитат