[ mrakodol @ 08.06.2006. 16:18 ] @
1.Dati su prirodan broj n(n>3) i skup A od n tacaka u ravni. Odrediti tri razlicite tacke skupa A tako da razlika izmedju povrsine kruga ogranicene kruznicom koja prolazi kroz prolazi kroz te tri tacke i povrsina trougla sa tjemenima u tim tackama bude najmanja. Ako takvih trojki tacaka ima vise onda ih odrediti sve.

2.Dati su prirodni brojevi m i n, i polinom P(x) stepena n svojim koeficientima uz X (na i) , a i=0,1,2,...,n. Odrediti koeficiente polinoma P(na m)(x) razvijenog po stepenima od x.
*P(na m)(x)-citati P na m od x
**X (na i)-citati X na i

Ovi zadaci su mi za zadacu pa vas molim da mi pomognete!Ili barem matematicki objasnite kako bi se to moglo rijesiti a sam cu da pisem program..jednostavno ne razumijem teks zadatka!
[ Igor Gajic @ 09.06.2006. 16:38 ] @

Sto se tice prvog zadatka.

Potrebne su ti tri ugnezdjene petlje tako da isprobavas sve moguce kombinacije tacaka,
svaka petlja ide od 0,...,n-1.

Proveravas da li su izabrane tri tacke razlicite, i ako jesu onda izracunavas:

povrsina trougla
Code:

Ptr=(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)/2


za krug je mnogo komplikovanije

Code:

M11=x1*y2+y1*x3+x2*y3-x3*y2-x1*y3-x2*y1
M12=y2*(x1^2+y1^2)+y1*(x3^2+y3^2)+y3*(x2^2+y2^2)-y2*(x3^2+y3^2)-y3*(x1^2+y1^2)-y1*(x2^2+y2^2)
M13=x2*(x1^2+y1^2)+x1*(x3^2+y3^2)+x3*(x2^2+y2^2)-x2*(x3^2+y3^2)-x3*(x1^2+y1^2)-x1*(x2^2+y2^2)
M14=x2*y3*(x1^2+y1^2)+x1*y2*(x3^2+y2^2)+y1*x3*(x2^2+y2^2)-x2*y1*(x3^2+y2^2)-x3*y2*(x1^2+y1^2)-x1*y3*(x2^2+y2^2)


Ako je M11<1e-6 tj. skoro nula, tacke se nalaze na pravoj!

Pkr=((M11^2+M13^2)/(4*M11)+M14/M11)*Pi


E sad, ako je DeltaP manja od prethodnih mozes te tacke da smestas u listu,niz ili sta ti je vec lakse.
Toliko, sad sve sto treba jeste da isprogramiras.

Drugi zadatak ti je skroz nejasan.

Pozdrav
[ Mali Misha @ 09.06.2006. 17:26 ] @
Citat:
Potrebne su ti tri ugnezdjene petlje tako da isprobavas sve moguce kombinacije tacaka,
svaka petlja ide od 0,...,n-1.

Ček, zar ne bi i samo
Code:
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            for(k=j+1;k<n;k++)
            {
                printf("%d %d %d\n",i,j,k);
            }

pokrilo sve mogucnosti?


*edit
A za krug može da posluži i , , gde je ugao izmedju i tj. . Rastojanje b bi bilo rastojanje između A i C. A, B i C su date tačke.

- Vektor
- Skalarni proizvod
- Duzina .

Kao što reče Igor, obrati pažnju na slučajeve kada su tačke (skoro) kolinearne, jer će sam radijus kruga pa i njegova površina u tom slučaju biti veliki a površina trougla stvarno sićušna. Prepoznaćeš ih po jako maloj apsolutnoj vrednosti sinusa. Njihovo isključivanje bi moglo biti rešeno vraćanjem negativne vrednosti umesto vrednosti površina, što bi bilo znak da te rezultate treba ignorisati. Ovim bi se isključili i slučajevi kada beta nije blisko samo 180° nego i 0° ali priča je slična.

[Ovu poruku je menjao Mali Misha dana 09.06.2006. u 19:50 GMT+1]
[ Igor Gajic @ 09.06.2006. 19:11 ] @
Da, u pravu si sto se tice petlje. Moj nacin dao bi dosta ponovljenih trojki tacaka.

Code:

    for(i=0;i<n-2;i++)
        for(j=i+1;j<n-1;j++)
            for(k=j+1;k<n;k++)
            {
                printf("%d %d %d\n",i,j,k);
            }


Malo bolja petlja.
[ Igor Gajic @ 11.06.2006. 16:37 ] @


Koliko sam mogao da razumem drugi zadatak, tebi je dat polinom P, i trebas da ga podignes na stepen m,
i da ispises njegove koeficijente.

Prvi nacin za to je:

Code:

    int const dim1=3,dim2=3;
    int pol1[dim1]={2,1,1}; //prvi
    int pol2[dim2]={2,1,1}; //drugi
         int pol3[5];   //rezultat


    for(int i=0;i<dim1+dim2-1;i++) pol3[i]=0;  //inicijalizacija rezultata

    
        //mnozenje
    for(int i=0;i<dim1;i++)
        for(int j=0;j<dim2;j++)
            pol3[i+j]+=pol1[i]*pol2[j];

    for(int i=0;i<dim1+dim2-1;i++) printf("%d ",pol3[i]);



Nije tesko da od ovog primera napravis f-ju koju pozoves m puta i dobijes konacan rezultat.

Drugi nacin je da uradis FFT nad koeficijenta polinoma P. Pa da ih mnozis m puta. Pa onda da uradis IFFT.
Ali pretpostavljam da ti nije vredno truda.