|
Joi, 12 ian 2012 00:30
[#]
wmutex
1. "Codificarea" problemei. Este clar ca, pentru a ajunge din coltul stanga sus in coltul dreapta jos, trebuie facute 7 mutari in jos, si 7 mutari la dreapta. Ordine |
|
Joi, 12 ian 2012 00:42
[#]
wmutex
1. "Codificarea" problemei.Este clar ca, pentru a ajunge din coltul stanga sus in coltul dreapta jos, trebuie facute 7 mutari in jos, si 7 mutari la dreapta. Ordinea nu conteaza, dupa cum se poate observa usor. In total 14 mutari. O varianta de codificare ar fi urmatoarea: 1 codifica o mutare in jos, iar 0 codifica o mutare la dreapta. Un drum este atunci reprezentat in mod unic de catre un numar binar de 14 biti, din care 7 biti au valoarea 1 si 7 biti au valoarea 0. Problema se traduce atunci astfel: cate numere de 14 biti care au doar 7 biti cu valoarea "1" exista?2. Rezolvarea "codificarii"Problema e una simpla de combinatorica, cu rezultatul C(14, 7) (combinatii de 14 luate cate 7), fiindca problema ne cere sa alegem 7 pozitii din cele 14, nu conteaza in care ordine, in care sa punem bitii pe 1. Valoarea numerica: C(14, 7) = 3432 drumuri diferite. GeneralizareIn general, pt o tabla de dimensiunea n x n numarul de drumuri care ajung din coltul stanga-sus in cel dreapta-jos este: C(2( n-1), n-1) |
|
Joi, 12 ian 2012 00:54
[#]
wmutex
Ok, nu ma abtin sa nu propun problema si mai generala: Pe o tabla de dimensiuni infinite (adica 2 dimensiuni, coordonate intregi), care este numarul de drumuri ale un pion aflat in pozitia initiala ( h1, v1) pt. a ajunge in pozitia ( h2, v2), stiind ca drumul e o secventa de mutari: "mutare dreapta": ( h', v') = ( h, v) + (1, 0) "mutare sus": ( h', v') = ( h, v) + (0, 1). |
|
Joi, 12 ian 2012 02:45
[#]
catanedelcu
RE: voi nota Cxy = combinari de x luate cate y ca sa-mi iasa tabloul si explicatia. se vede oricum ca numarul cerut se afla printre coeficientii dezvoltarii (x+y)^(n) pe care il vom gasi mai jos astfel...sa folosim un tablou particular mai mic C44 C54 C64 C74 C84 C33 C43 C53 C63 C73 C22 C32 C42 C52 C62 C11 C21 C31 C41 C51 C00 C10 C20 C30 C40 se vede destul de clar , zic eu, dupa ce reguli "răsar" combinarile alea consideram fara sa restrangem ca (h1, v1)= (0,0) (originea); acum daca luam , par example C52 ..adica (h2, v2)=(3,2) vom avea numarul de drumuri C52 = C(h2-h1+v2-v1),(v2-v1) adica ,tradus un pic..pentru punctele de coordonate date general, numarul de drumuri este: Combinari de (h2-h1)+(v2-v1) luate cate (v2-v1)) unde h1,h2,v1,v2 sunt coordonatele stabilite si care indeplinesc, bineinteles, conditia care se impune: h2>=h1 , v2 >= v1 punand asta in problema particulara , ar veni , pentru ( h1,v1) = (0,0) ( h2,v2) =( 7,7) combinari de (7-0)+(7-0) luate cate (7-0) adica tocmai rezultatul obtinut anterior am inceput scrierea "coordonatelor" de la (0,0) ca sa nu ma mai incurc cu scazutul lui 1. exista si o demonstratie mai eleganta dar eu am scris-o asa cum mi-e obiceiul :D pentru o mai buna clarificare : termenii de pe oblicele care incep de la termenul n , de la dreapta jos la stanga sus, sunt coeficientii dezvoltarii binomului (x+y)^n. sau..daca intoarcem figura cu 90+45 de grade in sensul acelor de easornic avem triunghiul lui Pascal. |
|
Joi, 12 ian 2012 01:45
[#]
catanedelcu
iaca si de la mine o rezolvare practica , ca nu-l cred pe wmutex :D fiecare "nod" indica numarul total de drumuri ce se pot face pana la el, respectand conditiile impuse de problema. . 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 1 4 10 20 35 56 84 120 1 5 15 35 70 126 210 330 1 6 21 56 126 252 462 792 1 7 28 84 210 462 927 1716 1 8 36 120 330 792 1716 3432 |
|
Joi, 12 ian 2012 02:36
[#]
wmutex
RE: Nice. :-) C(k, p) = C(k-1, p) + C(k-1, p-1) da triunghiul lui Pascal; N(k, p) = N(k-1, p) + N(k, p-1) da tabla de sah a lui catanedelcu. :-) |
|
Joi, 12 ian 2012 09:50
[#]
Je
Gresiti cu totii:)) cand ajunge la capat se face regina sau turn si fuge direct in coltul destinatie, deci total 9 mutari. Ar mai fi o varianta pe care n-ati luat-o in calcul: se intreaba cate drumuri, nu cate mutari, deci trebuie calculat numarul traseelor distincte, nu cel al mutarilor distincte, pe care l-ati calculat voi. |
|
Joi, 12 ian 2012 10:39
[#]
catanedelcu
RE: au fost calculate drumurile,in mod corect, nu mutarile. Pentru edificare ,in imagine am pus cele 6 drumuri distincte pentru o tabla mai mica de 3x3. Numarul de drumuri ies din triunghiul lui Pascal cum s-a mai spus, nu e nicio greseala. Imagine ataşată |
|
Joi, 12 ian 2012 12:35
[#]
cosmin1899 
nici o mutare, in sah situatia expusa nu exista! |
|
Joi, 12 ian 2012 12:38
[#]
cosmin1899
unde mai pui si ca teoretic pionul nu poate muta decat in jos sau STANGA, nu dreapata, chestie de perspectiva! |
|
Vineri, 13 ian 2012 10:25
[#]
Seadog
RE: pionul se muta numai in sus ... si stanga sus sau dreapta sus cand ia o piesa .... sau la mutarea "en-passent" |
|
Joi, 12 ian 2012 12:45
[#]
catalin87
parerea mea inexperta este ca exista 3 drumuri |
|
Joi, 12 ian 2012 13:16
[#]
knowing
k.... poate imi explica si mie cineva cum acetilena poate avea p.f.(-84) la o temperatura mai mica de cat p.t.(-80.8) |
|
Joi, 12 ian 2012 14:45
[#]
wmutex
RE: Fierberea consta in "emitere" de vapori din tot volumul substantei (si nu doar de la suprafata). In stare solida majoritatea substantelor au legaturi atat de puternice incat e imposibil pentru o particula reprezentativa (atom, molecula, ion) sa scape din chingile legaturilor solidului respectiv. Starea lichida e caracterizata de legaturi un pic mai slabe decat cele din starea solida (pt. aceeasi substanta), de aceea multe dintre substante pot fierbe abia dupa ce se topesc (adica abia dupa ce legaturile inter-atomice/moleculare/ionice slabesc datorita agitatiei termice). Acetilena, se pare, are legaturi inter-moleculare suficient de slabe incat sa permita formare de vapori din tot volumui cristalului inainte sa ajunga in stare lichida. |
|
Problema zilei
Top 10 cele mai văzute probleme