Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++] Число в массивах


Автор: SoWa 28.2.2007, 19:05
Некоторое число содержится в каждом из трех целочисленных неубывающих массивов x[1] <= ... <= x[p], y[1] <= ... <= y[q], z[1] <= ... <= z[r]. Найти одно из таких чисел. Число действий должно быть порядка p + q + r. 

Алгоритм даже придумать не могу.
Перебор даст нам сложность p*q*r
Если сортировка Хоара работает линейное время, то как раз сложность будет около линейной.
Но желательно бы код )

Автор: Strannik 28.2.2007, 19:35
Вроде несложно... т.к. массивы отсортированы то должно работать следующее:

Код

int p1=0;
int p2=0;
int p3=0;
while (1){
   if((x[p1]=y[p2])&&(x[p1]=z[p3])){
     cout<<x[p1];
     break;
   }
   minn=min(х[p1],min(y[p2],z[p3]));
   if (minn==x[p1]) p1++;
   if (minn==y[p2]) p2++;
   if (minn==z[p3]) p3++;
}




Автор: Rockie 1.3.2007, 12:14
SoWa, практически тот же вопрос, только немного в другой форме, задавал в теме http://forum.vingrad.ru/topic-138038/hl/%25D1%2580%25D0%25B5%25D0%25BF%25D0%25B5/index.html


Автор: Dov 3.3.2007, 22:44
Особо не тестировал, но всё же.  smile  Возможно нужно добавить(или убрать) какие-нибудь проверки.  smile 
Код
#include <iostream.h>

int main(void)
{
    int  ar1[] = {10, 20, 30, 50, 60};
    int  ar2[] = {1, 5, 10, 20, 25, 30, 35, 40, 50, 60};
    int  ar3[] = {1, 3, 5, 9, 10, 50, 60};
    int  sz1   = sizeof(ar1) / sizeof(int),
         sz2   = sizeof(ar2) / sizeof(int), 
         sz3   = sizeof(ar3) / sizeof(int);
    int  i1    = 0, 
         i2    = 0,
         i3    = 0;
    bool found = ar1[i1] == ar2[i2] && ar1[i1] == ar3[i3];

    for(int i = 0; i < sz1; i++)
        cout << ar1[i] << ' ';
    cout << endl;

    for(i = 0; i < sz2; i++)
        cout << ar2[i] << ' ';
    cout << endl;

    for(i = 0; i < sz3; i++)
        cout << ar3[i] << ' ';
    cout << endl;

    while(!found && (i1 < sz1 - 1 || i2 < sz2 - 1 || i3 < sz3 - 1)) 
    {
        while((ar1[i1] < ar2[i2] || ar1[i1] < ar3[i3]) && i1 < sz1 - 1)
            i1++;
        while((ar2[i2] < ar3[i3] || ar2[i2] < ar1[i1]) && i2 < sz2 - 1)
            i2++;
        while((ar3[i3] < ar1[i1] || ar3[i3] < ar2[i2]) && i3 < sz3 - 1)
            i3++;

        found = ar1[i1] == ar2[i2] && ar1[i1] == ar3[i3];
    }

    if(found)
        cout << ar1[i1] << ' ' << ar2[i2] << ' ' << ar3[i3] << endl;
    else
        cout << "not found" << endl;

    return 0;
}

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)