Négyzetbejárás
2013-03-14T15:26:49+01:00
2013-03-15T16:05:44+01:00
2022-07-19T02:46:47+02:00

  • igazad van, úgy látszik egyre butább leszek (és/vagy figyelmetlenebb, de valamiért nekem csak 2 irány maradt meg, azaz az, hogy mondjuk jobbra és le, és/vagy olvasni sem tudok, és/vagy ...)
    Mutasd a teljes hozzászólást!
  • ...hiszen akkor független lenne a lehetséges utak száma a sorok számától...
    A N^(M-1) képlet nem független a sorok (N) számától.

    ... ha az első sor első oszlopában levő mezőből akarunk eljutni az utolsó oszlop első sorában levőbe, akkor azt csak jobbra haladással tudjuk megtenni, azaz csak 1 lehetséges megoldás van, nem?
    Nem, pl. 4×5-ösnél egy 12 lépéses lehetőség.
    0 * * * 12 1 * 7 8 11 2 3 6 9 10 * 4 5 * *


    Az N×M-es téglalapban - mely mátrixnak, vagy gráfnak is tekinthető - csak jobbra, fel és le lehet lépni.
    Szerintem további feltétel lenne - amire a kérdező utalt, de nem egyértelműen - hogy a fel és le lépések közvetlenül nem követhetik egymást.
    Minden oszlopból - az utolsó kivételével - egyszer át kell lépni jobbra a következőbe.
    Egy oszlopon belül - a feltétel miatt - csak fel, vagy csak le mozoghatunk (fel is út, le is út!), esetleg se fel, se le, mert mindjárt továbblépünk az azutáni oszlopba.

    Egy útvonal egyértelműen megadható azzal, hogy minden oszlopban - az utolsó kivételével - megjelöljük azt a mezőt, ahonnan majd átlépünk jobbra a következőbe. Ezek könnyen összeszámolhatók: minden oszlopban N lehetőség van, tehát N*N*...*N (M-1-szer), vagyis N^(M-1).

    Lényeges, hogy amikor beléptünk (balról) egy oszlopba, akkor már csak egyféleképpen lehet függőleges mozogni. Pl. ha a jobbra lépésnél egy oszlop 5.mezőjére érkeztünk és a 2. mezőről fogunk majd jobbra átlépni a következő oszlopba, akkor 3-at kell lépnünk felfelé (fel-fel-fel), más lehetőség nincsen, fel-fel-fel-fel-le nem jöhet szóba a feltétel miatt, de akárhány sor is van le-le-fel-fel-fel-fel-fel sem lehet.
    Mutasd a teljes hozzászólást!

  • N^(M-1)
    (Egyébként az első oszlop bármelyikéről indulva és az utolsó oszlop bármelyikét megcélozva ugyanez a megoldás.)


    ez utóbbi megjegyzésedben biztos vagy, vagy csak én nem értem?

    hiszen akkor független lenne a lehetséges utak száma a sorok számától, nem?

    vagy másképpen nem értve: ha az első sor első oszlopában levő mezőből akarunk eljutni az utolsó oszlop első sorában levőbe, akkor azt csak jobbra haladással tudjuk megtenni, azaz csak 1 lehetséges megoldás van, nem?

    én
    az első oszlop bármelyikén
    az első sor bármelyik mezőjét értem (hasonlóan az utolsó oszlopra), vagy mit értsünk alatta?


    szerkesztve: vagy a képletben valójában N-nel a
    (cél és kezdő)sorszámok különbsége+1
    -et jelölted (feltéve, hogy a cél sorszám nem kisebb a kezdőnél)? (így kell értelmezni az általam kifogásolt megjegyzésedet?)
    Mutasd a teljes hozzászólást!
  • Gyakori eset a prog.hu oldalain, hogy a már eleve rosszul megértett román/szlovák/szerb nyelvű feladatot rossz magyar fogalmazásban továbbítják nekünk.
    Másik, amikor az eredeti magyar/angol szöveget nem akaródzik közzétenni, mert google-vel pillanatokon belül megtaláltatik a forrás és helyette kapunk egy félreértett, pongyola átfogalmazást.
    Ilyenkor a kérdéssel foglalkozó szerencsétlen balekoknak nagyobb fejtörést okoz a feladat rekonstrukciója, mint annak megoldása.
    ---------------------------------------------------------------------
    Ha már belekeveredtem a dologba (legközelebb jobban vigyázok), sikerült a 3 irányba lépéses változatra egy épkézláb - nem nehéz, de nem is triviális - feladatot összehozni.
    Az N×M-es (N sor, M oszlop) négyzetrácsban a bal-felső sarokból a jobb-alsóba szeretnénk eljutni és csak jobbra, fel, vagy le léphetünk.
    Annyi kiegészítés kell csak, hogy a le/fel (vagy fel/le) lépések nem jöhetnek közvetlen egymás után. (Mindez teljesen összhangban áll az általad megfogalmazottakkal, de a Te homályos előadásod akkor sem fogadható el.)
    Ilyen feltételekkel nem lesznek végtelen ciklusok és nagyon egyszerű a megoldás:
    N^(M-1)
    (Egyébként az első oszlop bármelyikéről indulva és az utolsó oszlop bármelyikét megcélozva ugyanez a megoldás.)
    Mutasd a teljes hozzászólást!
  • Már bocs, de a feladat eredeti szövegében hol van az, hogy nem lehet fel le fel le?

    Mert így tényleg végtelen
    Ugyanakkor, ha csak le és jobbra lehet menni, akkor 7!/(4!*3!)
    Mutasd a teljes hozzászólást!
  • Ez a feladat eredeti szövege amit mondtam.
    NxM négzetrácsban hányféleképpen tudunk a bal felsö sarokból a jobb also sarokba eljutni ha minden négyzetbe a fel jobbra és a le irányt használhatjuk(ahol lehet mert pl felsö sorba hiába megyek felfele)??
    Mutasd a teljes hozzászólást!
  • Az kevés, mert egy hosszabb zárt útvonalon is lehet körbe-körbe járni a végtelenségig.
    Nem lehetne a feladat eredeti, hiteles szövegét (magyarul van?) nyilvánosságra hozni?
    ----------------------------------------------------------------

    A csak összeadást igénylő módszer:

    A négyzetrács minden mezejébe beírjuk, hogy hányféleképp érhető el.
    Az indulási (bal-felső) mezőbe 1 kerül, a bal oldali oszlopba és a felső sorba szintén.
    A többinél pedig a bal és jobb oldali szomszéd tartalmát kell összeadni.

    A 4×5-ös esetben végül a következőt kapjuk:
    1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35

    Egyébként az említett alsó tagozatos szintet ne nézzük le, mert a feladatot lehet bonyolítani, pl.
    - menet közben a jobbra lépések száma soha ne legyen kevesebb a lefelé lépések számánál, vagy
    - nem lehet egymás után három egyformát lépni,
    és hasonlók,
    akkor az általános képlettel bajok lesznek, viszont a kisiskolás összeadogatósdi használható.
    Mutasd a teljes hozzászólást!
  • Ki van kötve tehát azt nem lehet hogy egy mezön le fel le fel le fel...
    Mutasd a teljes hozzászólást!
  • A 3 és 4 irányra nyilvánvalóan végtelen sok lehetőség van, de ha kikötnénk, hogy egy mezőre nem léphetünk többször, akkor sokkal nehezebb a kérdés és nem hiszem, hogy van rá általános képlet. Ellenben kezdő programozók számára a back-track algoritmussal való ismerkedéshez nagyon jó.

    A 2 irány - le és jobbra - egyszerű kombinációval számolható: (M-N-2 alatt az M-1), tehát 4×5-nél: 7 alatt a 3 = 35 eset. Konkrét példára - képlet nélkül - alsó tagozatos szinten is megoldható, az összeadáson kívül más műveletet nem kell hozzá ismerni.
    Mutasd a teljes hozzászólást!
  • Hello mindekinke itt van egy ujabb feladat amiben a segitségeteket kernem:

    Van egy NxM nagyságu negyzetrács.Az a kérdes hogy a bal felsö sarokból hány féle modon tudun a jobb also sarokba eljutha ha csak fel le és jobbra mehetünk?Hát ha mind a négy irányba??
    Agyaltam rajta ugyanis az a feladat hogy 2 iránny szerint is vizsgaljuk pld egy 4x5 negyzetrácsot és ott csak le és jobbra lehet menni nos a a 2n-1 képletre jottem ra ahol n a lehtseges negyzeteket jelöli a 4x5 esetben 18 mivel 2 mezöre alapból nem lepünk(bal felsö ,jobb alsó).De az NxM és 3 iránynál elakadtam kérlek segitsetek
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd