Dve zadachi
11 отговора
376 прегледа
Dve zadachi
Ето две задачи, може да му е интересно на някой.
(1) Гръцки урни.
В една урна има 150 черни и 75 бяли топки. Извършваме следното нещо: Изваждаме по случаен начин 2 топки; ако и двете топки са от един и същи цвят (т.е. и двете бяли или и двете черни) слагаме обратно в урната 1 черна топка; ако двете извадени топки са с различен цвят, връщаме в урната една бяла топка. Този процес се повтаря постоянно, докато остане само 1 топка. Ясно е, че всеки път топките намаляват с по една.
Въпроса е дали можем да предвидим, или да кажем предварително, какъв ще е цвета на последната топка.
(2) Остров на хамелеоните.
На един остров живеят хамелеони които могат да се променят в 3 различни цвята: червено, жълто и зелено. Хамелеоните постоянно пълзят насам, натам. Когато два хамелеона се срещнат, правят следното: ако са с един и същи цвят, просто се разминават и нищо; но ако са с различен цвят и двата се променят до третия, неутрален цвят; примерно ако се срещнат червен и жълт, тогава и двата се променят в зелен, ако се срещнат червен и зелен и двата стават жълти, ...
Нека от начало имаме 15 червени, 14 жълти и 13 зелени хамелеона. Пускаме ги да пълзят и гледаме какво става. Въпроса е дали с течение на времето ще се установи някаква монохромна конфигурация, да речем всичките да станат жълти. Или ще си менкат вечно цветовете безразборно. Какво ще стане?
Поздрави,
/b33
PS.
Задачите взех от книгата Nachum Dershowitz, David A. Plaisted, "Rewriting", страница 4.
Има я на адреса [линк].
(1) Гръцки урни.
В една урна има 150 черни и 75 бяли топки. Извършваме следното нещо: Изваждаме по случаен начин 2 топки; ако и двете топки са от един и същи цвят (т.е. и двете бяли или и двете черни) слагаме обратно в урната 1 черна топка; ако двете извадени топки са с различен цвят, връщаме в урната една бяла топка. Този процес се повтаря постоянно, докато остане само 1 топка. Ясно е, че всеки път топките намаляват с по една.
Въпроса е дали можем да предвидим, или да кажем предварително, какъв ще е цвета на последната топка.
(2) Остров на хамелеоните.
На един остров живеят хамелеони които могат да се променят в 3 различни цвята: червено, жълто и зелено. Хамелеоните постоянно пълзят насам, натам. Когато два хамелеона се срещнат, правят следното: ако са с един и същи цвят, просто се разминават и нищо; но ако са с различен цвят и двата се променят до третия, неутрален цвят; примерно ако се срещнат червен и жълт, тогава и двата се променят в зелен, ако се срещнат червен и зелен и двата стават жълти, ...
Нека от начало имаме 15 червени, 14 жълти и 13 зелени хамелеона. Пускаме ги да пълзят и гледаме какво става. Въпроса е дали с течение на времето ще се установи някаква монохромна конфигурация, да речем всичките да станат жълти. Или ще си менкат вечно цветовете безразборно. Какво ще стане?
Поздрави,
/b33
PS.
Задачите взех от книгата Nachum Dershowitz, David A. Plaisted, "Rewriting", страница 4.
Има я на адреса [линк].
Re: Dve zadachi
Ami izhvurliame dvete beli topki, i slagama edna cherna topka v urnata (vzemame ia ot nekade - da rechem imame dostatuchno v zapas).
Estestven ti e vuprosa, poneje biah upotrebil dumite "Vrushtame nekakva topka obratno". Zadachata ia vijdam za purvi put, prevedoh ia ot angliiski, very sory ako ne sum bil dostatuchno iasen, dadoh adres na orginalnia text.
BTW, i dvete zadachi ne sa trivialni. Az, lichno, se podlugah i napisah komputerni programi (i zadvete) koito gi modelirat. Chak togava se chatnah kakva e dalaverata. Mogat da se reshat i s chisto "logichesko" mislene, ... no na koito mu e kus akula, sa mu dulgi krakata (govoria za sebe si :). Napisah si programkite na <Scheme Lisp> ... ubuh si ne poveche ot 2 chasa. Ako iskash trugni po moia nachin.
Znaia otgovora, no ne iskam da ti go kazvam, za da ne ti razvalia udovolstvieto ot reshavaneto.
BTW, onazi kniga e posvetena na vuprosa <kak da nakarame komputera da reshava takiva zadachi>. Za nas, horata, e trudno. No, nie horata, da nauchim komputera da gi reshava, triabva da e oshte po-trudno.
Pozdravi,
/b33
P.S.
Izviniavam se na onezi, deto ako ne chuiat dumite <integral> ili <proizvodna> kazvat che zadachata ne e za tozi klub. Na tiah sum im dosadil, predpolagam.
.
Estestven ti e vuprosa, poneje biah upotrebil dumite "Vrushtame nekakva topka obratno". Zadachata ia vijdam za purvi put, prevedoh ia ot angliiski, very sory ako ne sum bil dostatuchno iasen, dadoh adres na orginalnia text.
BTW, i dvete zadachi ne sa trivialni. Az, lichno, se podlugah i napisah komputerni programi (i zadvete) koito gi modelirat. Chak togava se chatnah kakva e dalaverata. Mogat da se reshat i s chisto "logichesko" mislene, ... no na koito mu e kus akula, sa mu dulgi krakata (govoria za sebe si :). Napisah si programkite na <Scheme Lisp> ... ubuh si ne poveche ot 2 chasa. Ako iskash trugni po moia nachin.
Znaia otgovora, no ne iskam da ti go kazvam, za da ne ti razvalia udovolstvieto ot reshavaneto.
BTW, onazi kniga e posvetena na vuprosa <kak da nakarame komputera da reshava takiva zadachi>. Za nas, horata, e trudno. No, nie horata, da nauchim komputera da gi reshava, triabva da e oshte po-trudno.
Pozdravi,
/b33
P.S.
Izviniavam se na onezi, deto ako ne chuiat dumite <integral> ili <proizvodna> kazvat che zadachata ne e za tozi klub. Na tiah sum im dosadil, predpolagam.
.
dobavka
Moje da vuzpriemem zadachata i taka:
Ako shte triabva da "vrushtame" cherna/biala topka ot nalichnite, deto sme bili izvadili veche, a niamame takiva pod ruka: otkazvame se ot poslednia eksperiment - moje bi na sledvashtia experiment shte izvadim 2 cherni, shte vurnem ednata, i posle shte si imame cherna topka v zapas.
Tova ne promenia igrata (spored men).
Samo da ne te odvede v greshna posoka na razsujdenia. Ne jelaia da podskazvam.
BTW, zadachata za "Chameleons Island" e po-trudna (za men pone beshe po-trudna). Turpi obobshtenie ... po princip i dvete mi se struvat interesni.
Pozdravi,
/b33
Ako shte triabva da "vrushtame" cherna/biala topka ot nalichnite, deto sme bili izvadili veche, a niamame takiva pod ruka: otkazvame se ot poslednia eksperiment - moje bi na sledvashtia experiment shte izvadim 2 cherni, shte vurnem ednata, i posle shte si imame cherna topka v zapas.
Tova ne promenia igrata (spored men).
Samo da ne te odvede v greshna posoka na razsujdenia. Ne jelaia da podskazvam.
BTW, zadachata za "Chameleons Island" e po-trudna (za men pone beshe po-trudna). Turpi obobshtenie ... po princip i dvete mi se struvat interesni.
Pozdravi,
/b33
Re: Dve zadachi
Zada4a 1.
Neka prosledim sastoianieto na belite topki
Ako izwadim dwe 4erni, wry6tame edna 4erna, koli4estwoto beli ne se promenia
Ako izwadim 4erna i biala, wrashtame bialata, te pak ne se promeniat
Ako izwadim 2 beli, slagame 1 4erna, t.e, belite namaliat s 2
Belite ili ostawat sa6tite, ili namaliawat s 2, t.e tiahnata "4etnost" nikoga ne se promenia. Zna4i, za da ostane nakraia 1 biala ( i nula 4erni) e neobhodimo i dostata4no broiat im w na4aloto da e ne4eten. Za da ostane 1 4erna (i nula beli) triabwa da e 4eten. W slu4aia broiat im e ne4eten, zna4i 6te ostane biala topka
------------------------
Zada4a 2.
Sa6to e swarzana s 4etnostta, no s ostatyk pri delene na 3.
W na4aloto imame 3 grupi, s posledowatelen broj, sas ostatak pri delene na 3 (0,1 i 2). Hitrinata tuk e, 4e kakto i da se sblaskwat hameleonite, winagi imame grupa s ostatak 0, edna s ostatak 1 i edna s ostatok 2. Sblaskwaneto na hameleoni ot 2 grupi namaliawa broia na tezi grupi s 1 i uweli4awa broia na tretata s 2. Neka grupa A ima ostatok 0, B-1 i C-2. Ako se sblaskat A-B, ostatacite pri delene na 3 sa (saotwetno za A, B i C) (2,0,1). Ako se sblaskat A-C ostatacite sa (2,0,1), ako se sbllaskat B-C, ostatacite stawat (2,0,1). T,e kakto i da se sblaskwat, niama kak da se polu4at 2 grupi s rawen (nulew) broj. Zna4i e newazmojno da ostanat hameleoni samo ot edin cwiat
---------Izwiniawam se na horaya, koito 4etat towa, no w i-net klubowete niamat phoneti4na kirilica
Neka prosledim sastoianieto na belite topki
Ako izwadim dwe 4erni, wry6tame edna 4erna, koli4estwoto beli ne se promenia
Ako izwadim 4erna i biala, wrashtame bialata, te pak ne se promeniat
Ako izwadim 2 beli, slagame 1 4erna, t.e, belite namaliat s 2
Belite ili ostawat sa6tite, ili namaliawat s 2, t.e tiahnata "4etnost" nikoga ne se promenia. Zna4i, za da ostane nakraia 1 biala ( i nula 4erni) e neobhodimo i dostata4no broiat im w na4aloto da e ne4eten. Za da ostane 1 4erna (i nula beli) triabwa da e 4eten. W slu4aia broiat im e ne4eten, zna4i 6te ostane biala topka
------------------------
Zada4a 2.
Sa6to e swarzana s 4etnostta, no s ostatyk pri delene na 3.
W na4aloto imame 3 grupi, s posledowatelen broj, sas ostatak pri delene na 3 (0,1 i 2). Hitrinata tuk e, 4e kakto i da se sblaskwat hameleonite, winagi imame grupa s ostatak 0, edna s ostatak 1 i edna s ostatok 2. Sblaskwaneto na hameleoni ot 2 grupi namaliawa broia na tezi grupi s 1 i uweli4awa broia na tretata s 2. Neka grupa A ima ostatok 0, B-1 i C-2. Ako se sblaskat A-B, ostatacite pri delene na 3 sa (saotwetno za A, B i C) (2,0,1). Ako se sblaskat A-C ostatacite sa (2,0,1), ako se sbllaskat B-C, ostatacite stawat (2,0,1). T,e kakto i da se sblaskwat, niama kak da se polu4at 2 grupi s rawen (nulew) broj. Zna4i e newazmojno da ostanat hameleoni samo ot edin cwiat
---------Izwiniawam se na horaya, koito 4etat towa, no w i-net klubowete niamat phoneti4na kirilica
Re: Dve zadachi
lele, nima pishesh na lisp! ah! 
ima li neshto drugo interesno v tazi knijka? no istinski interesno - a ne topki i shapki, ili presmiatane na kombinacii, veroiatnosti i drugi takiva iziskvashti 5 reda kod. tazi za hameleonite e mnogo sladka - interesna i zabavno predstavena
ima li neshto drugo interesno v tazi knijka? no istinski interesno - a ne topki i shapki, ili presmiatane na kombinacii, veroiatnosti i drugi takiva iziskvashti 5 reda kod. tazi za hameleonite e mnogo sladka - interesna i zabavno predstavena
в отговор на edno momiche
#10
Re: Dve zadachi
Гледал съм какво се говори в клуба "Логика" и преди година даже се изказах 1-2 пъти ... но не ми е интересно да участвам там.
Онази книга не съм я чел до края, само я прегледах. Попаднах на нея и целия сайт, понеже търсих нещо за да разбера какво означава "Knuth-Bendix completion procedure". Вече съм забравил за това нещо - не зная колко е ценно, но се ползва в програми като MathCad и Maple за аналитични преобразувания на формули.
Ако някой знае повече по въпроса за rewriting, нека обясни, ще го изчета с удоволствие.
Понякога пиша на Lisp, понеже мога и е много удобен за някои задачи, като да провериш някой алгоритъм или да пробваш някоя идея. Това е за удоволствие, иначе си искарвам хляба с писане на VC++ и Assembler/C за микроконтролери ... каквото каже шефа :)
Поздрави,
/b33
Онази книга не съм я чел до края, само я прегледах. Попаднах на нея и целия сайт, понеже търсих нещо за да разбера какво означава "Knuth-Bendix completion procedure". Вече съм забравил за това нещо - не зная колко е ценно, но се ползва в програми като MathCad и Maple за аналитични преобразувания на формули.
Ако някой знае повече по въпроса за rewriting, нека обясни, ще го изчета с удоволствие.
Понякога пиша на Lisp, понеже мога и е много удобен за някои задачи, като да провериш някой алгоритъм или да пробваш някоя идея. Това е за удоволствие, иначе си искарвам хляба с писане на VC++ и Assembler/C за микроконтролери ... каквото каже шефа :)
Поздрави,
/b33
в отговор на edno momiche
#12
Re: Dve zadachi
Не търсим постоянно програмисти, понеже стагнацята в областта засяга всички. Е, случва се да дойде нов човек; за целта трябва да убедиш шефовете, че много им трябваш. Пиши ми на e-mail: [email protected] ако желаеш да обменим повече информаця, понеже тук е много публично, и не мога да говоря.
/b33
[email protected]
/b33
[email protected]