odtwarzanie zbioru na podstawie innego zbioru

Odpowiedz Nowy wątek
2018-02-15 18:13
0

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;
}

Pozostało 580 znaków

2018-02-15 20:40
0

Trzeba się za to zabrać inaczej, najpierw odtworzyć ile jest elementów w danym zbiorze Mapa, znajac ilośc elementów zbioru A. Widać, że jeśli ta ilość to #A, to:
#A = n + (n - 1) + (n - 2) + ... + (n - (n - 1))
Gdzie n to #Mapa, n - elementy mapy + ilość par (n - 1), trójek, aż do (n - (n - 1)) - suma całego zbioru. Widać, że jest to ilość kolejnych liczb od jeden, które trzeba zsumować, żeby uzyskać #A, a na to jest wzór:
#A = n * (n + 1) / 2
Dla Twojego przykładu 5:
15 = n (n + 1) / 2, rozwiązaniem jest 5.
Mając n wiemy, że n pierwszych elementów A to elementy zbioru Mapa, nie znamy kolejności i wiemy, który jest pierwszy. Teraz nie rozumiem po co to jest posortowane, gdyby nie było to łatwo możnaby przeiterować od elementów n + 1 sprawdzając sumy dwójek, ewentualnie trójek itd...


Pozostało 580 znaków

2018-02-15 20:50
0

Co do liczności masz racje, mój program ją wylicza wcześniej, ale nie zamieściłam tego fragmentu kodu ( jest to k+1 ). Natomiast co do tego że pierwsze n liczb ze zbioru utworzy mapę - prosty przykład ilustrujący że nie może tak być:
mapa = {2,15,4,2}
daje nam A = {2,2,4,15,17,19,6,21,21,23} co po posortowaniu A = {2,2,4,6,15,17,19,21,21,23} dawałoby jako elementy mapy 2,2,4 oraz 6 - czyli błędnie. Natomiast zbiór A jest na wejściu posortowany by było trudniej rozwiązać to zadanie

lion137 napisał(a):

Trzeba się za to zabrać inaczej, najpierw odtworzyć ile jest elementów w danym zbiorze Mapa, znajac ilośc elementów zbioru A. Widać, że jeśli ta ilość to #A, to:
#A = n + (n - 1) + (n - 2) + ... + (n - (n - 1))
Gdzie n to #Mapa, n - elementy mapy + ilość par (n - 1), trójek, aż do (n - (n - 1)) - suma całego zbioru. Widać, że jest to ilość kolejnych liczb od jeden, które trzeba zsumować, żeby uzyskać #A, a na to jest wzór:
#A = n * (n + 1) / 2
Dla Twojego przykładu 5:
15 = n (n + 1) / 2, rozwiązaniem jest 5.
Mając n wiemy, że n pierwszych elementów A to elementy zbioru Mapa, nie znamy kolejności i wiemy, który jest pierwszy. Teraz nie rozumiem po co to jest posortowane, gdyby nie było to łatwo możnaby przeiterować od elementów n + 1 sprawdzając sumy dwójek, ewentualnie trójek itd...

Pozostało 580 znaków

2018-02-15 23:15
0

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.


Pozostało 580 znaków

2018-02-16 08:55
0

Skoro kolejność ma znaczenie, to dane wejściowe nie są zbiorem, ale ciągiem, prawda? I wyjściowe też?

Pozostało 580 znaków

2018-02-16 09:45
0

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Pozostało 580 znaków

2018-02-16 09:46
0

Tak, są to ciągi, nie zbiory

koszalek-opalek napisał(a):

Skoro kolejność ma znaczenie, to dane wejściowe nie są zbiorem, ale ciągiem, prawda? I wyjściowe też?

Pozostało 580 znaków

2018-02-16 11:08
0
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?


Pozostało 580 znaków

2018-02-16 12:01
0

Zadanie jest chyba jednoznaczne, jeśli przyjąć, że nie chodzi jednak o ciągi, ale o multizbiory -- wtedy wszystko się zgadza.

Pozostało 580 znaków

2018-02-16 12:04
0
koszalek-opalek napisał(a):

Zadanie jest chyba jednoznaczne, jeśli przyjąć, że nie chodzi jednak o ciągi, ale o multizbiory -- wtedy wszystko się zgadza.

W multizbiorze kolejnośc elementów nie jest istotna, a tutaj jest.


A rzeczywiście, przepraszam, bo sąsiadujące... - koszalek-opalek 2018-02-16 12:15

Pozostało 580 znaków

2018-02-16 12:24
0

bioinformatyczny problem mapowania częściowym trawieniem

lion137 napisał(a):
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0