Rumah > Artikel > pembangunan bahagian belakang > Untuk semua nombor perduaan yang mungkin panjang n, jumlah dua bahagian adalah sama?
Di sini kita akan melihat semua kemungkinan nombor binari n bit (n diberikan oleh pengguna) di mana jumlah setiap separuh adalah sama. Sebagai contoh, jika nombor adalah 10001 di sini 10 dan 01 adalah sama kerana jumlah mereka adalah sama, dan mereka berada dalam bahagian yang berbeza. Di sini kita akan menjana semua nombor jenis itu.
kiri dan kanan pada mulanya kosong, diff adalah memegang perbezaan antara kiri dan kanan
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
#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); }
100001 100010 101011 110011 100100 101101 101110 110101 110110 111111
Atas ialah kandungan terperinci Untuk semua nombor perduaan yang mungkin panjang n, jumlah dua bahagian adalah sama?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!