Проверка на pangrams в C

Это будет проверяться, если пользователь ввел pangram (каждая буква в алфавитном порядке, используемая хотя бы один раз), однако с 4 циклами for есть должен стать лучшим алгоритмическим подходом или с самим языком C.

pangram.c

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

 typedef enum { true, false } bool;

 typedef struct node{
     char letter;
     bool exists;
 } node;

 int main(int argc, char *argv[]){
     int SIZE = 500;
     char input[SIZE];

     printf("Enter your pangram: ");
     fgets(input, SIZE, stdin);

     // 26 letters
     node alphabet[26];
     int i = 0;
     for(char c='a'; c<='z'; ++c, i++){
         alphabet[i].letter = c;
         alphabet[i].exists = false;
     }


     for(int i=0; i<SIZE; i++){
         for(int j=0; j<27; j++){
             if(isalpha(input[i]) && input[i] == alphabet[j].letter){
                 alphabet[j].exists = true;
             }
         }
     }

     for(int i=0; i<27; i++){
         if(alphabet[i].exists==false){
             printf(" no pangram, missing letter.\n");
             return 1;
         }
     }

     printf("you've entered a pangram.\n");

     return 0;
 }

:

>> gcc -o pangram pangram.c -std=c99; ./pangram
Enter your pangram: this should fail
 no pangram, missing letter.

>> gcc -o pangram pangram.c -std=c99; ./pangram
Enter your pangram: the quick brown fox jumps over the lazy dog
you've entered a pangram.
11 голосов | спросил Tony 22 FebruaryEurope/MoscowbThu, 22 Feb 2018 05:19:40 +0300000000amThu, 22 Feb 2018 05:19:40 +030018 2018, 05:19:40

3 ответа


10

Это хороший вызов. Ваш код прост и понятен.

Некоторые вещи могут быть улучшены, в дополнение к тем, которые упомянуты в ответе Роланда.

Выберите main()

Поскольку мы не используем argc и argv, мы можем использовать более простой int main(), который не принимает аргументов.

Альтернативно (и это упрощает тестирование), вы можете использовать аргументы командной строки и запрашивать только вход, если ни один не был указан:

int main(int argc, char *argv[])
{
    if (argc < 2) {
        char input[500];
        printf("Enter your pangram: ");
        fflush(stdout);
        if (!fgets(input, sizeof input, stdin)) {
            perror("fgets");
            return 1;
        }
        return test_pangram(input);
    } else {
        int failures = 0;
        for (int i = 1;  i < argc;  ++i) {
            failures += test_pangram(argv[i]);
        }
        return failures;
    }
}

Я выделил действие программы в новую функцию test_pangram() поэтому мы можем назвать это из обеих ветвей этого.

Обратите внимание, что я вызывал fflush() между записью вывода и чтением ввода. Это гарантирует, что подсказка будет видна пользователю вовремя.

Ошибка

Это неправильно:

 /* BUG */
 for(int i=0; i<SIZE; i++){
     /* code that uses input[i] */
 }

Когда мы читаем ввод с использованием fgets(), он написал строку с завершающим нулем в input - все после символа NUL uninitialized , и использование его - неопределенное поведение. Вполне возможно, что неопределенные значения, которые мы читаем, могут привести к ложноположительному результату (если они заполняют символы, отсутствующие на фактическом вводе). Нам нужно остановить цикл, когда input[i] есть '\0':

 for(int i=0;  input[i];  i++){
     /* code that uses input[i] */
 }

Предположения о письмах

Этот код делает критическое предположение:

node alphabet[26];
int i = 0;
for(char c='a'; c<='z'; ++c, i++){
    alphabet[i].letter = c;
    alphabet[i].exists = false;
}

Предполагается, что буквы a ... z имеют смежные коды символов. Но C не гарантирует этого, и существуют системы, где 'z'-'a' не 25. Вы, вероятно, используете ASCII, или Latin-1 , или UTF-8, в качестве вашей кодировки, где ваше предположение оказывается удачным, но если ваш код скомпилирован для машины на базе EBCDIC (например), вы будете писать за пределами alphabet во время этого цикла. Это не хорошая вещь.

Более безопасный способ приблизиться к этому - это сделать обработку в обратном порядке: вместо того, чтобы искать каждого персонажа, как вы его видите, мы можем просто сохранить примечание каждого другого увиденного символа (буква или иначе), а затем проверить что все буквы отмечены. Для этого требуется немного больше памяти, но это будет немного более эффективно:

int test_pangram(const char *input)
{
    char seen[UCHAR_MAX+1] = { 0 };
    for (const char *p = input;  *p;  ++p) {
        unsigned char c = (unsigned char)*p;
        seen[c] = 1;
    }

    for (unsigned int i = 0;  i < sizeof seen;  ++i) {
        if (!seen[i] && islower(i)) {
            /* missing a required letter */
            return 1;
        }
    }
    return 0;
}

Здесь есть несколько вещей:

  • Я использую sizeof seen, поэтому я могу заставить компилятор предоставить правильное значение там, где это необходимо.
  • Я использовал указатель p вместо индексации в input - это точно эквивалентный, но более короткий и более идиоматический C.
  • Все символы должны быть преобразованы в unsigned char перед использованием с <ctype.h> - это одно из раздражающих ограничений этих функций.
  • Поскольку я использовал isalpha(), у нас больше шансов сделать эту работу в локалях, отличных от английского, например, Датский, где æ, ø, ---- +: = 27 =: + ---- и å тоже.

Рассмотрим символы верхнего регистра

Традиционно, панграмы игнорируют случай символов. Вы должны иметь возможность изменять программу, чтобы символы в верхнем регистре указывали на ü. Возможно, самый простой способ сделать это - подсчитать как верхнюю, так и нижнюю версии каждого символа (seen и toupper() просто возвращают свои входы для неалфавитных символов). Затем удалите тест tolower() из второго цикла.


Измененная программа

Вот мой вопрос по этой проблеме, с изменениями, которые я имеюпредложил:

islower(i)
#include <ctype.h>
#include <limits.h>
#include <stdio.h>
    
/* return true if it's a pangram */
int test_pangram(const char *input)
{
    char seen[UCHAR_MAX+1] = { 0 };
    for (const char *p = input;  *p;  ++p) {
        unsigned char c = (unsigned char)*p;
        seen[toupper(c)] = 1;
        seen[tolower(c)] = 1;
    }

    for (unsigned int i = 0;  i < sizeof seen;  ++i) {
        if (!seen[i] && isalpha(i)) {
            printf("Not a pangram - missing '%c'.\n", (char)i);
            return 0;
        }
    }

    printf("You've entered a pangram.\n");
    return 1;
}
ответил Toby Speight 22 FebruaryEurope/MoscowbThu, 22 Feb 2018 12:40:44 +0300000000pmThu, 22 Feb 2018 12:40:44 +030018 2018, 12:40:44
14

Пожалуйста, никогда не определяйте true, чтобы иметь значение 0, так как это значение зарезервировано для имени false. Просто укажите <stdbool.h> вместо определения типа самостоятельно.

Не вызывайте никакой функции из <ctype.h> с помощью char, так как легко приведет к неопределенному поведению .

При вызове fgets входной массив может быть неинициализирован, что также приведет к неопределенному поведению.

Доступ к alphabet[26] приводит к неопределенному поведению, так как действительные индексы массива идут от 0..25.

Остальная часть вашего кода выглядит хорошо организованной и легко читается. Поздравляю с этим.

Для вашего основного вопроса о решении pangram с менее чем 4 для циклов вы можете найти по крайней мере 10 различных решений путем поиска в Интернете, поскольку pangram - классическая задача программирования.

Забудьте вышеприведенный параграф. Я просто искал «pangram c» и нашел только дрянные решения, и говорить об этом, кроме хороших, для новичков невозможно.

Одна идея состоит в том, чтобы помнить для каждого письма, было ли это не обнаружено:

bool found[26] = { false };   // This initializes all 26 values at once, but only works for "zero" values.
int remaining = 26;

for (size_t i = 0; input[i] != '\0'; i++) {
    char ch = input[i];

    if ('a' <= ch && ch <= 'z') {
        if (!found[ch - 'a']) {
            found[ch - 'a'] = true;
            remaining--;
        }
    }
}

Если в конце цикла нет оставшегося символа, вы все их нашли, а входной - это pangram. Все с одним циклом.

Примечание: код, который я предложил, работает только тогда, когда все 26 букв определены в смежном блоке набора символов. На всех современных системах это так. При работе с машинами IBM и кодировкой EBCDIC это не сработает. На Rosetta Code, код совершенен , а также обрабатывает эти экзотические случаи. Он использует ту же идею и заботится обо всем. Это выглядело сложным с первого взгляда, поэтому я предпочел сначала объяснить основную идею. Но теперь вы должны понимать код там.

ответил Roland Illig 22 FebruaryEurope/MoscowbThu, 22 Feb 2018 06:09:26 +0300000000amThu, 22 Feb 2018 06:09:26 +030018 2018, 06:09:26
3

Поскольку вы спрашиваете о лучшем алгоритме, я укажу, что существует более эффективный, хотя и, возможно, менее читаемый, способ решения проблемы.

В алфавите только двадцать шесть букв. Один из подходов заключался бы в присвоении каждой буквы одному биту целого числа. После проверки предложенной pangram все биты 0 - 25 должны быть установлены. Если эти биты целого числа установлены, значение будет (от 2 до 26) минус 1.

Поскольку, как указывали другие ответы, буквы не могут быть смежными в наборе символов, мы сначала создаем таблицу переводов, которая идет от букв к бит-маскам.

    int32_t masks[UCHAR_MAX] = { 0 };
    int32_t index = 0;

    // build translation table
    for (unsigned char c = 0; c < UCHAR_MAX; c++) {
        if (isalpha(c) && islower(c)) masks[c] = 1 << index++;
    }

Это создает массив, элементы которого равны нулю, кроме тех, которые соответствуют буквам 'a' через 'z', чьи записи получают 1 сдвинутое левое 0 раз, 1 сдвинутое влево 1 раз и т. Д. Таким образом, значения 1, 2, 4, 8, 16, ... вплоть до 33 554 432.

Когда пришло время проверить предлагаемую панграмму, мы маскируем эти значения вместе, сначала преобразуя символ в нижний регистр, чтобы мы учитывали буквы верхнего регистра в нашем pangram:

    int32_t total = 0;
    for (const char *p = proposal; *p; p++) {
        total |= masks[tolower((unsigned char) *p)];
    }

Это принимает каждый символ, отбрасывает его в unsigned, потому что tolower ожидает int, и мы не хотим, чтобы отрицательные значения из подписанных символов были сфокусированы, преобразует его в нижний регистр, если это возможно (если нет, он просто возвращает исходное значение без изменений) и ищет маску из нашей таблицы переводов.

Теперь наша таблица переводов имеет нули для всех символов not строчных букв. Мы ИЛИ эти значения вместе в total. Буквы будут вызывать их соответствующие биты; нули будут проигнорированы.

Когда это будет завершено, total будет иметь значение (от 2 до 26) минус 1, если и только если строка была панграмма; если бы это было не так, нулевые биты могли бы использоваться для обнаружения , которые отсутствовали, если это было необходимо.

Вот полная программа:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

#define SIZE 512
// 2 to the 26 minus 1:
#define TARGET ((1 << 26) - 1)

int main() {
    int32_t masks[UCHAR_MAX] = { 0 };
    int32_t index = 0;

    // build translation table
    for (unsigned char c = 0; c < UCHAR_MAX; c++) {
        if (isalpha(c) && islower(c)) masks[c] = 1 << index++;
    }
    assert(index == 26);

    char proposal[SIZE];

    do {
        fputs("Enter proposed pangram: ", stdout);
        fflush(stdout);
        fgets(proposal, SIZE, stdin);

        if (strlen(proposal) > 1) {
            int32_t total = 0;
            for (const char *p = proposal; *p; p++) {
                total |= masks[tolower((unsigned char) *p)];
            }
            if (total == TARGET) puts("you've entered a pangram.");
            else puts(" no pangram - missing letter.");
        }
    } while (strlen(proposal) > 1);

    return 0;
}

Я считаю, что этот код будет правильным в локали C, где всего 26 букв. Если в другом языковом выражении имеется более 32 символов без знака, для которых isalpha(c) && islower(c) возвращает true, это может дать непредсказуемые результаты. Я добавил утверждение, чтобы гарантировать, что есть только 26 букв, которые не нарушаются.

ответил David Conrad 22 FebruaryEurope/MoscowbThu, 22 Feb 2018 13:55:05 +0300000000pmThu, 22 Feb 2018 13:55:05 +030018 2018, 13:55:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132