Acum este Lun Apr 21, 2014 1:32 am
Text

Programare / Web Design

combinari de n luate cate k - OPTIM

Despre PHP, MySQL, HTML, C++, VB, JAVA etc.

combinari de n luate cate k - OPTIM

Mesajde Colegu » Mar Noi 02, 2004 7:47 pm

combinari de n luate cate k - OPTIM
cum se face chestia asta,da optim...
matematic stiu cum e(cred,e o regula a triunghiului)
da nu prea stiu cum s-o implementez..
ca daca iau o matrice de n pe n pierd spatiu de pomana..si la n suficient de mare o sa pierd resurse garla...
Colegu
 
Mesaje: 3692
Membru din: Mar Ian 29, 2002 2:00 am
Localitate: ingliş pliz.

Mesajde iLogiK » Mar Noi 02, 2004 8:21 pm

vrei sa afli valoarea ( n!/(n-k)!*k! parca era....), sau sa listezi fiecare combinare?
Avatar utilizator
iLogiK
 
Mesaje: 3189
Membru din: Mar Aug 12, 2003 10:37 pm
Localitate: Oradea / Timisoara

Mesajde kix » Mar Noi 02, 2004 9:22 pm

Vezi daca te ajuta ...

Cod: Selectaţi tot
//Combinari.java   
class Combinari   //   calculul combinarilor cu factoriale NU este bun !!!
{
   public static void main(String[] args)
   {
   // calculeaza toate C(n,0), C(n,1), ..., C(n,n)
   // cu formula: C(n,k)=(n-k+1)/k C(n,k-1) unde C(n,0)=1
   int cnk=1,n=4;
   System.out.print(cnk+" ");
   for(int k=1;k<=n;k++)
   {
      cnk=(n-k+1)*cnk/k;   // asa merge (se divide sigur prin k)
      System.out.print(cnk+" ");//   1 4 6 4 1   
   }
   //----------------------------------------------------
   cnk=1;   // atentie la operatiile cu numere intregi
   System.out.print("\r"+cnk+" ");   //         c(n,0)=1
   for(int k=1;k<=n;k++)    //   (4-1+1)/1*1=4/1*1=4*1=4
   {                  //   (4-2+1)/2*4=3/2*4=1*4=4
      cnk=(n-k+1)/k*cnk;   //   (4-3+1)/3*4=2/3*4=0*4=0   la fel c(4,4)
      System.out.print(cnk+" ");//   1 4 4 0 0   
   }
   //----------------------------------------------------
   // triunghiul lui Pascal: C(n,k)=C(n-1,k) + C(n-1,k-1)
   // pentru combinarile pe primele n niveluri (n+1=elemente)
   // folosesc o matrice triunghiulara !!!
   n=6;
   int[][] x=new int[n+1][];
   System.out.println("\rx.length = "+x.length);//x.length = 7
   for(int k=0;k<=n;k++)
   {                  // apare matrice triunghiulara
      x[k]=new int[k+1];   // x[0].length = 1 ...x[6].length = 7
      System.out.println("x["+k+"].length = "+x[k].length);
   }
   x[0][0]=1;
   for(int i=1;i<=n;i++)
   {
      x[i][0]=1;
      x[i][i]=1;
      for(int j=1;j<=i-1;j++) x[i][j]=x[i-1][j]+x[i-1][j-1];
   }
   for(int i=0;i<=n;i++)
   {
      System.out.println();
      for(int j=0;j<=i;j++) System.out.print(x[i][j]+" ");
   }
   }//main()
}//class
/*
1 4 6 4 1
1 4 4 0 0
x.length = 7
x[0].length = 1
x[1].length = 2
x[2].length = 3
x[3].length = 4
x[4].length = 5
x[5].length = 6
x[6].length = 7

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1 Process Exit...
*/
?!?!?!
Avatar utilizator
kix
 
Mesaje: 25
Membru din: Sâm Aug 28, 2004 8:58 am
Localitate: Constanta

Mesajde Colegu » Mie Noi 03, 2004 6:53 am

mersi kix,cu triunghiul lui pascal voiam sa aflu...
da n-am auzit de matrice triunghiulara si d-aia am intrebat..
ma uit pe codul tau acu si vad ce inseamna asta..
danke!
Colegu
 
Mesaje: 3692
Membru din: Mar Ian 29, 2002 2:00 am
Localitate: ingliş pliz.

Mesajde ThrillSeeker » Sâm Noi 13, 2004 3:05 am

.. backtracking ?? ?? Poate nu e asa de optim pe cat vrei tu dar merge inkis .
Avatar utilizator
ThrillSeeker
 
Mesaje: 439
Membru din: Dum Iul 11, 2004 3:10 pm
Localitate: cache software


Înapoi la Programare / Web Design

Autentificare

Autentifică-mă automat la fiecare vizită