Здесь объединяются в одном коде два признака – пол и образование.
Задача 30. Самое длинное слово текста. Входной текст состоит из слов, разделенных пробелами и/или символами "новая строка". Составить программу определения самого длинного слова.
Тест. Вход:
Я снова тут,
Я собран весь <Ctrl-z> <Enter> <Ctrl-z> - конец файла
Выход:
Самое длинное слово: собран.
Алгоритм символьной обработки разрабатываетcя, исходя из структуры читаемого им текста, которую удобно описать в виде синтаксических правил - грамматик. Разным способам такого описания соответствуют разные варианты алгоритма. Рассмотрим два крайних подхода для данной задачи (возможны и другие решения).
Решение 1. Грамматика текста имеет вид:
текст ::= [слово]...
слово ::= [разделитель]... [символ-слова]...
разделитель ::= пробел | новая-строка
Входной текст рассматривается как последовательность слов. Слово - последовательность символов (отличающихся от пробела, "новой строки" и признака конца файла EOF), которой может предшествовать последовательность разделителей (пробелов или "новых строк").
Каждому знаку повторения "..." синтаксического правила, описывающего структуру текста, в алгоритме чтения и анализа текста соответствует цикл, знаку "|" (или) – ветвление. Таким образом, структура алгоритма повторяет структуру читаемого текста.
Соответствующий алгоритм содержит цикл чтения слов, который включает цикл пропуска пробелов и "новых строк" и цикл чтения символов слова.
Обозначим:
sl - текущее слово,
dsl - длина текущего слова,
maxsl - максимальное слово,
dmaxsl - длина максимального слова.
Алгоритм на псевдокоде:
dmaxsl = 0;
while (не конец файла)
{ Пропуск пробелов и "новых строк";
dsl = 0;
Чтение текущего слова sl;
if (dsl > dmaxsl)
Копирование sl в maxsl; dmaxsl = dsl;
}
if (dmaxsl > 0) Вывод maxsl; else Вывод "В тексте нет слов";
Рассмотренный алгоритм реализован в программе 29а.
/* Программа 30а. Слово максимальной длины */
#include <stdio.h>
#define DSLMAX 20 /* Максимальная длина слова */
main ()
{ char sl [DSLMAX]; /* Текущее слово */
int dsl; /* Длина текущего слова */
char maxsl [DSLMAX]; /* Максимальное слово */
int dmaxsl; /* Длина максимального слова */
int sim; /* Текущий символ */
int i; /* Текущий индекс копирования */
dmaxsl = 0;
while ((sim = getchar()) != EOF)
{
while (sim==' ' || sim=='\n') sim=getchar();
dsl = 0;
while (sim!=' ' && sim!='\n' && sim!=EOF)
{sl [dsl++] = sim; sim = getchar();}
sl [dsl] = '\0';
if (dsl > dmaxsl)
{for (i = 0; maxsl [i] = sl [i]; i++);
dmaxsl = dsl;
}
}
if (dmaxsl > 0) printf ("\nСамое длинное слово: %s\n", maxsl);
Входной текст рассматривается как последовательность символов. Символы делятся на два вида: разделители слов (пробел, '\n’ или EOF) и символы, составляющие слова. Программа содержит один цикл с постусловием для чтения символов, так как текст содержит хотя бы один символ.
Алгоритм на псевдокоде:
dmaxsl = 0; dsl = 0;
do
{
if (текущий символ s - не разделитель)
текущий символ s в слово sl;
else /* разделитель - конец слова */
{if (dsl > dmaxsl)
{Копирование sl в maxsl; dmaxsl = dsl; }
dsl = 0;
}
}
while (не конец файла);
if (dmaxsl > 0) Вывод maxsl; else Вывод "В тексте нет слов";
Рассмотренный алгоритм реализован в программе 29б.
/* Программа 30б. Слово максимальной длины */
#include <stdio.h>
#define DSLMAX 20 /* Максимальная длина слова */
void main (void)
{ char sl [DSLMAX]; /* Текущее слово */
int dsl; /* Длина текущего слова */
char maxsl [DSLMAX]; /* Максимальное слово */
int dmaxsl; /* Длина максимального слова */
int sim; /* Текущий символ */
int i; /* Текущий индекс копирования */
dmaxsl = 0; dsl = 0;
do
{
if ((sim=getchar()) != ' ' && sim!='\n' && sim!=EOF)
sl [dsl++] = sim;
else
{ if (dsl > dmaxsl)
{ sl [dsl] = '\0';
for (i = 0; maxsl [i] = sl [i]; i++);
dmaxsl = dsl;
}
dsl = 0;
}
}
while (sim != EOF);
if (dmaxsl > 0) printf ("\nСамое длинное слово: %s\n", maxsl);
else printf ("\nВ тексте нет слов\n");
}
В этом примере отразились весьма характерные и важные закономерности программирования.
1. Существует много решений даже очень простой задачи.
2. Наилучшая программа решения даже простой задачи не существует! По разным критериям лучшими оказываются разные программы, необходим поиск компромиссных вариантов.
3. Выиграешь время - проиграешь память и наоборот: экономя память, увеличишь время решения задачи.
4. Структурное программирование сверху вниз облегчает поиск вариантов алгоритма.
5. Неструктурный алгоритм может оказаться компактнее структурного, но он обычно бывает более запутанным и менее надежным.
Существуют десятки взаимосвязанных критериев оценки программ, основные из которых следующие.
1. Функциональность – выполняемые программой функции, ее полезность.
2. Надежность - вероятность безошибочной работы программы в течение определенного времени.
3. Эффективность по времени - время решения задачи.
4. Эффективность по памяти - требуемая память для программы и обрабатываемых данных.
5. Удобство эксплуатации определяется качествами самой программы и ее документации.
6. Затраты на разработку программы. Для уменьшения затрат на разработку важна мобильность программы.
Критерии часто противоречат друг другу. Особенно характерна закономерность время-память: обычно для ускорения работы программы требуется дополнительная память и наоборот: экономия памяти замедляет работу программы.
