主题：第70次编程比赛题目
雨中飞燕 [专家分：18980] 发布于 2008-08-08 19:21:00
[size=3]上次比赛冠军得主因为长时间没有再在此发帖子，也联系不到
正好偶有题目，先抢占个位置了。。。
本次比赛题目如下：
[color=Blue]题目描述：[/color]
有n个正整数(4<=n<=13)，在这n个正整数之间插入四则运算符，
使得结果恰好等于一个给定的整数值，注意这n个整数的先后顺序不能改变，
不插入运算符的地方的数字直接连起来成一个新数，
如1 2之间不插入运算符则为12，1 2 3之间的话则为整数123
如：1*23-4=19 12+3+4=19
[color=Blue]输入：[/color]
你的程序只需处理一组测试数据，每组第一行1个正整数n
接下来一行为n个小于20的正整数，这n个数和结果连起来总长度小于15位
第三行为要计算出的结果k(-10000<k<10000)
[color=Blue]输出：[/color]
输出1行1个整数，表示解的个数
[color=Blue]样例输入：[/color]
4
1 2 3 4
2
[color=Blue]样例输出：[/color]
2
[color=Blue]其它信息：[/color]
对于样例，只有
1+2+3-4 = 2
1*2*3-4 = 2
两组解
注意 -1+2-3+4=2 这组不合法，只能为四则运算符，不能作为正负号
[color=Red]你需要考虑运算优先级[/color]
题目来源：yzfy无聊改编
比赛结束时间：8月18日 23:00
比赛代码提交方式：直接回复本帖子，回复将隐藏
主要评比内容：代码时间效率
比赛注意事项：必须严格按照要求进行输入输出，不要输出多余的内容
其它：本题提供在线测试，链接[url]http://yzfy.org/dis/listpost.php?tid=897[/url]
如有疑问，请到[url]http://bbs.pfan.cn/post-282271.html[/url]提出
[/size]
最后更新于：2008-08-12 12:11:00
回复列表 （共34个回复）
31 楼
ckeryradish [专家分：140] 发布于 2008-08-18 22:03:00
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <cctype>
#include <string>
#include <ctime>
#define EXPRESS_SIZE 256
#define UNVALID_OPERA ' '
static char g_szInfixExp[EXPRESS_SIZE] = {'\0'};
static int g_iExpLastIndex = 0;
static int g_iLastOpera = 0;
static int g_iFirstOpera = 0;
static char g_szOpera[] = "+-*/";
static char g_szPostfixExp[EXPRESS_SIZE] = {'\0'};
//满足要求的解的表达式个数
static unsigned int g_uExpFound = 0;
//题目输入的表达式计算结果
static double g_dfWantExpResult = 0.0;
/*将将中缀表达式转换成后缀表达式*/
typedef struct tag_OperateStack
{
char operate[EXPRESS_SIZE];
int iTop;
}OperateStack_t;
static OperateStack_t g_operateStack;
void expressInfixToPostfix(const char szInfixExpIn[EXPRESS_SIZE], char szPostfixExpOut[EXPRESS_SIZE])
{
int iInIndex = 0;
int iOutIndex = 0;
g_operateStack.iTop = -1;
char ch = szInfixExpIn[0];
iInIndex++;
while('\0' != ch)
{
switch(ch)
{
case'(':
g_operateStack.iTop++;
g_operateStack.operate[g_operateStack.iTop] = ch;
break;
case')':
while(-1 != g_operateStack.iTop && '(' != g_operateStack.operate[g_operateStack.iTop])
{
szPostfixExpOut[iOutIndex] = g_operateStack.operate[g_operateStack.iTop];
g_operateStack.iTop--;
iOutIndex++;
}
g_operateStack.iTop--;
break;
case'+':
case'-':
while(-1 != g_operateStack.iTop && '(' != g_operateStack.operate[g_operateStack.iTop])
{
szPostfixExpOut[iOutIndex] = g_operateStack.operate[g_operateStack.iTop];
g_operateStack.iTop--;
iOutIndex++;
}
g_operateStack.iTop++;
g_operateStack.operate[g_operateStack.iTop]=ch;
break;
case'*':
case'/':
while(-1 != g_operateStack.iTop &&
('/' == g_operateStack.operate[g_operateStack.iTop]
|| '*' == g_operateStack.operate[g_operateStack.iTop]))
{
szPostfixExpOut[iOutIndex] = g_operateStack.operate[g_operateStack.iTop];
g_operateStack.iTop--;
iOutIndex++;
}
g_operateStack.iTop++;
g_operateStack.operate[g_operateStack.iTop] = ch;
break;
default:
//操作数直接输出
while(0 != isdigit(ch))
{
szPostfixExpOut[iOutIndex] = ch;
iOutIndex++;
ch = szInfixExpIn[iInIndex];
iInIndex++;
}
iInIndex--;
//区分操作数
szPostfixExpOut[iOutIndex] = UNVALID_OPERA;
iOutIndex++;
break;
} //end switch
ch = szInfixExpIn[iInIndex];
iInIndex++;
} //end while
while(-1 != g_operateStack.iTop)
{
szPostfixExpOut[iOutIndex] = g_operateStack.operate[g_operateStack.iTop];
iOutIndex++;
g_operateStack.iTop--;
}
szPostfixExpOut[iOutIndex]='\0';
}
32 楼
ckeryradish [专家分：140] 发布于 2008-08-18 22:04:00
//计算后缀表达式的值
typedef struct tag_ResultStack
{
double tmpResult[EXPRESS_SIZE];
int iTop;
}ResultStack_t;
static ResultStack_t g_resultStack;
double calcPostfixExp(const char szPostfixExpIn[EXPRESS_SIZE])
{
int iIndex=0;
g_resultStack.iTop=-1;
char ch = szPostfixExpIn[0];
iIndex++;
while(ch!='\0')
{
switch(ch)
{
case'+':
g_resultStack.tmpResult[g_resultStack.iTop-1] += g_resultStack.tmpResult[g_resultStack.iTop];
g_resultStack.iTop--;
break;
case'-':
g_resultStack.tmpResult[g_resultStack.iTop-1] -= g_resultStack.tmpResult[g_resultStack.iTop];
g_resultStack.iTop--;
break;
case'*':
g_resultStack.tmpResult[g_resultStack.iTop-1] *= g_resultStack.tmpResult[g_resultStack.iTop];
g_resultStack.iTop--;
break;
case'/':
if(0.0 == g_resultStack.tmpResult[g_resultStack.iTop])
{
// std::cout << "error div zero" << std::endl;
// return g_resultStack.tmpResult[g_resultStack.iTop];
//避免 g_resultStack.tmpResult[g_resultStack.iTop] 刚好等于g_dfWantExpResult
return g_dfWantExpResult - 1.0;
}
else
{
g_resultStack.tmpResult[g_resultStack.iTop-1] /= g_resultStack.tmpResult[g_resultStack.iTop];
}
g_resultStack.iTop--;
break;
//区分操作数的无效操作符
case UNVALID_OPERA:
break;
default:
double dfOperaNum = 0.0;
while(0 != isdigit(ch))
{
dfOperaNum = 10.0 * dfOperaNum + (double)(ch - '0');
ch = szPostfixExpIn[iIndex];
iIndex++;
}
g_resultStack.iTop++;
g_resultStack.tmpResult[g_resultStack.iTop] = dfOperaNum;
iIndex--;
break;
} //end switch
ch = szPostfixExpIn[iIndex];
iIndex++;
} //end while
return g_resultStack.tmpResult[g_resultStack.iTop];
}
void rec_constructInfixExp(int iPos)
{
if (iPos == g_iLastOpera)
{
//将中缀表达式转换成后缀表达式
expressInfixToPostfix(g_szInfixExp,g_szPostfixExp);
double dfResult = calcPostfixExp(g_szPostfixExp);
//不考虑精度因素，直接使用==
if (g_dfWantExpResult == dfResult)
{
g_uExpFound++;
std::cout << g_szInfixExp << " = " << dfResult << std::endl;
}
g_szInfixExp[g_iLastOpera] = UNVALID_OPERA;
return;
}
int iNextPos = iPos + 1;
int j = 0;
if (0 == isdigit(g_szInfixExp[iNextPos]))
{
for (j = sizeof(g_szOpera) - 2; j >= 0; j--)
{
g_szInfixExp[iNextPos] = g_szOpera[j];
rec_constructInfixExp(iNextPos);
}
}
else
{
rec_constructInfixExp(iNextPos);
}
}
33 楼
ckeryradish [专家分：140] 发布于 2008-08-18 22:05:00
//构造中缀表达式
void constructInfixExp()
{
g_iLastOpera = -1;
g_iFirstOpera = -1;
for (int k = g_iExpLastIndex - 1; k > 0; k--)
{
if (0 == isdigit(g_szInfixExp[k]))
{
g_iLastOpera = k;
break;
}
}
for (int l = 1; l <= g_iLastOpera; l++)
{
if (0 == isdigit(g_szInfixExp[l]))
{
g_iFirstOpera = l;
break;
}
}
//表达式只有一个操作数的情况下
if (-1 == g_iFirstOpera)
{
expressInfixToPostfix(g_szInfixExp,g_szPostfixExp);
double dfResult = calcPostfixExp(g_szPostfixExp);
if (g_dfWantExpResult == dfResult)
{
g_uExpFound++;
std::cout << g_szInfixExp << " = " << dfResult << std::endl;
}
return;
}
rec_constructInfixExp(g_iFirstOpera - 1);
}
void constructOperaNum(const char szNumStr[EXPRESS_SIZE / 2 ], int iNextDigitalIndex, int *piNextTraceChars)
{
if ('\0' == szNumStr[iNextDigitalIndex])
{
std::cout << "src input error" << std::endl;
return;
}
int iNextTraceChars = 0;
iNextTraceChars = 0;
*piNextTraceChars = 0;
//把操作数输出
while('\0' != szNumStr[iNextDigitalIndex] && 0 != isdigit(szNumStr[iNextDigitalIndex]))
{
g_szInfixExp[g_iExpLastIndex] = szNumStr[iNextDigitalIndex];
g_iExpLastIndex++;
(*piNextTraceChars)++;
iNextDigitalIndex++;
}
if ('\0' == szNumStr[iNextDigitalIndex])
{
constructInfixExp();
return;
}
if (0 == isdigit(szNumStr[iNextDigitalIndex]))
{
//跳过操作符
constructOperaNum(szNumStr, iNextDigitalIndex + 1, &iNextTraceChars);
g_iExpLastIndex -= iNextTraceChars;
memset(&(g_szInfixExp[g_iExpLastIndex] ), 0x00, sizeof(g_szInfixExp) - g_iExpLastIndex);
//输出操作符
g_szInfixExp[g_iExpLastIndex] = szNumStr[iNextDigitalIndex];
g_iExpLastIndex++;
(*piNextTraceChars)++;
iNextDigitalIndex++;
constructOperaNum(szNumStr, iNextDigitalIndex, &iNextTraceChars);
g_iExpLastIndex -= iNextTraceChars;
memset(&(g_szInfixExp[g_iExpLastIndex] ), 0x00, sizeof(g_szInfixExp) - g_iExpLastIndex);
}
}
34 楼
ckeryradish [专家分：140] 发布于 2008-08-18 22:06:00
int findExpressCounts(const char *pszInputFile, const char *pszOutputFile)
{
#define DEBUG 0
#if !DEBUG
assert(NULL != pszInputFile);
assert(NULL != pszOutputFile);
FILE *fpInput = NULL;
FILE *fpOutput = NULL;
fpInput = fopen(pszInputFile, "r");
if (NULL == fpInput)
{
std::cout << "failed to open input file " << pszInputFile << std::endl;
return -1;
}
fpOutput = fopen(pszOutputFile, "w");
if (NULL == fpOutput)
{
std::cout << "failed to open output file" << pszOutputFile << std::endl;
fclose(fpInput);
return -1;
}
int iDigitalCount = 0;
fscanf(fpInput, "%d", &iDigitalCount);
// std::cout << "iDigitalCount " << iDigitalCount << std::endl;
//忽略第一行给的整数数字
//把第二行所有的数字组装成一个字符串
//第二行一定要以有效数字结尾
char szDigitalString[EXPRESS_SIZE / 2] = {'\0'};
//获取第二行第一个字符
int ch = fgetc(fpInput);
//去掉第一行的'\n'
while ('\n' == ch || '\r' == ch)
{
ch = fgetc(fpInput);
}
int i = 0;
while('\n' != ch && '\r' != ch)
{
szDigitalString[i] = ch;
i++;
ch = fgetc(fpInput);
}
szDigitalString[i] = '\0';
std::cout << "Numbers: " << szDigitalString << std::endl;
//获取最后一行构造表达式的计算结果
int iWantExpResult = 0;
fscanf(fpInput, "%d", &iWantExpResult);
g_dfWantExpResult = (double)iWantExpResult;
std::cout << "Express Result: " << g_dfWantExpResult << std::endl;
#else
const char szDigitalString[] = "10 11 12 13";
int iDigitalCount = 4;
g_dfWantExpResult = (double)46;
#endif
clock_t start;
clock_t end;
start = clock();
int iTraceChars = 0;
constructOperaNum(szDigitalString, 0, &iTraceChars);
end = clock();
std::cout << "Timing " << (float)(end - start) / CLK_TCK << " Seconds" << std::endl << std::endl;
std::cout << "Express counts Found: " << g_uExpFound << std::endl;
#if !DEBUG
fprintf(fpOutput, "%u", g_uExpFound);
fclose(fpInput);
fclose(fpOutput);
#endif
return 0;
}
int main(int argc, char *argv[])
{
return findExpressCounts("70th_input.txt", "70th_output.txt");
}
我来回复
您所在位置：