Program ami eldönti ha egy négyzet egy másik négyzeten belül van (C-ben)?

Vizsgáld meg mindet minddel. Sosem írtál ilyen algoritmust?

ciklus i=0tól n-1ig:

__ciklus j=i+1től nig:

__ _ha fedi(negyzet[i], negyzet[j]) akkor ++fedett

> meg kell nézni az összeshez képest mindegyiket.

Akkor tedd ezt. :)

ciklus i = 1..N

ciklus j = 1..N

ha (i != j) akkor megnézed_amit_kell(i,j);

ciklus vége

ciklus vége

#2 vagyok

Ja, igen... Wampa algoritmusa optimálisabb, ő nem számol mindent 2x, mint én :))

Persze. Akkor játsszuk végig:

negyzet tömbben van a 6 négyzeted, 0..5-ig.

Megfogja az első négyzetet (i=0). Melyikkel kell összehasonlítani? A másodikkal(j=i+1=1), a harmadikkal(j=2)...és az utolsóval(j=n=5).

Ezután fogjuk a másodikat(i=1). Az elsővel már megvolt, önmagával nem kell -> j=2-től n-ig.

Az utolsó előttit már csak az utolsóval kell hasonlítani. i=4, j=5.

Az utolsót már nem hasonlítjuk senkihez.

Remélem nem csúsznak el a sorok:

Pl.

i=0; j=1---->5

i=1; j=.2--->5

i=2; j=..3-->5

i=3; j=...4->5

A lényeg, hogy minden elemet összehasonlíts minden másik elemmel.

Mivel bármely "i-edik" elemre igaz, hogy az előtte levőkkel már minddel összehasonlítottad (mert korábban azok voltak az "i-edikek"), saját magával pedig sohasem hasonlítod össze, így a belső ciklus j-je mindig i+1-ről indul, tehát az "i-edik" elem után közvetlenül következő elemről. Ezen felül az utolsó elem sohasem lesz "i-edik", mivel nincs utána következő elem, minden előrébb elhelyezkedővel pedig már össze lett hasonlítva, tehát ezt már nincs mivel összevetni.

Ahogyan az előző válaszoló is szemléltette:

Ha van öt darab almám, és mindet össze akarom hasonlítani mindegyik másikkal, akkor

1. Fogom az első almát. Összehasonlítom a másodikkal, majd a harmadikkal, a negyedikkel, majd az ötödikkel.

2. Fogom a második almát. Az elsővel nem hasonlítom össze, hiszen azt már megtettem az előbb. Magával szintén nem. Tehát a következő (j=i+1), harmadik almával, ezt követően a negyedikkel fogom összehasonlítani, majd az ötödikkel.

3. Fogom a harmadikat. Ugyanez a helyzet: Az első kettővel már összehasonlítottam, magával nincs értelme, így a negyediktől kezdem.

4. Fogom a negyedik, utolsó előtti almát. A helyzet változatlan, vagyis amivel már összehasonlítottam, azzal felesleges volna mégegyszer megtennem, így az utolsó, ötödik almával hasonlítom össze (nem speciális eset, j=i+1 itt is igaz)

5. Az utolsó alma viszont speciális eset, mivel ezt az előzőekben már mindegyik másikkal összehasonlítottam, így ezzel egyszerűen nem szükséges foglalkoznom.

Itt a "fogom az almát" a külső ciklus, az "összehasonlítom az X-edikkel" pedig a belső. Latható, hogy

- "i < tömb_mérete" helyett "i < tömb_mérete - 1" lesz a külső ciklusfeltétel, mert az utolsó almát "már nem fogom"

- A belső ciklus mindig "j = i + 1" -től indul, mert a korábbi almákkal már megtörtént az éppen megfogott alma összehasonlítása, önmagával meg nincs értelme összevetni.

Ennyi a trükk, semmi több. A belső ciklusmagban szépen összehasonlítod a squares[i] -t squares[j] -vel, és az eredménnyel kezdesz valamit (növelsz egy számlálót).

Kicsit hosszúra sikeredett, de bízom benne, hogy egyúttal könnyen érthetőre is.