使用递归将二进制代码转换为等效格雷码的 Java 程序
使用递归将数字的二进制代码转换为等效的格雷码。二进制是存储数字的默认方式，但是在许多应用程序中，二进制数字没有用，需要二进制的变体。格雷码具有两个连续数字仅相差一位的特性，用于 K 图、纠错和通信。
例:
Input: 1101
Output: 1011
Input: 11010001
Output: 10111001
方法#1:整数限制下的数字
算法:
- 如果 n=0，则灰色=0。
- 否则，如果最后两位是相反的，那么 gray = 1+(10 * binary gray(n/10))。
- 否则，如果最后两位相同，那么 gray = 10 * binary gray(n/10)
下面是上述方法的实现。
爪哇
// Java Program to Convert Binary Code
// Into Equivalent Gray Code Using Recursion
import java.io.*;
class GFG {
// Function to change Binary Code
// to Gray using Recursion
public static int binaryToGray(int n)
{
if (n == 0) {
return 0;
}
// Extracting the last digit
int a = n % 10;
// Extracting the second last digit
int b = (n / 10) % 10;
// Else If last two digits
// are opposite bits to each other
if ((a & ~b) == 1 || (~a & b) == 1) {
return (1 + 10 * binaryToGray(n / 10));
}
// Else If the last
// two bits are same
return (10 * binaryToGray(n / 10));
}
// Driver's Function
public static void main(String[] args)
{
int binaryNumber = 11010001;
int result = binaryToGray(binaryNumber);
System.out.println("Gray Code is " + result);
}
}
输出
Gray Code is 10111001
方法#2:大二进制数
算法:
- Enter in string format.
- Pass the current pointer in a recursive function.
- Store the XOR of the I-th bit and the (i-1)-th bit in the array.
- Returns an array at the end of recursion.
下面是上述方法的实现。
爪哇
// Java Program to Convert Binary Code
// Into Equivalent Gray Code Using Recursion
import java.io.*;
class GFG {
// XOR two numbers
public static char xor(char a, char b)
{
if (a == b)
return '0';
else
return '1';
}
// Recursive function Gray code conversion
public static char[] ans(char[] kp, String str, int i)
{
if (i == str.length())
return kp;
kp[i] = xor(str.charAt(i), str.charAt(i - 1));
i++;
return ans(kp, str, i);
}
// Driver Program
public static void main(String args[])
{
String str = "01001";
char[] kp = new char[str.length()];
kp[0] = str.charAt(0);
// Recursive function call
ans(kp, str, 1);
// Print Gray Code
System.out.print("Gray Code is ");
for (char i : kp)
System.out.print(i + "");
}
}
输出
Gray Code is 01101
时间复杂度: O(N)，其中 N 为二进制码的长度。
版权属于：月萌API www.moonapi.com，转载请注明出处
