문자열을 뒤집는 재귀 함수

Question

문자열을 뒤집을 재귀 함수를 작성하려고합니다. 재귀에 대한 기본이 확실하지만 작업 할 수 없다는 것을 확신합니다.

기준 : 길이가 < = 1이면. 그렇지 ,

내가 strcat를 사용하여 추가 할 생각 ... 처음과 마지막 요소를 교환하고 앞으로 하나 개의 요소를 발전 1.

내가 1 길이를 줄이는에 문제가에 의해 길이를 줄이 각각의 재귀와 함께 앞에있는 첫 번째 요소가 있지만 상수에만 적합합니다 ...

참고 2 : 나는 함수의 서명을 변경할 수 없으며 다른 라이브러리를 사용할 수 없습니다.

여기서 사용하는 라이브러리 및 명령을 편집하지 마십시오. 이들은 내가 알고 사용하는 것들입니다.

#include <string.h> 
#include <iostream> 

using namespace std; 
void recuverse(char s[]); 
int main() 
{ 
    char s[] = "abcde"; 
    recuverse(s); 
    cout << s << endl; 
} 

void recuverse(char s[]){ 
    int len = strlen(s); 
    int i; 

    if (len <= 1)return; 
    else{ 
     for (i = len-1; i>0; i--){ 

      swap(s[0], s[i]); 

      recuverse(s + 1); 
     } 
    } 
} 

Answer 1

구현 내부의 for 루프가 필요하지 않습니다 : 당신이 루프를 갖는 결과로 너무 많은 스왑을 수행하고 있습니다. 사실,이 연습의 핵심은 루프를 제거하는 것이 었습니다.

한 번 문자열의 길이를 측정하는 추가 기능을 추가하여 구현을 수정, 다음과 같이 두 개의 인수 recuverse_impl를 호출

void recuverse_impl(char *s, size_t len) { 
    // Base case 
    if (len < 2) return; 
    // Swap elements the two ends 
    swap(s[0], s[len-1]); 
    // then call recuverse_impl again 
    recuverse_impl(s+1, len-2); 
} 

void recuverse(char s[]){ 
    recuverse_impl(s, strlen(s)); 
} 

어떤 이유에 대한 요구 사항은 허용하지 된 경우 다음과 같이 명시 적으로 길이를 통과, 당신은 구현을 변경할 수 있습니다 :

void recuverse(char *s) { 
    // Compute the length 
    size_t len = strlen(s); 
    // Do the base case 
    if (len < 2) return; 
    // Squirrel away the last element, and replace it with '\0' 
    char t = s[len-1]; 
    s[len-1] = '\0'; 
    // Make a recursive call 
    recuverse(s+1); 
    // Now complete the swap 
    s[len-1] = s[0]; 
    s[0] = t; 
} 

Demo.

Answer 2

여기 재귀 역의 적절한 버전 :

void reverse(char *s, char *e) { 
    if (s < e) { 
     char t = *s; 
     *s = *e; 
     *e = t; 
     reverse(s+1, e-1); // here is length is decreased by 2 
    } 
} 

void recuverse(char s[]) { 
    int len = strlen(s); 

    reverse(s, s+len-1); 
} 

Answer 3

이 시도 :

void recuverse(char s[]) 
{ 
    int len = strlen(s); 
    if (len <= 1) 
     return; 
    char c = s[len-1]; 
    s[len-1] = 0; 
    recuverse(s+1); 
    s[len-1] = s[0]; 
    s[0] = c; 
} 

Answer 4

는 mirror(cs) = cat(mirror(s),c) (c는 문자와 s 문자열 인) 발언 경우 :

void rev(char *s) { 
    if (*s==0) return; 
    rev(s+1); 
    sprintf(s,"%s%c",s+1,*s); 
} 

Answer 5

C 아래 ++ 구현을 반복적으로 문자열을 여기에

자료 케이스 역 않습니다 문자열에서 NULL 문자를 찾고 있습니다.

#include<bits/stdc++.h> 
using namespace std; 


    void reverse(string s,long i){ 


     if(s[i] == '\0') 
     return; 


     reverse(s,i+1); 

     cout<<s[i]; 
     return; 
    } 

    int main(){ 


     string s; 

     cin>>s; 


     reverse(s,0); 
     return 0; 
    } 

Answer 6

이것은 서명을 변경하지 않지만, 중간에 도달 할 때까지 std::swap을 사용하여 s [begin]와 s [end]을 교체합니다.재귀를 달성하고도 서명을 유지하려면 전역 변수로, 중간 길이 시작 선언한다 (당신이해야 의미 넣은 사람은 아니다) 할 수 있습니다

이

int beg = 0; 
int len = 0; 
int mid = 0; 

void recuverse(char s[]) { 
    if (beg == 0) { // this block runs one time. 
     len = strlen(s)-1; 
     mid = len/2; 
    } 
    if (beg == mid) 
     return; 
    swap(s[beg], s[len]); 
    ++beg, --len; 
    recuverse(s); 
} 

출력 : edcba

Answer 7

당신이 시도 할 수 있습니다 :

#include <string.h> 
#include <iostream> 

using namespace std; 

void recuverse(char *s, int right); 

int main() 
{ 
    char s[] = "abcde"; 
    recuverse(s , 0); 
    cout << s << endl; 
} 

void recuverse(char *s, int right){ // Here right is the position of the right position(from right to left) of character with which you will swap 
    int len = strlen(s); 
    int i; 

    if (len <=right)return; 

    swap(s[0], s[len-1-right]); 

    recuverse(s + 1, right+1); 
} 

Answer 8

내가 알 수있는 바로는 이것이 부당한 제한으로 요구 한 것을 성취 할 수있는 유일한 방법입니다.

이것은 바보 같을 것입니다. 어리 석음이 기능을 작성하는 방법이지만 지정된 지침 내에서 요청한 사항을 수행합니다.

// Reverses a string in place. 
// Note: string cannot be a constant, without write permission 
void reverse(char s[]) 
{ 
    // Get string length 
    int len = strlen(s); 

    if (len > 2) 
    { 
     // Save last character 
     char lastChar = s[len - 1]; 

     // Temporarily shorten string by replacing last character 
     // with a null-terminator character 
     s[len - 1] = '\0'; 

     // Recursively swap remaining characters 
     reverse(s + 1); 

     // Swap first and last character 
     s[len - 1] = s[0]; 
     s[0] = lastChar; 
    } 
} 

재귀가이 문제에 접근하는 가장 효율적인 방법이 아니기 때문에 위의 접근 방법을 나쁜 것으로 생각합니다. 재귀가 사용 되더라도이 코드의 재귀 부분에 대해 별도의 함수를 작성하는 것이 훨씬 효율적입니다. 여기에는 상태를 추적하고 여기에서 반복되는 일부 논리를 방지하는 추가 인수가 포함될 수 있습니다. 또한 다른 라이브러리를 피하는 것이 바람직하지 않습니다. 특히 C++ 응용 프로그램의 일부가 될 라이브러리가 포함되는 경우에는 특히 그렇습니다.

이러한 제한이 없으면 다음과 같이 역순으로 작성하는 방법이 있습니다.

void reverse(char* s) 
{ 
    char *pEnd = s + (strlen(s) - 1); 
    while (s < pEnd) 
    { 
     char c = *s; 
     *s++ = *pEnd; 
     *pEnd-- = c; 
    } 
} 

Answer 9

My C 솔루션에는 추가 라이브러리 (iostream 대신 stdio)가 사용되며 동일한 기능 시그니처가 사용됩니다.

#include <stdio.h> 
#include <string.h> 

void recuverse(char s[]){ 
    char saved; 
    int len = strlen(s); 
    if (len > 1) { 
     saved = s[len-1]; // keep last char  
     s[len-1] = 0;  // shorten string 
     recuverse(s+1);  // with shorter string 
     s[len-1] = s[0]; // replace last char with first 
     s[0] = saved;  // replace first char with last 
    }      // job done 
} 

int main() 
{ 
    char str0 [] = "";  // test with various 
    char str1 [] = "a"; 
    char str2 [] = "ab"; 
    char str3 [] = "abc"; 
    char str4 [] = "abcd"; 

    recuverse (str0); 
    printf ("'%s'\n", str0); 
    recuverse (str1); 
    printf ("'%s'\n", str1); 
    recuverse (str2); 
    printf ("'%s'\n", str2); 
    recuverse (str3); 
    printf ("'%s'\n", str3); 
    recuverse (str4); 
    printf ("'%s'\n", str4); 
} 

프로그램 출력은

'' 
'a' 
'ba' 
'cba' 
'dcba' 

Answer 10

내가 당신이 당신이 구현하려고 접근하는 것입니다 필요한 이해 것으로 보인다.

당신은

void recuverse(char s[]) 
{ 
    recuverse(s , std::strlen(s)); 
} 

void recuverse(char s[], size_t n) 
{ 
    if (!(n < 2)) 
    { 
     std::swap(s[0], s[n-1]); 
     recuverse(s + 1, n - 2); 
    } 
} 

같은 기능을 쓸 수 그러나 그것이 재귀 함수입니다 void recuverse(char s[]); 작동하지 때문에 그것은 잘못된 솔루션입니다. 재귀적인 함수 void recuverse(char s[], size_t n);입니다. 그러나 귀하의 임무에 따라 재귀가되어야하는 것은 void recuverse(char s[]);입니다.

그래서 유일한 해결책은 다음과 같습니다.

#include <iostream> 
#include <utility> 

char * recuverse(char s[]) 
{ 
    if (*s ) 
    { 
     char *p = s; 

     do 
     { 
      std::swap(*p, *(p + 1)); 
     } while (*p++); 

     recuverse(s); 

     std::swap(*p, *(p - 1)); 
    } 

    return s; 
} 


int main() 
{ 
    char s[] = "abcde"; 

    std::cout << s << std::endl; 
    std::cout << recuverse(s) << std::endl; 

    return 0; 
} 

출력은 또한 당신의 코드를 대체 할 수있는이 재귀 함수는 std::swap 제외하고는 어느 쪽도 표준 기능을 사용하지

abcde 
edcba 

입니다. :)

내가 함수가 반환 형식을 가지고 것을 선호 char * 표준 C 문자열 함수와 비슷한 방식입니다.이 함수가 반환 형식 void을 것이라고하려면 다음이 역 기능을 strlen이 작업은 "ABC"를 간단한 예를 사용하여 단계별로 고려할 수있는 표준 기능없이 어떻게 작동하는지 이해하는

void recuverse(char s[]) 
{ 
    if (*s ) 
    { 
     char *p = s; 

     do 
     { 
      std::swap(*p, *(p + 1)); 
     } while (*p++); 

     recuverse(s); 

     std::swap(*p, *(p - 1)); 
    } 
} 

처럼 보일 것입니다.

그래서 우리는 그것이 종료 제로를 교환 할 때까지이 abc0

while 루프로

while (*p++) ... 

스왑 문자를 기입 할 제로

abc\0 

종료와 함께 문자열을 가지고있다. 첫 번째 재귀 호출에서

루프는 다음

abc0 
bac0 
bca0 
bc0a 

---

이제 함수가 자신을 호출하지만 지금은 문자열이 루프에 따라서

bc0

모양을하고있다

bc0 
cb0 
c0b 

다음 재귀 호출에서

---

인수는 두 문자 그래서 마침내

0c 

를 교환하는 기능이 빈 문자열로 호출 루프에서

C0

될 것입니다. 그래서 그것은 단순히 우리는 영을 종료 TP의 올바른 위치를 이동해야

0cba 

처럼

전체 문자열이 지금 보이는 것을 고려 호출자에게 제어 및 발신자 스왑 문자열의 마지막 문자를 반환 문자열 끝에. 이것은 루프 이후의 스왑으로 수행됩니다. 이다

0c => c0 
-------- 
c0b => cb0 
----------- 
cb0a => cba0 

모든 :)

Answer 11

정적 변수를 사용할 수있는 경우,이

void recuverse(char s[]){ 
    static int e; 
    int z=strlen(s)-e++;   // z is the number of characters to be evaluated 
    if(z>1){  
     char t=*(s+z-1); 
     *(s+z-1)=*s; 
     *s=t; 
     recuverse(s+1); 
    } 
}