Supposons que nous ayons un nombre binaire qui représente un nombre n. Nous devons trouver un nombre binaire supérieur à n mais le plus petit, et qui possède également le même nombre de 0 et de 1. Donc, si le nombre est 1011 (11 en décimal), alors la sortie sera 1101 (13 en décimal). Ce problème peut être résolu en utilisant le prochain calcul de permutation. Regardons l'algorithme pour avoir cette idée. La traduction chinoise de
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
#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] == '0' && bin[i+1] == '1') { 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] == '1' && bin[k] == '0') { char ch = bin[j]; bin[j] = bin[k]; bin[k] = ch; j++; k--; } else if (bin[i] == '0') break; else j++; } return bin; } int main() { string bin = "1011"; cout << "Binary value of next greater number = " << nextBinary(bin); }
Binary value of next greater number = 1101
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!