Laborfeladatok
1. Tegyük fel, hogy a1, a2, a3 ... an típusú pénzérménk van, amivel S összeget kell kifizessünk. Egy backtracking program segítségével
írjuk fel azt a megoldást, amikor
a) minimum számú érmével kell kifizetni az összeget
b) maximum számú érmével kell kifizetni az összeget
Feltételezzük, hogy minden pénzérméből véges számú áll a rendelkezésünkre ahhoz, hogy az S összeget kifizessük.
2. a) Egy egér egy labirintus elején van (0,0 pozicíó) s szeretne eljutni a labirintus végére (n-1, m-1 pozició)
ahol egy darab sajt található, de a labirintusban valahol van egy macska.
Segítsünk neki, írva egy backtracking programot, amely az összes lehetséges utat legenerálja.
Feltételezzük, hogy az egér csak le-fel, jobbra-balra tud mozogni (tehát átlósan nem),
illetve nem kerülhet a macska közvetlen szomszédjába.
Jelöljük -2 vel a cicát,
-1 el a falakat,
s egy labirintus.txt állpományból olvassuk be a labirintutst,
amelynek első sorában két szám van, az n és m (a labirinuts méretei),
az utána következő n sorban a labirintus értékei lesznek (minden sorban m érték).
2. b) az a pontnál kapott útvonalak közül keressük meg, s írjuk ki a legrövidebbet!
3. Csöpp Báró a norokszöáj sikerén felbuzdulva eldöntötte, hogy új slágert ír, de ezúttal a "duzsmán", "bány", "jubitá", és "inimámnyá" szavakat szeretné használni. Tudva, hogy a refrén
segítsünk neki azáltal, hogy írunk egy backtracking programot, amely legenerálja az összes lehetséges variációt!
#include <iostream>
#include <string>
#include <vector>
int osszeg=10;
int megoldasokszama = 0;
int penzermek[] = {10, 5, 1};
int elegendo[] = {3,1, 5};
int N = 3;
using namespace std;
string megoldas = "";
/*
logikai fuggveny, amely megvizsgalja, hogy megvan e az adott osszeg
igazat terit vissza, ha igen
hamisat, ha nem
*/
bool egyenlo(int ideiglenesosszeg)
{
if (ideiglenesosszeg == osszeg)
{
return true;
}
return false;
}
/*
logikai fuggveny, amely megvizsgalja,
hogy az adott penzermet hozza lehet e meg adni az ideiglenes osszeghez
igazat terit vissza, ha igen
hamisat, ha nem
*/
bool hozzaadhatom(int ideiglenesosszeg, int penzerme, int hanyvan)
{
if (penzerme + ideiglenesosszeg > osszeg)
{
return false;
}
if (hanyvan < 1){
return false;
}
return true;
}
/*
backtrack fuggveny,megvizsgalja, hogy a jelenlegi megoldas vegso megoldas-e.
Ha igen, akkor kiirja es kilep, ha nem, akkor probalja a kovetkezo ermet hozzaadni
*/
bool backtrack(int ideiglenesosszeg,int index, vector<int> megoldas, int eleg[])
{
if(egyenlo(ideiglenesosszeg))
{
megoldasokszama++;
for(int erme: megoldas){
cout << erme << " " ;
}
cout << endl;
return 0;
}
for(int i=index; i<N; i++)
{
if (hozzaadhatom(ideiglenesosszeg, penzermek[i], eleg[i]))
{
vector<int> tempmegoldas;
for(int erme: megoldas){
tempmegoldas.push_back(erme);
}
tempmegoldas.push_back(penzermek[i]);
int tempeleg[N];
for(int k = 0; k < N; k++){
tempeleg[k] = eleg[k];
}
tempeleg[i] --;
int temposszeg = ideiglenesosszeg+penzermek[i];
//megoldas.append(" ");
backtrack(temposszeg, i, tempmegoldas, tempeleg);
}
}
return 0;
}
int main()
{
vector<int> megoldas;
backtrack(0,0, megoldas, elegendo);
cout << "a lehetseges megoldasok szama " << megoldasokszama;
return 0;
}
2. Egy mennyasszonynak segítségre van szüksége mennyasszonyi csokra elkészítéséhez.
Kedvenc virágai a rózsa, tulipán, gerbera, orchidea és liliom, de ezekől csak 3 at szeretne a mennyaszonyi csokrában látni.
Segítsünk neki azáltal, hogy írunk egy C++ programot, amelyben az összes lehetséges kombinációt legeneráljuk!
#include <iostream>3. Egy egér egy labirintus elelén van (0,0 pozicíó) s szeretne eljutni a labirintus végére (n-1, m-1 pozició)
using namespace std;
int N = 3;
string virag[] = {"rozsa", "tulipan", "gerbera","orchidea", "liliom"};
/**
A lehet fuggveny, amiben csak azt kell vizsgaljuk,
hogy a megadott uj virag megvan-e mar az ideiglenes csokorban.
Ha igen, akkor hamisat terit vissza,
kulonben igazat
args:
csokor - az ideiglenes csokor, amelyikbe mar lehetnek viragok
n - az ideiglenes csokor nagysaga
ujvirag - az uj viragnak a neve, amit bele szeretnenk tenni a csokorba
*/
bool lehet(string csokor[], int n, string ujvirag)
{
//vegigmegyunk a tombon, s megnezzuk, hogy barmelyik elem megegyezik-e
//a uj viraggal, mert ha igen, akkor nem tehetjuk bele a csokorba
for(int i = 0; i<n; i++)
{
if (csokor[i] == ujvirag)
{
return false;
}
}
return true;
}
/**
Kiir fuggveny, kiir egy string tombot, aminek n a hossza
*/
void kiir(string csokor[], int n)
{
for(int i = 0; i<n; i++)
{
cout << csokor[i] << " " ;
}
cout << endl;
return;
}
/**
a backtrack fuggveny, amely megprobalja osszerakni a mennyasszonyi csokrot
args:
csokor - az ideiglenes csokor, amelyikkel probalkozunk
n - az ideiglenes csokor hossza
index - az a szam, ahanyadik viragnal tartunk a virag tombbol (pl index = 1, akkor csak a tulipant, s az azutani viragokat probaljuk a csokorba tenni)
*/
void backtrack(string csokor[], int n, int index)
{
//ha az ideiglenes csokor hossza N, amennyi viragra szuksegunk van
//akkor ez megoldas, leallunk, s kiirjuk
if (n == N)
{
kiir(csokor, n);
return;
}
//megprobaljuk az osszes lehetseges variaciot a viragokkal,
//ezert kezdjuk az elso szamnal, az indexnel, ahonnan probalkozzunk, s megyunk vegig a virag tombon
for(int i = index; i<5; i++)
{
//megvizsgaljuk. hogy bele lehet e tenni az aktualis uj viragot a mar meglevo csokorba
if (lehet(csokor, n, virag[i]))
{
//ha igen, letrehozunk egy ideiglenes csokrot, aminek N=3 lesz a hossza,
//mivel max akkora kell legyen a menyasszonyi csokrunk
string tempcsokor[N];
//atmasoljuk az eddigi csokrot az ideiglenes csokorba
for(int j = 0; j<n; j++)
{
tempcsokor[j] = csokor[j];
}
//az n-1 edik helyig másoltunk, uh a következo helyre kell tegyuk
//az uj viragot. Pl ha az eddigi csokor = {rozsa, tulipan}, akkor n = 2
//az uj csokor {rozsa tulipan gerbera} kell legyen, tehat az n. indexre kell tenni az uj viragot
tempcsokor[n] = virag[i];
//meghivjuk a backtrack fuggvenyt az uj ideiglenes csokorra, s mivel hozzaadtunk egy viragot, ezert az n et noveljuk 1 el
//mivel vizsgaljuk a lehet fuggvenyben, hogy ne legyen ket ugyanolyan virag, ezert az i erteket nem muszaj novelni.
backtrack(tempcsokor, n+1, i);
}
}
}
int main()
{
//letrehozunk egy ures csokrot, mivel meg nem tudjuk milyen viragok lesznek a menyasszonyi csokorban
string csokor[] = {""};
//mivel meg nem tettunk egy viragot sem sehova, ezert az eddigi csokorban 0 virag van, tehat n=0,
//s minden viragbol szeretnenk, ha lenne a csokorban, ezert az indexet is 0 rol inditjuk
//nezzuk meg, hogy ha 1 rol inditjuk, akkor rozsa nem lesz a csokrokban, ha 2 rol, rozsa s tulipan sem...
backtrack(csokor, 0, 0);
return 0;
}
#include <iostream>
#include <fstream>
using namespace std;
//A lehetseges koordinatak legeneralasa
short xlehet[] = {0,0,-1, 1};
short ylehet[] = {-1,1, 0, 0};
/**
Fuggvent a labirintus kiirasara
*/
void kiir(int tomb[100][100], int n, int m)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cout << tomb[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/**
Lehet fuggveny, ami hamist fog visszateriteni,
ha
- falba utkozunk
- voltunk mar ott, ahova lepni szeretnenk
- kilepnenk a labirintusbol
*/
bool lehet(int tomb[100][100], int n, int m, int xpos, int ypos)
{
//ha a megadott pozicio nincs a labirintusba,
//teristsunk vissza hamisat
//elobb az x koordinatara
if (xpos <0 )
{
return false;
}
if (xpos > n-1)
{
return false;
}
//aztan az y koordinatara
if (ypos <0 )
{
return false;
}
if (ypos > m-1)
{
return false;
}
//a falat 1 essel jeloltuk, szoval ha 1 esre lepnenk,
//akkor teritsunk vissza hamisat
if (tomb[xpos][ypos] == 1)
{
return false;
}
if (tomb[xpos][ypos] == 2)
{
return false;
}
//ha semmi sem akadalyoz meg minket abban, hogy ide lepjunk, akkor teritsunk vissza igazat
return true;
}
void backtrack(int tomb[100][100], int n, int m, int xpos, int ypos)
{
//a leallasi feltetel az lesz, hogy a labirintus vegen vagyunk
if ((xpos == n-1) && (ypos == m-1))
{
kiir(tomb, n, m);
return ;
}
for(int i = 0; i<4; i++)
{
if (lehet(tomb, n, m, xpos+xlehet[i], ypos+ylehet[i]))
{
int tempxpos = xpos+xlehet[i];
int tempypos = ypos+ylehet[i];
int templabirintus[100][100];
//az ideiglenes labirintusban atmasoljuk az eger helyet
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
templabirintus[i][j] = tomb[i][j];
}
}
//az ideiglenes labirintusban frissitjuk az eger helyet
templabirintus[tempxpos][tempypos] = 2;
backtrack(templabirintus, n, m, tempxpos, tempypos);
}
}
}
int main()
{
int a[100][100];
ifstream inputfile("labirintus.in");
int n, m;
//beolvassuk az n es m erteket
inputfile >> n >> m;
//beolvassuk a labirintust
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
inputfile >> a[i][j];
}
}
//az egeret a 0 0 helyre tesszuk
//feltetelezzuk, hogy az eger helyzetet 2 essel jeloljuk
a[0][0] = 2;
//meghivjuk a backtrack fuggvenyt
backtrack(a, n, m, 0, 0);
return 0;
}