寻找整数的适当后代
Finding proper descendants of an integer
我被一个基本的算法问题困住了,我不知道如何解决它。
基本上我想列出所有作为整数的适当后代的数字。也就是说,如果我的数是21,我想用它的二进制表示(10101),列出所有至少有一个公共位为1和21且小于21的数。这里的结果应该是10100, 10001, 10000, 101, 100, 1.
真后代的数学定义如下:
令h为小于2^m的非负数。 h = d0 + d1*2^1 + ... + dm-1*2^(m-1)
其中 di = 0 或 1。
设 h' 为另一个非负数,例如 h' = d0' + d1'*2^1 + ... + dm-1'*2^(m-1)
其中 di' = 0 或 1。
h' 是 h 的后代,如果 di'<=di for 0<=i
我在 Python 和 C 中尝试了很多实现,并尝试了旧的笔和纸技术,但都失败了。我知道这很简单,但我似乎无法弄清楚。我正在用 C 编写代码,所以如果您找到一个适用于 C 的解决方案那将是理想的,但我现在会采取任何措施。
好的,所以我终于想出了一个 C 代码,它看起来很不好看,可能优化得非常糟糕,但仍然可以按预期工作。可能有更简单的解决方案,但出于知识目的,这是我的解决方案:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
unsigned int pui(unsigned int a, unsigned int b)
{
if (b == 0)
return 1;
if (b == 1)
return a;
if (b % 2 == 0)
return pui(a * a, b / 2);
else
return pui(a * a, (b - 1) / 2);
}
unsigned int testBit(unsigned int h, unsigned int offset)
{
unsigned int mask = 1 << offset;
return (h & mask);
}
bool isInList(unsigned int x, unsigned int *output_size, unsigned int **output)
{
for (int i = 0; i < *output_size; i++)
{
if (*(*output + i) == x)
{
return true;
}
}
return false;
}
void listDescendants(unsigned int h, unsigned int *output_size, unsigned int **output, int *currently_processing)
{
unsigned int max_offset = 0;
unsigned int temp_h = h;
unsigned int initial_output_size = *output_size;
while (temp_h > 0)
{
max_offset++;
temp_h /= 2;
}
unsigned int h_radix2[max_offset];
for (int i = 0; i < max_offset; i++)
{
if (testBit(h, i))
{
if (h > pui(2, i) && !isInList(h - pui(2, i), output_size, output))
{
*(*output + *output_size) = h - pui(2, i);
*output_size += 1;
}
}
}
if (*currently_processing < (int)*output_size)
{
*currently_processing += 1;
listDescendants(*(*output + *currently_processing), output_size, output, currently_processing);
}
}
int main()
{
int currently_processing = -1;
unsigned int size = 0;
unsigned int *output = malloc(300 * sizeof(unsigned int));
listDescendants(21, &size, &output, ¤tly_processing);
printf("size = %u\n", size);
for (int i = 0; i < size; i++)
{
printf("%u ", output[i]);
}
printf("\n");
return 0;
}
您可以使用递归解决方案,例如下面的解决方案。
我有点懒,所以没有把数字列成一个列表,只是简单地打印出来,并且还打印了0和给定的数字。
我相信你可以很容易地调整代码,让它做你想做的事。
#include <stdio.h>
#define CHAR_BIT 8
void ProperDescendantsRecursive(unsigned int num, unsigned int bit_index)
{
if (CHAR_BIT * sizeof(unsigned int) - 1 == bit_index)
{
printf("%u\n", num);
}
else
{
unsigned int mask = 1U << bit_index;
if (num & mask)
{
/* with the bit at index bit_index is off */
ProperDescendantsRecursive(num ^ mask, bit_index + 1);
/* with the bit at index bit_index is on */
ProperDescendantsRecursive(num, bit_index + 1);
}
else
{
ProperDescendantsRecursive(num, bit_index + 1);
}
}
}
void ProperDescendants(unsigned int num)
{
ProperDescendantsRecursive(num, 0);
}
int main(void)
{
ProperDescendants(21);
return 0;
}
编译和 运行 结果输出:
0
16
4
20
1
17
5
21
这里有一个非常简单的方法:枚举n-1
和1
之间的所有整数,打印那些严格包含在n
中的整数,即:(i & n) == i
.
void list_descendants(int n) {
printf("descendants of %d:", n);
for (int i = n; i --> 1;) {
if ((i & n) == i)
printf(" %d", i);
}
printf("\n");
}
我被一个基本的算法问题困住了,我不知道如何解决它。
基本上我想列出所有作为整数的适当后代的数字。也就是说,如果我的数是21,我想用它的二进制表示(10101),列出所有至少有一个公共位为1和21且小于21的数。这里的结果应该是10100, 10001, 10000, 101, 100, 1.
真后代的数学定义如下:
令h为小于2^m的非负数。
h = d0 + d1*2^1 + ... + dm-1*2^(m-1)
其中 di = 0 或 1。设 h' 为另一个非负数,例如
h' = d0' + d1'*2^1 + ... + dm-1'*2^(m-1)
其中 di' = 0 或 1。h' 是 h 的后代,如果 di'<=di for 0<=i
我在 Python 和 C 中尝试了很多实现,并尝试了旧的笔和纸技术,但都失败了。我知道这很简单,但我似乎无法弄清楚。我正在用 C 编写代码,所以如果您找到一个适用于 C 的解决方案那将是理想的,但我现在会采取任何措施。
好的,所以我终于想出了一个 C 代码,它看起来很不好看,可能优化得非常糟糕,但仍然可以按预期工作。可能有更简单的解决方案,但出于知识目的,这是我的解决方案:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
unsigned int pui(unsigned int a, unsigned int b)
{
if (b == 0)
return 1;
if (b == 1)
return a;
if (b % 2 == 0)
return pui(a * a, b / 2);
else
return pui(a * a, (b - 1) / 2);
}
unsigned int testBit(unsigned int h, unsigned int offset)
{
unsigned int mask = 1 << offset;
return (h & mask);
}
bool isInList(unsigned int x, unsigned int *output_size, unsigned int **output)
{
for (int i = 0; i < *output_size; i++)
{
if (*(*output + i) == x)
{
return true;
}
}
return false;
}
void listDescendants(unsigned int h, unsigned int *output_size, unsigned int **output, int *currently_processing)
{
unsigned int max_offset = 0;
unsigned int temp_h = h;
unsigned int initial_output_size = *output_size;
while (temp_h > 0)
{
max_offset++;
temp_h /= 2;
}
unsigned int h_radix2[max_offset];
for (int i = 0; i < max_offset; i++)
{
if (testBit(h, i))
{
if (h > pui(2, i) && !isInList(h - pui(2, i), output_size, output))
{
*(*output + *output_size) = h - pui(2, i);
*output_size += 1;
}
}
}
if (*currently_processing < (int)*output_size)
{
*currently_processing += 1;
listDescendants(*(*output + *currently_processing), output_size, output, currently_processing);
}
}
int main()
{
int currently_processing = -1;
unsigned int size = 0;
unsigned int *output = malloc(300 * sizeof(unsigned int));
listDescendants(21, &size, &output, ¤tly_processing);
printf("size = %u\n", size);
for (int i = 0; i < size; i++)
{
printf("%u ", output[i]);
}
printf("\n");
return 0;
}
您可以使用递归解决方案,例如下面的解决方案。
我有点懒,所以没有把数字列成一个列表,只是简单地打印出来,并且还打印了0和给定的数字。
我相信你可以很容易地调整代码,让它做你想做的事。
#include <stdio.h>
#define CHAR_BIT 8
void ProperDescendantsRecursive(unsigned int num, unsigned int bit_index)
{
if (CHAR_BIT * sizeof(unsigned int) - 1 == bit_index)
{
printf("%u\n", num);
}
else
{
unsigned int mask = 1U << bit_index;
if (num & mask)
{
/* with the bit at index bit_index is off */
ProperDescendantsRecursive(num ^ mask, bit_index + 1);
/* with the bit at index bit_index is on */
ProperDescendantsRecursive(num, bit_index + 1);
}
else
{
ProperDescendantsRecursive(num, bit_index + 1);
}
}
}
void ProperDescendants(unsigned int num)
{
ProperDescendantsRecursive(num, 0);
}
int main(void)
{
ProperDescendants(21);
return 0;
}
编译和 运行 结果输出:
0
16
4
20
1
17
5
21
这里有一个非常简单的方法:枚举n-1
和1
之间的所有整数,打印那些严格包含在n
中的整数,即:(i & n) == i
.
void list_descendants(int n) {
printf("descendants of %d:", n);
for (int i = n; i --> 1;) {
if ((i & n) == i)
printf(" %d", i);
}
printf("\n");
}