> 백엔드 개발 > C++ > 길이 n의 가능한 모든 이진수에 대해 두 반쪽의 합은 동일합니까?

길이 n의 가능한 모든 이진수에 대해 두 반쪽의 합은 동일합니까?

WBOY
풀어 주다: 2023-09-03 13:21:11
앞으로
1121명이 탐색했습니다.

길이 n의 가능한 모든 이진수에 대해 두 반쪽의 합은 동일합니까?

여기서 각 절반의 합이 동일한 n 비트(n은 사용자가 제공함)의 가능한 모든 이진수를 볼 수 있습니다. 예를 들어, 숫자가 10001이면 여기서 10과 01은 합이 동일하고 절반이 다르기 때문에 동일합니다. 여기서는 해당 유형의 모든 숫자를 생성합니다.

Algorithm

genAllBinEqualSumHalf(n, left, right, diff)

왼쪽과 오른쪽은 처음에는 비어 있고, diff는 왼쪽과 오른쪽의 차이를 유지합니다.

Begin
   if n is 0, then
      if diff is 0, then
         print left + right
      end if
      return
   end if
   if n is 1, then
      if diff is 0, then
         print left + 0 + right
         print left + 1 + right
      end if
      return
   end if
   if 2* |diff| <= n, then
      if left is not blank, then
         genAllBinEqualSumHalf(n-2, left + 0, right + 0, diff)
         genAllBinEqualSumHalf(n-2, left + 0, right + 1, diff-1)
      end if
      genAllBinEqualSumHalf(n-2, left + 1, right + 0, diff + 1)
      genAllBinEqualSumHalf(n-2, left + 1, right + 1, diff)
   end if
End
로그인 후 복사

Example

#include <bits/stdc++.h>
using namespace std;
//left and right strings will be filled up, di will hold the difference between left and right
void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
   if (n == 0) { //when the n is 0
      if (di == 0) //if diff is 0, then concatenate left and right
         cout << left + right << " ";
      return;
   }
   if (n == 1) {//if 1 bit number is their
      if (di == 0) { //when difference is 0, generate two numbers one with 0 after left, another with 1 after left, then add right
         cout << left + "0" + right << " ";
         cout << left + "1" + right << " ";
      }
      return;
   }
   if ((2 * abs(di) <= n)) {
      if (left != ""){ //numbers will not start with 0
         genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
         //add 0 after left and right
         genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
         //add 0 after left, and 1 after right, so difference is 1 less
      }
      genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); //add 1 after left, and 0 after right, so difference is 1 greater
      genAllBinEqualSumHalf(n-2, left+"1", right+"1", di); //add 1 after left and right
   }
}
main() {
   int n = 5;
   genAllBinEqualSumHalf(n);
}
로그인 후 복사

输출

rreee

위 내용은 길이 n의 가능한 모든 이진수에 대해 두 반쪽의 합은 동일합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿