Гайки и болты

Рейтинг: -1Ответов: 1Опубликовано: 04.12.2014

Здравствуйте.

С помощью метода быстрой сортировки работающего по принципу разделяй и властвуй решить следующую задачу. "Гайки и болты": Неорганизованный плотник имеет смешанный набор N гаек и N болтов. Цель состоит в том, чтобы найти соответствующие пары гаек и болтов. Каждая гайка соответствует точно одному болту, и каждый болт соответствует точно одной гайке. Соединяя гайку и болт между собой, плотник может узнать из них больше (однако он не может сравнивать непосредственно две гайки или два болта). Разработайте алгоритм для этой задачи, который использует в среднем N log(N) сравнений.

Метод быстрой сортировки:

    private void quickSort(int[] array, int start, int end)
    {
        if (start >= end) return;
        int pivot = array[start];
        int i = start;
        int j = end;
        int temp = 0;

        while (i <= j)
        {
            while (array[i] < pivot)
            {
                i++;
            }
            while (array[j] > pivot)
            {
                j--;
            }
            if (i <= j)
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        if (start < j)
        {
            quickSort(array, start, j);
        }
        if (i < end)
        {
            quickSort(array, i, end);
        }
    }

Прошу помощи в решении задачи, буду очень благодарен.

Ответы

▲ 1

Решить поставленную задачу можно двумя способами:

  1. Итеративное решение
  2. Рекурсивное решение

Вот тут в подробностях описаны два способа решение вашего вопроса, смотри тут