Hello!

Irtak egy par felezmerolegeses megoldast latom, szerintem mindenesetre
egyszerubb a kovetkezo:
3 pont -> Ismered x,y koordinatakat

Kor: (x-u)^2 + (y-v)^2 = R^2

A 3 pont koordinatai teljesitik az egyenletet => abban 3 ismeretlen
van: Kor kp-janak x,y koordinataja: u,v es sugara: R

3 egyenlet, 3 ismeretlen => megoldhato

Tehat szepen egyikbol a masikba egy-egy ismeretlent kifejezve megoldod
az egyenletrendszert.

Udv

On 15 Feb 02, at 10:43,  wrote:

> > Felado :  [International]
> 
> > algoritmust keresek 3 egysiban levo pontra kene kort rajzolni
> > kellene a sogar es a kozeppont
> 
 ...
> Mivel a haromszok koreirhato korenek kozeppontja az oldalfelezo
> merloegesek metszepontjaban talalhato, ezert ket oldalra meroleges
> allitva megkaphatjuk ezek metszespont helyvektorat (jelolje m_):

Sziasztok!

Ketten is ugy lattatok neki, mintha szerkeszteni kellene. Persze igy
is kijon a megoldas, de azt hiszem, egyszerubb az alapdefiniciot
hasznalni: A kor azon pontok mertani helye, amik a kozepponttol azonos
r tavolsagra vannak (a sikban). Szoval olyan pontot keresunk, amik
mindharomtol azonos tavolsagra vannak. Ez a tavolsag mellesleg pont a
sugar.

A harom pont legyen az (ax,ay), (bx,by) es (cx,cy). Az egyszerubb
szamolas miatt toljuk el az origot mondjuk az A-ba, igy vegulis (0,0)
(b1,b2) es (c1,c2) lesznek a pontok, ahol b1=bx-ax, b2=by- ay, stb.

A keresett kozeppont az (x,y) pont (az A-ba tolt koordinata-
rendszerben), ami mindharomtol azonos tavolsagra van. Tehat egyszeruen
a Pitagorasz tetel szerint:

r^2 = x^2+y^2 = (x-b1)^2+(y-b2)^2 = (x-c1)^2+(y-c2)^2

ez valojaban ket egyenlet (ha az r^2-et nem tekintem), csak egy 
sorba irtam. Az elso egyenletbol ez jon:

x^2-(x-b1)^2 = (y-b2)^2-y^2
x^2-x^2+2x*b1-b1^2 = y^2-2y*b2+b2^2-y^2
2x*b1=b1^2+b2^2-2y*b2

szoval:

x = (b1^2+b2^2)/(2*b1) - (b2/b1)*y

A masik egyenletbol termeszetesen ugyanigy kijon ez is:

x = (c1^2+c2^2)/(2*c1) - (c2/c1)*y

Ebbol a ket egyenletbol y-t konnyen ki lehet fejezni:

y = [ (b1^2+b2^2)/(2*b1) - (c1^2+c2^2)/(2*c1) ] / [b2/b1 - c2/c1]

kozos nevezore hozva, hogy csak egy osztas maradjon:

y = [ c1*(b1^2+b2^2) - b1*(c1^2+c2^2) ] / [ 2*(c1*b2 - c2*b1 ) ]

Ezt visszahelyettesitve kiszamithato lenne az x is, de kar vele
veszodni, mivel teljesen szimmetrikus a dolog x-re y-ra, igy siman fel
lehet irni x-et az y mintajara behelyettesites nelkul:

x = [ c2*(b1^2+b2^2) - b2*(c1^2+c2^2) ] / [ 2*(c2*b1 - c1*b2) ]

Szoval kesz is vagyunk, megvan az (x,y) kozeppont, es az sqrt(x^2+y^2)
sugar is. Persze az eredeti koordinatarendszerbe visszatolva a
kozeppont (x+ax,y+ay) lesz!

Istvan

On 14 Feb 02, at 21:33,  wrote:

> Sziasztok!
> 
> Kellene nekem valami magyar nyelvu, ertheto backtracking es rekurzio
> leiras...
> Algoritmus illetve peldaprogik C-ben...

Szia!

A rekurzio nagyon egyszeru, pont ugyanaz, mint a matekban a teljes
indukcio: a problemat sajat magaval oldod meg. Ez igy persze nem
ertheto, vegyunk egy peldat:

A faktorialis nem rekurzios definicioja ez: Pozitiv egesz N-re N! (N
faktorialis) az a szam, amit az 1-tol N-ig tarto egeszek
osszeszorzasaval kapunk. Ezt at lehet ultetni rekurziv formaba is:
Ha tudjuk (N-1)! erteket, akkor N! azonos lesz N es (N-1)! 
szorzataval. Ahhoz, hogy a teljes rekurziv definicio meglegyen, 
annyit kell meg hozzatenni, hogy tudjuk azt is, hogy 1! = 1.

Mindez programmal megvalositva:

int factor(int n)
{
        if (n==1)
                return 1;
        else
                return n*factor(n-1);
}

(ez a fenti kod persze nem bombabiztos, mert negativ szamokra meg 0-ra
hulyeseget csinal, valamint viszonylag gyorsan tul is csordul, de az
most nem problema.)

Altalanossagban is hasonlo utat kell kovetni: meg kell fogalmazni a
feladat rekurziv definiciojat, amibe beletartozik az is, hogy a
feladat legegyszerubb fajtajat hogyan kell megoldani onmagaban, es
utana mar nagyon egyszeru mindebbol kodot gyartani.

Vegyunk egy masik, nem ennyire evidens peldat is: Hogyan kell egy
szamot atkonvertalni ascii stringge mondjuk 10-es szamrendszerben?
Szoval ha a szam maga a 0x1000 (4096), akkor azt a stringet kell
eloallitani, hogy "4096".

Egy 10-nel kisebb szambol ugy tudunk stringet csinalni, hogy a '0'
kodjahoz hozzaadjuk a szam erteket, es ez lesz a string egyetlen
betuje (mogotte zaro nulla). Nagyobb szambol tobbjegyu string lesz,
meghozza ugy, hogy az elso jegyek string-je megegyezik a szam
tizedreszenek (egesz osztas!) a stringjevel, az utolso jegy pedig a
10-zel osztas maradekanak kodda konvertalt betuje lesz.

char *decstr(int n, char *buf)
{
        if (n<10) {
                *buf++ = '0' + n;
                *buf = 0;
                return buf;
        } else {
                buf = decstr(n / 10, buf);
                return decstr(n % 10, buf);
        }
}

Megint csak ez a kod nem figyel semmi puffertulcsordulast, de ez
persze konnyen megoldhato. Kicsit mas szervezessel meg lehetne
sporolni a masodik decstr() hivast, de igy erthetobb, ezert igy
hagytam.

Fontos dolog, hogy tisztaban legyunk azzal, hogy mi a rekurzio soran
az invarians, nem valtozo dolog, es mi az, amit maga a rekurziv kod
modosithat. Statikus valtozokat altalaban nem szabad hasznalni, mivel
a problema rekurziv megfogalmazasakor tipikusan kihasznaljuk azt, hogy
az egyszerubb problema megoldasanak nincs mellekhatasa. Ez auto
(stack) valtozok hasznalataval minden tovabbi nelkul teljesul. Neha
viszont szukseg van mellekhatasra is, ilyen volt a masodik peldaban a
buf valtozo modositasa, vagyis hogy a rutin visszaadja, hogy hol van a
kialakult string vege, hova kell a maradekot irni. Ezt egyszerubb lett
volna egy globalis (de legalabbis statikus) buf valtozoval csinalni,
de valahogy viszolyogtam tole ;)

Lassan kimeritem a sorlimitet, ugyhogy a backtrack-rol majd 
holnap...

Istvan