Решение задачи Статическая сложность с Меньшиков

Без пояснения   Просмотров: 38


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

Обычно определяют время выполнения алгоритма по отношению к n - "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от n - непростая задача, было бы замечательно, если бы её можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:

<Программа> ::= "BEGIN" <Список операторов> "END"
<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
<Оператор> ::= <Оператор LOOP> | <Оператор OP>
<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
<Оператор OP> ::= "OP" <число>
Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключённый в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, то есть или заданное константное число раз, если задано число, или n раз, если параметром является n. Время выполнения списка операторов равно сумме времени выполнения его частей. Таким образом, время выполнения программы в целом зависит от n.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <string.h>
 
using namespace std;
const int MAX_SIZE = 2048 + 10;
const int MAX_STEPS = 12;
 
int n;
typedef vector<int> algoComplex;
 
void ReadOperatorsList(char* &pos, algoComplex &totalAC);
void output(algoComplex &ac, int num)
{
    printf("Program #%d\n",num);
    printf("Runtime = ");
    bool isFirst = true;
    bool isEmpty = true;
    for (int i = MAX_STEPS-1; i>=0; i--) {
        int mul = ac[i];
        if (mul){
            isEmpty = false;
            if (isFirst)
                isFirst = false;
            else
                cout<<"+";
           
            if (mul != 1 || (mul == 1 && i ==0))
                cout<<mul;
            if (i != 0){
                if (mul != 1) cout<<"*";
                cout<<"n";
                if (i!=1)
                    cout<<"^"<<i;
            }
        }
    }
    if (isEmpty) cout<<0;
    printf("\n\n");
}
 
inline bool _isEnd(const char* pos)
{
    return *pos == 0;
}
inline void _SkipSeps(char* &pos)
{
    if (_isEnd(pos)) return;
    while (!_isEnd(pos) && *pos == ' ')
        pos++;
}
inline bool _isLoopBegin(const char* pos)
{
    if (_isEnd(pos)) return false;
    return *pos == 'L';
}
inline bool _isOpBegin(const char* pos)
{
    if (_isEnd(pos)) return false;
    return *pos == 'O';
}
inline bool _isOperatorBegin(const char* pos)
{
    return _isLoopBegin(pos) || _isOpBegin(pos);
}
inline bool _isDigit(const char pos)
{
    return '0' <= pos && pos <= '9';
}
inline void ReadLex(char* &pos, int len)
{
    for (int i=0;i<len;i++)
        pos++;
}
void ReadNumber(char* &pos, int &number)
{
    if (*pos == 'n') {
        pos++;
        number = -1;
        return;
    }
    while (_isDigit(*pos)) {
        number = number*10 + *pos - '0';
        pos++;
    }
}
void ReadOperatorLoop(char* &pos, algoComplex &listAC)
{
    //<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
    //<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
    ReadLex(pos, strlen("LOOP"));
    int loopNumber = 0;
 
    _SkipSeps(pos);
    ReadNumber(pos, loopNumber);
    _SkipSeps(pos);
 
    algoComplex loopAC(MAX_STEPS);
 
 
    bool isIns = false;
    while (_isOperatorBegin(pos)) {
 
        isIns = true;
        _SkipSeps(pos);
        ReadOperatorsList(pos,loopAC);
        _SkipSeps(pos);
    }
    if (isIns) {
        if (loopNumber != -1) { // !=n
            for (int i=0;i<MAX_STEPS;i++)
                loopAC[i] *= loopNumber;
        }
        else {
            for (int i=MAX_STEPS-2;i>=0;i--)
            {
                loopAC[i+1] = loopAC[i];
                loopAC[i] = 0;
            }
        }
    }
    else {
        if (loopNumber != -1)  // !=n
            loopAC[0] = loopNumber;
        else
            loopAC[1]++;
    }
 
    for (int i=0;i<MAX_STEPS;i++)
        listAC[i] += loopAC[i];
 
    _SkipSeps(pos);
    ReadLex(pos,strlen("END"));
}
 
void ReadOperatorOp(char* &pos, algoComplex & listAC)
{
    //<Оператор OP> ::= "OP" <число>
    ReadLex(pos, strlen("OP"));
    _SkipSeps(pos);
    int opNumber = 0;
    ReadNumber(pos, opNumber);
    if (opNumber != -1) // !=n
        listAC[0] += opNumber;
    else
        listAC[1]++;   
}
 
void ReadOperator(char* &pos, algoComplex &curAC)
{
    //<Оператор> ::= <Оператор LOOP> | <Оператор OP>
    if (_isLoopBegin(pos))
        ReadOperatorLoop(pos, curAC);
    else
        ReadOperatorOp(pos, curAC);
}
void ReadOperatorsList(char* &pos, algoComplex &totalAC)
{
    //<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
    do
    {
        _SkipSeps(pos);
        algoComplex curAC(MAX_STEPS);
        ReadOperator(pos, curAC);
        for (int i=0;i<MAX_STEPS;i++)
            totalAC[i] += curAC[i];
        _SkipSeps(pos);
    }
    while (_isOperatorBegin(pos));
}
void ReadProgram(char* &pos, algoComplex &ac)
{
    // <Программа> ::= "BEGIN" <Список операторов> "END"
    _SkipSeps(pos);
    ReadLex(pos, strlen("BEGIN"));
 
    ReadOperatorsList(pos, ac);
 
    _SkipSeps(pos);
    ReadLex(pos, strlen("END"));   
}
void input()
{
    cin>>n;
    string allPrograms = "";
    char buf[MAX_SIZE];
    while (cin.getline(buf,MAX_SIZE)) {
        allPrograms += string(buf);
        allPrograms += " ";
    }
 
    algoComplex progAC(MAX_STEPS);
    char *str  = new char[allPrograms.size()];
    strcpy(str, allPrograms.c_str());
    char *pos = str;
    for (int i=0;i<n;i++)
    {
        progAC.assign(MAX_STEPS,0);
        ReadProgram(pos, progAC);
        output(progAC, i+1);
    }   
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться