Binäre Darstellung der nächstgrößeren Zahl mit der gleichen Anzahl von Einsen und Nullen im C-Programm?

Angenommen, wir haben eine Binärzahl, die eine Zahl n darstellt. Wir müssen eine Binärzahl finden, die größer als n, aber am kleinsten ist und die auch die gleiche Anzahl an Nullen und Einsen hat. Wenn die Zahl also 1011 (11 in Dezimalzahl) ist, dann ist die Ausgabe 1101 (13 in Dezimalzahl). Dieses Problem kann mit der nächsten Permutationsrechnung gelöst werden. Schauen wir uns den Algorithmus an, um auf diese Idee zu kommen. Die chinesische Übersetzung von

algorithm

nextBin(bin) −

Begin
   len := length of the bin
   for i in range len-2, down to 1, do
      if bin[i] is 0 and bin[i+1] = 1, then
         exchange the bin[i] and bin[i+1]
         break
      end if
   done
   if i = 0, then there is no change, return
   otherwise j:= i + 2, k := len – 1
   while j < k, do
      if bin[j] is 1 and bin[k] is 0, then
         exchange bin[j] and bin[k]
         increase j and k by 1
      else if bin[i] is 0, then
         break
      else
         increase j by 1
      end if
   done
   return bin
End

Example

lautet:

Example

#include <iostream>
using namespace std;
string nextBinary(string bin) {
   int len = bin.size();
   int i;
   for (int i=len-2; i>=1; i--) {
      if (bin[i] == &#39;0&#39; && bin[i+1] == &#39;1&#39;) {
         char ch = bin[i];
         bin[i] = bin[i+1];
         bin[i+1] = ch;
         break;
      }
   }
   if (i == 0)
   "No greater number is present";
   int j = i+2, k = len-1;
   while (j < k) {
      if (bin[j] == &#39;1&#39; && bin[k] == &#39;0&#39;) {
         char ch = bin[j];
         bin[j] = bin[k];
         bin[k] = ch;
         j++;
         k--;
      }
      else if (bin[i] == &#39;0&#39;)
         break;
      else
         j++;
   }
   return bin;
}
int main() {
   string bin = "1011";
   cout << "Binary value of next greater number = " << nextBinary(bin);
}

Output

Binary value of next greater number = 1101

Das obige ist der detaillierte Inhalt vonBinäre Darstellung der nächstgrößeren Zahl mit der gleichen Anzahl von Einsen und Nullen im C-Programm?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!