VPF::[Алгоритм] Олимпиадная информатика, комбинаторика

saysmonic

Дата 20.8.2011, 18:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 26.7.2011

Репутация: нет
Всего: нет

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

Выражение, построенное из констант a,b,c,d,e,f,g,h и комбинаторов I, K, S, будем называть корректным, если оно удовлетворяет следующей грамматике:
<выр> ::= a | b | c | d | e | f | g | h | I <выр> | K <выр> <выр> | S <выр> <выр> <выр>.
Корректному выражению соответствует ответ 1, некорректному – 0.
Например, выражение IKcd является корректным, а SbKd – нет. Вывод ответа: 1,0.
Определите, являются ли корректными следующие выражения:
1. SKghaIISdKIbhId
2. IKScgKSgeIIKcfd
3. KShfIKaSbebIIeISdfIc
4. SKKhKaIeebdKIScIhKcIIb
5. KeSaSefSffISKIIfSeaIIeIKbceIIg
6. KSdSIabaSfdghSIKIbIfd
Ответы введите через запятую без пробелов, для корректного выражения укажите ответ 1, для некорректного – 0.

Ответ: 1,0,0,0,1,0.

Ответы как видите есть, но мне нужен процесс решения, желательно на си или паскале. Заранее спасибо

Silent

Дата 22.8.2011, 14:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 6
Всего: 9

А откуда задачка? Держи:

Код


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

char s[10000];
int index = 0, 
    n = 0, 
    len = 0;

bool DoIt()
{
    bool res = false;
    if (index == len) res = false;
    else
        switch (s[index])
        {
            case ('I'):
                {
                    index++;
                    res = DoIt();
                    break;
                }
            case ('K'):
                {
                    index++;
                    res = DoIt() && DoIt();
                    break;
                }
            case ('S'):
                {
                    index++;
                    res = DoIt() && DoIt() && DoIt();
                    break;
                }
            default:
                {
                    res = (s[index] >= 'a') && (s[index] <= 'h');
                    index++;
                    break;
                }
        }
    return res;
}


void main()
{
    scanf("%d",&n);
    gets(s);    //read "\n" after n
    for (int i = 0; i < n; i++)
    {
        gets(s);
        index = 0;
        len = strlen(s);
        printf(((DoIt() && index == len) ? "1\n" : "0\n"));
    }
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »