mając zbiór np Mapa = (3, 4, 2, 6, 3) tworzony jest zbiór A, w którego skład wchodzą wszystkie elementy mapy oraz sumy sąsiadujących dwójek (3+4,4+2,...), trójek, czwórek itp aż do sumy wszystkich elementów mapy - dla tej konkretnej mapy wyszedłby zbiór A = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}. Moim zadaniem jest odtworzyć prawidłową kolejność elementów w mapie mając do dyspozycji zbiór A i informację że pierwszy element mapy to zawsze element ostatni A minus element przedostatni A (w tym wypadku 18-15 = 3)
Utknęłam na etapie w którym prawidłowo sprawdzane są tylko pary i nie mogę wpaść na pomysł jak mam sprawdzać trójki, czwórki, bez tworzenia osobnych funkcji. Problemem jest też to że w przypadku tego zbioru A utworzy mi w pierwszej iteracji mapę (3,3,...) ponieważ jest 6 w zbiorze A - ale mapa z 3 na drugim miejscu nie ma prawa istnieć - nie wiem więc jak sprawdzać z góry czy liczba może zająć dane miejsce w mapie jeśli dotychczasowe sumy się zgadzają, ale te z kolejnych iteracji już nie.
int mapowanie( int k, bool * uzyto, int ind, int * jest )
{
int suma, suma_trojki;
int warto = false; // do sprawdzania czy warto kontunuowac roziwazanie
if( mapa.size() == k + 1 ) // jesli na mapie jest juz k+1 elementow (czyli wymagana licznosc)
{
cout << "jest";
* jest == 1;
return 1;
}
else for( int i = 0; i < A.size(); i++ )
{
suma = mapa.back();
if( uzyto[ i ] == false )
{
suma += A[ i ];
if( suma > A.back() )
{
warto = false;
break;
}
else
for( int j = 0; j < A.size(); j++ )
{
if( A[ j ] == suma && uzyto[ j ] == false ) // jesli taka suma jest w zbiorze A i nie jest sumą jakis innych liczb
{
uzyto[ j ] = true;
uzyto[ i ] = true;
mapa.push_back( A[ i ] );
warto = true;
break;
}
}
}
if( mapa.size() == k + 1 )
{
* jest = 1;
break;
return 1;
}
if( warto == true ) // jesli rozwiazanie warto kontynuowac bo sumy wystapily w A
mapowanie( k, uzyto, ind + 1, jest );
}
}
void nieuzyte( int licznosc, bool * odwiedzone )
{
for( int i = 0; i < licznosc; i++ )
{
odwiedzone[ i ] = false;
}
}
int main()
{
// .....
mapowanie( k, uzyte, 0, & jest );
if( jest == 0 )
cout << endl << "nie ma rozwiazania" << endl;
return 0;
}