Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme


Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

C


Index » educatie » » informatica » C
Solutie problema Iepuri


Solutie problema Iepuri


Solutie problema Iepuri

Solutia se bazeaza pe metoda programarii dinamice si are complexitatea O(N*K).

Observam ca putem deduce numarul de posibilitati de a imparti un anumit numar j de morcovi la un iepure i si oricati morcovi la iepurii subordonati direct sau indirect daca cunoastem numarul de posibilitati de a imparti j+1, j+2, , j+K morcovi la fiecare fiu al sau si oricati morcovi iepurilor ce apartin subarborilor desemnati de fiecare fiu. Astfel, structura de date folosita pentru implementarea recurentei devine evidenta:

T[i][j] = numarul de posibilitati de a imparti morcovi la iepurii ce apartin subarborelui cu radacina in iepurele i stiind ca iepurele i ia j morcovi

Astfel definita structura de date, luam numarul de posibilitati de a imparti morcovi la iepurii din subarborele desemnat de primul fiu pentru fiecare din cazurile: primul fiu ia j+1, j+2, , j+K morcovi. La sfarsit, adunam toate aceste valori iar rezultatul il inmultim cu valorile pentru al doilea fiu, al treilea fiu etc. calculate in mod similar.

T[i][j] = 1, daca iepurele i corespunde unui nod terminal

T[i][j] = (T[f1][j+1]+T[f1][j+2]++T[f1][j+K]) *

(T[f2][j+1]+T[f2][j+2]++T[f2][j+K]) * * (T[fp j+1]+T[fp][j+2]++T[fp][j+K]),

unde f1, f2, fp sunt numerele de ordine a celor p iepuri fii ai iepurelui i

Rezultatul problemei va fi dat de T[R 1]+T[R][2]++T[R][K] unde R reprezinta numarul de ordine al lui Rila-Iepurila, adica al iepurelui care nu are nici un sef (radacina arborelui) .

Iepuri - solutie alternativa Stelian Ciurea

1. reprezentam arborele sub forma listelor de adiacenta implementate dinamic; la citire construim si vectorul de predecesori (legaturi de tip tata aceasta ne permite sa determinam radacina arborelui si deasemenea sa parcurgem arborele in adancime fara sa utilizam un vector pentru nodurile vizitate)

2. determinam radacina

3. facem o parcurgere in adancime a arborelui plecand din radacina: aceasta functie de parcurgere are 2 parametri: nd = nodul curent si i care reprezinta numarul minim de morcovi pe care ii poate manca iepurele din nd.

In aceasta functie, pentru o valoare j a numarului de morcovi, daca notam cu nrp1 numarul de posibilitati pe care le avem in fiul_1 al lui nd cu cel putin j+1 morcovi, cu nrp2 numarul de posibilitati pe care le avem in fiul_2 cu cel putin j+1 morcovi etc, numarul de posibilitati pe care le avem pentru nd este nrp1*nrp2*

Numarul total de posibilitati la nivelul lui nd se obtine ca o insumare a valorilor pe care le obtinem pentru toate valorile pe care le ia j (de la i la k).

Aceasta solutie obtine 60 de puncte; pentru 40% dintre teste nu se incadreaza in limita de rulare de o secunda.



loading...




Politica de confidentialitate

loading...




Politica de confidentialitate

Copyright © 2019 - Toate drepturile rezervate

Afaceri


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word