如何递归地构造一个二元微分问题？
如何递归地构造一个二元微分问题？
提问于 2021-01-11 21:27:54
我头撞墙已经有一段时间了.
这个问题要求我制定这个区分规则，它应用于一个字节数组(源应该被覆盖)，递归地从数组的末尾(derive.length - 1)开始，然后向i=0移动。不应该使用第二个数组，而输入数组应该被覆盖。下面是迭代版本。
public static void derivative(byte[] derive) {
for (int i = derive.length - 1; i > 0; i--) {
if (i == 0 && derive[0] == 0) {
derive[0] = 0;
}
if (i > 0 && derive[i] == derive[i-1]) {
derive[i] = 0;
}
else {
derive[i] = 1;
}
}该算法将以下规则集应用于二进制数字数组，如1,0,1,1：i应等于：
- 0 if i=0和ai=0
- 0 if i>0和ai=ai-1
- 1 ai=0
例如：{1，0，1，0}变成：{1,1,1,1,0}，{0,1,1,0}变成：{0,1,0,1}
我如何递归地表达这一点？
回答 2
Stack Overflow用户
发布于 2021-01-11 21:42:35
public static byte derivative(byte[] derive, int index) {
byte curr = derive[index];
if (index == 0) {
derive[index] = 0;
return curr;
} elif (derive[index] == derivative(derive, index - 1)) {
derive[index] = 0;
return curr;
}
derive[index] = 1;
return curr;
}编辑:修改返回类型
Stack Overflow用户
发布于 2021-01-11 22:09:09
您的代码实际上是这样做的：
public static void derivative(byte[] derive) {
for (int i = derive.length - 1; i > 0; i--) {
derive[i] = derive[i] == derive[i-1] ? 0 : 1;
}
}我会让你查一下这个。
这更有趣，因为它是如此简单。
一个更好的方法是使用位，每字节8位，或者长一点。
public static void derivative(byte[] derive) {
long num = toBits(derive);
num = (num >>> 1)^num;
fromBits(bits, derive);
}
private static long bits(byte[] derive) {
long bits = 0;
for (byte b : derive) {
bits = (bits << 1) | (b == 0 ? 0 : 1);
}
return bits;
}使用以下算法
{1,0,1,0,0} becomes:
{1,1,1,1,0}
10100
10100
1010 shift right
----- xor
11110简化函数在顶部的递归是很简单的。
public static void derivative(byte[] derive) {
derivativeRecursively(derive, derive.length - 1);
}
private static void derivativeRecursively(byte[] derive, int i) {
...
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65674771
复制相关文章
相似问题
腾讯云开发者
