[ nikitahigh @ 27.03.2011. 19:17 ] @
da li neko moze da mi pomogne oko sledeceg zadatka?Klasa graph je zadata u sledecem formatu:
class graph {
public :
graph();
~graph();
friend void polynomial (graph &);
private:
int n;
double p[11];
double s[10];
int a[10][10];
};
Broj n cvorova grafa G birati metodom slucajnog izbora (2<=n<=10).Elemente a[i ][j] matrice susedstva grafa G birati takodje metodom slucajnog izbora : a[i ][j]=a[j][i ] ako je i not= j; i a[i ][j]=0 ako je i=j.
Upotrebom funkcije void polynomial(graph &) prikazati karakteristicni polinom P_G(\lambda)=|\lambda I-A| u obliku (1,0,a_2,...a_n);
(niz p[11] sadrzi koeficijente P_G(\lambda)).
Upotrebom funkcije void matrix(graph &) prikazati matricu susedstva grafa G u sledecem formatu:
n m a_{21} a_{31} a_{32}...a_{n1} a_{n2}...a_{n,n-1};
gde je :
a)n broj cvorova grafa G;
b)m=|a_2| broj grana grafa G.
Ako neko zna kako se ovo radi,ili moze da uradi ovaj zadatak,neka mi posalje na mail:[email protected]
Hvala!

[Ovu poruku je menjao Mihajlo Cvetanović dana 27.03.2011. u 21:39 GMT+1]
[ Nedeljko @ 28.03.2011. 09:13 ] @
Što se tiče broja grana, to je broj jedinicaa u matrici susedstva podeljen sa 2 ili broj jedinica iznad (odnosno ispod) glavne dijagonale. Što se ostalog tiče, tačka 6 pravilnika nalaže da prvo sam pokušaš nešto da uradiš i da napišeš dokle si stigao.
[ nikitahigh @ 30.03.2011. 07:34 ] @
Da li sam ovo dobro odradila?

Code:
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int determinanta (int mat[10][10], int n, int br);
int rek (int mat[10][10], int n);
double Izracunaj(double niz[11], double n, double vr);
void polinomtal(double jednacine[12][12], double *p, int n);
void spektar (double *s, double p[12], int n);
void matrix (int mat[10][10], int n);


void main() {
    int i,j,n,k,vrednost;
    int mat[10][10];
    double jednacine[12][12];
    double p[11], s[11];
    double koef;
    n=1;
    srand((unsigned)time(NULL));

    //Generisanje velicine matrice!
    while (n<3) n=int((double(rand())/RAND_MAX)*9) + 1;

    //Nule na glavnoj dijagonali i u nizovima p[] i s[]!
    for (i=0;i<n;i++) mat[i][i]=0;
    for (i=0;i<11;i++) p[i]=0;
    for (i=0;i<10;i++) s[i]=0;

    //Generisanje matrice!
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            if (i>j) 
                mat[i][j]=mat[j][i]=int((double(rand())/RAND_MAX)*2);

    //Ispis matrice!
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++)
            cout<<mat[i][j]<<"  ";
        cout<<endl;
    }

    //Generisanje sistema jednacina za dobijanje karakteristicnog polinoma!
    for (i=0;i<12;i++) 
        for (j=0;j<12;j++) jednacine[i][j]=0;
    vrednost=0;
    for (k=0;k<=n;k++) {
        koef=1;
        for (i=0;i<=n;i++) { jednacine[k][i]=koef; koef=koef*vrednost; }
        jednacine[k][11]=determinanta(mat,n,-vrednost);
        vrednost++;
    }

    //Racunanje karakteristicnog polinoma!
    polinomtal(jednacine,p,n);
    
    //Racunanje resenja karakteristicnog polinoma!
    spektar (s,p,n);

    //Trazeni ispis!
    matrix(mat,n);
     
    cin>>i;
}

int determinanta (int mat[10][10], int n, int br){
    int i;
    for (i=0;i<n;i++) mat[i][i]=br;
    return rek(mat,n);
}

int rek (int mat[10][10], int n){
    int s=0, i;
    if (n==3) {
        s+=mat[0][0]*mat[1][1]*mat[2][2];
        s+=mat[0][1]*mat[1][2]*mat[2][0];
        s+=mat[0][2]*mat[1][0]*mat[2][1];
        s-=mat[0][0]*mat[1][2]*mat[2][1];
        s-=mat[0][1]*mat[1][0]*mat[2][2];
        s-=mat[0][2]*mat[1][1]*mat[2][0];
        return s;
    }
    else {
        for (i=0;i<n;i++) {
            int pom [10][10];
            int k,m,a=0,b=0,znak;

            for (k=1;k<n;k++)
                for (m=0;m<n;m++) {
                    if (m==i) continue;
                    pom[a][b++]=mat[k][m];
                    if (b==n-1) { b=0; a++; }
                }

            if (i%2==0) znak=1; else znak=-1;
            s+=mat[0][i]*znak*rek(pom,n-1);
        }
    }
    return s;
}

double Izracunaj(double niz[11], double n, double vr){
    double s=0, x=1;
    for (int i=0;i<=n;i++) { s+=niz[i]*x;  x*=vr;}
    return s;
}

void polinomtal(double jednacine[12][12], double *p, int n) {
    int i,j,k,m;

    /*//Ispis sistema jednacina! Oblik : a0+x*a1+...=det(x)
    for (i=0;i<=n;i++) {
        for (j=0;j<=n;j++) cout<<jednacine[i][j]<<"\t";
        cout<<"    REZ:  "<<jednacine[i][11]<<endl;
    }*/

    //Resavanje sistema!
    p[0]=jednacine[0][11]; 
    cout<<endl;
    
    for (i=2;i<=n;i++)   {
        k=jednacine[i-1][i-1];
        for (int s=i;s<=n;s++){
            m=jednacine[s][i-1];
            for (j=i-1;j<=n;j++) jednacine[s][j]=jednacine[s][j]*k-jednacine[i-1][j]*m;
            jednacine[s][11]=jednacine[s][11]*k-jednacine[i-1][11]*m;
        }
    }    

    /*//Ispis svedenog sistema jednacina!    
    for (i=0;i<=n;i++) {
        for (j=0;j<=n;j++) cout<<jednacine[i][j]<<"\t";
        cout<<"    REZ:  "<<jednacine[i][11]<<endl;
    }*/

    //Popunjavanje p[] iz sistema!
    for (k=n;k>0;k--) {
        int s=0;
        for (i=0;i<=n;i++) if (i!=k) s+=jednacine[k][i]*p[i]; //Ovo smem da radim jer je p[i]=0!
        p[k]=(jednacine[k][11]-s)/jednacine[k][k];
    }
    //Ispis karakteristicnog polinoma!
    cout<<"Karakteristican polinom: ";
    for (i=0;i<=n;i++) cout<<p[i]<<"  ";
}

void spektar (double *s, double p[12], int n) {
    double min,max,res,res2,dres,dtek,tek;
    int i,k;

    //Racunanje nula karakteristicnog polinoma! R[-500;500]
    res=Izracunaj(p,n+1,-11.0);
    dtek=0.001;
    k=i=0; 
    max=10.0;
    for (tek=-10.0; tek < max ;tek=tek+dtek) {
        res2=Izracunaj(p,n+1,tek);
        if (res*res2<0)  { s[i++]=(res+res2)/2; k++; } 
        res=res2;
    }

    //Ispis resenja karakteristicnog polinoma!
    cout<<endl<<endl<<"Resnje karakteristicnog polinoma:"<<endl;
    for (i=0;i<k;i++) cout<<s[i]<<"  ";
}

void matrix (int mat[10][10], int n){
    int i,j;
    cout<<endl;
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++)
            if (i>j) cout<<mat[i][j]<<"  ";
        cout<<endl;
    }
}



[Ovu poruku je menjao Mihajlo Cvetanović dana 30.03.2011. u 10:21 GMT+1]