Язык Си в примерах/Скобочки: различия между версиями
Нет описания правки |
|||
Строка 26: | Строка 26: | ||
<source lang="c"> |
<source lang="c"> |
||
#include <stdio.h> |
#include <stdio.h> |
||
int main (void) |
|||
{ |
{ |
||
int ch, a=0; |
int ch, a=0; |
||
Строка 37: | Строка 37: | ||
if( a == 0) printf ("Правильно\n"); |
if( a == 0) printf ("Правильно\n"); |
||
else printf ("Не правильно\n"); |
else printf ("Не правильно\n"); |
||
return 0; |
|||
} |
} |
||
</source> |
</source> |
Версия от 17:20, 18 ноября 2008
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
Задача "Скобки"
Программа "Скобки" должна определять правильность введённой скобочной структуры. Правильная скобочная структура, это то, что можно получить из арифметического выражения со скобками, выкинув все знаки операций и цифры. Например:
- Правильные скобочные структуры
- ()
- ()()
- ((()))
- (()())
- ((()())())
- Неправильные скобочные структуры
- )(
- ())(
- (
- ())
- )(())(
Вход: Слово в алфавите из двух круглых скобочек ( и ). Длина слова меньше 100000 символов.
Выход: Либо NO, либо YES.
#include <stdio.h>
int main (void)
{
int ch, a=0;
printf ("Введите слово из скобок: ");
do {
ch = getchar();
if( ch == '(' ) a++;
else if( ch == ')' ) if(--a < 0) break;
} while(ch != '\n');
if( a == 0) printf ("Правильно\n");
else printf ("Не правильно\n");
return 0;
}
Здесь нам встречается оператор ==, который соответствует логическому "тождественно равно". Когда мы пишем i = 0, то мы присваеваем переменной i значение 0.
Выражение i == 0 является проверкой равенства, её значение равно "истина" или "ложь".
В языке C/C++ "истина" соответствует любому ненулевому числу. Поэтому, вместо i == 0 мы могли бы написать равносильное i, но это не рекомендуется делать.
Обратите внимание на то, что программа не хранит скобочную структуру в памяти. В этом нет необходимости, поскольку алгоритм однопроходный, то есть достаточно конечной памяти и одного пробега по сколь угодно большим входным данным, чтобы получить результат.
Свойством однопроходности обладает также рассмотренный нами алгоритм поиска максимума из чисел.
Задача сортировка чисел не является однопроходным алгоритмом.
- Какие из перечисленных задач имеют однопроходные решения:
- Найдите среднее арифметическое чисел.
- Найдите дисперсию чисел (средний квадрат отклонения от среднего).
- Найдите три самых маленьких числа среди введенных.
- Напишите программу, которая проверяет правильность скобочной структуры, составленной из нескольких типов скобок (круглых, квадратных и фигурных).Например, ({()[]}) — правильная структура, а ({()[)}] — неправильная.
- Напишите программу, которая выводит все правильные скобочные структуры заданной длины. А именно, опишите рекурсивную функцию "вывести все правильные скобочные структуры длины n".
- Напишите программу, которая определяет число правильных скобочных структур заданной длины. Сведите задачу к множеству задач: число префиксов правильных скобочных структур длины n, которые имеют k незакрытых скобок.