VPF::[C++] Число в массивах - Форум программистов

SoWa

Дата 28.2.2007, 19:05 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 3
Всего: 74

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

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

--------------------

Всем добра smile

Strannik

Дата 28.2.2007, 19:35 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: 1
Всего: 2

Вроде несложно... т.к. массивы отсортированы то должно работать следующее:

Код


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

Это сообщение отредактировал(а) Strannik - 28.2.2007, 19:37

Rockie

Дата 1.3.2007, 12:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31

SoWa, практически тот же вопрос, только немного в другой форме, задавал в теме Сравнение массивов

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

Dov

Дата 3.3.2007, 22:44 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Особо не тестировал, но всё же. 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;
}

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »