Обработка символьных данных
Замечание: при решении некоторых задач этого раздела необходимы минимальные знания о «стандартном» вводе и выводе литер.
3.48. Пусть во входном потоке находится последовательность литер, заканчивающаяся точкой (кодировка ASCII):
a) определить, сколько раз в этой последовательности встречается символ ‘a’;
b) определить, сколько символов ‘e’ предшествует первому вхождению символа ‘u’ ( либо сколько всего символов ‘e’ в этой последовательности, если она не содержит символа ‘u’ );
c) выяснить, есть ли в данной последовательности хотя бы одна пара символов-соседей ‘n’ и ‘o’, т.е. образующих сочетание ‘n’ ‘o’ либо ‘o’ ‘n’;
d) выяснить, чередуются ли в данной последовательности символы ‘+’ и ‘-‘, и сколько раз каждый из этих символов входит в эту последовательность;
e) выяснить, сколько раз в данную последовательность входит группа подряд идущих символов, образующих слово С++;
f) выяснить, есть ли среди символов этой последовательности символы, образующие слово char;
g) выяснить, есть ли в данной последовательности фрагмент из подряд идущих литер, образующий начало латинского алфавита (строчные буквы), и какова его длина. Если таких фрагментов несколько, найти длину наибольшего из них. Если такого фрагмента нет, то считать длину равной нулю;
h) выяснить, есть ли в данной последовательности фрагменты из подряд идущих цифр, изображающие целые числа без знака. Найти значение наибольшего из этих чисел. Если в этой последовательности нет ни одной цифры, то считать, что это значение равно нулю;
i) определить, имеет ли данная последовательность символов структуру, которая может быть описана с помощью следующих правил:
последовательность ::= слагаемое + последовательность | слагаемое
слагаемое ::= идентификатор | целое
идентификатор ::= буква | идентификатор буква | идентификатор цифра
буква ::= A | B | C | D | E | F | G | H | I | J | K
цифра ::= 0 | 1 | 2 | 3 | 4 | 5
целое ::= цифра | целое цифра
3.49. Пусть во входном потоке находится последовательность литер, заканчивающаяся точкой (кодировка ASCII). Вывести в выходной поток последовательность литер, измененную следующим образом:
a) заменить все символы ‘?’ на’!’;
b) удалить все символы ‘-‘ и удвоить все символы ‘&’;
c) удалить все символы, не являющиеся строчными латинскими буквами;
d) заменить все прописные латинские буквы строчными (другие символы копировать в выходной поток без изменения);
e) заменить все строчные латинские буквы прописными (другие символы копировать в выходной поток без изменения);
f) каждую группу рядом стоящих символов ‘+’ заменить одним таким символом;
g) каждую группу из n рядом стоящих символов ‘’ заменить группой из n/2 рядом стоящих символов ‘+’ ( n >= 2 ); одиночные ‘’ копировать в выходной поток без изменения;
h) удалить из каждой группы подряд идущих цифр все начальные незначащие нули (если группа состоит только из нулей, то заменить эту группу одним нулем);
i) удалить все комбинации символов the;
j) оставить только те группы цифр, которые составлены из подряд идущих цифр с возрастающими значениями; все остальные цифры и группы цифр удалить ( другие символы копировать в выходной поток без изменения);
k) заменить все комбинации символов child комбинациями символов children;
l) удалить группы символов, расположенные между фигурными скобками { и }. Скобки тоже должны быть удалены. Предполагается, что скобки сбалансированы, и внутри каждой пары скобок других фигурных скобок нет.
3.50. Пусть во входном потоке находится последовательность литер, заканчивающаяся маркером конца $ (кодировка ASCII). Вывести в выходной поток последовательность литер, измененную следующим образом:
a) удалить из каждой группы подряд идущих цифр, в которой более двух цифр и которой предшествует точка, все цифры, начиная с третьей (например, a+12.3456-b-0.456789+1.3-45678 преобразуется в a+12.34-b-0.45+1.3-45678);
b) удалить из каждой группы цифр, которой не предшествует точка, все начальные нули (кроме последнего, если за ним идет точка либо в этой группе нет других цифр, кроме нулей ; например, a-000123+bc+0000.0008-0000+0001.07 преобразуется в a-123+bc+0.0008-0+1.07).
4.ФУНКЦИИ И СТРУКТУРА ПРОГРАММЫ
4.1. Перечислите все существенные изменения, внесенные стандартом ANSI в правила объявления и описания функций. Какова цель этих изменений?
4.2. Перечислить все случаи, когда в Си используется тип void. Дать определение этого типа.
4.3. Перечислить классы памяти, определенные в Си. Что определяет класс памяти? В каких случаях и каким образом класс памяти определяется по умолчанию? Привести примеры.
4.4. Определен ли в Си класс памяти для функций? Если определен, то каким образом; если нет, то почему.
4.5. Допустима ли в Си вложенность функций? Можно ли в Си каким-то образом управлять видимостью функций?
4.6. Объяснить, чем различаются описание ( объявление, declaration ) и определение ( definition) – по терминологии Б. Кернигана и Д. Ритчи [1, см. стр.71]. Привести примеры.
4.7. Эквивалентны ли следующие объявления функций:
a) double f ( ); и double f (void);
b) char g ( int i, char c); и char g ( int, char);
c) h ( double x); и int h ( double x);
d) void h ( int ); и h ( int );
e) extern int q ( int ); и int q ( int);
f) static void s ( char c); и void s ( char c);
4.8. Определить, какие конструкции являются определениями, а какие описаниями; где они могут располагаться и что обозначают:
int i; char c = ‘a’; extern int f ( int, char );
static int j; register int b; double g( ) { return 3.141592; };
extern long k; int h ( int i ); static char q( int, double );
auto short n; s(); static void p( int i ) { };
4.9. Верны ли следующие утверждения:
a) «тип выражения в операторе return должен совпадать с типом результата функции»
b) «функция, которая не возвращает результата (тип результата void), может не содержать оператор return;»
c) «функция, которая возвращает результат, может не содержать оператор return E; но вызывает другую функцию, которая содержит такой оператор»
d) «функция, которая возвращает результат, может содержать несколько операторов return E; »
e) «в Си аргументы функции всегда передаются по значению»
f) «в теле одной функции могут находиться два разных оператора, помеченных одинаковыми метками, если эти операторы находятся в разных блоках»; например,
void f(void)
{ ... label: S1; ...
{ ... label: S2; ... goto label; ...}
... goto label;
...
}
g) «в Си нельзя использовать две (или более) взаимно рекурсивных функций»; например, если есть void f(void){... g();...} и void g(void){...f();...}, то программа, использующая такие функции, будет ошибочной.
h) «в Си можно войти в блок, минуя его заголовок; при этом память под локальные переменные, описанные в этом блоке, будет отведена, но инициализация (если она есть) выполняться не будет»
i) «любая функция, описанная в каком-либо файле, входящем в состав программы, может быть использована в этом и любом другом файле этой программы»
-
«в этом фрагменте программы нет ошибок »
#include
int f(void) { return 100;}
void g(void) { printf("O.K.\n");}
main()
{ int i, j;
i = f();
j = g(), f();
g(); f();
printf("i=%d, j=%d f=%d\n", i, j, f());
}
4.10. В каких случаях в Си возможна инициализация переменных? Когда она происходит? Как определяется инициализация по умолчанию?
4.11. Допустимо ли в Си? Если "да" - опишите семантику этих действий; если "нет" - объясните почему.
a) #include b) #include
main() main()
{ int i; int sum = 0; { int i; int sum = 0;
for ( i = 1; i <= 3; i++) for ( i = 1; i <= 3; i++)
{ sum += i; { sum += i;
{ int i; { for ( i = 1; i <= 5; i++)
for ( i = 1; i <= 5; i++) sum = i;
sum = i; }
} }
} printf("sum=%d\n", sum);
printf("sum=%d\n", sum); }
}
c) #include d) #include
main() main()
{ double x; { double x;
scanf("%f", &x;); scanf("%f", &x;);
if ( x >= 0 ) goto ok; if ( x >= 0 ) goto ok;
{ double y = 5.0; { double y;
x = x ? x : -x; x = x ? x : -x;
ok: y+=sqrt(x); ok: y = sqrt(x);
printf("y = %f\n",y);} printf("y = %f\n",y);
} }
} }
4.12. Допустимо ли в Си? Если "да" - опишите семантику этих действий; если "нет" - объясните почему.
a) файл f1: b) файл f1:
#include #include
main() static int f(void)
{ extern int f(int); { int k;
int i; scanf("%d", &k;); return k; }
i = f(g(5)); extern int g(int);
printf("i = %d\n", i); main()
} { int i;
int g(int k) i = f(); j = g(i);
{ k++; printf("i=%d,j=%d\n", i,j);
return f(k); }
} файл f2:
файл f2: extern int f(void);
int f(int i) { return ii; } int g(int i)
{ return f()+i; }
c) файл f1: d) файл f1:
#include #include
extern int i; extern void f(void); extern int f(void);
main() int i;
{ f(); main()
printf("i = %d\n", i); { printf("res = %d\n", i+f()+f());
f(); }
printf("i = %d\n", i);
} файл f2:
int f(void)
файл f2: { static int i = 10;
int i = 1; return i--;
void f(void) { i++; } }
4.13. Что напечатает следующая программа?
a). #include b). #include
int i = 0; void f(void); int f( int ); int b = 10;
main() main()
{ int i =1; { int c = 3;
printf("i1 = %d\n", i); b = f(c);
f(); printf("c=%d b=%d\n",c,b);
{ int i = 2; printf("i4 = %d\n", i); }
{ i +=1; printf("i5 = %d\n", i); } int f( int b )
printf("i6 = %d\n", i); { int c = 5;
} c--; b++;
printf("i7 = %d\n", i); printf("c=%d b=%d\n",c,b);
} return c+b;
void f(void) }
{ printf("i2 = %d\n", i);
i = i + 10; printf("i3 = %d\n", i); }
c). #include d). #include
char g ( char c); int abc( int ); int x;
int f ( int i, char c) main()
{ int k = i+4; char b = g(c) + i; { int b;
printf("c1 = %c k0 = %d\n", c, k); b = abc(x);
{ int i = 3; k += i; printf("b1=%d x1=%d\n",b,x);
printf("i1 = %d k1 = %d\n", i, k); x = abc(b);
c = g(‘b’); printf("c2 = %c\n", c); printf("b2=%d x2=%d\n",b,x);
} }
i++; printf("i2 = %d k2 = %d\n", i, k); int abc( int b )
return i(b-c); } { static int x = 5;
char g(char c) x += 7; b++;
{ c = c + 1; return c; } printf("b0=%d x0=%d\n",b,x);
main() return x+b;
{ int k =2; char c = ‘a’; k = f (k, c); }
printf("c3 = %c k3 = %d\n", c, k);
}
e). #include f). #include
int i = 1; int i = 1;
int reset ( void ); int reset ( void );
int next ( int ); int next ( void );
int last ( int ); int last ( void );
int new ( int ); int new ( int );
main() main()
{ int i, j; i = reset(); { int i, j; i = reset();
for ( j = 1; j <= 3; j++ ) for ( j = 1; j <= 3; j++ )
{ printf("i=%d j=%d\n", i, j); { printf("i=%d j=%d\n", i, j);
printf("%d %d\n", next(i), last(i)); printf("%d\n", next(),);
printf("%d\n", new(i+j)); printf("%d\n", last());
} } printf("%d\n", new(i+j)); } }
int reset ( void ) { return i; } в файле f1:
int next ( int j ) { return j = i++; } static int i =10;
int last ( int j ) int next ( void ) { return i += 1; }
{ static int i = 10; return j = i--; } int last ( void ) { return i -= 1; }
int new ( int i ) int new ( int i)
{ int j = 10; return i = j += i; } { static int j = 5; return i=j+=i; }
в файле f2:
extern int i;
int reset ( void ) { return i; }
4.14. Программа. Описать рекурсивную функцию вычисления n! - факториала числа n, основанную на соотношении n! = n(n-1)!. С ее помощью найти факториалы натуральных чисел от1 до 10.
4.15. Программа. Описать рекурсивную функцию вычисления xn для вещественного x (x 0) и целого n:
1 при n = 0
xn = 1/x|n| при n < 0
x xn-1 при n > 0
Протестировать эту функцию на подходящих наборах входных данных.
4.16. Программа. Описать рекурсивную функцию вычисления НОД(n,m) - наибольшего общего делителя неотрицательных целых чисел n и m, основанную на соотношении НОД(n,m) = НОД(m,r), где r - остаток от деления n на m (см. задачу 3.43). С ее помощью найти наибольший общий делитель натуральных чисел a и b. Сравнить эффективность рекурсивной и нерекурсивной функций вычисления НОД.
4.17. Программа. Описать рекурсивную функцию вычисления
НОД ( n1, n2, n3, ..., nm), воспользовавшись для этого соотношением:
НОД ( n1, n2, n3, ... , nk) = НОД ( НОД ( n1, n2, n3, ... , nk-1 ), nk ), k = 3, 4, ... , m. С ее помощью найти НОД ( a1, a2, a3, ..., a10).
4.18. Программа. Описать рекурсивную функцию вычисления n–ого числа Фибоначчи: f0 = 1; f1 = 1; fj+1 = fj-1+ fj; j = 1, 2, 3,.…С ее помощью вычислить 100-ое число Фибоначчи.
4.19. Программа. Описать рекурсивную функцию вычисления значения A(n,m) - функции Аккермана для неотрицательных целых чисел n и m:
m+1 если n = 0
A(n,m) = A(n-1,1) если n 0, m = 0
A(n-1, A(n, m-1)) если n>0, m>0
С помощью этой функции найти значение A(5,8).
<предыдущая страница | следующая страница>