Калькулятор подпоследовательности. Могу ли я сделать это более эффективным?
Идея подпоследовательностей очень хорошо объясняется в этом посте: генерировать подпоследовательности
Но я не понял ответы на этот вопрос, потому что я новичок.
Что я хотел знать, так это то, могу ли я сделать свою 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, некоторые из подпоследовательностей появляются дважды. Есть ли простой способ это исправить? Спасибо!
2 ответа
Задачу можно разделить на две задачи: (1) найти все подпоследовательности массива цифр и (2) упаковать и распаковать целые числа в цифры.
Давайте рассмотрим подпоследовательности массива {a, b, c}, Вы можете создать их, пройдя по массиву слева направо и следуя двум путям: один, где вы включаете текущий элемент в подпоследовательность, и другой, где вы этого не делаете.
Это приводит к рекурсивному подходу, который мы можем представить в виде дерева:
{}
/ \
{} {a}
/ \ / \
{} {b} {a} {ab}
/ \ / \ / \ / \
{} {c} {b} {bc} {a} {ac} {ab} {abc}
Когда мы разветвляемся влево, мы пропускаем текущий элемент, а когда мы идем направо, мы включаем элемент. Сами элементы - это глубина дерева: на первом уровне мы рассматриваем элемент aна следующий bи на последнем c,
Нижний ряд имеет все подпоследовательности. Это включает в себя пустую последовательность и полную последовательность, которую вы не хотите. Но давайте включим их пока. (Массивы в нижнем ряду обычно называют набором мощности, который является хорошим термином для поиска в сети.)
Я упомянул рекурсию, которая влечет за собой рекурсивные функции, а функции отсутствуют.
Таким образом, мы должны решить проблему по-другому. Давайте перевернем дерево на бок. Тире означает, что элемент был пропущен. Обозначение справа использует другое обозначение: 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. Затем разделите число на десять, пока оно не станет равным нулю. Этот код возвращает цифры справа налево. Так же как и код для поиска битов, что означает, что мы можем определить, установлен ли бит и какую цифру печатать в одном цикле, всегда беря самый правый бит, и, если он установлен, печатать самую правую цифру исходного числа.
Пустая и полная подпоследовательности являются первым и последним элементами в перечислении. Если вы не хотите их, пропустите их.
Это оставляет проблему дублированных подпоследовательностей, если цифра имеет повторяющиеся цифры. Я не вижу простого способа решить эту проблему, кроме предложения пользователя 3629249 создать подпоследовательность в любом случае, а затем проверить, было ли уже напечатано.
Простой способ сделать это - сохранить массив подпоследовательностей. Этот массив имеет 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;
}
Корень причины того, что некоторые подпоследовательности появляются более одного раза с некоторыми числами, состоит в том, что эти числа имеют повторения одной и той же цифры.
Это повторение можно устранить, сохранив каждую подпоследовательность в массиве и проверив этот массив, чтобы увидеть, есть ли конкретная подпоследовательность в массиве. Если уже в массиве, не печатать. В противном случае добавьте подпоследовательность к содержимому массива и напечатайте