POJ1472-Instant Complexity

[POJ] [INDEX] [1472] [Instant Complexity]

[Time: 1000MS] [Memory: 10000K] [难度: 中级] [分类: 模拟法]

---

问题描述

给出一段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再处理

测试数据

• 来源：Southwestern European Regional Contest 1997
• 下载：download
• 输入：input
• 输出：output

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;
}

---

版权声明

　　

• Site: http://exp-blog.com
• Mail: [email protected]

---