•domino
|
|
« : Februarie 21, 2005, 20:22:34 » |
|
Aici puteţi discuta despre problema Iepuri.
|
|
|
Memorat
|
|
|
|
•junior
Strain
Karma: 20
Deconectat
Mesaje: 42
|
|
« Răspunde #1 : Aprilie 17, 2005, 11:16:18 » |
|
Care e algoritmul de ridicare la putere in timp logaritmic al unei matrice? Spune-mi si mie, te rog, numele. Sa stiu ce caut, ca pana acum nu l-am gasit pe nicaieri.
Multumesc!
|
|
|
Memorat
|
|
|
|
•cavendish
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #2 : Aprilie 17, 2005, 12:03:45 » |
|
Pai nu e valabil doar la matrici . E foarte simplu: Ca sa calculezi a^100, inmultesti a^99 cu a sau a^50 cu a^50 sau orice alta combinatie. Daca a este numar, nu prea conteaza ce alegi, fiindca dimensiunea lui a creste cu exponentul, dar daca dimensiunea lui a nu depinde de exponent cel mai bine e a^50 * a^50. Sau a^64 * a^32 * a^4. Deci pe a^100 il gasesti din 2 inmultiri si inca 6 [ca sa gasesti a^64]. Deci 9 in total. Daca tot inmulteai cu a, il gaseai dupa 99 de inmultiri.
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #3 : Aprilie 17, 2005, 12:38:47 » |
|
Calculeaza A, A^2, A^4, ... etc., fiecare ridicand-o la patrat pe precedenta. Inmulteste astea in functie de descompunerea binara a exponentului. ex: A ^ 14.
14 = 1110 = 2 ^ 3 + 2 ^ 2 + 2 ^ 1, deci A ^ 14 = A ^ 8 * A ^ 4 * A ^ 2.
Bafta.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•silviug
|
|
« Răspunde #4 : Aprilie 18, 2005, 15:53:53 » |
|
Ce spune greco se poate rezuma la definitia recursiva a puterii: A^B = A^(B-1) daca B este impar si A^B = (A^(B div 2))*(A^(B div 2)) daca B este par (si aici daca il memoram pe A^(B div 2) si nu-l calculam de doua ori obtinem timp logaritmic)
Silviu
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•wickedman
|
|
« Răspunde #5 : Aprilie 18, 2005, 19:11:56 » |
|
bineinteles, algoritmul functioneaza pentru orice operatie asociativa.
|
|
|
Memorat
|
|
|
|
•junior
Strain
Karma: 20
Deconectat
Mesaje: 42
|
|
« Răspunde #6 : Aprilie 20, 2005, 14:45:25 » |
|
Multumesc pt ajutor. Merge acum.
|
|
|
Memorat
|
|
|
|
cippi
Vizitator
|
|
« Răspunde #7 : Mai 31, 2005, 12:52:06 » |
|
Am si eu o mare dilema la problema asta... Am facut prima oara cu matrici si am luat 0 (Raspuns gresit la toate). Apoi am incercat sa testez rezolvarea cu matrici folosind inca o rezolvare, cu forta bruta. Imi mergeau toate testele, asa ca m-am hotarat sa trimit varianta cu forta bruta sa vad cate puncte obtin: tot 0. NU inteleg ce se intampla, am pus peste tot '\n',nu pun spatii aiurea, deci nu vad unde ar fi problema!! Am folosit si faza cu "%"... Va rog sa ma ajutati ca mai e o luna pana la bac si eu fac Iepuri de 2 zile ...
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #8 : Mai 31, 2005, 13:22:23 » |
|
Vezi ca sunt mai multe teste intr-un fisier, sigur reintializezi variabilele dupa fiecare test?
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #9 : August 11, 2005, 17:07:49 » |
|
Eu acuma trec a 11-a asa ca nu stiu matrici. Ma gandeam daca se poate rezolva gasind forma generala a termenului l[n] in functie de l[0],l[1] si l[2]. Eu am calculat cateva l - dar nu observ nici o forma generala. Intrebarea mea este: are rost sa mai caut forma generala sau nu se poate decat cu matrici?
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•Cosmin
|
|
« Răspunde #10 : August 11, 2005, 17:37:06 » |
|
Nu cred ca poti face logaritmic fara matrici ... liniar rezolvi cu recurenta de ordinu 2. Ca sa gasesti formula generala a unei recurente de ordinu 2 parca tot prin a 11-a se facea. Vezi aici de recurente liniare http://mathworld.wolfram.com/LinearRecurrenceEquation.html , dar chestia asta nu te prea ajuta pentru ca trebuie sa ridici numere reale la puteri mari si pierzi precizie. Dar oricum inmultirea unei matrici nu e chestie complicata, ai putea lua un manual si sa te uiti pe acolo ce se intampla.
|
|
|
Memorat
|
|
|
|
•andrei_blanaru
Strain
Karma: 0
Deconectat
Mesaje: 8
|
|
« Răspunde #11 : Iulie 13, 2006, 10:48:10 » |
|
Care e smecheria cu inmultirea de matrice? Ca nu ma prind deloc.
|
|
|
Memorat
|
"Tot ce este gandit corect este sau matematica, sau susceptibil de matematizare!" Grigore MOISIL
|
|
|
•devilkind
|
|
« Răspunde #12 : Iulie 13, 2006, 13:59:10 » |
|
cauta intrun manual de clasa a 11-a. Eu acolo am gasit si e destul de simplu de inteles cum se inmultesc 2 matrici.
|
|
|
Memorat
|
|
|
|
•andrei_blanaru
Strain
Karma: 0
Deconectat
Mesaje: 8
|
|
« Răspunde #13 : Iulie 13, 2006, 14:40:43 » |
|
stiu sa inmultesc matrici, dar nu-mi dau seama cum sa folosesc treaba asta in problema
|
|
|
Memorat
|
"Tot ce este gandit corect este sau matematica, sau susceptibil de matematizare!" Grigore MOISIL
|
|
|
•tm_radu
|
|
« Răspunde #14 : Iulie 13, 2006, 15:00:43 » |
|
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
•andrei_blanaru
Strain
Karma: 0
Deconectat
Mesaje: 8
|
|
« Răspunde #15 : Iulie 14, 2006, 09:46:54 » |
|
merci mult. n-am stiut ca e de la preONI.
|
|
|
Memorat
|
"Tot ce este gandit corect este sau matematica, sau susceptibil de matematizare!" Grigore MOISIL
|
|
|
•peanutz
|
|
« Răspunde #16 : Mai 01, 2007, 17:57:06 » |
|
Nu-si gaseste careva 2 minute libere sa explice faza cu inmultirea unei matrici, sau whatever ai nevoie sa rezolvi asta de 100? Cred ca i-ar ajuta si pe altii. Multumesc.
|
|
|
Memorat
|
....staind....
|
|
|
•DITzoneC
|
|
« Răspunde #17 : Mai 01, 2007, 21:36:18 » |
|
Pare destul de bine explicat in articol. Inmultind matricea respectiva M cu matricea cu o singura coloana (I n,I n+1,I n+2) va rezulta chiar matricea cu o singura coloana (I n+1,I n+2,I n+3). Prin inductie se poate demonstra ca M n * (I 0,I 1,I 2) = (I n,I n+1,I n+2).
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #18 : Mai 01, 2007, 23:10:39 » |
|
Sunt cateva notiuni elementare de matematica de clasa a 11-a legate de matrici pe care trebuie sa le cunosti pentru a rezolva aceasta problema. Citeste in Cormen la capitolul cu matrici cum se inmultesc, apoi consulta articolul cum a spus si ditzone mai sus si nu ar trebui sa ai probleme in a intelege rezolvarea. Bafta!
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Florian
|
|
« Răspunde #19 : Noiembrie 25, 2007, 19:05:55 » |
|
La problema asta, am declarat toate variabilele de tip long long unsigned, si luam KBS 11 pe toate testele. Dupa ce am declarat long long [fara unsigned] am luat 100. Faza era, ca pe a doua si a treia linie din matricea finala, imi apareau elemente negative, din cauza faptului k atunci knd efectuam inmultirele intre doua numere mai mari, imi depasea long long`ul kiar daca aplicam operatia modulo 666013. Acest lucru e normal sau e din cauza algoritmului meu?
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #20 : Noiembrie 25, 2007, 19:12:18 » |
|
La problema asta, am declarat toate variabilele de tip long long unsigned, si luam KBS 11 pe toate testele. Dupa ce am declarat long long [fara unsigned] am luat 100. Faza era, ca pe a doua si a treia linie din matricea finala, imi apareau elemente negative, din cauza faptului k atunci knd efectuam inmultirele intre doua numere mai mari, imi depasea long long`ul kiar daca aplicam operatia modulo 666013. Acest lucru e normal sau e din cauza algoritmului meu? Nu cred ca ar trebui sa iti apara valori negative , ai grija la operatia de modulo.
|
|
|
Memorat
|
vid...
|
|
|
•DraStiK
|
|
« Răspunde #21 : Aprilie 07, 2008, 17:45:26 » |
|
legat de permiterea vizualizarii surselor altora a dus la multi in furt
adik dalalau alexandru mie coleg de scoala este la acelasi profil ca si mine si sunt 100% sigur ca nu are cunostinte destule pentru a rezolva de 100p problema iepuri care a fost data la preoni2005 runda 1 la clasele 11-12
nu mi se pare corect ca altii sa ma intreacs in clasamentul arhivei doar pentru k dau si ei copy paste.
multumesc
|
|
|
Memorat
|
|
|
|
•stef2n
|
|
« Răspunde #22 : Aprilie 07, 2008, 18:11:36 » |
|
Ti-ai raspuns singur la nemultumirea ta: clasamentul arhivei nu este relevant in conditiile in care unele surse sunt publice. Si gandeste-te ca 100 de probleme grele rezolvate nu se compara cu 100 de probleme usoare rezolvate si, implicit, acelasi loc in clasament. Asa ca nu e un motiv intemeiat de nemultumire. Daca vrei o masurare de forte, aveti destule probleme nepublice pe care sa le incercati.
|
|
|
Memorat
|
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
|
|
|
•miculprogramator
|
|
« Răspunde #23 : August 02, 2009, 12:29:03 » |
|
Salut ! Am citit articolul cu solutii si am probleme la implemantare... Am construit M[3][3]: [0 1 0] M = [0 0 1] [C B A] si a[3][1] [I0] [I1] [I2] In matricea c[3][1] vreau sa obtin [I0] [IN ] M * [I1] = [IN+1] [I2] [IN+2] Produsul il calculez asa: for (i=0;i<N-1;i++) for (j=0;j<N-1;j++) { c[i][j]=0; for (k=0;k<N-1;k++) c[i][j]=c[i][j]+M[i][k]*a[k][j]; } Insa c[3][1] nu arata bine. Cred ca gresesc la calcularea produsului...Putin ajutor ?
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #24 : August 02, 2009, 13:34:37 » |
|
Ai pus dimensiunile gresit. In primul rand, nu mergi pana la N, ci pana la 3 (dimensiunea matricii), iar in al doilea rand, j poate lua doar valoarea 0 (a[...][1] iese din matrice dupa cum l-ai definit tu). Intai trebuie ridicata matricea M la puterea N (sa o inmultesti cu ea insasi de N ori sau, ca sa intre in timp, sa faci asta logaritmic), iar abea apoi inmultesti cu acel "a".
PS: Problema asta cere niste cunostinte putin mai avansate de matematica (cam clasa a 11-a, dar poate inveti mai repede). Cred ca din acest motiv nu ai inteles pe deplin rezolvarea problemei sau de ce este corecta metoda.
|
|
|
Memorat
|
|
|
|
|