Рубрики

Программа PHP для поиска ближайшей пары из двух отсортированных массивов

Учитывая два отсортированных массива и число 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

PHP

<?php
// PHP программа для поиска пары
// из двух отсортированных массивов таких
// что сумма пары равна
// ближе всего к данному числу x

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

function printClosest($ar1, $ar2,

                      $m, $n, $x)

{

      

    // Инициализируем разницу между

    // пара сумм и х.

    $diff = PHP_INT_MAX;

  

    // результат res_l и res_r

    // индексы из ar1 [] и ar2 []

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

    $res_l

    $res_r;

  

    // Начинаем с левой стороны

    // ar1 [] и правая часть ar2 []

    $l = 0;

    $r = $n - 1;

    while ($l < $m and $r >= 0)

    {

          

        // Если эта пара ближе к

        // х, чем ранее

        // нашли ближайший, то

        // обновляем 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++;

    }

  

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

    echo "The closest pair is [", $ar1[$res_l], ", ", $ar2[$res_r], "] \n";

}

  

    // Код драйвера

    $ar1 = array(1, 4, 5, 7);

    $ar2 = array(10, 20, 30, 40);

    $m = count($ar1);

    $n = count($ar2);

    $x = 38;

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

  
// Этот код предоставлен anuj_67.
?>

Выход:

The closest pair is [7, 30]

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

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

Программа PHP для поиска ближайшей пары из двух отсортированных массивов

0.00 (0%) 0 votes