반복을 사용하지 않고 배열 반전
오늘 저에게 질문이 왔는데, 저는 그것이 가능하다고 생각하지 않지만, 제가 틀리거나 생각이 지나칠 수 있습니다.어떻게 C에서 반복을 사용하지 않고 배열을 되돌릴 수 있습니까?
제 생각에는 배열이 어떤 크기든 될 수 있고 어떤 형태의 반복도 사용하지 않고는 어떤 C 프로그램도 그런 종류의 지원을 염두에 두고 표현할 수 없기 때문에 불가능하다고 생각합니다.
당신의 질문에 대한 대답은, 예, 반복 없이 배열을 되돌릴 수 있다는 것입니다.질문의 표현 자체는 모호할 수 있지만, 질문의 정신은 분명합니다: 재귀적 알고리즘이 사용될 수 있고, 이러한 의미에서 재귀적 의미에 대한 모호성은 전혀 없습니다.
일류 회사와의 인터뷰 상황에서 이런 질문을 받았다면, 다음의 유사 코드는 재귀가 무엇을 의미하는지를 진정으로 이해한다는 것을 증명하기에 충분할 것입니다.
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]., 위의 역 알고리즘은 다음과 같이 시각화할 수 있습니다.
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
재귀 알고리즘으로 해결되는 모든 문제는 분할 및 정복 패러다임을 따릅니다.
문제는 [둘 이상] 하위 문제로 나뉘는데, 각 하위 문제는 원래 문제보다 작지만(분할) 유사한 방식으로 해결할 수 있습니다.
문제는 각 하위 문제가 독립적이며 재귀적으로 또는 충분히 작으면 간단한 방법으로 해결할 수 있는 [2개 이상의] 하위 문제로 나뉩니다(정복).
문제는 [2개 이상의] 하위 문제로 나뉘는데, 여기서 하위 문제의 결과가 결합되어 원래 문제에 대한 해결책을 제공합니다(결합).
배열을 반전시키기 위한 위의 유사 코드는 위의 기준을 엄격하게 충족합니다.따라서, 이것은 재귀 알고리즘으로 간주될 수 있고 우리는 반복을 사용하지 않고 배열을 반전시킬 수 있다는 것을 의심의 여지 없이 진술할 수 있습니다.
및 재귀 과 같습니다.
재귀적 구현은 알고리즘이 재귀적이라는 것을 의미한다는 것은 일반적인 오해입니다.그들은 동등하지 않습니다.위 솔루션에 대한 자세한 설명을 포함하여 그 이유에 대한 명확한 설명이 있습니다.
반복 및 재귀란 무엇입니까?
지난 1990년, 컴퓨터 과학 분야에서 가장 존경받는 현대 알고리즘 분석 학자인 Thomas H. Cormen, Charles E. Leiserson과 Ronald L. Rivest는 그들의 호평을 받은 알고리즘 입문서를 발표했습니다.이 책은 200개 이상의 존경받는 텍스트들이 그들 자신의 권리로 합쳐진 것이며, 20년 이상 동안 전 세계의 대부분의 일류 대학에서 알고리즘을 가르치는 첫 번째이자 유일한 텍스트로 사용되어 왔습니다, Mssrs.Cormen, Leiserson 및 Rivest는 무엇이 반복을 구성하고 무엇이 재귀를 구성하는지에 대해 명시적이었습니다.
두 개의 고전적인 정렬 알고리즘인 삽입 정렬과 병합 정렬의 분석과 비교에서, 그들은 반복 및 재귀 알고리즘의 기본적인 특성을 설명합니다(반복의 고전적인 수학적 개념이 동일한 맥락에서 사용될 때 명확하게 하기 위해 때때로 증분 알고리즘이라고 함).
첫째, 삽입 정렬은 반복 알고리즘으로 분류되며 동작은 다음과 같이 요약됩니다.
하위 배열 A[1...j-1]를 정렬한 후 단일 항목 A[j]를 적절한 위치에 삽입하여 정렬된 배열 A[1...j]를 생성합니다.
출처: 알고리즘 소개 - Cormen, Leisersen, Rivest, 1990 MIT Press.
이 문은 반복 알고리즘을 알고리즘의 이전 실행("반복")의 결과 또는 상태에 의존하는 것으로 분류하며, 이러한 결과 또는 상태 정보는 현재 반복에 대한 문제를 해결하는 데 사용됩니다.
그러나 병합 정렬은 재귀 알고리즘으로 분류됩니다.재귀 알고리즘은 재귀 알고리즘의 작동을 비재귀 알고리즘과 구별하는 세 가지 기본 기준 집합인 분할 및 정복이라는 처리 패러다임을 준수합니다.알고리즘은 주어진 문제를 처리하는 동안 다음과 같은 경우에 재귀적으로 간주될 수 있습니다.
문제는 [둘 이상] 하위 문제로 나뉘는데, 각 하위 문제는 원래 문제보다 작지만(분할) 유사한 방식으로 해결할 수 있습니다.
문제는 각 하위 문제가 재귀적으로 또는 충분히 작으면 간단한 방법으로 해결될 수 있는 [2개 이상의] 하위 문제로 나뉩니다(정복).
문제는 [2개 이상의] 하위 문제로 나뉘는데, 여기서 하위 문제의 결과가 결합되어 원래 문제에 대한 해결책을 제공합니다(결합).
참조:알고리즘 소개 - Cormen, Leisersen, Rivest, 1990 MIT Press.
반복 알고리즘과 재귀 알고리즘 모두 종료 조건에 도달할 때까지 작업을 계속합니다.삽입 정렬의 종료 조건은 j'번째 항목이 배열 A[1...j]에 올바르게 배치되었다는 것입니다.분할 및 정복 알고리즘의 종료 조건은 패러다임의 기준 2가 바닥을 치는 경우, 즉 하위 문제의 크기가 더 이상의 하위 분할 없이 해결될 수 있을 정도로 충분히 작은 크기에 도달하는 경우입니다.
분할 및 정복 패러다임은 재귀를 허용하기 위해 원래 문제와 유사한 방식으로 하위 문제를 해결해야 합니다.원래 문제는 외부 의존성이 없는 독립형 문제이므로 하위 문제도 외부 의존성이 없는 독립형 문제인 것처럼 해결할 수 있어야 합니다. 특히 다른 하위 문제는 특히 다른 하위 문제에 대해서도 마찬가지입니다.이는 분할 및 정복 알고리즘의 하위 문제가 자연스럽게 독립적이어야 한다는 것을 의미합니다.
반대로 반복 알고리즘에 대한 입력은 알고리즘의 이전 반복을 기반으로 하기 때문에 순서대로 고려하고 처리해야 합니다.이는 반복 간에 의존성을 만들어 문제를 재귀적으로 해결할 수 있는 하위 문제로 나누는 알고리즘을 방지합니다.예를 들어, 삽입 정렬에서 A[1...j] 항목을 두 개의 하위 집합으로 나눌 수 없습니다. 모든 항목 A[1...j-1]이 배치되기 전에 A[1...j-1]의 정렬된 위치가 결정됩니다. A[1...j-1]이 배치되는 동안 A[j]의 실제 올바른 위치가 이동할 수 있기 때문입니다.
재귀 알고리즘 대재귀적 구현
재귀라는 용어에 대한 일반적인 오해는 일부 작업에 대한 재귀적 구현이 자동으로 재귀적 알고리즘으로 문제가 해결되었다는 것을 의미한다는 일반적이고 잘못된 가정이 있다는 사실에서 비롯됩니다.재귀 알고리즘은 재귀적 구현과 동일하지 않으며 이전에도 존재하지 않았습니다.
재귀적 구현은 전체 작업이 해결되는 것과 정확히 같은 방식으로 전체 작업의 하위 부분을 해결하기 위해 결국 스스로를 호출하는 함수 또는 함수 그룹을 포함합니다.재귀 알고리듬(즉, 분할 및 정복 패러다임을 충족하는 알고리듬)이 재귀 구현에 잘 도움이 되는 경우가 발생합니다.그러나 재귀 알고리즘은 다음과 같은 반복 구조를 사용하여 구현될 수 있습니다.for(...)그리고.while(...)재귀 알고리즘을 포함한 모든 알고리즘은 결과를 얻기 위해 일부 작업을 반복적으로 수행하게 됩니다.
이 게시물에 대한 다른 기여자들은 반복 알고리즘이 재귀 함수를 사용하여 구현될 수 있다는 것을 완벽하게 입증했습니다.실제로, 어떤 종료 조건이 충족될 때까지 반복되는 모든 작업에 대해 재귀적 구현이 가능합니다.기본 알고리즘에 분할 또는 결합 단계가 없는 재귀적 구현은 표준 종료 조건을 가진 반복 구현과 동일합니다.
삽입 정렬을 예로 들면, 삽입 정렬이 반복 알고리즘이라는 것을 이미 알고 있습니다(그리고 증명되었습니다).그러나 삽입 정렬의 재귀적 구현을 방지하지는 않습니다.실제로 재귀적 구현은 다음과 같이 매우 쉽게 생성될 수 있습니다.
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
볼 수 있듯이 구현은 반복적입니다.그러나 삽입 정렬은 반복 알고리즘이며 우리가 알고 있는 것입니다.그러면 위의 재귀적 구현을 사용하더라도 삽입 정렬 알고리즘이 재귀적이 되지 않았다는 것을 어떻게 알 수 있을까요?분할 및 정복 패러다임의 세 가지 기준을 알고리즘에 적용하여 확인해 보겠습니다.
문제는 각 하위 문제가 원래 문제보다 작지만 유사한 방식으로 해결할 수 있는 [2개 이상의] 하위 문제로 나뉩니다.
예: 길이가 1인 배열을 제외하고, 항목 A[j]를 배열의 적절한 위치에 삽입하는 방법은 이전의 모든 항목 A[1...j-1]을 배열에 삽입하는 방법과 동일합니다.
이 문제는 [2개 이상의] 하위 문제로 나뉘는데, 각 하위 문제는 독립적이며 재귀적이거나 충분히 작으면 간단한 방법으로 해결할 수 있습니다.
NO: A[j] 항목의 적절한 배치는 A[1...j-1] 항목이 포함된 배열과 정렬되는 항목에 전적으로 의존합니다.따라서 나머지 배열이 처리되기 전에 항목 A[j](항목 ToSort라고 함)가 배열에 배치되지 않습니다.
문제는 [2개 이상의] 하위 문제로 나뉘는데, 여기서 하위 문제의 결과가 결합되어 원래 문제에 대한 해결책을 제공합니다.
NO: 반복 알고리즘이기 때문에 주어진 반복에 A[j] 항목 하나만 제대로 배치할 수 있습니다.공간 A[1...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
이것은 순전히 반복적인 알고리즘입니다.알고리즘의 재귀성을 결정하는 분할 및 정복 패러다임과 비교하여 이 결론에 도달할 수 있는 이유를 알아보겠습니다.
문제는 각 하위 문제가 원래 문제보다 작지만 유사한 방식으로 해결할 수 있는 [2개 이상의] 하위 문제로 나뉩니다.
예: 배열의 반전은 미세한 입자, 요소로 구분되며 각 요소의 처리는 다른 모든 처리 요소와 동일합니다.
이 문제는 [2개 이상의] 하위 문제로 나뉘는데, 각 하위 문제는 독립적이며 재귀적이거나 충분히 작으면 간단한 방법으로 해결할 수 있습니다.
예: 배열에서 요소 i를 반전시킬 수 있습니다. 요소 i + 1(예: i + 1)을 반전시킬 필요가 없습니다.또한, 배열에서 요소 i의 반전은 완료하기 위해 다른 요소 반전의 결과를 요구하지 않습니다.
문제는 [2개 이상의] 하위 문제로 나뉘는데, 여기서 하위 문제의 결과가 결합되어 원래 문제에 대한 해결책을 제공합니다.
NO: 반복 알고리즘이기 때문에 모든 알고리즘 단계에서 하나의 계산 단계만 수행됩니다.문제를 하위 문제로 나누지 않으며 두 개 이상의 하위 문제의 결과를 병합하여 결과를 얻을 수 없습니다.
위의 첫 번째 알고리즘에 대한 위의 분석은 분할 및 정복 패러다임에 맞지 않으므로 재귀 알고리즘으로 간주할 수 없음을 확인했습니다.그러나 기준(1)과 기준(2)이 모두 충족되었기 때문에 재귀 알고리즘이 가능할 것이 분명합니다.
핵심은 반복 솔루션의 하위 문제가 가능한 최소 세분성(즉, 요소)이라는 사실에 있습니다.(시작부터 가장 미세한 세분화를 추구하는 대신) 문제를 연속적으로 더 작은 하위 문제로 나눈 다음 하위 문제의 결과를 병합함으로써 알고리듬을 재귀적으로 만들 수 있습니다.
예를 들어, 라틴 알파벳의 처음 16개 문자를 포함하는 16개 요소의 배열이 있다고 가정합니다(A.., 재귀 알고리즘은 시각적으로 다음과 같습니다.
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개 요소는 하위 문제의 미세한 세분화, 즉 단위 길이 배열이 순방향(5단계, 개별 요소)에 도달할 때까지 점점 더 작은 하위 문제 크기(레벨 1~4)로 분할됩니다.이 시점에서 16개의 어레이 요소는 여전히 정상인 것으로 보입니다.그러나 단일 요소 배열도 자체적으로 반전된 배열이기 때문에 동시에 반전됩니다.그런 다음 단일 요소 배열의 결과를 병합하여 길이가 2인 8개의 역방향 배열을 얻은 다음(6단계), 길이가 4인 4개의 역방향 배열을 얻은 다음(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
보시다시피, 알고리즘은 즉각적인 결과를 제공하는 가장 미세한 하위 문제에 도달할 때까지 문제를 하위 문제로 나눕니다.그런 다음 결과가 병합되는 동안 결과를 반대로 하여 반대의 결과 배열을 제공합니다.이 알고리즘이 재귀적이라고 생각하지만, 분할 및 정복 알고리즘에 대한 세 가지 기준을 적용하여 확인해 보겠습니다.
문제는 각 하위 문제가 원래 문제보다 작지만 유사한 방식으로 해결할 수 있는 [2개 이상의] 하위 문제로 나뉩니다.
예: 레벨 2, 3, 4 또는 5와 동일한 알고리즘을 사용하여 레벨 1에서 어레이를 반전할 수 있습니다.
이 문제는 [2개 이상의] 하위 문제로 나뉘는데, 각 하위 문제는 독립적이며 재귀적이거나 충분히 작으면 간단한 방법으로 해결할 수 있습니다.
예: 단위 길이가 아닌 모든 하위 문제는 문제를 두 개의 독립적인 하위 배열로 나누고 해당 하위 배열을 재귀적으로 반대로 설정하면 해결됩니다.가능한 최소 배열인 단위 길이 배열은 자체적으로 반대되므로 종료 조건과 결합 결과의 보장된 첫 번째 집합을 제공합니다.
문제는 [2개 이상의] 하위 문제로 나뉘는데, 여기서 하위 문제의 결과가 결합되어 원래 문제에 대한 해결책을 제공합니다.
예: 레벨 6, 7, 8 및 9의 모든 문제는 바로 위의 레벨, 즉 하위 문제의 결과로만 구성됩니다.각 수준에서 배열을 반전시키면 전체적으로 반전된 결과가 나타납니다.
볼 수 있듯이, 우리의 재귀 알고리즘은 분할 및 정복 패러다임의 세 가지 기준을 통과했기 때문에 진정한 재귀 알고리즘으로 간주될 수 있습니다.따라서 반복 알고리즘을 사용하지 않고 배열을 되돌릴 수 있습니다.
배열 반전을 위한 원래 반복 알고리듬이 재귀 함수를 사용하여 구현될 수 있다는 점은 흥미롭습니다.이러한 구현을 위한 유사 코드는 다음과 같습니다.
function reverse(array)
if length(array) < 2
return
end
swap array[0] and array[n-1]
reverse(array[1..(n-1)])
end
이는 다른 포스터에서 제안한 솔루션과 유사합니다.이것은 정의된 함수가 배열의 모든 요소에 대해 동일한 작업을 반복적으로 수행하도록 스스로 호출하기 때문에 반복적으로 구현됩니다.그러나 문제를 하위 문제로 분할하지 않고 하위 문제의 결과를 병합하여 최종 결과를 제공하지 않으므로 알고리즘을 재귀적으로 만들지 않습니다.이 경우, 재귀는 단순히 흐름 제어 구성으로 사용되며 알고리즘적으로 전체 결과는 솔루션에 제안된 원래 반복 알고리즘과 정확히 동일한 순서로 동일한 단계 순서를 수행하고 있음을 증명할 수 있습니다.
이것이 반복 알고리즘, 재귀 알고리즘 및 재귀 구현의 차이입니다.
사람들이 댓글에서 말했듯이, 그것은 반복의 정의에 달려 있습니다.
사례 1. 재귀와 다른 프로그래밍 스타일로 반복
반복의 대안으로 재귀(단순히)를 택한다면, 칼라이가 제시한 재귀 솔루션이 정답입니다.
사례 2. 하한 선형 시간으로 반복
반복을 "각 요소 검사"로 간주하면, 배열 반전이 선형 시간을 필요로 하는지 또는 하위 선형 시간에 수행할 수 있는지에 대한 질문이 됩니다.
배열 반전에 대한 하위 선형 알고리즘이 없음을 나타내려면 요소가 n개인 배열을 고려합니다.각 요소를 읽을 필요가 없는 반전을 위해 알고리즘 A가 존재한다고 가정합니다.그리고 거기에는 요소가 존재합니다.a[i]어떤 사람들에게는i0..n-1알고리즘이 절대 읽지 않지만 배열을 올바르게 반전시킬 수 있습니다. (편집: 홀수 길이 배열의 중간 요소를 제외해야 합니다. 이 범위에서 아래 주석을 참조하십시오. 아래 주석을 참조하십시오.) 그러나 이것은 점근적인 경우 알고리즘이 선형인지 또는 하위 선형인지에 영향을 미치지 않습니다.
요소를 않기 입니다.a[i]우리는 그것의 가치를 바꿀 수 있습니다.우리가 이렇게 해요.그런 다음 이 값을 전혀 읽지 않은 알고리즘은 값을 변경하기 전과 같은 반전에 대한 답을 생성합니다.하지만 이 대답은 새로운 가치에 맞지 않을 것입니다.a[i]따라서 적어도 모든 입력 배열 요소(하나 저장)를 읽지 않는 올바른 반전 알고리즘은 존재하지 않습니다.따라서 배열 반전은 O(n)의 하한을 가지며 따라서 반복이 필요합니다(이 시나리오에 대한 작업 정의에 따름).
(이 증명은 어레이 반전만을 위한 것이며 이진 검색 및 요소 조회와 같은 하위 선형 구현이 있는 알고리즘으로는 확장되지 않습니다.)
사례 3. 루핑 구조물로서의 반복
반복이 "조건이 충족될 때까지 루프"로 간주되면, 이것은 조건부 점프가 있는 기계 코드로 해석되며, 일부 심각한 컴파일러 최적화(분기 예측 등의 이점 활용)를 필요로 하는 것으로 알려져 있습니다.이 경우 "반복하지 않고" 수행할 수 있는 방법이 있는지 묻는 사용자는 (직선 코드로) 루프를 풀 것을 염두에 두고 있을 수 있습니다.이 경우 원칙적으로 직선(루프 없음) C 코드를 작성할 수 있습니다.그러나 이 기술은 일반적이지 않습니다. 어레이의 크기를 미리 알고 있을 때만 작동합니다. (답변에 다소 경솔한 사례를 추가하는 것은 미안하지만, 완전성을 위해, 그리고 이런 식으로 사용되는 "반복"이라는 용어를 들었기 때문에, 루프 언롤링은 중요한 컴파일러 최적화입니다.)
재귀 함수를 사용합니다.
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);
}
위의 방법을 역방향(array,0,length of array-1)으로 호출합니다.
정렬된 배열을 되돌리는 재귀 함수를 구현합니다.즉, 배열 [1, 2, 3, 4, 5]이 주어지면 절차는 [5, 4, 3, 2, 1]을 반환해야 합니다.
void reverse(int a[], int start, int end )
{
std::cout<<a[end] <<std::endl;
if(end == start)
return;
reverse(a, start, end-1);
}
배열 값을 인쇄하는 데 루프가 필요하지 않기 때문에 이 방법이 더 낫습니다.
자바스크립트 함수에서 재귀를 이용한 깔끔한 해결책이 있습니다.배열 자체 이외의 매개 변수는 필요하지 않습니다.
/* 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을 사용하여 배열 슬라이싱을 수행하지 않으면 최종 결과의 첫 번째 요소로 배열이 표시됩니다.왜 그래야 하는지 잘 모르겠습니다.
#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]);
}
}
한 가지 해결책은 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
void swap(int v[], int v_start, int v_middle, int v_end) {
int *aux = calloc(v_middle - v_start, sizeof(int));
int k = 0;
for(int i = v_start; i <= v_middle; i++) {
aux[k] = v[i];
k = k + 1;
}
k = v_start;
for(int i = v_middle + 1; i <= v_end; i++) {
v[k] = v[i];
k = k + 1;
}
for(int i = 0; i <= v_middle - v_start; i++) {
v[k] = aux[i];
k = k + 1;
}
}
void divide(int v[], int v_start, int v_end) {
if(v_start < v_end) {
int v_middle = (v_start + v_start)/2;
divide(v, v_start, v_middle);
divide(v, v_middle + 1, v_end);
swap(v, v_start, v_middle, v_end);
}
}
int main() {
int v[10] = {4, 20, 12, 100, 50, 9}, n = 6;
printf("Array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", v[i]);
}
printf("\n\n");
divide(v, 0, n - 1);
printf("Reversed: \n");
for (int i = 0; i < n; i++) {
printf("%d ", v[i]);
}
return 0;
}
언급URL : https://stackoverflow.com/questions/11322514/reverse-an-array-without-using-iteration
'codememo' 카테고리의 다른 글
| django-rest-framework serializer를 사용하여 외부 키 값을 검색하는 중 (0) | 2023.07.22 |
|---|---|
| 커서에서 행 수를 찾는 방법 (0) | 2023.07.22 |
| 장고에서 언제 새로운 앱(시작 앱 포함)을 만들 수 있습니까? (0) | 2023.07.22 |
| 데이터 볼륨을 사용하는 MariaDB Docker 컨테이너 - 오류 2002, 소켓을 통해 연결할 수 없음 (0) | 2023.07.22 |
| 데이터베이스 열에서 행 생성 (0) | 2023.07.22 |