使用递归的C++程序将二进制数转换为格雷码

格雷码或反射二进制码是一种特殊的二进制数表示方法，其中两个连续的值只有一位不同。例如，1和2的二进制等价分别为01和10，这里改变了两位。但在格雷码中，1是01，2是11，只有一位改变。在本文中，我们将学习如何使用C++中的递归将给定的二进制数转换为其格雷码等价。

传递十进制整数作为数字

在第一个示例中，我们以十进制提供数字。数字只有0和1，但数字是十进制的。例如，如果我们想传递6作为输入，我们传递110（十进制的一百一十），它在二进制表示中等于6。程序也以类似的方式返回输出。

算法

  • 定义一个函数solve()，它将接收一个二进制数
  • 如果n为0，则
    • 返回0
  • 结束if
  • last := n的最后一位
  • second_last = n的倒数第二位
  • 如果最后一位和倒数第二位不同，则
    • 放置1并调用solve(去掉最后一位的n)
  • 否则
    • 放置0并调用solve(去掉最后一位的n)
  • 结束if
  • solve()函数结束

示例

#include <iostream>
using namespace std;

int solve( int n ) {
   if( n == 0 )
   return 0;
   int last = n % 10;
   int second_last = (n / 10) % 10;
   if( (last && !second_last) || (!last && second_last) ) {
      return (1 + 10 * solve( n / 10 ));
   }
   return (10 * solve( n / 10 ));
}

int main()
{
   cout << "Gray code for the number 2 (10) is: " << solve( 10 ) << endl;
   cout << "Gray code for the number 6 (110) is: " << solve( 110 ) << endl;
   cout << "Gray code for the number 13 (1101) is: " << solve( 1101 ) << endl;
   cout << "Gray code for the number 93 (1011101) is: " << solve( 1011101 ) << endl;
}

输出

Gray code for the number 2 (10) is: 11
Gray code for the number 6 (110) is: 101
Gray code for the number 13 (1101) is: 1011
Gray code for the number 93 (1011101) is: 1110011

结论

格雷码或反射二进制码可以通过对连续位应用异或运算来找到。通过取给定数字的最后两位来实现相同的功能，当它们不相同时，递归调用函数并传递除最后一位以外的数字，结果将与1连接，否则与0连接，以此类推。在示例中，我们以整数十进制数作为输入，输出也以整数十进制格式显示。可以通过采用字符串类型输入来解决相同的问题，这可以在需要时用于提供更大的输入。

更新于：2022年10月19日

736 次浏览

开始你的职业生涯

通过完成课程获得认证

开始学习
广告