Подследственный калькулятор. Могу ли я сделать его более эффективным?

Question

Идея подпоследовательностей объясняется очень хорошо в этом сообщении: Generate subsequences

Но я не понял ответы на этот вопрос, потому что я начинающий.

Что я хотел знать, может ли я сделать свою программу на C более эффективной, сохраняя при этом ее простоту и понятность и без использования функций?

#include <stdio.h> 
#define NUM 123456 

int main(void) { 

    int i,num=NUM,x,y,mask,digits=0,max=1; 

    while (num != 0) { //calculate digits 
     num /= 10; 
     digits++; 
    } 

    for (i = 1; i <= digits; i++) { //calculate max number of subsequences 
     max *= 2;  
    } 
    max=max-2; 

    printf("Subsequences are:\n"); 
    for (i = 1; i <= max ; i++) { 
     mask = i;  //digit selector 
     x = 1;  //multiplier 
     num = NUM; 
     y=0;   //subsequence value 

     while (num != 0) { 
      if (mask % 2 == 1) { 
       y += num % 10 * x; 
       x *= 10; 
      } 
      num /= 10; 
      mask /= 2; 
     } 
     printf("%d \n" , y); 
    } 

    return 0; 
} 

Обратите внимание, что когда мы определяем NUM как число, такое как 5111 или 100, некоторые из подпоследовательностей появляются дважды. Есть ли простой способ исправить это? Спасибо!

Answer 1

Корень причины, по которой некоторые подпоследовательности появляются несколько раз с некоторыми числами, состоит в том, что эти числа имеют повторения одной и той же цифры.

Это повторение может быть устранено путем сохранения каждой подпоследовательности в массиве и проверки этого массива, чтобы увидеть, существует ли определенная подпоследовательность уже в массиве. Если уже в массиве, не печатайте. В противном случае добавьте подпоследовательность к содержимому массива и распечатайте

Answer 2

Проблема может быть разделена на две задачи: (1) найти все подпоследовательности массива цифр и (2) упаковать и распаковать целые числа на цифры.

Рассмотрим подпоследовательности массива {a, b, c}. Вы можете сгенерировать их, пройдя через массив слева направо и следуя двум путям: один, где вы включаете текущий элемент в подпоследовательность, и тот, где вы этого не делаете.

Это приводит к рекурсивной подход тат можно представить в виде дерева:

    {} 
      / \ 
     {}    {a} 
    / \   / \ 
    {}  {b}  {a}  {ab} 
/\ / \ / \ / \ 
    {} {c} {b} {bc} {a} {ac} {ab} {abc} 

Когда мы ветвь слева, мы пропустить текущий элемент и когда мы идем вправо, мы включаем элемент. Сами элементы - это глубина дерева: На первом уровне мы обрабатываем элемент a, на следующем b и на последнем c.

Нижняя строка имеет все подпоследовательности. Это включает в себя пустую последовательность и полную последовательность, которую вы не хотите. Но давайте включим их сейчас. (Массивы в нижнем ряду обычно называются power set, что является хорошим термином для поиска в Интернете.)

Я упоминал рекурсию, которая влечет за собой рекурсивные функции и функции.

Таким образом, нам нужно решить проблему другим способом. Давайте повернем дерево на бок. Черточка означает, что элемент был пропущен. Запись на праве использует другое обозначение: 0 означает, что элемент был пропущен, 1 означает, что элемент был включен:

- - -  000 
- - c  001 
- b -  010 
- b c  011 
a - -  100 
a - c  101 
a b -  110 
a b c  111 

Я надеюсь, что коды на праве выглядеть знакомыми, потому что, как вы считаете от 000 к 111 в двоичный файл. Это хороший способ перечислить наши элементы. Теперь нам нужно определить, какие биты установлены в каждом номере.

Самый правый бит устанавливается, когда число нечетное. Мы можем узнать о других битах путем многократного деления числа на два, которые в двоичном формате являются сдвигом вправо, отбрасывая самый правый бит.

Теперь, как извлечь цифры из исходного номера? Это число является десятичным числом; он находится в базе 10. Мы можем использовать тот же подход, что и для поиска битов в двоичном числе, потому что биты 0 и 1 являются двоичными цифрами.

Начало с номером. Последняя цифра является результатом взятия остатка после деления на 10. Затем разделите число на десять, пока оно не станет равным нулю. Этот код дает цифры справа налево. Так же и код для поиска битов, что означает, что мы можем определить, установлен ли бит и какая цифра печататься в одном цикле, всегда беря самый правый бит, и если он установлен, напечатайте самую правую цифру исходного номера.

Пустые и полные подпоследовательности являются первым и последним элементами перечисления. Если вы не хотите их, пропустите их.

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

Простой способ сделать это - сохранить массив подпоследовательностей. Этот массив имеет max записей. После того, как вы заполнили этот массив, отсортируйте его и распечатайте, но пропустите записи, которые соответствуют предыдущей записи.

Вот пример реализации, который использует массив цифр, так что исходный номер не нужно разлагать каждый раз. Она использует функцию сортировки qsort из <stdlib.h>, который требует функции сортировки:

#include <stdlib.h> 
#include <stdio.h> 

#define NUM 412131 

typedef unsigned int uint; 

int uintcmp(const void *pa, const void *pb) 
{ 
    const uint *a = pa; 
    const uint *b = pb; 

    return (*a > *b) - (*a < *b); 
} 

int main(void) 
{ 
    uint digit[20];    // array of digits 
    size_t ndigit = 0;   // length of array 
    uint num = NUM; 
    uint max = 1; 
    size_t i; 

    while (num) { 
     digit[ndigit++] = num % 10; 
     num /= 10; 
     max *= 2; 
    } 

    uint res[max];    // array of subsequences 

    for (i = 0; i < max; i++) { 
     uint mask = i;   // mask for bit detection 
     uint j = ndigit;  // index into digit array 
     uint s = 0; 

     while (j--) { 
      if (mask % 2) s = s*10 + digit[j]; 
      mask /= 2; 
     } 

     res[i] = s; 
    } 

    qsort(res, max, sizeof(*res), uintcmp); 

    for (i = 1; i < max - 1; i++) { 
     if (res[i] != res[i - 1]) printf("%u\n", res[i]); 
    } 

    return 0; 
}