UVa 656 Optimal Programs

题目描述给定一个函数以若干输入/输出对的形式描述n≤10n \le 10n≤10。要求生成一个最短的、在该栈式机器上运行的程序能够将每个输入映射到对应的输出。机器支持五种指令ADD弹出栈顶两个元素aaa栈顶、bbb次栈顶压入ababab。SUB弹出栈顶两个元素aaa、bbb压入b−ab-ab−a。MUL弹出栈顶两个元素aaa、bbb压入a×ba \times ba×b。DIV弹出栈顶两个元素aaa、bbb若a0a0a0则错误否则压入b/ab/ab/a整数除法向零取整。DUP复制栈顶元素压入一个副本。程序开始时栈中只有一个整数输入结束时栈中也必须只有一个整数输出。若执行过程中出现以下情况则程序进入错误状态执行DIV时栈顶元素为000。执行ADD、SUB、MUL、DIV时栈中元素少于222个。操作结果绝对值超过300003000030000。若存在多个最短程序输出字典序最小的按指令字符串排序ADDDIVDUPMULSUB。若不存在程序输出Impossible若最短程序为空即n0n0n0或恒等函数输出Empty sequence。输入格式输入包含多个函数描述。每个描述第一行为整数nnnn≤10n \le 10n≤10表示输入/输出对数量。接下来两行各有nnn个整数第一行是输入值第二行是对应的输出值。输入以n0n0n0结束。输出格式对于每个函数描述输出两行第一行为Program X:其中XXX为程序编号从111开始第二行为程序指令序列指令间用空格分隔若不存在则输出Impossible若为空序列则输出Empty sequence。每个程序输出后跟一个空行。样例输入1 1 1 1 1 2 2 3 4 0注样例输入不完整仅为示意。题目分析本题要求在栈式机器上搜索最短程序。由于指令数量有限555种且程序长度上限未明确给出但搜索结果通常在101010步以内可以使用广度优先搜索BFS\texttt{BFS}BFS从输入状态出发逐步扩展程序直到找到能将所有输入映射到对应输出的程序。为了保证最短和字典序最小BFS\texttt{BFS}BFS按层扩展并在同一层中按指令字典序生成后继状态。状态表示对于每个输入值需要维护其对应的栈状态当前栈中所有元素。由于n≤10n \le 10n≤10且每个输入独立执行但指令序列对每个输入是相同的因此搜索时需同时模拟所有输入的栈状态以确保同一程序对所有输入均有效。解题思路状态定义使用结构体state包含operations当前程序指令序列字符表示每个字符0–4对应五种指令。operands当前栈内容仅针对第一个输入值作为搜索的引导。由于所有输入共享同一指令序列只需用一个输入来驱动搜索即可其他输入在检查时再验证。搜索策略采用广度优先搜索BFS\texttt{BFS}BFS初始状态程序为空栈为{source[0]}。从队列中取出状态若当前程序长度超过101010则跳过或继续但一般101010步足够。若当前栈只有一个元素且等于target[0]则调用check函数验证该程序是否对所有输入都正确。若正确则找到最短程序因为BFS\texttt{BFS}BFS按层扩展首次找到即为最短。否则生成后继状态若栈大小≤1\le 1≤1只能执行DUP因为其他指令需要至少两个元素。若栈大小≥2\ge 2≥2可尝试所有五种指令但需模拟执行并检查错误条件如除零、溢出、栈下溢。按指令的字典序顺序ADD、DIV、DUP、MUL、SUB生成后继保证同一层中字典序最小。使用check函数对每个输入/输出对复制初始栈按当前指令序列逐步执行若任何步骤出错或最终结果不匹配则返回false。结果输出若找到程序将operations转换为指令字符串如ADD若为空则输出Empty sequence。若BFS\texttt{BFS}BFS结束未找到输出Impossible。复杂度分析搜索深度通常不超过101010分支因子最多555状态数有限。每个状态检查时对nnn个输入执行程序每次O(L)O(L)O(L)其中LLL为程序长度。总体时间复杂度O(states⋅n⋅L)O(\text{states} \cdot n \cdot L)O(states⋅n⋅L)在可接受范围内。代码实现// Optimal Programs// UVa ID: 656// Verdict: Accepted// Submission Date: 2017-06-06// UVa Run Time: 0.260s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string commands[]{ADD,DIV,DUP,MUL,SUB};intn,source[10],target[10];structstate{string operations;vectorintoperands;};boolcalculate(vectorintresult,charoperators){inta,b;switch(operators){case0:// ADDaresult.back();result.pop_back();bresult.back();result.pop_back();if(abs(ab)30000)returnfalse;result.push_back(ab);break;case1:// DIVaresult.back();result.pop_back();bresult.back();result.pop_back();if(a0)returnfalse;if(abs(b/a)30000)returnfalse;result.push_back(b/a);break;case2:// DUPresult.push_back(result.back());break;case3:// MULaresult.back();result.pop_back();bresult.back();result.pop_back();if(abs(a*b)30000)returnfalse;result.push_back(a*b);break;case4:// SUBaresult.back();result.pop_back();bresult.back();result.pop_back();if(abs(b-a)30000)returnfalse;result.push_back(b-a);break;}returntrue;}boolcheck(stringoperations){for(inti0;in;i){vectorintresult;result.push_back(source[i]);for(intj0;joperations.size();j)if(!calculate(result,operations[j]))returnfalse;if(result.back()!target[i])returnfalse;}returntrue;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinn,n0){for(inti0;in;i)cinsource[i];for(inti0;in;i)cintarget[i];string sequenceImpossible,empty;state current,next;queuestateunvisited;unvisited.push(state{empty,vectorint(1,source[0])});while(!unvisited.empty()){currentunvisited.front();unvisited.pop();if(current.operations.size()10)continue;if(current.operands.size()1current.operands.back()target[0]){if(check(current.operations)){sequence.clear();for(inti0;icurrent.operations.size();i){if(i0)sequence ;sequencecommands[current.operations[i]-0];}if(sequence.length()0)sequenceEmpty sequence;break;}}if(current.operands.size()1){nextcurrent;next.operations2,next.operands.push_back(next.operands.back());unvisited.push(next);}else{for(inti0;i5;i){nextcurrent;next.operations(char)(0i);if(!calculate(next.operands,(char)(0i)))continue;unvisited.push(next);}}}coutProgram cases\n;coutsequence\n\n;}return0;}总结本题通过广度优先搜索在指令空间中找到最短且字典序最小的程序。关键在于利用栈式机器的特性用单个输入驱动搜索减少状态空间。按指令字典序生成后继保证最短程序中的最小字典序。正确模拟所有五种指令包括错误检查。搜索深度限制为101010实际足够避免无限循环。最终验证程序对所有输入均有效。该解法是典型的自动程序合成问题展示了搜索算法在简单编程语言中的应用。