mindig paros szam legyen

Algoritmusok

Sziasztok,

A problemam a kovetkezo lenne. Kellene irnom egy algoritmust egy hianyos egyenletre. Adott egy n termeszetes szam (N), melyre igaz, hogy n => 2. Ha elosztom kettovel, minden esetben egy m termeszetes szamot kell, hogy kapjak, melyre igaz kell, hogy legyen n > m. Lenyegeben van egy hianyos egyenletem ahol n erteket kellene varialnom mielott elosztom kettovel.

Nos az tiszta sor, hogy ha csokkentem az erteket 1-gyel egy paratlannak, akkor az paros lesz, csakhogy n erteke lehet paros is kezdetben, ekkor viszont paratlanna teszem es ha elosztom kettovel, akkor mar nem a termeszetes szamok halmazan leszek. (ugye vissza is kellene ellenoriznem kesobb) Valamint, ha megszorzom 2-vel, akkor egeszen biztos, hogy paros szamot kapok, de akkor meg nem lesz igaz, hogy n > m.

Sajnos elagazast nem hasznalhatok, hogy megnezzem elotte a parossagot majd csak paratlan eseten csokkentsem 1-gyel. Eloszor fuggvenyeken agyaltam, de ott is rendszerint tortszamokat kaptam az pedig nem jo. Mar az is megfordult a fejemben, hogy nincs ra megoldas, de talan masnak szelesebbek az ismeretei mint nekem. :-)

Meg annyit, hogy ha esetleg valaki biztos lenne benne, hogy nincs megoldasa, kernem, hogy erositse meg a gyanumat.

Koszonom elore is a segitseget, javaslatokat :-)

Szerk: bocsanat ezt megkotest lefelejtettem: m => 1, tehat m nem lehet kisebb mint 1

  • 2572 megtekintés

( oattila | 2006. 04. 02., v – 18:52 )

Azt hiszem pontosan nem értem a kérdést, de nézd meg ez jó lenne-e neked:
int m,n;
m=n>>1;

( uid_4278 | 2006. 04. 02., v – 18:54 )

m=(n-n%2)/2;
tehat n bol kivonod az n kettovel torteno osztas utan maradt maradekat (paros szam eseten a 0-t, paratlan eseten az 1-et) majd osztod 2vel.
valami ilyesmire gondoltal?

( Morzel | 2006. 04. 02., v – 18:56 )

Nekem sem tiszta. Meg tudod adni a feladat pontos specifikációját?

Morzel

( gd | 2006. 04. 02., v – 18:59 )

Egyáltalán milyen nyelvről van szó? (És az m=1 nem elégíti ki a feltételeket?)

( cln | 2006. 04. 02., v – 18:59 )

Esetleg azt is lehet nézni hogy mi az utolsó számjegy, mert az csak
1. esetben 0,2,4,6,8
2. esetben 1,3,5,7,9 lehet.
Elég gyalogos módszer, de eccerű.

ELaci

( oattila | 2006. 04. 02., v – 19:19 )

m=((n or 1) -1)/2
C-ben:
m=(n|1-1)/2;

( rigidus | 2006. 04. 02., v – 23:39 )

Sziasztok,

Eloszor is koszonom az eddigi valaszaitokat, figyelmeteket. :-)

Megprobalom megegyszer leirni a problemat. Van egy 9 ismeretlenes egyenlentrendszerem ahol ez egy reszproblema lenne. Annak nem latom ertelmet, hogy leirjam ide az egeszet, mert igy is 11 A4-es oldalon van az egesz es valszeg hamar kihalna ez a topik. :-)

Ez egy reszfeladat lenne ahol egy masik egyenletrendszerbol fogom megkapni n erteket es m fog tovabblepni egy kovetkezobe.

Eloszor nem akartam leirni, hogy meddig jutottam vele, mert lehet, hogy teljesen rosszul kozelitettem meg es nem akartam vele vakvaganyra terelni senkit rogton az elejen.

Azert nem lehet elagazast alkalmazni, mert az egyiranyu ill. az egyenletben nem tudom megfogalmazni. Az algoritmus resze itt igazabol nem is erdekes, az mar nem okoz problemat ha az egyenletem hianyzo darabkaja meg van.

Tehat, en arra gondoltam, hogy n erteket parossa teszem azzal, hogy megszorzom 2-vel, csokkentem az erteket egy ujonnan felvett ismeretlennel ami legyen x, elosztom kettovel, majd megkapom m-et. Itt a lenyeg az az x erteke. Ime az egyenlet:

m = (2n-x)/2

Ugye x nem lehet paratlan szam mert, akkor az egesznek nem volt semmi ertelme, ujbol paratlan szamot osztanek kettovel ill. mivel ez egy uj ismeretlen valahogyan meg kellene hataroznom az erteket. Az egyeduli amit ismerek az n erteke az osszes tobbi mar azon mulik, hogy milyen erteket vesz fel. Tehat, a fentiek ismereteben atrendeztem az egyenletet es megprobaltam kifejezni n ertekebol x-et:

x = 2n-2m

El kell tuntetni m-et, vagyis behelyettesitem a fenti kifejezest:

x = 2n-2(2n-x)/2
x = 2n-2n-x

es megkapom, hogy x = x ami megnyugtato, de korant sem kielegito. :D

En az x-nek egy olyan kifejezesere gondoltam ahol n-tol fugg az x erteke, pl ilyen lenne az igazsagtablazata:

ha n = 1; akkor x = 2; igy m = 1
ha n = 2; akkor x = 2; igy m = 2
ha n = 3; akkor x = 4; igy m = 2
ha n = 4; akkor x = 4; igy m = 4
ha n = 5; akkor x = 6; igy m = 4

Az vilagos, hogy a fenti megoldhato modulus-szal, de akkor m ertekebol nem tudom visszaellenorizni az egyenletet. Nekem az az erzesem, hogy ez nem megoldhato, ezert gondoltam, hogy talan mas ismer olyan megoldast (szabalyt) amit esetleg en nem, vagy mar nem emlekszem ra.

Az, hogy az algoritmus milyen nyelven lesz megirva az meg nem dolt el (valszeg C), de azt megirni mar csak a gyertya lesz a torta tetejen. Az mar egyedul is megy, itt a hangsuly a torta megsutese lenne. :-)

Koszonom ismetelten. :-)

---------------------
Ригидус а бетегадьбол

Ha jól értem akkor bármely n-t el kell osztani 2-vel úgy, hogy az eredmény egész legyen és m-ből egyértelműen megállapítható legyen n?
Ha az osztási műveletet helyettesíted egy bitenkénti eltolással n>>1, akkor tulajdonképpen megkapod a feltételeknek megfelelő m-et. Az eltolás során viszont elveszik a legértéktelenebb bit (páros/páratalan) ezért ezt már nem lehet az eredeti n-et visszanyerni. Ez egyszerűen belátható ha pl.: addig végzed ezt a műveletet (n->m, n=m, n->m, n=m, ...), amíg igaz n>=2 feltétel, ekkor a végén m=1 és te ebből szeretnéd visszanyerni az eredeti n-et:
m=1, n=3432647823 vagy
m=1, n=3645365436 ...

Ha már segédváltozót használsz, akkor evvel az erővel eltárolhatnád az n eredeti értékét. Viszont könnyen beláthatod, hogy ha n értékét teszed párossá, akkor többet nem tudod visszanyerni algoritmussal az értékét, hisz természetes számból kétszerannyi van, mint páros számból.

jól mondja az előttem szóló: megszámlálhatóan végtelen sok a természetes számok halmazának számossága.
Egy ilyen feladathoz némi algebra előtanulmány nem árt.

Rigidus: a képlet valahogy így nézne ki: m = (n - (n mod 2))/2. Ebből ha csak m-et ismered nem fogod tudni kinyerni n értékét, ugyanis minden m-re két n is jó megoldást szolgáltat. Valami plusz információt tárolnod kell.

Lesesett (átfordítottam a problémát sé szerintem a következőt akarod), de valóban nem megoldható mert a páros számok számossága és a természetes számok számosága ugyanaz ezt valaki már írta. Ez pont olyan mint ha a hányados ismeretéből akarnád kitalálni, hogy mely két számot osztottad el egymással az hogy pl: n=6 végtelen sok hányadosból megadható. Ez így megoldhatatlan. Szűkitsd a dolgot. Nem alulhatározott az az egyenletrendszer? Mert akkor melózhatsz vele a végtelenségig.

Szerk:
Amit így leírsz ez egy alulhatározott egyenletet fog adni.

ha n = 1; akkor x = 2; igy m = 1
ha n = 2; akkor x = 2; igy m = 2
ha n = 3; akkor x = 4; igy m = 2
ha n = 4; akkor x = 4; igy m = 4
ha n = 5; akkor x = 6; igy m = 4

==> Ebből képtelenség visszafelé megállapítani n-t. Ha csak egyetlen olyan m is van, ami két n-ből is kijöhet, akkor nincs egyértelmű visszaút (a fv nem invertálható.)
nekem is az az érzésem, hogy nem megoldható, de még gondolkozom :)

martinj

( imp | 2006. 04. 03., h – 02:02 )

miután elveszítetted az n párosságára vonatkozó információt azzal, hogy kivontál belőle (n mod 2) -et, elosztod 2-vel, hogy egész m-et kapj, ebből az m-ből szeretnéd megmondani, hogy (n mod 2) mennyi volt? wtf?

( -Mr- | 2006. 04. 03., h – 12:54 )

Hali!

Ha jól értem neked az kell, hogy ha elosztod N-t akkor egész számot kapjál. Ha ehez nem kell görcsösen ragaszkodnod a kindulási N értékhez akkor ha N-t elosztod kettővel és elhagyod a maradékot, és az ekkor kapott M-t értéke neked megfelelő, akkor semmi gond. (Mivel az elején írtad hogy N értéke legalább 2 lehet, M értékének meg legalább 1-nek kell lenni, így az a kitétel, hogy N>M mindig teljesülni fog.)

Pl.:
N=2,M=1
N=3,M=1
N=4,M=2
N=5,M=2

Itt az a gond, hogy ha késöbb vissza akarnád konvertálni CSAK M értékéből az eredeti N-t (nem a módosított N-t), az sehogy sem lehetséges mivel elhagysz egy fontos információt az osztás után, és M ugyanazon értéket felvehet két különböző szám esetén is. Hacsak nem használsz valami kiegészitőt regisztert arra hogy jelezd a kindulási érték páros vagy páratlanságát, akkor a visszaellenőrzés nem lehetséges, ezt algoritmusal nem lehet megoldani.

-Mr-

Még itt kis számok esetén tényleg csak néhány vari van de 1000-es nagyságredeknél már borzalmas sok kombináció van ha pedig a visszafejtést nézed ott meg végtelen. Tök mindegy, hogy visz e magával segédváltozót vagy nem. egyszerűen a páros számokból is végtelen sok van. Ez végtelen variűció, megoldhatatlan.Ennyi. Ezt hívják alúlhatározott egyenletnek. Fizika feladatok megoldásénál azt szoktam csinálni hogy vagy megpróbálok kispórolni egy változót (túl kicsi elhenyagolható, vagy nem nagyn váltotatat a línearitáson), vagy egyet megmondom, hogy te pl 3 vagy és kész. Vagy bejön vagy nem. Mert ha egy egyenletrendszer alulhatározott nincs mit vele kezdeni. Ezzel a rögzítéssel meg tudom nézni hogy egyáltralán megoldható e, ha már megvan a változó valahogy.