POJ 1472 - Instant Complexity


问题描述

给出一段Pascial程序,计算其时间复杂度(能计算的项则计算,不能计算则化到最简的关于n的表达式O(n),并把各项根据n的指数从高到低排列),输出时,系数为0的项不输出,系数为1的项不输出系数,指数为1的项不输出指数。

一段程序只有唯一一个BEGIN,代表程序的开始。与其对应的为最后的END,代表程序的结束。

一段程序最多只有10层循环嵌套,循环的入口为LOOP,一个LOOP对应一个END,代表该层循环的结束。

一段程序中OP的个数不限。

LOOP是循环的入口,其后面的数据可能是常量(非负整数),也可能是变量n,代表循环体执行的次数。

OP是语句,其后面的数据只能为常量(非负整数),代表该语句执行的次数。

解题思路

此题就是一条表达式化简的模拟题,用递归直接模拟(也可用状态机做)。

以第一个样例说明处理方法:

BEGIN
  LOOP n
    OP 4
    LOOP 3
      LOOP n
        OP 1
      END
      OP 2
    END
    OP 1
  END
  OP 17
END

从该例子我们可以得到一条关于n的最初表达式: n*(4+3*(n*1+2)+1)+17

稍微化简一下,合并同一层的OP值,得到了: n*(3*(n*1+2)+5)+17

不难看出每一个循环体都能写成 k*n+i 形式的子表达式,其中loop是 * 关系,op是 + 关系

由于最大循环次数为10,那么我们用 exp[11] 存储多项式的每一项的指数i和系数 k=exp[i],其中 exp[0] 其实就是常数项,由OP语句产生

注意LOOP后面可能输入字符n,也可能输入数字

处理方法:

  • 用字符串输入s
  • 若为 s[0]==n,则直接作字符处理
  • s[0]!=n,则认为是数字串,把它转换为int再处理

测试数据

AC 源码

//Memory Time 
//264K   0MS 

#include<iostream>
using namespace std;

/*字符串转数字*/
int StrToNum(char* s)
{
    int digit=0;
    for(int i=0;s[i];i++)
        digit=digit*10+(s[i]-'0');

    return digit;
}

bool solve(int* exp)
{
    char s[30];
    cin>>s;

    if(s[0]=='E')    //END
        return false;
    else if(s[0]=='B')  //BEGIN
        while(solve(exp));   //若因为OP返回,则继续;若因为END返回,则结束
    else if(s[0]=='O')  //0P
    {
        cin>>s;
        exp[0]+=StrToNum(s);
        return solve(exp);
    }
    else     //LOOP
    {
        int TempExp[11]={0};  //临时exp[]
        cin>>s;
        while(solve(TempExp));

        if(s[0]=='n')   //LOOP n
        {
            for(int i=10;i>0;i--)
                TempExp[i]=TempExp[i-1];  //表达式乘以n,则所有项的次数+1
            TempExp[0]=0;
        }
        else  //LOOP Num
        {
            int x=StrToNum(s);
            for(int i=0;i<11;i++)
                TempExp[i]*=x; //表达式乘以const,则所有项的系数*const
        }
        for(int i=0;i<11;i++)
            exp[i]+=TempExp[i];
    }
    return true;
}

int main(void)
{
    int test;
    cin>>test;
    for(int t=1;t<=test;t++)
    {
        char s[6];
        int exp[11]={0};  //指数为i的项,其系数为exp[i]

        solve(exp);

        cout<<"Program #"<<t<<endl;
        cout<<"Runtime = ";

        bool flag=false;
        bool before=false;  //标记输出当前项之前,是否输出过前面的项
        for(int i=10;i>=0;i--)
            if(exp[i])   //当系数不为0时,才输出该项
            {
                flag=true;

                if(before)
                {
                    cout<<'+';
                    before=false;
                }

                if(!i)  //当指数为0时,直接输出系数
                {
                    cout<<exp[i];
                    before=false;
                }
                else
                {
                    bool sign=false;  //标记系数是否为1
                    if(i && exp[i]!=1)
                    {
                        sign=true;
                        cout<<exp[i];
                        before=true;
                    }
                    if(i)  //当指数不为0时
                    {
                        if(sign)
                            cout<<'*';
                        cout<<'n';
                        if(i!=1)
                            cout<<'^'<<i;
                        before=true;
                    }
                }
            }
        if(!flag)
            cout<<0<<endl<<endl;
        else
            cout<<endl<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1276 - Cash Machine POJ 1276 - Cash Machine
POJ 1276 - Cash Machine Time: 1000MS Memory: 10000K 难度: 初级 分类: 背包 问题描述有各种不同面值的货币,每种面值的货币有不同的数量,请找出利用这些货币可以凑成的最接近且小于等于给
2011-09-15
下一篇 
POJ 2632 - Crashing Robots POJ 2632 - Crashing Robots
POJ 2632 - Crashing Robots Time: 1000MS Memory: 65536K 难度: 初级 分类: 模拟法 问题描述无。 解题思路简单的模拟题而已。 程序很长不是因为算法(根本就没算法),而是因为很多情况
2011-09-13
  目录