Возможные комбинации символов на цифровой клавиатуре телефонной в

Question

я столкнулся с вопросом в последнее время в С. Мы имеем NumPad телефона, с следующей планировкой:

 
1[abc] 2[def] 3[ghi] 
4[jkl] 5[mno] 6[pqr] 
7[st] 8[uv] 9[wx] 
     0[yz] 

Как придумать API, который дает все возможные комбинации символы, принадлежащие каждому числу для заданного ввода цифр. . input = 1234

Затем API должен печатать все возможные комбинации characters-

adgjbdgjcdgjaegjbegjcegj .. и так далее.

Есть ли простой способ сделать это? Помимо жестко закодированных вложенных циклов for. Мне дали подсказку как рекурсию, но я не мог понять, как выйти из нее.

Answer 1

Способ поиска комбинаций, которые вы ищете, может быть побитовой логикой с двоичным числом и целым числом. Двоичное число будет до тех пор, пока строка, с 0 и 1, будет действовать как включенные и выключенные переключатели для того, что включено и исключено в строке. Дело в том, что мы используем основание 3 или 4 в зависимости от числа «нажатых», и

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

Answer 2

Рекурсия - это всего лишь скрытый способ вложения четырех петель for. Вот то, что код выглядит

#include <stdio.h> 

void sneaky(int depth, int maxDepth, char str[]) 
{ 
    char c, start; 

    start = 'a' + depth * 3; 
    for (c = start; c < start + 3; c++) 
    { 
     str[depth] = c; 
     str[depth+1] = '\0'; 

     if (depth == maxDepth) 
      printf("%s\n", str); 
     else 
      sneaky(depth + 1, maxDepth, str); 
    } 
} 

int main(void) 
{ 
    char str[5] = { 0 }; 
    sneaky(0, 3, str); 
} 

Вы также можете решить эту проблему, и подобные комбинаторные задачи, с помощью простого алгоритма подсчета. Алгоритм подсчета эмулирует естественный подсчет, в котором вы увеличиваете наименьшую значащую цифру от 0 до 9. Когда наименьшая значащая цифра обертывает от 9 до 0, увеличивается следующая цифра влево.

То же самое можно сделать для решения проблемы OP. Но в этом случае цифры имеют либо два, либо три возможных значения. И если вы исследуете шаблон в OP, то очевидно, что младшая значащая цифра слева. В структуре
adgjbdgjcdgjaegj
вы можете увидеть, что a становится b, b становится c, а когда c обручи обратно a, то d становится e.

Вот код

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

static char InitialValue[] = { 'y', 'a', 'd', 'g', 'j', 'm', 'p', 's', 'u', 'w' }; 

static char NextValue[] = { 'b', 'c', 'a', 'e', 'f', 'd', 'h', 'i', 'g', 
          'k', 'l', 'j', 'n', 'o', 'm', 'q', 'r', 'p', 
          't', 's', 'v', 'u', 'x', 'w', 'z', 'y'  }; 

static void error(char *msg) 
{ 
    fprintf(stderr, "%s\n", msg); 
    exit(EXIT_FAILURE); 
} 

int main(void) 
{ 
    int i, oldDigit; 
    char str[12]; 

    // get the input string from the user 
    printf("Enter the input string: "); 
    fflush(stdout); 
    if (scanf("%10s", str) != 1) 
     error("whatever"); 

    // convert the input string to the corresponding first output string 
    for (i = 0; str[i] != '\0'; i++) 
    { 
     if (str[i] < '0' || str[i] > '9') 
      error("invalid input string"); 
     str[i] = InitialValue[str[i] - '0']; 
    } 
    printf("%s\n", str); 

    // use a simple counting algorithm to generate the string combinations 
    for (;;) 
    { 
     for (i = 0; str[i] != '\0'; i++) 
     { 
      oldDigit = str[i];     // save the current digit 
      str[i] = NextValue[oldDigit - 'a']; // advance the digit to the next value 
      if (str[i] > oldDigit)    // if the digit did not wrap 
       break;       // then we've got a new string 
     } 

     if (str[i] == '\0')     // if all the digits wrapped 
      break;        // then we're done 
     printf("%s\n", str);     // output the new string 
    } 

    return(EXIT_SUCCESS); 
} 

Answer 3

(Это не стандартное расположение для телефона, кстати.)

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

Идея состоит в том, чтобы изменить выходную строку в определенном индексе, используя цикл for, чтобы перебрать все возможные замены в этом индексе. Затем рекурсивно перейдите к следующему индексу в выходном массиве в теле цикла for.

Если вы дойдете до конца массива, распечатайте и верните.

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

char* data[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7prs", "8tuv", "9wxy"}; 

char* input = "23456783"; 

char* arr; 

void current(int index) 
{ 
    if(index == strlen(input)) printf("%s\n", arr); 
    else 
    { 
     for(int i = 0; i < strlen(data[input[index] - '0']); ++i) 
     { 
       arr[index] = data[input[index] - '0'][i]; 
       current(index + 1); 
     } 
    } 
} 

void main() 
{ 
    arr = malloc(strlen(input) + 1); 
    arr[strlen(input)] = '\0'; 
    printf("%s\n\n", input); 
    current(0); 
} 

Answer 4

Рекурсия - хорошее решение для таких проблем, где вы должны найти комбинации. Преимущество над вложенными циклами заключается в том, что рекурсия работает для строк любой длины.

В вашем случае, вам нужна функция, которая принимает:

• исходная строка
• вспомогательный char буфер для решения * и
• текущего индекса, который начинается с 0.

Рекурсивные функции требуют условия завершения: Когда вы достигли конца исходной строки, распечатайте ее и верните.

В противном случае выполните следующую цифру, проверьте, действительно ли это, определите связанные с ней буквы и затем вызовите функцию для каждой из букв. То есть для каждой буквы скопируйте ее в решение по текущему индексу, затем вызовите функцию со следующим индексом.

Ниже приведен пример реализации, который использует промежуточную функцию, чтобы сделать некоторые дома по поддержанию:

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



/* 
*  Recursive back-end, that produces all combinations in sol. 
*/ 
void alpha_r(const char *str, char *sol, int index) 
{ 
    const char *combo[] = { 
     "yz", "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx" 
    }; 

    if (str[index] == '\0') { 
     printf("%s\n", sol); 
    } else { 
     int k = str[index] - '0'; 
     const char *p = combo[k]; 

     while (*p) { 
      sol[index] = *p++; 
      alpha_r(str, sol, index + 1); 
     }   
    } 
} 

/* 
*  Non-recursive front-end that checks the string for validity 
*  and creates a temporary buffer for the solutions. 
*/  
void alpha(const char *str) 
{ 
    int len = 0; 

    while (str[len]) { 
     if (str[len] < 0 || str[len] > '9') { 
      fprintf(stderr, "Invalid input.\n"); 
      return; 
     } 
     len++; 
    } 

    char sol[len + 1]; 

    sol[len] = '\0'; 
    alpha_r(str, sol, 0); 
} 

int main() 
{ 
    alpha("123"); 

    return 0; 
} 

*) Кроме того, можно использовать саму строку для хранения решений.