Поиск подходящих потомков целого числа

Question

Я застрял на основной алгоритмической проблеме, и я не могу понять, как ее решить.

В основном я хочу перечислить все числа, которые являются правильными потомками целого числа. То есть, если мое число равно 21, я хочу использовать его двоичное представление (10101) и перечислить все числа, которые имеют хотя бы один общий бит значения 1 с 21 и меньше 21. Результат здесь должен быть 10100, 10001, 10000, 101, 100, 1.

Математическое определение собственных потомков выглядит следующим образом:

• Пусть h — неотрицательное число меньше 2^m. h = d0 + d1*2^1 + ... + dm-1*2^(m-1)где ди = 0 или 1.

• Пусть h' будет другим неотрицательным, таким как h' = d0' + d1'*2^1 + ... + dm-1'*2^(m-1)где di' = 0 или 1.

• h' является потомком h, если di'<=di для 0<=i<m

Я перепробовал множество реализаций как на Python, так и на C, пробовал старую технику с ручкой и бумагой, но все они потерпели неудачу. Я знаю, что это довольно просто, но я не могу понять это. Я пишу код на C, поэтому, если вы найдете решение, которое работает на C, это было бы идеально, но я бы взял что угодно прямо сейчас.

Answer 1

Вот очень простой подход: перечислить все целые числа между 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");
}

Answer 2

Итак, я наконец-то придумал код на 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, &currently_processing);

  printf("size = %u\n", size);
  for (int i = 0; i < size; i++)
  {
    printf("%u ", output[i]);
  }
  printf("\n");

  return 0;
}

Answer 3

Вы можете использовать рекурсивное решение, такое как следующее.

Я немного ленив, поэтому я не стал заносить числа в список, а просто напечатал их, а также напечатал 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