Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 050 Iepuri  (Citit de 8731 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« : Februarie 21, 2005, 20:22:34 »

Aici puteţi discuta despre problema Iepuri.
Memorat
junior
Strain
*

Karma: 20
Deconectat Deconectat

Mesaje: 42



Vezi Profilul
« 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 Deconectat

Mesaje: 43



Vezi Profilul WWW
« Răspunde #2 : Aprilie 17, 2005, 12:03:45 »

Pai nu e valabil doar la matrici Smile. 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
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 227
Deconectat Deconectat

Mesaje: 670



Vezi Profilul WWW
« Răspunde #5 : Aprilie 18, 2005, 19:11:56 »

bineinteles, algoritmul functioneaza pentru orice operatie asociativa.
Memorat
junior
Strain
*

Karma: 20
Deconectat Deconectat

Mesaje: 42



Vezi Profilul
« 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

 Brick wall ...
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« 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
Vorbaret
****

Karma: 33
Deconectat Deconectat

Mesaje: 166



Vezi Profilul
« 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?  Think
Memorat

Vlad Berteanu
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« 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 Deconectat

Mesaje: 8



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« 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 Deconectat

Mesaje: 8



Vezi Profilul
« 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
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #14 : Iulie 13, 2006, 15:00:43 »

Citeste articolul cu solutia problemei :
http://info.devnet.ro/articole.php?page=art&art=40&artpage=1

spor la implementat Smile
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
andrei_blanaru
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« 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 (In,In+1,In+2) va rezulta chiar matricea cu o singura coloana (In+1,In+2,In+3). Prin inductie se poate demonstra ca Mn * (I0,I1,I2) = (In,In+1,In+2).
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« 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?  Huh
Memorat
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« 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?  Huh

Nu cred ca ar trebui sa iti apara valori negative wink , ai grija la operatia de modulo.
Memorat

vid...
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« 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. Smile 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
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« 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]:
Cod:
   [0 1 0]
M = [0 0 1]
    [C B A]

si a[3][1]
Cod:
[I0]
[I1]
[I2]

In matricea c[3][1] vreau sa obtin
Cod:
    [I0]  [IN  ]
M * [I1] = [IN+1]
    [I2]  [IN+2]

Produsul il calculez asa:

Cod:
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 ? Neutral



Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« 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
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines