Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Zdravím, máme za úkol takovou ošklivou věc. Přemýšlím o tom snad celý den a nic mě nenapadá. Nechci po vás napsat ten program, ale jenom nakoupnout, jak na to :-) Děkuju.
Úkolem je napsat program, který dokáže řešit hlavolam "přeskakování sirek".
Tento hlavolam má jednoduché zadání: na stole leží n sirek v řadě vedle sebe. Úkolem je z těchto sirek vytvořit "křížky", tedy přesunout sirku o vlevo nebo vpravo a položit ji křížem přes ležící sirku. Sirku lze přemístit pouze jednou, dokud leží samostatně (nelze tedy rozebrat křížek). Sirku lze přesunout vlevo nebo Provpravo, při přesunutí je potřeba přeskočit zadaný počet ležících sirek. Přeskakovaná samostatná sirka se počítá za 1, křížek za 2.
Příklad pro n=12 (počet sirek) a k=4 (velikost skoku):
0 1 2 3 4 5 6 7 8 9 10 11
| | | | | | | | | | | |
4R
| | | | | | | | X | |
8L
| | X | | | | X | |
5R
| | X | | | X X |
7L
| X X | | X X |
0R
X X X | X X |
6R
X X X X X X
Vstupem programu jsou dvě celá čísla n a k. Číslo n představuje počet sirek (n > 1) a k představuje velikost skoku (k >= 0).
Výstupem programu jsou všechny posloupnosti přesunů sirek, kterými lze pro daný vstup vytvořit křížky. Každá posloupnost přesunů je na zvláštní řádce. Na řádce jsou čárkami oddělené jednotlivé přesuny. Pro každý přesun je určeno číslo sirky (počítáno od nuly) a směr posunutí (L, R). Poslední řádka výstupu udává počet různých existujících řešení. Za informací o počtu řešení je odřádkování.
Program detekuje chybu, pokud jsou na vstupu nečíselné hodnoty nebo pokud je počet sirek menší roven jedné nebo pokud je velikost kroku záporná. V případě chyby je zobrazeno chybové hlášení podle vzoru v ukázce. Za chybovým hlášením je odřádkování, chybové hlášení zobrazujte na std. výstup (ne na chybový výstup).
Při řešení je zakázáno používat datový typ C++ string a datové kontajnery z STL (ani jedno uvedené nemá pro tuto úlohu použití). Počítejte s tím, že program běží v omezeném prostředí. Je omezen velikostí dostupné paměti (pro tuto úlohu postačuje pamět velikosti několika málo kilobyte) a dobou běhu. Max. doba běhu je omezena na 30 sec (za tuto dobu zvládne ref. program bezpečně vypočtat úlohu pro 18 sirek a krok velikosti 2 - 676144 různých řešení).
Offline
Tak jsem to už tak nějak pořešil použitím rekurze, ale mám problém. Řešení mají být různá, takže když jsou 2 sirky a krok 0, tak to má vypadat takto:
0R -- tj. I I --> _ X
1L -- tj. I I --> X _
a mně to vypíše
0R *
0L *
1R **
1L **
kde řešení označené stejným počtem hvězdiček jsou vlastně stejná řešení. Nejde nějak "spočítat" počet řešení, že bych prostě skončil až jich najdu určitý počet ...
Offline
Tak sice už je na úkol pozdě, ale tady je řešení s rekurzí i bez:
#include <iostream>
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
using namespace std;
static size_t pocet_sirek = 0;
static size_t velikost_skoku = 0;
struct Item
{
Item *next;
size_t pocet_kroku;
size_t polozky[1];
static Item* create()
{
Item* result = (Item*)malloc(sizeof(Item) + (pocet_sirek - 1 + (pocet_sirek >> 1)) * sizeof(size_t));
result->next = 0;
result->pocet_kroku = 0;
for (size_t i = 0; i < pocet_sirek; ++i)
{
result->polozky[i] = 1;
}
return result;
}
static Item* create(Item* from)
{
Item* result = (Item*)malloc(sizeof(Item) + (pocet_sirek - 1 + (pocet_sirek >> 1)) * sizeof(size_t));
result->next = 0;
result->pocet_kroku = from->pocet_kroku;
memcpy(result->polozky, from->polozky, (pocet_sirek + (pocet_sirek >> 1)) * sizeof(size_t));
return result;
}
bool hotovo() const
{
/*for (size_t i = 0; i < pocet_sirek; ++i)
{
if (polozky[i] == 1) return false;
}
return true;*/
return (pocet_kroku == (pocet_sirek >> 1));
}
void vypisKroky() const
{
for (size_t i = pocet_sirek; i < pocet_sirek + (pocet_sirek >> 1); ++i)
{
if (polozky[i] & ((size_t)1 << sizeof(size_t)*8-1))
{
cout << (polozky[i] & (~((size_t)1 << sizeof(size_t)*8-1))) << "L";
}
else
{
cout << (polozky[i] & (~((size_t)1 << sizeof(size_t)*8-1))) << "R";
}
if (i != (pocet_sirek + (pocet_sirek >> 1)) - 1) cout << ",";
}
cout << endl;
}
bool zkusKrok(size_t index, bool vlevo)
{
if (polozky[index] != 1) return false;
size_t novy_index = index;
size_t preskocit = velikost_skoku;
while (preskocit > 0)
{
if (polozky[novy_index] > preskocit) return false;
if (vlevo)
{
if (novy_index == 0) return false;
--novy_index;
}
else
{
if (novy_index == pocet_sirek-1) return false;
++novy_index;
}
preskocit -= polozky[novy_index];
}
if (vlevo)
{
if (novy_index == 0) return false;
--novy_index;
}
else
{
if (novy_index == pocet_sirek -1) return false;
++novy_index;
}
while (polozky[novy_index] == 0)
{
if (vlevo)
{
if (novy_index == 0) return false;
--novy_index;
}
else
{
if (novy_index == pocet_sirek -1) return false;
++novy_index;
}
}
if (polozky[novy_index] == 1)
{
polozky[index] = 0;
polozky[novy_index] = 2;
polozky[pocet_sirek + (pocet_kroku++)] =
vlevo ?
(index | (((size_t)1 << sizeof(size_t)*8-1))) :
(index & (~((size_t)1 << sizeof(size_t)*8-1)));
return true;
}
return false;
}
};
struct Fifo
{
Item *first;
Item *last;
Fifo(): first(0), last(0) {}
~Fifo() {}
void push(Item* item)
{
if (!last)
{
first = last = item;
}
else
{
last->next = item;
last = item;
}
}
Item* pop()
{
Item *result = first;
if (first)
{
first = first->next;
if (first == 0) last = 0;
}
return result;
}
};
void res(Fifo& fifo, Item *item, size_t index, size_t& pocet_reseni, bool vlevo)
{
item = Item::create(item);
if (item->zkusKrok(index, vlevo))
{
if (item->hotovo())
{
item->vypisKroky();
++pocet_reseni;
}
else
{
fifo.push(item);
item = 0;
}
}
if (item)
{
free(item);
}
}
int main(int argc, char **argv)
{
cout << "Zadejte pocet sirek:" << endl;
if (!((cin >> pocet_sirek) && (pocet_sirek > 1)))
{
cout << "Nespravny vstup." << endl;
return 1;
}
cout << "Zadejte velikost skoku:" << endl;
if (!((cin >> velikost_skoku) && (velikost_skoku >= 0)))
{
cout << "Nespravny vstup." << endl;
return 2;
}
size_t pocet_reseni = 0;
if ((pocet_sirek & 1) == 0)
{
Fifo fifo;
Item *item;
fifo.push(Item::create());
while ((item = fifo.pop()) != 0)
{
for (size_t i = 0; i < pocet_sirek; ++i)
{
res(fifo, item, i, pocet_reseni, true);
res(fifo, item, i, pocet_reseni, false);
}
free(item);
}
}
cout << "Celkem nalezeno " << pocet_reseni << " ruznych reseni." << endl;
return 0;
}
#if 0
struct Data
{
int *sirky;
size_t *kroky;
size_t pocet_sirek;
size_t pocet_reseni;
size_t krok;
size_t pocet_kroku;
};
void vypisKroky(Data& d)
{
for (size_t i = 0; i < d.pocet_kroku; ++i)
{
if (d.kroky[i] & ((size_t)1 << sizeof(size_t)*8-1))
{
cout << (d.kroky[i] & (~((size_t)1 << sizeof(size_t)*8-1))) << "L";
}
else
{
cout << (d.kroky[i] & (~((size_t)1 << sizeof(size_t)*8-1))) << "R";
}
if (i != d.pocet_kroku - 1) cout << ",";
}
cout << endl;
}
bool dec(size_t& num, size_t max)
{
if (num == 0)
{
return false;
}
--num;
return true;
}
bool inc(size_t& num, size_t max)
{
if (num == max)
{
return false;
}
++num;
return true;
}
bool pohniKdyzMozno(Data& d, size_t index, bool l, size_t& novy_index)
{
size_t zbyva_kroku = d.krok;
novy_index = index;
if (l)
{
while (zbyva_kroku > 0)
{
if (!dec(novy_index, d.pocet_sirek-1)) return false;
if (d.sirky[novy_index] > zbyva_kroku)
{
return false;
}
zbyva_kroku -= d.sirky[novy_index];
}
if (!dec(novy_index, d.pocet_sirek-1)) return false;
while (d.sirky[novy_index] == 0)
{
if (!dec(novy_index, d.pocet_sirek-1)) return false;
}
if (d.sirky[novy_index] != 1)
{
return false;
}
d.sirky[index] = 0;
d.sirky[novy_index] = 2;
d.kroky[d.pocet_kroku++] = index | (((size_t)1 << sizeof(size_t)*8-1));
}
else
{
while (zbyva_kroku > 0)
{
if (!inc(novy_index, d.pocet_sirek-1)) return false;
if (d.sirky[novy_index] > zbyva_kroku)
{
return false;
}
zbyva_kroku -= d.sirky[novy_index];
}
if (!inc(novy_index, d.pocet_sirek-1)) return false;
while (d.sirky[novy_index] == 0)
{
if (!inc(novy_index, d.pocet_sirek-1)) return false;
}
if (d.sirky[novy_index] != 1)
{
return false;
}
d.sirky[index] = 0;
d.sirky[novy_index] = 2;
d.kroky[d.pocet_kroku++] = index & (~((size_t)1 << sizeof(size_t)*8-1));
}
return true;
}
void hledej2(Data& d)
{
if (d.pocet_kroku == (d.pocet_sirek >> 1))
{
++d.pocet_reseni;
vypisKroky(d);
return;
}
size_t novy_index;
for (size_t i = 0; i < d.pocet_sirek; ++i)
{
if (d.sirky[i] == 1)
{
// vpravo
if (pohniKdyzMozno(d, i, false, novy_index))
{
hledej2(d);
--d.pocet_kroku;
d.sirky[i] = 1;
d.sirky[novy_index] = 1;
}
// vlevo
if (pohniKdyzMozno(d, i, true, novy_index))
{
hledej2(d);
--d.pocet_kroku;
d.sirky[i] = 1;
d.sirky[novy_index] = 1;
}
}
}
}
void hledej(Data& d)
{
// když počet sirek není dělitelný 2 beze zbytku, řešení neexistuje
if ((d.pocet_sirek & 1) == 0)
{
hledej2(d);
}
}
int main(int argc, char **argv)
{
Data d = { 0, 0, 0, 0, 0, 0 };
cout << "Zadejte pocet sirek:" << endl;
if (!((cin >> d.pocet_sirek) && (d.pocet_sirek > 1)))
{
cout << "Nespravny vstup." << endl;
return 1;
}
cout << "Zadejte velikost skoku:" << endl;
if (!((cin >> d.krok) && (d.krok >= 0)))
{
cout << "Nespravny vstup." << endl;
return 2;
}
d.sirky = new int[d.pocet_sirek];
for (size_t i = 0; i < d.pocet_sirek; ++i)
{
d.sirky[i] = 1;
}
d.kroky = new size_t[d.pocet_sirek/2];
hledej(d);
cout << "Celkem nalezeno " << d.pocet_reseni << " ruznych reseni." << endl;
delete []d.sirky;
delete []d.kroky;
return 0;
}
#endif
Offline