北京大学ACM国际大学生程序设计竞赛课件4

问题求解与程序设计第三讲模拟问题李文新2004.2–2004.6内容提要作业总结-1016作业总结-1048讨论–1207作业–12071016NumbersThatCount题意countthenumbersofeachdigittoformthenewnumber123321-〉2122231）Self-inventory2)enterselfinventoryafterksteps3)enterinventoryloopoflengthk4)cannotdeterminedafter15steps1016NumbersThatCount函数inv(char*n1,char*n2)将n1转成n2对于每个测试数据•i从1到15做inventory每次得到新的数码即跟前面的比对，如果发现与第j个相同，就下结论。i=1&&j=0selfinventoryingj=i-1selfinventoryingafteri-1stepsElseinventoryloopoflengthi-jafterjsteps•Cannotbeclassified源程序1016c0400348274.txt1016c0400348198.txt1048FollowMyLogic对于一个逻辑电路和给定的输入值，计算该电路的输出值。该逻辑电路有一个或多个输入端，零个或多个逻辑门电路，和一个输出端。本题中用标准ASCll字符来表示逻辑电路：横竖导线分别用‘-’和‘|’表示，转折点用‘+’表示，输入端用大写字母‘A’-’Z’表示，输出端用问号‘?’表示，小写字母‘o’表示取反。与门、或门及电路各部分示例如下：:\:\-:\-o:\A-o:\:)::)-:)o-:)o-?:/:/-:/--:/B--:/与门或门带输入输出输入输出完整电路的门电路取反的门电路1048FollowMyLogic题中的逻辑电路满足以下条件：•1.逻辑电路图中至多有100行，每行至多有100个字符。•2.电路走向在交叉点转90˚，其余部分沿直线传播。任意两个交叉点都不相邻（竖直方向和水平方向）。•3.整个电路是连通的，不含残缺电路。•4.两段电路之间不会交叉。•5.门电路（与门、或门）的输入端与输出端都是水平的。•6.取反运算的出现只会在紧挨门电路输入端之前，或紧挨门电路输出端之后。（如上图所示）1048FollowMyLogic输入：•输入数据包含多个输入数据块。每个输入数据块包含以下部分：一个电路图，以上述形式表示，用只含‘*’的单独一行结束。多行01字符串，每行对应一组数据，包含26个0或1，分别对应A-Z的值。用只含‘*’的单独一行结束输出：•对每组输入数据，输出对应的电路输出值。•每个结果占一行。•不同输入数据块的输出结果之间用空行隔开。1048FollowMyLogic思路•将逻辑电路表示成后缀表达式•根据输入求解后缀表达式源程序•1048nealzane.txt内容提要作业总结-1016作业总结-1048讨论–1207作业作业12071028