Обратный массив без использования итерации

Сегодня мне задали вопрос, и я не верю, что это возможно, но я могу ошибаться или думаю об этом. Как вы можете изменить массив без использования итерации в C?

Моя мысль заключается в том, что это невозможно из-за того, что массив может быть любого размера и что никакая программа C не может быть выражена с такой поддержкой в ​​виду, не используя какую-либо форму итерации.

Ответы

Ответ 1

Ответ на ваш вопрос заключается в том, что да, можно изменить массив без итерации. Однако формулировка самого вопроса может быть неоднозначной, однако дух вопроса очевиден: можно использовать рекурсивный алгоритм; и нет никакой двусмысленности вообще относительно значения рекурсивного в этом смысле.

Если в ситуации интервью с компанией, занимающейся вопросами высшего полета, вас задали этот вопрос, тогда будет достаточно следующего псевдокода, чтобы продемонстрировать вам по-настоящему понятное, что подразумевается под рекурсией:

function reverse(array)

    if (length(array) < 2) then
        return array

    left_half = reverse(array[0 .. (n/2)-1])
    right_half = reverse(array[(n/2) .. (n-1)])

    return right_half + left_half

end

Например, если у нас есть массив из 16 элементов, содержащий первые 16 букв латинского алфавита, [A].. [P], вышеупомянутый обратный алгоритм можно визуализировать следующим образом:

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Recurse
2.        ABCDEFGH                IJKLMNOP           Recurse
3.    ABCD        EFGH        IJKL        MNOP       Recurse
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Recurse

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Reverse
7.    DCBA        HGFE        LKJI        PONM       Reverse
8.        HGFEDCBA                PONMLKJI           Reverse
9.                PONMLKJIHGFEDCBA                   Reverse

                  Reversed Output

Любая проблема, решаемая с помощью рекурсивного алгоритма, следует парадигме Divide и Conquer, а именно:

  • Задача делится на [две или более] под-проблемы, где каждая подзадача меньше, но может быть решена аналогично исходной задаче (Разделить).

  • Проблема разделяется на [две или более] субадресы, где каждая подзадача является независимой и может быть решенной либо рекурсивно, либо простым способом, если она достаточно мала (Conquer).

  • Проблема разделяется на [две или более] субадресы, где результаты этих подзадач объединяются, чтобы дать решение исходной задачи (Объединить).

Псевдокод выше для реверсирования массива строго удовлетворяет приведенным выше критериям. Таким образом, его можно считать рекурсивным алгоритмом, и мы можем без всяких сомнений утверждать, что реверсивный массив можно сделать без использования итерации.

ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИОННАЯ ИНФОРМАЦИЯ
Разница между итерацией, рекурсивными реализациями и рекурсивными алгоритмами

Это распространенное недоразумение в том, что рекурсивная реализация означает, что алгоритм является рекурсивным. Они не эквивалентны. Вот окончательное объяснение того, почему, включая подробное объяснение вышеупомянутого решения.


Что такое итерация и рекурсия?

Еще в 1990 году три из самых уважаемых ученых современного алгоритма анализа в области информатики, Thomas H. Cormen, Чарльз Э. Лейзерсон и Рональд Л. Ривест, выпустили свои знаменитые Введение в алгоритмы. В этой книге, которая представляла собой совокупность более чем 200 уважаемых текстов в своем собственном праве и которая более 20 лет использовалась в качестве первого и единственного текста для обучения алгоритмам в большинстве университетов высшего уровня по всему миру, Mssrs, Кормен, Лейсерсон и Ривест были откровенно о том, что представляет собой Итерацию и что представляет собой рекурсирование.

В своем анализе и сравнении двух классических алгоритмов сортировки, Sorting Sort и Merge Sort, они объясняют фундаментальные свойства итеративных и рекурсивных алгоритмов (иногда называемых инкрементальными алгоритмами, чтобы устранить неоднозначность, когда классическое математическое понятие iteration используется в том же контексте).

Во-первых, Сортировка вставки классифицируется как Итеративный алгоритм, с его поведением суммируется следующим образом:

Сопоставив подмассиво A [1..j-1], мы вставим один элемент A [j] в его надлежащее место, получив отсортированный массив A [1..j].

Источник: Введение в алгоритмы - Cormen, Leisersen, Rivest, 1990 MIT Press

Этот оператор классифицирует итеративный алгоритм как тот, который полагается на результат или состояние предыдущего выполнения ( "итерация" ) алгоритма и что такие результаты или информация о состоянии затем используются для решения проблемы для текущей итерации.

Слияние Сортировка, с другой стороны, классифицируется как рекурсивный алгоритм. Рекурсивный алгоритм соответствует парадигме обработки Divide и Conquer, которая представляет собой набор из трех основных критериев, которые различают работу рекурсивных алгоритмов от нерекурсивных алгоритмов. Алгоритм можно считать рекурсивным, если при обработке данной проблемы:

  • Задача делится на [две или более] под-проблемы, где каждая подзадача меньше, но может быть решена аналогично исходной задаче (Разделить).

  • Проблема разделяется на [две или более] субадресы, где каждая подзадача может быть решена либо рекурсивно, либо простым способом, если она достаточно мала (Conquer).

  • Проблема разделяется на [две или более] субадресы, где результаты этих подзадач объединяются, чтобы дать решение исходной задачи (Объединить).

Ссылка: Введение в алгоритмы - Cormen, Leisersen, Rivest, 1990 MIT Press

Итеративные алгоритмы и рекурсивные алгоритмы продолжают свою работу до тех пор, пока не будет достигнуто условие завершения. Условием завершения в Sorting Sort является то, что j-й элемент был правильно помещен в массив A [1..j]. Условие завершения в алгоритме Divide и Conquer заключается в том, когда критерий 2 парадигмы "заканчивается", т.е. Размер подзадачи достигает достаточно малого размера, что ее можно решить без дальнейшего разделения.

Важно отметить, что парадигма Divide and Conquer требует, чтобы субадресы были разрешимы аналогично исходной проблеме, позволяющей рекурсию. Поскольку исходной проблемой является автономная проблема, без внешних зависимостей, следует, что подзадачи также должны быть разрешимы, как если бы они были автономными проблемами без внешних зависимостей, особенно по другим подзадачам. Это означает, что суб-проблемы в алгоритмах Divide и Conquer должны быть естественными независимыми.

И наоборот, не менее важно отметить, что ввод в итеративные алгоритмы основан на предыдущих итерациях алгоритма и поэтому должен рассматриваться и обрабатываться по порядку. Это создает зависимости между итерациями, которые препятствуют алгоритму, делящему проблему на подзадачи, которые могут быть рекурсивно решены. Например, при сортировке вставки вы не можете разделить элементы A [1..j] на два подмножества, чтобы отсортированная позиция в массиве A [j] принималась перед всеми элементами A [1..j-1 ], поскольку реальное правильное положение A [j] может перемещаться, в то время как любой из A [1..j-1] сами размещаются.

Рекурсивные алгоритмы против рекурсивных реализаций

Общее непонимание термина рекурсия проистекает из того, что существует общее и неправильное предположение, что рекурсивная реализация для некоторой задачи автоматически означает, что проблема решена с помощью рекурсивного алгоритма. Рекурсивные алгоритмы не совпадают с рекурсивными реализациями и никогда не были.

Рекурсивная реализация включает в себя функцию или группу функций, которые в конечном итоге назовут себя, чтобы решить часть части общей задачи точно так же, как и в решении общей задачи. Бывает, что рекурсивные алгоритмы (т.е. те, которые удовлетворяют парадигме Divide and Conquer), хорошо зарекомендовали себя при рекурсивных реализациях. Однако рекурсивные алгоритмы могут быть реализованы с использованием только итеративных конструкций, таких как for(...) и while(...), поскольку все алгоритмы, включая рекурсивные алгоритмы, в конечном итоге выполняют некоторую задачу повторно, чтобы получить результат.

Другие участники этой публикации отлично продемонстрировали, что итеративные алгоритмы могут быть реализованы с использованием рекурсивной функции. Фактически, рекурсивные реализации возможны для всего, что требует повторения, до тех пор, пока не будет выполнено какое-либо условие завершения. Рекурсивные реализации, в которых нет шаге Divide или Combine в базовом алгоритме, эквивалентны итеративным реализациям со стандартным условием завершения.

Взятие Insertion Sort в качестве примера, мы уже знаем (и было доказано), что Sorting Sorting является итеративным алгоритмом. Однако это не мешает рекурсивной реализации Sorting Sorting. Фактически, рекурсивная реализация может быть создана очень легко следующим образом:

function insertionSort(array)

    if (length(array) == 1)
        return array
    end

    itemToSort = array[length(array)]
    array = insertionSort(array[1 .. (length(array)-1)])

    find position of itemToSort in array
    insert itemToSort into array

    return array

end

Как видно, реализация является рекурсивной. Однако Insertion Sort - это итеративный алгоритм, и это мы знаем. Итак, как мы узнаем, что даже используя вышеупомянутую рекурсивную реализацию, наш алгоритм сортировки вставки не стал рекурсивным? Применим три критерия парадигмы Divide и Conquer к нашему алгоритму и проверим.

  • Задача делится на [две или более] суб-проблемы, где каждая подзадача меньше, но может быть решена аналогично исходной проблеме.

    ДА. Исключая массив длиной один, метод вставки элемента A [j] в нужное место в массиве идентичен методу, используемому для вставки всех предыдущих элементов A [1..j-1] в массив.

  • Проблема разделяется на [две или более] субадресы, где каждая подзадача независима и может быть решена либо рекурсивно, либо простым образом, если она достаточно мала.

    НЕТ. Правильное размещение элемента A [j] полностью зависит от массива, содержащего элементы A [1..j-1], и отсортированные элементы. Следовательно, элемент A [j] (называемый itemToSort) не помещается в массив до обработки остальной части массива.

  • Задача состоит из [двух или более] под-проблем, где результаты этих подзадач объединяются, чтобы дать решение исходной задачи.

    НЕТ. Будучи итерационным алгоритмом, только один элемент A [j] может быть правильно помещен в любую итерацию. Пространство A [1..j] не делится на под-задачи, где A [1], A [2]... A [j] все правильно размещены независимо, а затем все эти правильно размещенные элементы объединены, чтобы дать отсортированный массив.

Очевидно, что наша рекурсивная реализация не сделала алгоритм вставки Сортировка рекурсивным по своей природе. Фактически, рекурсия в реализации в этом случае действует как управление потоком, позволяя продолжить итерацию до тех пор, пока условие завершения не будет выполнено. Поэтому использование рекурсивной реализации не изменило наш алгоритм на рекурсивный алгоритм.

Реверсирование массива без использования итерационного алгоритма

Итак, теперь, когда мы понимаем, что делает алгоритм итеративным, и что делает рекурсивным, как это сделать, мы можем изменить массив без использования итерации?

Есть два способа изменить массив. Оба метода требуют, чтобы вы знали длину массива заранее. Итерационный алгоритм предпочитает его эффективность, а его псевдокод выглядит следующим образом:

function reverse(array)

    for each index i = 0 to (length(array) / 2 - 1)
        swap array[i] with array[length(array) - i]
    next

end

Это чисто итерационный алгоритм. Давайте посмотрим, почему мы можем прийти к такому выводу, сравнив его с парадигмой Divide и Conquer, которая определяет рекурсивность алгоритма.

  • Задача делится на [две или более] суб-проблемы, где каждая подзадача меньше, но может быть решена аналогично исходной проблеме.

    ДА. Сторнирование массива разбивается на его тончайшую детализацию, элементы и обработку для каждого элемента идентичны всем другим обрабатываемым элементам.

  • Проблема разделяется на [две или более] субадресы, где каждая подзадача независима и может быть решена либо рекурсивно, либо простым образом, если она достаточно мала.

    ДА. Сторнирование элемента я в массиве возможно без необходимости повторного обращения к элементу (i + 1) (например). Более того, изменение элемента я в массиве не требует результатов других обращений элементов, чтобы они могли быть завершены.

  • Задача состоит из [двух или более] под-проблем, где результаты этих подзадач объединяются, чтобы дать решение исходной задачи.

    НЕТ: будучи итеративным алгоритмом, на каждом шаге алгоритма выполняется только один этап вычисления. Он не делит проблемы на подзадачи и нет слияния результатов двух или более подзадач, чтобы получить результат.

Вышеупомянутый analsys нашего первого алгоритма выше подтвердил, что он не соответствует парадигме Divide и Conquer и поэтому не может считаться рекурсивным алгоритмом. Однако, поскольку оба критерия (1) и критерии (2) были удовлетворены, очевидно, что рекурсивный алгоритм может быть возможен.

Ключевым моментом является то, что подзадачи в нашем итеративном решении имеют наименьшую возможную детализацию (т.е. элементы). Разделив задачу на последовательно более мелкие и более мелкие подзадачи (вместо того, чтобы с самого начала перейти на самую точную детализацию), а затем слияние результатов подзадач, алгоритм можно сделать рекурсивным.

Например, если у нас есть массив из 16 элементов, содержащих первые 16 букв латинского алфавита (A..P), рекурсивный алгоритм визуально выглядит следующим образом:

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Divide
2.        ABCDEFGH                IJKLMNOP           Divide
3.    ABCD        EFGH        IJKL        MNOP       Divide
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Divide

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Conquer (Reverse) and Merge
7.    DCBA        HGFE        LKJI        PONM       Conquer (Reverse) and Merge
8.        HGFEDCBA                PONMLKJI           Conquer (Reverse) and Merge
9.                PONMLKJIHGFEDCBA                   Conquer (Reverse) and Merge

                  Reversed Output

На верхнем уровне 16 элементов постепенно разбиваются на более мелкие размеры подзадач точно равного размера (уровни с 1 по 4), пока мы не достигнем тончайшей детализации суб-проблемы; единичные массивы в прямом порядке (шаг 5, отдельные элементы). На данный момент, наши 16 элементов массива все еще выглядят в порядке. Тем не менее, они в то же время также обращаются вспять, поскольку один элементный массив также является обратным массивом в своем собственном праве. Результаты одноэлементных массивов затем объединяются для получения восьми реверсивных массивов длины два (шаг 6), а затем снова объединяются для получения четырех реверсивных массивов длиной четыре (шаг 7) и т.д. До тех пор, пока наш исходный массив не будет восстановлен в обратном порядке (шаги с 6 по 9).

Псевдокод для рекурсивного алгоритма для обращения к массиву выглядит следующим образом:

function reverse(array)

    /* check terminating condition. all single elements are also reversed
     * arrays of unit length.
     */
    if (length(array) < 2) then
        return array

    /* divide problem in two equal sub-problems. we process the sub-problems
     * in reverse order so that when combined the array has been reversed.
     */
    return reverse(array[(n/2) .. (n-1)]) + reverse(array[0 .. ((n/2)-1)])

end

Как вы можете видеть, алгоритм разбивает проблему на подзадачи до тех пор, пока не достигнет наилучшей детализации подзадачи, которая дает мгновенный результат. Затем он меняет результаты, пока они объединяются, чтобы получить реверсивный массив результатов. Хотя мы считаем, что этот алгоритм рекурсивный, применим три критерия для алгоритмов Divide и Conquer для подтверждения.

  • Задача делится на [две или более] суб-проблемы, где каждая подзадача меньше, но может быть решена аналогично исходной проблеме.

    ДА. Реверсирование массива на уровне один может быть выполнено с использованием того же алгоритма, что и на уровне 2, 3, 4 или пять.

  • Проблема разделяется на [две или более] субадресы, где каждая подзадача независима и может быть решена либо рекурсивно, либо простым образом, если она достаточно мала.

    ДА. Каждая подзадача, которая не является единичной длиной, решается путем разбиения задачи на две независимые под-массивы и рекурсивное реверсирование этих под-массивов. Массивы длины блока, самые маленькие массивы, сами по себе, меняются на противоположные, что обеспечивает условие завершения и гарантированный первый набор результатов комбайнов.

  • Задача состоит из [двух или более] под-проблем, где результаты этих подзадач объединяются, чтобы дать решение исходной задачи.

    ДА. Каждая проблема на уровнях 6, 7, 8 и 9 состоит только из результатов сразу же выше уровня; т.е. их подсуммы. Сторнирование массива на каждом уровне приводит к обратному результату в целом.

Как видно, наш рекурсивный алгоритм прошел три критерия для парадигмы Divide и Conquer и поэтому может считаться истинно рекурсивным алгоритмом. Следовательно, можно изменить массив без использования итерационного алгоритма.

Интересно отметить, что наш исходный итеративный алгоритм обращения массива может быть реализован с использованием рекурсивной функции. Псевдокод для такой реализации выглядит следующим образом:

function reverse(array)

    if length(array) < 2
        return
    end

    swap array[0] and array[n-1]
    reverse(array[1..(n-1)])

end

Это похоже на решения, предлагаемые другими плакатами. Это рекурсивная реализация, так как определенная функция в конечном итоге вызывает себя для многократного выполнения одной и той же задачи над всеми элементами массива. Однако это означает, что не делает алгоритм рекурсивным, так как нет разделения проблем на подзадачи, и нет слияния результатов подзадач, чтобы дать окончательный результат. В этом случае рекурсия просто используется в качестве конструкции управления потоком, и алгоритмически общий результат может быть доказан как выполнение той же последовательности шагов точно в том же порядке, что и исходный итеративный алгоритм, предложенный для решение.

В этом разница между Итеративным алгоритмом, Рекурсивным алгоритмом и Рекурсивная реализация.

Ответ 2

Как говорили в комментариях люди, это зависит от определения итерации.

Случай 1. Итерация как стиль программирования, отличный от рекурсии

Если вы берете рекурсию (просто) как альтернативу итерации, то правильный ответ, представленный Калаем, является правильным ответом.

Случай 2. Итерация как линейное время с нижней границей

Если вы принимаете итерацию как "проверяя каждый элемент", тогда вопрос становится одним из того, требует ли реверсирование массива линейное время или может быть выполнено в сублинейное время.

Чтобы показать, что нет сублинейного алгоритма обращения массива, рассмотрим массив с n элементами. Предположим, что существует алгоритм A для разворота, который не нуждается в чтении каждого элемента. Тогда для i в 0..n-1 существует элемент a[i], который алгоритм никогда не читает, но все же способен правильно изменить массив. ( EDIT: мы должны исключить средний элемент массива нечетной длины - см. комментарии ниже этого диапазона - см. комментарии ниже - но это не влияет на то, является ли алгоритм линейным или сублинейной в асимптотическом случае.)

Поскольку алгоритм никогда не читает элемент a[i], мы можем изменить его значение. Скажем, мы делаем это. Тогда алгоритм, никогда не прочитавший это значение, даст тот же ответ для разворота, как и прежде, чем изменит его значение. Но этот ответ будет неправильным для нового значения a[i]. Следовательно, правильный алгоритм обращения, который, по крайней мере, не считывает каждый элемент входного массива (кроме одного), не существует. Следовательно, разворот массива имеет нижнюю границу O (n) и, следовательно, требует итерации (в соответствии с рабочим определением для этого сценария).

(Обратите внимание, что это доказательство является только для обращения массива и не распространяется на алгоритмы, которые действительно имеют сублинейные реализации, такие как бинарный поиск и поиск элементов.)

Случай 3. Итерация как петлевая конструкция

Если итерация принимается за "цикл до тех пор, пока не будет выполнено условие", это переводит в машинный код с условными переходами, которые, как известно, требуют некоторой серьезной оптимизации компилятора (используя предсказание ветвления и т.д.). В этом случае кто-то спрашивает, есть способ сделать что-либо "без итерации", возможно, имеет смысл разворачивать петлю цикла (к прямолинейному коду). В этом случае вы можете в принципе писать прямолинейный (без петли) C-код. Но этот метод не является общим; он работает только в том случае, если вы заранее знаете размер массива. (Извините, что добавил этот ответ более или менее, но я сделал это для полноты и потому, что я слышал, что термин "итерация" используется таким образом, а циклическое разворачивание - важная оптимизация компилятора.)

Ответ 3

Использовать рекурсивную функцию.

void reverse(int a[],int start,int end)
{
     int temp;
     temp = a[start];
     a[start] = a[end];
     a[end] = temp;


    if(start==end ||start==end-1)
       return;
    reverse(a, start+1, end-1);
}

Просто вызовите вышеуказанный метод как reverse (array, 0, lengthofarray-1)

Ответ 4

Реализовать рекурсивную функцию для изменения отсортированного массива. Т.е., учитывая массив [1, 2, 3, 4, 5] ваш процедура должна возвращать [5, 4, 3, 2, 1].

Ответ 5

Здесь аккуратное решение, использующее рекурсию в функции javascript. Он не требует каких-либо параметров, кроме самого массива.

/* Use recursion to reverse an array */
function reverse(a){
    if(a.length==undefined || a.length<2){
        return a;
    }
    b=[];
    b.push(reverse(copyChop(a)));
    b.push(a[0]);
    return b;
    /* Return a copy of an array minus the first element */
    function copyChop(a){ 
        b=a.slice(1); 
        return b;
    }
}

Вызовите его следующим образом:

reverse([1,2,3,4]);

Обратите внимание, что если вы не используете вложенную функцию copyChop для обработки среза массива, вы получите массив как первый элемент в конечном результате. Не совсем уверен, почему это должно быть так.

Ответ 6

   #include<stdio.h>


   void rev(int *a,int i,int n)
  {

if(i<n/2)
{
    int temp = a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=temp;
    rev(a,++i,n);
 }
}
int main()
    {
    int array[] = {3,2,4,5,6,7,8};
   int len = (sizeof(array)/sizeof(int));
   rev(array,0,len);    
   for(int i=0;i<len;i++)
   {
    printf("\n array[%d]->%d",i,array[i]);
  }
}