길이 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!