Chyba prosty problem algorytmiczny

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?

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

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.

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

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.

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

#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

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.