블 루 브리지 컵 준비 경기: 알고리즘 훈련 2 의 차 멱 표시 (재 귀)

문제 설명 은 모든 정수 가 2 진법 으로 표시 할 수 있다. 예 를 들 어 137 의 2 진법 은 1000101 을 나타 낸다.이 2 진법 을 2 의 차 멱 의 합 을 나타 내 는 형식 으로 차 멱 을 앞 세 워 다음 과 같은 표현 식 을 얻 을 수 있 습 니 다. 137 = 27 + 23 + 2 ^ 0 현재 약 속 된 멱 차 는 괄호 로 표시 합 니 다. 즉, a ^ b 는 a (b) 로 표시 합 니 다. 이때 137 은 2 (7) + 2 (3) + 2 (0) 로 한 걸음 더 나 아 갑 니 다. 7 = 22 + 2 + 20 (2 ^ 1 은 2 로 표시 합 니 다)3 = 2 + 2 ^ 0 그래서 마지막 137 은 2 (2 (2) + 2 (0) + 2 (2 + 2 (0) + 2 (0) + 2 (0) 와 같다.출력 형식 이 약정 에 부합 되 는 n 의 0, 2 는 (표시 에 빈 칸 이 있 으 면 안 됨) 샘플 입력 137 샘플 출력 2 (2 (2) + 2 + 2 (0) + 2 (2 + 2 (0) + 2 (0) + 2 (0) 샘플 입력 1315 샘플 출력 2 (2 (2 + 2 (0) + 2) + 2 (2 + 2 (0)) + 2 (2 (2) + 2 (0) + 2 (0) 알림 용 재 귀적 실현 이 간단 하 며 재 귀적 으로 출력 할 수 있 습 니 다.
개인 분석: 이 문 제 는 힌트 도 분명하게 말 했 습 니 다. 시험 점 은 재 귀 에 있 습 니 다!문 제 를 읽 으 면서 우 리 는 재 귀적 인 사상 을 대충 느 낄 수 있다. 이것 은 분명 하 다!자, 분석 시작:

 	int r=0;
    while(pow(2,r)<=n)
    {
        r++;
    }
    r--;

여기 서 왜 뒤에 r - - (r 대표 지수) 를 해 야 합 니까? 예 를 들 어 우리 n 은 32 와 같 습 니 다. 분명히 2 ^ 5 = 32 는 r = 5 시 에 while 순환 의 조건 을 만족 시 킬 때 r + r 는 6 이지 만 2 ^ 6 = 64 이기 때문에 뒤에 r - 뒤 에는 재 귀 입 니 다. 핵심 적 인 부분 은 제 가 설명 하 겠 습 니 다.

	int other=n-pow(2,r);
    if(other)
    {
        cout<<"+";
        f(other);
    }

예 를 들 어 샘플 137 은 2 (7) + 2 (3) + 2 (0) 로 표시 할 수 있다. 처음에 우리 가 얻 은 것 은 r = = 7 이 고 재 귀 를 하면 2 (2 (2) + 2 (0) 를 얻 을 수 있다. 이것 은 앞의 부분 일 뿐 이 고 분명 한 부분 은 우리 가 other 에 게 할당 한 다음 에 계속 재 귀 를 해서 뒤의 두 부분 + 2 (2 + 2 (0) + 2 (0) 를 얻 을 수 있 기 때문에 마지막 사례 수출: 2 (2 (2) + 2 (0) + 2 (2 + 2) + 2 (0) + 2 (0) + 2 (0) + 2 (0)
구체 적 인 코드 는 다음 과 같다: AC

#include
#include
using namespace std;
void f(int n)
{
    int r=0;
    while(pow(2,r)<=n)
    {
        r++;
    }
    r--;
    if(r==0)
    {
        cout<<"2(0)";
    }
    else if(r==1)
    {
        cout<<"2";
    }
    else
    {
        cout<<"2(";
        f(r);
        cout<<")";
    }
    int other=n-pow(2,r);
    if(other)
    {
        cout<<"+";
        f(other);
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        f(n);
        cout<<endl;
    }
    return 0;
}

      ，