Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Бинарный поиск.

Автор: ferq 9.1.2006, 22:04

Даны две последовательности 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

Я бы эту задачу чуть по другому решал бы. Ну раз бинарный поиск.
Я написал маленький пример на С++. Извини на паскале уже давно не писал.
Первое что нужно делать, это отсортировать массив 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;
}

Автор: podval 10.1.2006, 09:47

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