Проверка панграммы в C


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

панграмма.с

 #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.


1736
11
задан 22 февраля 2018 в 02:02 Источник Поделиться
Комментарии
3 ответа

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

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

Выбрать 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() он писал null-завершенной строку input - все после нулевой символ является неинициализированным и используя это неопределенное поведение. Вполне возможно, что неопределенные значения мы читаем оттуда могло стать причиной ложно-положительного результата (если они заполняют в персонажах отсутствует фактический ввод). Нам нужно остановить цикл, когда 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 иметь непрерывный характер коды. Но не гарантирует этого и существуют системы, в которых 'z'-'a' это не 25. Вы, наверное, с помощью ASCII или Latin-1 или UTF-8, как ваши кодирования, где ваше предположение окажется повезло, но если ваш код компилируется для кодировка машине (например), вы будете писать после окончания 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 - это совсем равноценны, но короче и более идиоматические С.

  • Все символы должны быть преобразованы в unsigned char перед использованием с <ctype.h> функции - это одна из самых раздражающих проблем этих функций.

  • Потому что я использовал isalpha()мы стоим больше шансов сделать эту работу в регионах, отличных от английского, например, Дании, где æ, ø, å и ü письма, тоже.

Рассмотрим прописные буквы

Традиционно, панграммы игнорировать регистр символов. Вы должны быть в состоянии модифицировать программу так, чтобы заглавные буквы учитываются 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;
}

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;
}
}

10
ответ дан 22 февраля 2018 в 09:02 Источник Поделиться

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

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

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

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

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

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

Забудьте о предыдущем пункте. Я просто искал "панграмма С" и нашла только дерьмовые решения, и рассказываю только хорошие невозможно для новичка.

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

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--;
}
}
}

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

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

14
ответ дан 22 февраля 2018 в 03:02 Источник Поделиться

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

Есть только двадцать шесть букв в алфавите. Один из подходов можно было бы присвоить каждой буквы в одно целое. После проверки предлагаемого панграмма, бит 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.

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

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

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

Итак, наш перевод таблица имеет нули для всех символов, которые не строчными буквами. Мы или эти значения вместе в 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 букв.

3
ответ дан 22 февраля 2018 в 10:02 Источник Поделиться