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

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