C# Feladat backtraking

Címkék
C# Feladat backtraking
2019-06-10T07:22:03+02:00
2019-06-11T19:18:54+02:00
2022-10-15T21:31:37+02:00
WarninG1
Sziasztok!

Lenne egy viszonylag egyszerű vizsga feladatom, de sehogyse tudom megoldani. Kérlek szépen ha tudjátok hogyan kell megoldani, segitsetek.

Igy szól a feladat:

Legyen n szék és n személy 1-től n-ig megszámozva. Kezdetben az i-edik személy az i-edik széken ül, de minden szomszéd összevesz. Képezzük a személyek összes olyan átültetését, amelyben az ellenségek között legalább egy, de legfennebb két másik személy ül.
Mutasd a teljes hozzászólást!
Át lehet írni static tömbösre is, persze:

static int[] elemek= { 1,2,3,4 }; static int elemekHossz=elemek.Length; static int[] ultetes=new int[elemekHossz]; static int ultetesHossz=0; static int UltetesbenKeres(int mit) { for (int i = 0; i < ultetesHossz; i++) if (ultetes[i] == mit) return i; return -1; } static bool Stimmel() { for (var i = 0; i < ultetesHossz; i++) { int pos = UltetesbenKeres(ultetes[i] - 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } pos = UltetesbenKeres(ultetes[i] + 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } } return true; } static bool Keres() { if (!Stimmel()) return false; if (elemekHossz == 0) return true; for(int i = 0; i < elemekHossz; i++) { ultetes[ultetesHossz] = elemek[i]; ultetesHossz++; elemekHossz--; elemek[i] = elemek[elemekHossz]; if (Keres()) return true; //elemek[elemekHossz] = elemek[i]; // már az van ott elemekHossz++; ultetesHossz--; elemek[i] = ultetes[ultetesHossz]; } return false; } static void Main(string[] args) { if(Keres()) { Console.Write(ultetes[0]); for (int i = 1; i < ultetesHossz; i++) Console.Write(", " + ultetes[i]); } Console.ReadLine(); }
Gyakorlatilag az első sor ("elemek") a bemenet. Mivel tömbből törölni, illetve a backtrack keretében a törlést visszacsinálni macerás (for ciklussal kéne pakolgatni az elemeket oda-vissza, esetleg valamilyen ArrayCopy-ra bízni ugyanezt), ezért a kód inkább az utolsó elemet teszi át a törölt helyére. A szimmetria viszont szépen látszik, ahogy a backtrack keretében a sikertelen kísérlethez vezető előkészítő lépéseket játssza le visszafele a program.
Mutasd a teljes hozzászólást!

  • Mellékelem ameddig haladtam.

    Találtam egy példát ami jó lehet, de nem tudom átirni.

    backtracking(x[],k)
    ha megoldás(x,k) akkor
    kiír(x,k)
    vége ha
    minden i=1,nk+1 végezd
    < eloállítjuk x[k+1]-ben az A ˝ k+1 halmaz i-edik elemét >
    ha ígéretes(x,k+1) akkor
    backtracking(x,k+1)
    vége ha
    vége minden
    vége backtracking
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Hát, ő, tessék:

    static bool Stimmel(List<int> ultetes) { for (var i = 0; i < ultetes.Count; i++) { int pos = ultetes.IndexOf(ultetes[i] - 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } pos = ultetes.IndexOf(ultetes[i] + 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } } return true; } static List<int> Keres(List<int> elemek,List<int> eddig) { if (!Stimmel(eddig)) return null; if (elemek.Count == 0) return eddig; for(int i = 0; i < elemek.Count; i++) { int elem = elemek[i]; elemek.Remove(elem); eddig.Add(elem); List<int> eredmeny = Keres(elemek, eddig); if (eredmeny != null) return eredmeny; eddig.Remove(elem); elemek.Insert(i, elem); } return null; } static void Main(string[] args) { List<int> elemek=new List<int>{1,2,3,4}; List<int> eredmeny = Keres(elemek, new List<int>()); if (eredmeny != null) { Console.Write(eredmeny[0]); for (int i = 1; i < eredmeny.Count; i++) Console.Write(", " + eredmeny[i]); } }
    Kipróbálható itt: Ideone.com
    Mutasd a teljes hozzászólást!
  • Köszönöm szépen, viszont azt mondták, hogy tömb-be oldjuk, szóval ez sajnos nekem nem lesz jó.

    De haladtam vele, mostmár csak az a kérdés, hogy hogyan oldjam meg, hogy az ellenségek ne üljenek egymás mellé? 

    Erre jutottam eddig.

    info2
    Mutasd a teljes hozzászólást!
  • Át lehet írni static tömbösre is, persze:

    static int[] elemek= { 1,2,3,4 }; static int elemekHossz=elemek.Length; static int[] ultetes=new int[elemekHossz]; static int ultetesHossz=0; static int UltetesbenKeres(int mit) { for (int i = 0; i < ultetesHossz; i++) if (ultetes[i] == mit) return i; return -1; } static bool Stimmel() { for (var i = 0; i < ultetesHossz; i++) { int pos = UltetesbenKeres(ultetes[i] - 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } pos = UltetesbenKeres(ultetes[i] + 1); if (pos >= 0) { int d = Math.Abs(pos - i); if (d < 2 || d > 3) return false; } } return true; } static bool Keres() { if (!Stimmel()) return false; if (elemekHossz == 0) return true; for(int i = 0; i < elemekHossz; i++) { ultetes[ultetesHossz] = elemek[i]; ultetesHossz++; elemekHossz--; elemek[i] = elemek[elemekHossz]; if (Keres()) return true; //elemek[elemekHossz] = elemek[i]; // már az van ott elemekHossz++; ultetesHossz--; elemek[i] = ultetes[ultetesHossz]; } return false; } static void Main(string[] args) { if(Keres()) { Console.Write(ultetes[0]); for (int i = 1; i < ultetesHossz; i++) Console.Write(", " + ultetes[i]); } Console.ReadLine(); }
    Gyakorlatilag az első sor ("elemek") a bemenet. Mivel tömbből törölni, illetve a backtrack keretében a törlést visszacsinálni macerás (for ciklussal kéne pakolgatni az elemeket oda-vissza, esetleg valamilyen ArrayCopy-ra bízni ugyanezt), ezért a kód inkább az utolsó elemet teszi át a törölt helyére. A szimmetria viszont szépen látszik, ahogy a backtrack keretében a sikertelen kísérlethez vezető előkészítő lépéseket játssza le visszafele a program.
    Mutasd a teljes hozzászólást!
  • Tökéletes, köszi szépen.
    Mutasd a teljes hozzászólást!
  • szerintem...
    bocsánat, hogy így utólag belekotyogok, de gondolom az megvan, hogy gyakorlatilag ez ugyanaz a probléma, mint az n (általában 8) királynőé?
    a "megfeleltetés" pld. a következő lehet: az oszlopok az egyes személyek, a sorok pedig a székek, az i. személy nincs ütésben feltétel meg az, hogy az i. sorában nincsen korábbi (egy széken csak egy ember ülhet), és az őt közvetlenül megelőző oszlopban levő (tehát a "megelőző" szomszédja) 2 vagy 3 "távolságra" "ül" tőle, a rákövetkezővel nem kell hasonlítani, hiszen a reláció szimmetrikus (ha a i. össze volt veszve a i+1.-kel, akkor a i+1. is össze van veszve a i.-kel), tehát ezt majd az i+1-nél fogjuk ellenőrizni,
    ha esetleg körben ülnek, akkor egyrészt az első és az utolsó között is kell ellenőrzést végezni, amit nyilván az utolsó "után" kell megtenni, ill. minden szomszédosnál azt is ellenőrizni kell, hogy az egyik nem-e az "első", a másik meg az "utolsó" széken ül, vagy "körben" háromnál nagyobb a "távolság",
    azaz fogod az n(8) kiráynő programját, majd átírod benne a "nincs ütésben" függvényt, a fentiek szerint, és már meg is vagy...
    ...szerintem
    Mutasd a teljes hozzászólást!
Címkék
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd