VPF::Бинарный поиск. - Форум программистов

ferq

Дата 9.1.2006, 22:04 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Даны две последовательности A1, A2,..., AN и B1, B2, ..., BM. Ваша задача вывести все общие элементы этих последовательностей в возрастающем порядке.

Входные данные
В первой строке входного файла записаны числа N и M (1 <= N <= 10^3, 1 <= M <= 10^5). Во второй строке записано N чисел, элементы последовательности A. В третьей строке записаны элементы последовательности B (M чисел). Элементы последовательностей разделяются пробелами, гарантируется, что они не превосходят 10^6 по абсолютной величине.

Выходные данные
В первой строке выходного файла выведите число K -- количество различных общих элементов в этих двух последовательностях. Во второй строке выведите K различных общих элементов в возрастающем порядке.

Пример

Ввод

6 8
1 2 5 2 7 3
9 3 4 2 2 1 9 7

Вывод

4
1 2 3 7

Нужен код на pascale или хоть намекните как решать.

Fin

Дата 10.1.2006, 01:23 (ссылка)

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

Загрузка ...

Дракон->Спать();

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

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

Я бы эту задачу чуть по другому решал бы. Ну раз бинарный поиск.
Я написал маленький пример на С++. Извини на паскале уже давно не писал.
Первое что нужно делать, это отсортировать массив A по возрастаюшей. Да кстати ни в коем случае не используй пузырек для этого. 10^3 ээлементов это довольно много для него уже.
Я написал в обших чертах, чтобы понять. Все красивости делай сам. Прочитать подробно про этот алгоритм Д.Кнут "Исскуство программирования" том 3. начиная с 442 страници.

Код


#include <iostream.h>
int main()
{
    const int n=7;
    const int m=13;
    int A[n]={1, 2, 3, 5, 7, 10, 15}; //Massiv uge otsortirovan :)
    int B[m]={9, 3, 4, 2, 1,  7, 8, 15, 16, 22, 10, 25, 6 };
    int levU; int levD;  //Granica verhnya i nignaya
    int beg;
    for (int i=0; i<m; i++)                       // Cikl perebora massiva  B
    {
        levD=0; levU=n-1;                         //Nastraivaem granitsi massiva A
        beg=levD+(levU-levD)/2;
        while (((levU-levD)>1) && (B[i] != A[beg]))              //Sobstvenno poisk
        {
            if (B[i]>A[beg]) levD=beg;
            else levU=beg;
            beg=levD+(levU-levD)/2;
        }
        //Tuta proveryaem udachniy poisk ili net
        if (B[i] == A[levD]) cout << B[i] <<" ";
        if (B[i] == A[levU]) cout << B[i] <<" ";
        if ((beg !=levD) && (beg != levU) && (B[i] == A[beg])) cout << B[i] <<" ";
    }
    cout << endl;
    return 0;
}

Это сообщение отредактировал(а) Fin - 10.1.2006, 01:23

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

Пролетал мимо.

podval

Дата 10.1.2006, 09:47 (ссылка)

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

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

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

Модератор: Тема перемещена из раздела "Алгоритмы"

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