Рубрики

Программа на C, чтобы найти ближайшую пару из двух отсортированных массивов

Учитывая два отсортированных массива и число x, найдите пару, сумма которой ближе всего к x, и у пары есть элемент из каждого массива .

Нам даны два массива ar1 [0… m-1] и ar2 [0..n-1] и число x, нам нужно найти пару ar1 [i] + ar2 [j] такую, что абсолютное значение (ar1 [i] + ar2 [j] — x) минимально.

Пример:

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 32      
Output:  1 and 30

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 50      
Output:  7 and 40

C ++

// C ++ программа для поиска пары из двух отсортированных массивов, таких
// что сумма пары ближе всего к данному числу x
#include <climits>
#include <cstdlib>
#include <iostream>

using namespace std;

  
// ar1 [0..m-1] и ar2 [0..n-1] два заданных отсортированных массива
// и х это номер. Эта функция печатает пару из
// оба массива таковы, что сумма пары ближе всего к x.

void printClosest(int ar1[], int ar2[], int m, int n, int x)

{

    // Инициализируем diff между парой sum и x.

    int diff = INT_MAX;

  

    // res_l и res_r являются индексами результата из ar1 [] и ar2 []

    // соответственно

    int res_l, res_r;

  

    // Начинаем с левой стороны ar1 [] и правой стороны ar2 []

    int l = 0, r = n - 1;

    while (l < m && r >= 0) {

        // Если эта пара ближе к x, чем ранее

        // найти ближайший, затем обновить res_l, res_r и diff

        if (abs(ar1[l] + ar2[r] - x) < diff) {

            res_l = l;

            res_r = r;

            diff = abs(ar1[l] + ar2[r] - x);

        }

  

        // Если сумма этой пары больше чем x, перейти к меньшему

        // боковая сторона

        if (ar1[l] + ar2[r] > x)

            r--;

        else // переместимся в большую сторону

            l++;

    }

  

    // Распечатать результат

    cout << "The closest pair is [" << ar1[res_l] << ", "

         << ar2[res_r] << "] \n";

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int ar1[] = { 1, 4, 5, 7 };

    int ar2[] = { 10, 20, 30, 40 };

    int m = sizeof(ar1) / sizeof(ar1[0]);

    int n = sizeof(ar2) / sizeof(ar2[0]);

    int x = 38;

    printClosest(ar1, ar2, m, n, x);

    return 0;

}

Выход:

The closest pair is [7, 30]

Пожалуйста, обратитесь к полной статье на Найти ближайшую пару из двух отсортированных массивов для более подробной информации!

Рекомендуемые посты:

Программа на C, чтобы найти ближайшую пару из двух отсортированных массивов

0.00 (0%) 0 votes