Chyba prosty problem algorytmiczny

Chyba prosty problem algorytmiczny
0

Cześć

Natknąłem się gdzieś na pewien na pewien problem i nie przychodzi mi do głowy żaden sensowny pomysł. Pomożecie :) ? W zasadzie nadaje się on do każdego działu - niekoniecznie do C. Chodzi o to:
Mamy dwie tablice wypełnione liczbami w sposób malejący (bądź rosnący - obojętne).
np. { 12 10 9 8 6 5 3 2 1} i {7 5 4 2 1}
Następnie podajemy jakąś liczbę np. 7 i naszym zadaniem jest rozstrzygnąć czy tę liczbę da się przedstawić jako sumę dwóch liczb tak, żeby jedna z nich pochodziła z pierwszej tablicy a druga z drugiej. Dodatkowo podajmy indeksy takich liczb w tych tablicach (o ile istnieją). W naszym przypadku oczywiście: (2+5) (5+2) (3+4) może więcej - nie sprawdzam dokładnie. Nie można jednak tego zrobić na chama brutalną metodą sprawdzając wszystkie kombinacje) - złożoność tego algorytmu ma być liniowa. Pomysły?

0

for w forze i z pierwszej tablicy bierz 1 element i dodawaj go do każdego w drugiej tablicy, jeśli wyjdzie 7 to wypisz ? chyba najprościej

Sarrus
Wtedy złożoność nie będzie liniowa
Wibowit
  • Rejestracja:około 20 lat
  • Ostatnio:około 4 godziny
0

Jestem na systemie bez IDE, więc opiszę rozwiązanie słownie.

tab1 = { ciąg malejący }
tab2 = { ciąg malejący }
ind2 = indeks ostatniego elementu z tab2
for (ind1 = indeks pierwszego elementu z tab1; ind1 <= indeks ostatniego elementu z tab1; i++) {
while (ind2 > indeks pierwszego elementu z tab2 && tab1[ind1] + tab2[ind2] < wartość docelowa)
ind2--;
if (tab1[ind1] + tab2[ind2] == wartość docelowa)
wypisz tab1[ind1] i tab2[ind2]
}

Powinno zadziałać, możliwe że się walnąłem.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
0

@qwe -- oczywiście że najprościej, ale złożoność kwadratowa ;)
@Wibowit -- w skrajnym przypadku i tak trzeba przeiterować n^2 razy, nie?

Wibowit
  • Rejestracja:około 20 lat
  • Ostatnio:około 4 godziny
0

Nie. ind1 rośnie n razy. ind2 maleje co najwyżej n razy - jest inicjowany tylko raz, a potem zmniejszany. Zastanów się nad kodem, a nie licz pętle.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
mto9
  • Rejestracja:ponad 14 lat
  • Ostatnio:około 10 lat
  • Postów:380
0
Kopiuj
#include<iostream>
using namespace std;

int main()
{
    const int MAX_ELEMENTS = 100;
    int tab_1[MAX_ELEMENTS]; //ciąg malejący
    int tab_2[MAX_ELEMENTS]; //ciąg malejący

    int n1,n2;  //ilosc elementów odpowiednio: 1 i 2 tablicy

    cout<<"Podaj ilosc elementow 1 tablicy: ";
    cin>>n1;
    cout<<"\nPodaj ilosc elementow 2 tablicy: ";
    cin>>n2;

    for(int i=0;i<n1;i++)
    {
        cout<<"Podaj "<<i+1<<" element 1 tablicy: ";
        cin>>tab_1[i];
    }
    for(int i=0;i<n2;i++)
    {
        cout<<"Podaj "<<i+1<<" element 2 tablicy: ";
        cin>>tab_2[i];
    }

    int k;  //szukana suma
    cout<<"Podaj szukana sume: ";
    cin>>k;
    cout<<endl;

    if(k > tab_1[0] + tab_2[0] || k < tab_1[n1-1] + tab_2[n2-1])
        cout<<"Brak dopasowania!\n";
    else
    {
        int ix1=0,ix2=0,ix3=n2-1; //indexy od których szukanie ma sens

        for(;k < tab_1[ix1];ix1++);
        for(;k < tab_2[ix2];ix2++);

        for(int i=ix1;i<n1;i++)
        {
            for(int j=ix3;j >= ix2;j--)
            {
                if(tab_1[i] + tab_2[j] == k)
                {
                    cout<<tab_1[i]<<" + "<<tab_2[j]<<"\n";
                    ix3=j-1;
                    break;
                }
            }
        }
    }

    cin>>n1;
    return 0;
}
edytowany 1x, ostatnio: mto9
Wibowit
Dalej kwadratowe. Napisz liniówkę, a nie baw się w takie półśrodki. Liniówka byłaby zresztą 5x krótsza i prostsza.
mto9
w optymistycznych sytuacjach (duzo dopasowan) n^2/2 :D
Wibowit
No to piszę przecież, że kwadrat.
mto9
no dobrze dobrze...
mto9
  • Rejestracja:ponad 14 lat
  • Ostatnio:około 10 lat
  • Postów:380
0
Kopiuj
#include<iostream>
using namespace std;
int main()
{
    const int MAX_ELEMENTS = 100;
    int tab_1[MAX_ELEMENTS]; //ciąg malejący
    int tab_2[MAX_ELEMENTS]; //ciąg malejący
    int n1,n2;  //ilosc elementów odpowiednio: 1 i 2 tablicy
    cin>>n1;
    cin>>n2;
    for(int i=0;i<n1;i++) cin>>tab_1[i];
    for(int i=0;i<n2;i++) cin>>tab_2[i];
    int k;  //szukana suma
    cin>>k;

    if(k > tab_1[0] + tab_2[0] || k < tab_1[n1-1] + tab_2[n2-1])
        cout<<"Brak dopasowania!\n";
    else
    {
        int ix1=0,ix2=0; //indexy od których szukanie ma sens
        for(;k < tab_1[ix1];ix1++);
        for(;k < tab_2[ix2];ix2++);

        int help,v=(tab_1[ix1]>tab_2[ix2]) ? tab_1[ix1] : tab_2[ix2];
        int tab_v[v+1];
        for(int i=0;i<v+1;i++) tab_v[i]=0;

        for(int i=ix1;i<n1;i++) ++tab_v[tab_1[i]];
        for(int i=ix2;i<n2;i++) ++tab_v[tab_2[i]];

        for(int i=1;i<v+1;i++)
        {
            if(tab_v[i]>0 && tab_v[k-i]>0)
            {
                cout<<i<<" + "<<k-i<<endl;
                continue;

            }
        }
    }
    return 0;
}

PS. Z założeniem że ciąg malejący i zawiera liczby naturalne dodatnie

edytowany 2x, ostatnio: mto9
Wibowit
  • Rejestracja:około 20 lat
  • Ostatnio:około 4 godziny
0

Okay. Napisałem kod w edytorze zwanym TextBox w HTMLowym formularzu: http://ideone.com/N3ZVE - zakładam, że na początku podana jest szukana suma, potem ciągi, każdy zakończony jednym zerem (czyli po drugim zerze program już nic nie wczytuje), a wypisywane na wyjściu indeksy są liczone od zera. Niby działa, ale w 100 % pewny poprawności nie jestem.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
mto9
Muszę Cię zmartwić, ale nie działa. Np dla tab1{10,8,6,4,2,0} i tab2{9,7,5,3,1,0} i szukanej 5 istnieją 4 rozwiązania(4-1),(2-3),(3-2),(1-4) u Ciebie wyświetla aby 2
Wibowit
Bo są dwa rozwiązania przecież. Pierwsza liczba ma być z pierwszego ciągu, druga z drugiego. Rozwiązania (3, 2) i (1, 4) są u ciebie niepoprawne.
mto9
Looknij na polecenie, w przykładzie nawet jest pokazane (2-5) (5-2)
Wibowit
Bo obydwie liczby są w obu ciągach. Zważ też, że (3, 4) jest, a (4, 3) nie ma.
mto9
okej zwracam honor :D to ja źle zalookałem :D w takim razie moja wersja do małej poprawki :D

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.