Intrebare despre programare...

[•Twister]

Nu va suparati, eu am realizat cu ocazia localei ca am o mare problema:
nu stiu programare dinamica...  :cry:   :cry:
Nu stiti cum as putea sa dau gata dinamica cumva?
Dupa cum vedeti este o problema destul de grava, si v-as ruga, ajutor, nu stiti cursuri pe net sau altceva, cum ar fi carti, va rog mult...      :cry:

[•wickedman]

1. there is no magic silver bullet!
singura solutie e sa faci multe multe probleme.

2. fa rost de "Informatica. Culegere de probleme". Editura "Polirom", 2002.
parcurgerea capitolului de programare dinamica de acolo (eg. citesti, rezolvi si implementezi toate problemele rezolvate/propuse) e un foarte bun inceput.

programarea dinamica e fun & challenging!
spor la treaba!

[•DeadStar]

Sau ai putea sa inveti din "Proiectarea si Implementarea Algoritmilor" de Mihai Oltean , Editura Agora. Cuprinde vreo 30 de probleme de PD explicate si implementate si pe langa.. branch & bound si diverse probleme

 

[•Cosmin]

Doua tutoriale de pe topcoder:

http://www.topcoder.com/index?t=features&c=feat_040104

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

[•Twister]

Multumesc mult o sa incerc sa fac rost de materialele pe care mi le-ati recomandat, nu stiti cat ma bucur ca m-ati ajutat.

[VladS]

Apropo de dinamica, cine imi da un hint despre "problema 0-1 a rucsacului". Am intilnit-o la USACO training 2.4 ("Inflation"). Eu am facut un algoritm care prinde doar primele 5 teste, folosind o metoda destul de intuitiva, dar vrea sa aflu o solutie oficiala sau macar cateva idei de la care sa pornesc.

[•svalentin]

pai daca vrei doar un hint, spune-ne cum ai facut-o tu pana acum!
asa, un hint mai general, sa sortezi problemele dupa timp; dintre cele care au acelasi timp, sa pastrezi doar setul de probleme cu punctaj maxim  

[VladS]

In afara de sortare algortimul e urmatorul:

Programare dinamica:
v = punctajul maxim care se poate obtine in timpul i

s - indicii i pentru care v != 0. La fiecare pas fac combinatiile posibile
     dintre elementul curent si elementele din s, maximizand vectorul v.

[•svalentin]

nu trebuie neaparat pentru elem din s, ci pentru seturile de probleme!

Mai departe ai rezolvarea mea: (daca vrei sa incerci sa o faci singur, nu te uita...)


cu i, parcurgi v de la 0 la N (N=timpul care il ai la dispozitie); si iei, daca v!=0, fiecare set de probleme si vezi daca v[i+set[j].timp]<v+set[j].punctaj
intai insa bagi fiecare set de problem in v!
complexitate: O(N*M); M=nr de seturi de probleme

[•Cosmin]

De ce sortezi cand faci knapsack? Am mai auzit ideea asta da mi se pare aiurea chestia cu sortarea. Daca vrei sa citesti despre 0/1 knapsack e in ambele linkuri ce le-am pus mai sus.

[•vially]

M-am apucat si eu de curand de informatica sia s vrea sa stiu cum pot sa declar un numar de 100 de cifre in c++  

[•svalentin]

M-am apucat si eu de curand de informatica sia s vrea sa stiu cum pot sa declar un numar de 100 de cifre in c++  

Pai ideea e ca un poti sa declari un <numar> de 100 de cifre!!
Poti in schimb sa simulezi tu acest lucru. Adica ai un vector cu 100 de int-uri (int nr[103]) in care fiecare element din vector reprezinta cifra numarului.

exemplu:
pt 1234567
nr={7,6,5,4,3,2,1,0,0...}

Ideea e sa tii numarul invers, ca in cazul cand il aduni cu inca ceva si iti mai trebuie o cifra sa nu te complici.
Pe langa vectorul asta, mai trebuie sa tii minte si nr de cifre! (pt exemplu, nr_cif=7)

Apoi, pe vectori ca acestia simulezi si adunarea/ scaderea/ inmultirea.. (ce ai tu nevoie).

[•Twister]

Ma ca veni vorba; cum fac impartirea pe numere mari in pascal?

[•Cosmin]

Ca si in C numai ca schimbi in for i:=1 to n do din for (i=1;i<=n;i++) si chestii de genu asta . In cartea lui Francu o sa gasesti o implementare buna. Probabil o sa apara cat de curand un articol pe tema numerelor mari pe info.devnet.

[VladS]

In articolul de pe site "Aplicatii ale cautarii binare" scrie ca se foloseste cautare binara.

[•Twister]

void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{int i;

R[0]=0; C0[]=A[0];
for (i=A[0];i;i--)
     { SHL(R,1); R[1]=A[1];
        C=0;
        while (Sgn(B,R) !=1);
           { C++;
              Substract(R,B);
           }
      }
while (!C[C[0]] && C[0]>1) C[0]--;

}

Exact asta scrie in Francu; si eu nu inteleg, daca se gaseste un binevoitor care stie C si Pascal sa-mi traduca si mie va rog frumos...

[•druid]

Ahh... cum fac si eu rost de culegerea lui Francu? E online pe undeva... un link daca are cineva ar fi perfect  

[•domino]

Ahh... cum fac si eu rost de culegerea lui Francu? E online pe undeva... un link daca are cineva ar fi perfect  

O s-o integram pe site in curand.  

[•fbkk]

void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{int i;

R[0]=0; C0[]=A[0];
for (i=A[0];i;i--)
     { SHL(R,1); R[1]=A[1];
        C=0;
        while (Sgn(B,R) !=1);
           { C++;
              Substract(R,B);
           }
      }
while (!C[C[0]] && C[0]>1) C[0]--;

}

Exact asta scrie in Francu; si eu nu inteleg, daca se gaseste un binevoitor care stie C si Pascal sa-mi traduca si mie va rog frumos...

Implementarea mea in pseudo Pascal ar fi:

Cod:

procedure DivedeHuge(A,B,C,R: tiptablou);
var i;
begin
  R[0]:=0;
  C[0]:=A[0];
  i:=A[0];
  while (i <> 0) do
     begin
        SHL(R,1);
        R[1]:=A[1];
        C[i]:=0;
        while (Sgn(B,R) <> 1) do
           begin
              inc(C[i]);
              Scade(R,B);
           end;
        inc(i);
     end;

  while ( C[C[0]] <> 0 ) and ( C[0] > 1) do
      dec(C[0]);
end;

tiptablou : trebuie declarat ca un tip de tablou
SHL, Sgn si Scade: sunt functii pe care va trebui sa ti le implementezi
"Traducerea" codului nu implica corectitudinea acestuia, este doar o traducere "mot a mot" a codului pe care mi l-ai prezentat , imi pare rau NU am citit articolul lui Francu
Sper sa te ajute !

[•Twister]

MUltumesc mult de tot fbkk; btw ce clasa esti?

[•fbkk]

A X-a , De ce ?

[cristi8]

..voi cum afisati in C un numar real cu 2 zecimale nerotunjit ?

[•bogdan2412]

Cod:

printf("%.2f", x);

[cristi8]

Cod:

printf("%.2f", x);

 
asa il rotunjeste la alea 2 zecimale

Cod:

  float a = 1.148;
  printf("%.2f", a);

afiseaza 1.15

[•bogdan2412]

Da ai dreptate, dar oricum nu sunt rare cazurile in care un numar cum ar fi 1.15 este reprezentat in calculator ca fiind 1.1499999. Mai bine inmultesti deimpartitul cu 100 si faci impartirile pe int-uri.