一、欧拉回路
所谓欧拉回路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G （V ，E ）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．
在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果： 定理1 对连通图G （V ，E ），下列条件是相互等价的： （1）G 是一个欧拉图；
（2）G 的每一个节点的度数都是偶数；
（3）G 的边集合E 可以分解为若干个回路的并．
证明 ：()()12? 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．
()()23? 设G 中每一个节点的度数均为偶数．若能找到一个回路C 1使G=C 1，则结论成立．否则，令G 1=G\C 1，由C 1上每个节点的度数均为偶数，则G 1中的每个节点的度数亦均为偶数．于是在G 1必存在另一个回路C 2．令G 2=G 1\C 2，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路C r 使 G r =G r-1\C r 上各节点的度数均为零，即C r =G r-1．这样就得到Ｇ的一个分解 G C C C r =???12 ．
()()31? 设G C C C r =???12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连
通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．
利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法．
二、弗罗莱算法
算法步骤如下：
（1）任取起始点v v R 00,;→
（2）设路)},({,),,({),,({1
2
1
1
201r
r i i r i i i v v e v v e v v e R -???=已选出，则从E\}
,,,{21r e e e ???中选出边1+r e ，使1+r e 与r
i v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的．
（3）重复步骤（2），直至不能进行下去为止．
定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数
（进数）与离开该点的边数（出数）相等．
三、中国邮递员问题
一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．
用图论的述语，在一个连通的赋权图G （V ，E ）中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小．也就是说要从包含G 的每条边的回路中找一条权数最小的回路．
如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．
首先注意到，若图G 有奇数度节点，则G 的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G 中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E '．令G / =G+E /，即把附加边子集E / 叠加在原图G 上形成一个多重图G /，这时G /中连接两个节点之间的边不止一条．显然G /是一个欧拉图，因而可以求出G /的欧拉回路．该欧拉回路不仅通过原图G 中每条边，同时还通过E / 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E / 的权数ω(E / )为最小？为此有下列定理．
定理 3 设G （V ，E ）为一个连通的赋权图，则使附加边子集E / 的权数ω(E / )为最小的充分必要条件是G+E / 中任意边至多重复一次，且G+E / 中的任意回路中重复边的权数之和不大于该回路总权数的一半．
证明： 必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集E / 权数 ω(E / )为最小．若 G+E / 中有一条边重复n n ()≥2次，由于G+E /为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与 ω(E /)为最小的假设矛盾．这说明E /中的边均互不相同．
其次，若G+E / 中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在E / 中删去这些重复边（注意：这些边均在E /中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集E //仍为附加子集，且ω(E //)<ω(E /)，又产生矛盾． 充分性．设有两个附加边子集E /和E //，均使G+E /和G+E //中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明ω(E /)=ω(E //)．首先注意到，由E /和E //不相同的部分组成的图（记为]\[//
///
/
）（E E E
E G ）是由一个或若干个
欧拉子图所组成的．这是因为E /＋E //中每个节点的度数均为偶数，而E /和E //的公共边数也是偶数，故]\[//
///
/
）（E E E
E G 中每个节点的度数仍为偶数，所以它若为连通图时是
一个欧拉图；若为非连通图时则由若干个欧拉子图组成．
]\[/////
/）（E E E
E G 的任何回路都由E /和E //中的边组成，而E /和E //
在回路中的权
数分别不大于该回路权数的一半，因而任何回路中属于E /中的权数之和与属于E //中的边数之和必定相等，所以ω(E /)=ω(E //)．它就是最优附加边子集的权数，即E /和E //均为使附加边子集的权数达到最小的最优附加边子集．
由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：
例1 已知邮递员要投递的街道如图11-20所示，试求
最优邮路．
解 先找出奇节点：A 1，A 2，A 3，A 4，B 1，B 2，
B 3，B 4．奇节点进行配对，不妨把A 1与B 1，A 2与B 2，A 3与B 3，A 4与B 4配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．
第一次调整：删去多于一条的重复边，即A 3与B 3，A 4与B 4中的（A 4，B 3）．调整后，实际上成为A 1与B 1，A 2与B 2，A 3与A 4，B 3与B 4的配对，它们的最短路如图11-21所示． 第二次调整：发现在回路{A 1，A 2，B 2，A 4，B 3，B 4，B 1，A 1}中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图11-22．可以看出，实际上是调整为A 1与A 2，B 1与B 4，A 3与A 4，B 2与B 3配对．
第三次调整：在图11-22中发现回路{ A 3，A 4，B 2，A 3}中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（A 3，V 2，A 4）和（A 4，B 2），而添加（B 2，A 3），得到图11-23．进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图11-23就是最优的附加边子集E /，而G+E /为欧拉图，可由弗罗莱算法找出最优邮路．
在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”．因为此方法要验证每个回路，很不方便，Edmods 和Johnson 在1973年提出一种比较有效的方
法，有兴趣的读者可参考有关资料．
习 题 11-3
1．证明，若图G 为欧拉图，则G 的边数不少于节点数．
2．一名邮递员的投邮区，如下图11-24所示，每条边（街道）都有邮件需投递，各边旁所注的数字为该街道的长度，试求该邮区的最短投递路径及其长度． 3．求下列图11-25（a ）(b)所示的投邮区的最佳邮路及其长度．
【算法】欧拉图，欧拉回路，Eular Circuit ，随机生成欧拉图，搜索欧拉回路
背景：图论起源于18世纪，1736年瑞士数学家欧拉（Eular ）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图(1)。当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。
为了解决这个问题，欧拉用ABCD四个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，如图(2)，于是哥尼斯堡七桥问题就变成了图(2)中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。
1 定义
欧拉通路(欧拉迹)——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路(欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路。
欧拉图——存在欧拉回路的图。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。
3 有向图是否具有欧拉通路或回路的判定
D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。
欧拉通路、欧拉回路、欧拉图、半欧拉图的定义
定义15.1通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。
从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。
在这里做个规定，即平凡图是欧拉图。
图15.1
在图15.1所示各图中，e1e2e3e4e5为（1）中的欧拉回路，所以（1）图为欧拉图。e1e2e3e4e5为（2）中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以（2）为半欧拉图。（3）中既没有欧拉回路，也没有欧拉通路（为什么？），所以（3）不是欧拉图，也不是半欧拉图。e1e2e3e4为（4）图中的欧拉回路，所以（4）图为欧拉图。（5），（6）图中都既没有欧拉回路，也没有欧拉通路
欧拉回路
const maxn=100;
var
g:array[1..maxn,1..maxn] of longint;
du:array[1..maxn] of longint;
circuit:array[1..maxn] of longint;
n,circuitpos,i,j,start,oddnumber:longint;
procedure setIO;
begin
assign(input,'one.in');
reset(input);
assign(output,'one.out');
rewrite(output);
end;
procedure find_circuit(i:longint);
var j:longint;
begin
for j:=1 to n do
if g[i,j]=1 then
begin
g[i,j]:=0;
g[j,i]:=0;
find_circuit(j);
end;
circuitpos:=circuitpos+1;
circuit[circuitpos]:=i;
end;
begin
// setIO;
read(n);
for i:=1 to n do
begin
du[i]:=0;
for j:=1 to n do
begin
read(g[i,j]);
du[i]:=du[i]+g[i,j];
end;
end;
start:=1; oddnumber:=0;
for i:=1 to n do
if du[i] mod 2 =1 then
begin
start:=i;
oddnumber:=oddnumber+1;
end;
if (oddnumber>2)or(oddnumber=1)
then writeln('No Solution!')
else begin
circuitpos:=0;
find_circuit(start);
for i:=1 to circuitpos-1 do write(circuit[i],'--->');
writeln(circuit[circuitpos]);
end;
close(input);close(output);
end.
SPFA
实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
program spfaprg;
const
maxp=10000; {最大结点数}
var {变量定义}
p,c,s,t:longint; {p,结点数;c,边数;s:起点;t:终点}
a,b:array[1..maxp,0..maxp] of longint; {a[x,y]存x,y之间边的权;b[x,c]存与x相连的第c 个边的另一个结点y}
d:array[1..maxp] of integer; {队列}
v:array[1..maxp] of boolean; {是否入队的标记}
dist:array[1..maxp] of longint; {到起点的最短路}
head,tail:longint; {队首/队尾指针}
procedure init;
var
i,x,y,z:longint;
begin
read(p,c);
for i := 1 to c do
begin
readln(x,y,z); {x,y:一条边的两个结点;z:这条边的权值}
inc(b[x,0]); b[x,b[x,0]] := y; a[x,y] := z; {b[x,0]：以x为一个结点的边的条数}
inc(b[y,0]); b[y,b[y,0]] := x; a[y,x] := z;
end;
readln(s,t); {读入起点与终点}
end;
procedure spfa(s:longint); ｛SPFA｝
var i,,j,now,sum:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(v,sizeof(v),false);
for j := 1 to p do
dist[ j ]:=maxlongint;
dist[s] := 0; v[s] := true; d[1] := s; {队列的初始状态,s为起点}
head := 1; tail := 1;
while head<=tail do {队列不空}
begin
now := d[head]; {取队首元素}
for i := 1 to b[now,0] do
if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
begin
dist[b[now,i]]:= dist[now]+a[now,b[now,i]]; {修改最短路}
if not v[b[now,i]] then {扩展结点入队}
begin
inc(tail);
d[tail] := b[now,i];
v[b[now,i]] := true;
end;
end;
v[now] := false; {释放结点}
inc(head); {出队}
end;
end;
procedure print;
begin
writeln(dist[t]);
end;
begin
init;
spfa(s);
print;
end.
算法分块总结 为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。 图论模型的应用 分层图思想的应用： 用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。 层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。 这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。 二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用： 最大网络流算法的应用：典型应用就求图的最小割。 最小费用最大流的应用： 容量有上下界的最大流的应用： 欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。 最小生成树： 求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。 最小K度限制生成树： 抽象成数学模型就是： 设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。 首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k 电气及自动化课程设计报告 题目：基于PLC的六路抢答器系统设计 课程：PLC原理与应用 学生姓名： 学生学号： 年级：14级 专业：自动化 班级：2班 指导教师： 机械与电气工程学院制 2017年6月 目录 1课程设计的任务和要求 (1) 1.1课程设计的任务 (1) 1.2课程设计的要求 (1) 2.PLC控制器的原理与组成 (1) 2.1PLC硬件系统 (1) 2.2PLC工作原理 (3) 2.3六人抢答器基本组成 (4) 2.4六人抢答器工作原理 (4) 3六人抢答器系统设计方案制定 (5) 3.1PLC选型 (5) 3.2六人抢答器系统的I/O口分配 (6) 4六人抢答器系统的软件设计 (7) 4.1PLC编程语言 (7) 4.2抢答器系统程序 (7) 4.2.1主持人控制端 (7) 4.2.2抢答成功与抢答犯规指示灯显示 (9) 4.2.3七段数码管显示 (9) 4.2.4蜂鸣器电路 (11) 5六人抢答器系统程序仿真 (12) 5.1抢答成功仿真 (12) 5.2抢答犯规及抢答超时仿真 (12) 5.3加减分及数码管显示 (13) 5.4抢答超时 (14) 6总结及心得体会 (14) 参考文献 (15) 基于PLC的六路抢答器系统设计 机械与电气工程学院自动化专业 1课程设计的任务和要求 1.1课程设计的任务 使用西门子S7-200PLC编写程序实现六路抢答器的系统设计并使用仿真软件进行其功能的实现。 1.2课程设计的要求 （1）主持人控制功能，具有开始抢答按钮和复位按钮； （2）主持人未按下开始抢答按钮时抢答为违规抢答，违规指示灯亮，蜂鸣器响； （3）抢答延时，超过20S无人抢答时此题作废，蜂鸣器长鸣； （4）抢答成功后，抢答成功指示灯亮，数码管显示抢答成功的队伍编号； （5）在抢答成功后，主持人根据回答的正确与否可以对该队伍进行加减分控制； （6）每次正确抢答时，只有第一位按下抢答按钮的队伍为有效抢答。 2.PLC控制器的原理与组成 2.1PLC硬件系统 可编程控制器，英文称ProgrammableLogicController，简称PLC。PLC是基于电子计算机，且适用于工业现场工作的电控制器。它源于继电控制装置，但它不像继电装置那样，通过电路的物理过程实现控制，而主要靠运行存储于PLC内存中的程序，进行入出信息变换实现控制。PLC基于电子计算机，但并不等同于普通计算机。普遍计算机进行入出信息变换，多只考虑信息本身，信息的入出，只要人机界面好就可以了。而PLC则还要考虑信息入出的可靠性、实时性，以及信息的使用等问题。特别要考虑怎么适应于工业环境，如便于安装，抗干扰等问题[1]。 图论部分 第八章、一些特殊的图 8.1 二部图 二部图：定义设无向图G= 设M为G中一个匹配 v i与v j被M匹配: (v i,v j)∈M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 定理(Hall定理) 设二部图G= Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为t 条件. 满足t 条件的二部图一定满足相异性条件. 8.2 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性. 四 路 抢 答 器 设 计 实 验 报 告 信息科学技术学院自动化*班 **** 四路抢答器设计实验报告 一、设计任务： 1、巩固和加深对电子电路基本知识的理解，提高综合运用本课程所学知识的能 力。 2、养成根据设计需要选学参考书籍，查阅相关手册、图表和文献资料的自学能力。 3、通过电路方案的分析、论证和比较，设计计算和选取元器件、电路组装、 调试和检测等环节，初步掌握简单实用电路的分析方法和工程设计方法。 4、学会简单电路的实验调试和性能指标的测试方法，提高学生动手能力和进行 数字电子电路实验的基本技能。 二、技术指标 抢答器是一种具有优先输出的电子电路。它的基本功能是，在四组参赛的情况下，首先抢答者发出抢答信号，此时其他参赛组的抢答电路即失去控制作用。在优先抢答者解除抢答信号后，电路才自动恢复到各组又可均等抢答的状态中。 1、设计一个可供4人进行的抢答器。 2、系统设置复位按钮，按动后，重新开始抢答。 3、抢答器开始时数码管无显示，选手抢答实行优先锁存，优先抢答选手的编号一直保持到主持人将系统清除为止。抢答后显示优先抢答者序号，同时发出音响。并且不出现其他抢答者的序号，这样其它选手无法再抢答，达到抢答目的。 4、抢答器具有定时抢答功能，本抢答器的时间设定为10秒，当主持人启动“开始”开关后，定时器开始减计。 5、设定的抢答时间，选手可以抢答，这时定时器开始工作，显示器上显示选手 的和抢答时间。并保持到主持人按复位键。 6、当设定的时间一到，而无人抢答时，本题报废，选手们无法再抢答，同时扬 声器报警发出声音，定时器上显示0。 三、元件清单： 图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量（SCC划分） 3.2求传递闭包 4.最小环问题 一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色， 白色：未访问； 灰色：访问中（正在访问它的后代）； 黑色：访问完毕 一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v] 课程设计说明书 毕业设计（论文）原创性声明和使用授权说明 学位论文原创性声明 课程名称：电子技术课程设计课题题目：六人抢答器 专业班级：通信工程 姓名： 学号： 指导教师： 目录 1 功能介绍 (2) 1.1主要功能介绍 (2) 1.2扩展功能介绍 (2) 2总体方案设计 (3) 3单元模块设计 (4) 3.1抢答器控制端电路功能介绍 (4) 3.2定时时间电路 (6) 3.3控制电路 (7) 3.4报警电路 (7) 4主要芯片介绍 (8) 4.1 优先编码器74LS148 (8) 4.2 计数器74LS192 (10) 5六人抢答器仿真 (11) 6系统调试 (15) 7电路原理图 (16) 8元件清单 (17) 9参考文献 (17) 课题题目：六人抢答器 1功能介绍 1.1主要功能介绍 1）有多路抢答，抢答台数为6； 2）具有抢答开始后20秒倒计时，20秒倒计时后无人抢答显示超时，并报警： 3）能显示超前抢答台号并显示犯规报警： 2、系统复位后进入抢答状态，当有一路抢答按键按下，该路抢答信号将其余各路抢答信号封锁，同时铃声想起，直至该路按键松开，显示牌显示该路抢答台号。 1.2扩展功能介绍 （1）抢答器具有定时抢答的功能，且一次抢答的时间为20秒。当节目主持人启动“开始”键后，要求定时器立即减计时，并用 显示器显示。 （2）参加选手在未开始抢答时按下抢答键，则犯规。显示器上显示选手的编号,并报警。 （3）参加选手在设定的时间内抢答，抢答有效，定时器停止工作，显示器上显示选手的编号和抢答时刻的时间，并保持到主持人将系统清零为止。 （4）如果定时抢答的时间已到，却没有选手抢答时，本次抢答无效，封锁输入电路，禁止选手超时后抢答。 2总体方案设计 设计要求 图论学习报告 报告内容: 一．基本概念： 1.叙述图：所谓图G是一个三元组，记做G= 学号：xxxxxxxxxx 课程设计报告 基于AT89C51单片机抢答器的设计 院系电子信息工程学院 专业电子信息工程 班级 1 姓名xxx 摘要 单片机由于其微小的体积和极低的成本，广泛的应用于家用电器、工业控制等领域中。在工业生产中，单片微型计算机是微型计算机的一个重要分支，也是颇具生产力的机种。单片微型计算机简称单片机，特别适用于控制领域，故又称微控器。学校和电视台等单位场举办各种比赛，抢答器是必要设备。在我校举行的各种竞赛中我们经常看到有抢答的环节，举办方多数采用让选手通过举答题板的方法判断选手的答题权，这在某种程度上会因为主持人的主观判断造成比赛的不公平性。抢答器是一名公正的裁判员，他由主体电路与扩展电路组成。单片机由于其微小的体积和极低的成本，广泛的应用于家用电器、工业控制等领域中。在工业生产中，单片微型计算机是微型计算机的一个重要分支，也是颇具生产力的机种。单片微型计算机简称单片机，特别适用于控制领域，故又称微控器。学校和电视台等单位场举办各种比赛，抢答器是必要设备。在我校举行的各种竞赛中我们经常看到有抢答的环节，举办方多数采用让选手通过举答题板的方法判断选手的答题权，这在某种程度上会因为主持人的主观判断造成比赛的不公平性。抢答器是一名公正的裁判员，他由主体电路与扩展电路组成。 AT89C51是一种带4K字节FLASH存储器（FPEROM—Flash Programmable and Erasable Read Only Memory）的低电压、高性能CMOS 8位微处理器，俗称单片机。AT89C2051是一种带2K字节闪存可编程可擦除只读存储器的单片机。单片机的可擦除只读存储器可以反复擦除1000次。该器件采用ATMEL高密度非易失存储器制造技术制造，与工业标准的MCS-51指令集和输出管脚相兼容。由于将多功能8位CPU和闪速存储器组合在单个芯片中，ATMEL的AT89C51是一种高效微控制器，AT89C2051是它的一种精简版本。AT89C51单片机为很多嵌入式控制系统提供了一种灵活性高且价廉的方案。外形及引脚排列如图所示。 本设计是六路智力抢答器。使用51系列单片机，编写应用程序来实现智力抢答功能。硬件设计使用的是51系列单片机中的89C51。硬件设计利用其中断控制程序进行抢答部分的处理，通过非门的控制去申请单片机内部的中断，以达到显示抢答的目的。软件设计利用中断系统的基本构成原理编写中断服务程序，其信号由按键电路提供，由CPU响应中断，并输出响应。用到了查询按键模块、定时器模块、显示时间模块、显示组号模块、报警模块等。 关键词：89C51 中断定时器报警电路等 算法总结 一、动态规划和递推 dp一般的解题步骤： 分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化 由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧 Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解 关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。 二、图论及网络流 最小生成树：克鲁斯卡尔算法和普利姆算法， ——重要性质1：最小生成树上任意两点的路径的最大边最小 ——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数） 最短路：spfa算法、堆+迪杰斯特拉算法 Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 ——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环 堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的 拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环 ——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列 ——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可 强连通分量、缩点：tarjan算法 核心是每个点记一个时间戳ti[i], 另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。 六路数字抢答器设计报告 目录 一、任务设计和要求 (2) 二、设计方案与论证 (4) 三、电路设计计算与分析 (5) 3.1 主持人控制电路 (5) 3.2 10S倒计时电路 (7) 3.3 控制显示电路 (10) 3.4 主要元器件介绍 (12) 四、总结与心得 (18) 五、附录 (19) 附录一：元器件清单 (19) 附录二：六路抢答器原理图 (20) 附录三：六路抢答器的仿真 (21) 六、参考文献 (22) 1 一、设计任务和要求 六路数字抢答器的设计任务如下： 1．主持人按动启动按钮，抢答开始，同时开始10秒倒计时。 2．6名抢答选手编号分别为1-6，各自控制一个按钮进行抢答，有人按下时扬声器给出声音提示，倒计时电路停止计时，同时显示抢答选手的号码。 3．选用七段LED作为显示器。 4.完成电路的理论设计。 5.参数的计算和有关器件的选择。 6. 对电路进行仿真。 7.撰写设计报告书一份：A3图纸1张。报告书要求写明以下内容：（B5纸） （1）总体方案的选择和设计 （2）各个单元电路的选择和设计 （3）仿真过程的实现 课程设计要求如下： 课程设计大体可分成以下三个阶段： 1.设计与计算阶段 学生根据课程设计任务、要求和条件进行总体方案的设计，通过论证和选择，确定总体方案。此后是对方案中单元电路 2 进行选择和设计计算，包括元器件的选用和电路参数的计算。最后画出总体电路图，选用元件一览表。 2.计算机仿真及电路制版 运用仿真软件EWB或MULTISIM对设计电路进行仿真，排除电路故障、调整元器件参数、修改电路，使之达到设计指标要求。最后使用PROTEL软件完成对电路的PCB制版（选作）。 3.撰写设计报告阶段 设计报告是学生对课程设计全过程的系统总结。学生应按规定的格式撰写设计报告。设计报告的主要内容有： 1)课题名称。 2)设计任务和要求。 3)方案选择与论证。 4)原理框图，总体电路图、计算机电路仿真图，以及它们的说明；单元电路设计与计算说明；元器件选择和电路参数计算的说明等。 5)收获体会、存在问题和进一步的改进意见等。 3 1、问题背景 (2) 2 问题的发展与解决 (3) 3 问题的延伸与一笔画定理 (4) 4欧拉图 (4) 4.1欧拉图: (4) 4.2如何判断欧拉图： (5) 4.3求欧拉回路的算法: (6) 5图论 (7) 5.1图的基本概念(Graph) (7) 5.2有向图 (8) 5.3Dijkstra算法（两个点之间的最短路） (8) 分析：要讨论学校的设定点，使得所走的总路程最少，这样就要求学校所在地距离各居民点的总路程最小，所以首先要考虑学校到各居民点的最短路。 (9) 这里以V1为起点，计算最短路。 (9) 6数学文化的收获 (11) 7趣味数学题 (12) 数学文化报告 题目哥尼斯堡七桥 专业信息与计算科学 班级2013070202 姓名李亚梦 学号201307020229 指导教师张萍 二〇一四年十一月二十七日 目录 1、问题背景 (2) 2 问题的发展与解决 (3) 3 问题的延伸与一笔画定理 (4) 4欧拉图 (4) 4.1欧拉图: (4) 4.2如何判断欧拉图： (5) 4.3求欧拉回路的算法: (6) 5图论 (7) 5.1图的基本概念(Graph) (7) 5.2有向图 (8) 5.3Dijkstra算法（两个点之间的最短路） (8) 分析：要讨论学校的设定点，使得所走的总路程最少，这样就要求学校所在地距离各居民点的总路程最小，所以首先要考虑学校到各居民点的最短路。 (9) 这里以V1为起点，计算最短路。 (9) 6数学文化的收获 (11) 7趣味数学题 (12) 1、问题背景 现今的加里宁格勒，旧称哥尼斯堡，是一座历史名城。在十八、十九世纪，那里是东普鲁士的首府，曾经诞生和培育过许多伟大的人物。著名的哲学家，古典唯心主义的创始人康德，终生没有离开过哥尼斯堡一步!二十世纪最伟大的数学家之一，德国的希尔伯特也出生于此地。哥城景致迷人，碧波荡漾的普累格河，横贯其境。在河的中心有一座美丽的小岛。普河的两条支流，环绕其旁汇成大河，把全城分为下图所示的四个区域：岛区(A)，东区(B)，南区(C)和北区(D)。著名的哥尼斯堡大学，傍倚于两条支流的河旁，使这一秀色怡人的区域，又增添了几分庄重的韵味!有七座桥横跨普累格河及其支流，其中五座把河岸和河心岛连接起来。这一别致的桥群，古往今来，吸引了众多的游人来此散步。早在十八世纪以前，当地的居民便热衷于以下有趣的问题：能不能设计一次散步，使得七座桥中的每一座都走过一次，而且只走过一次? 这便是著名的哥尼斯堡七桥问题。 湖南大学课程设计报告 课程名称：电子技术课程设计 系部：电气工程系 专业班级：电子科学技术 学生姓名： 指导教师： 完成时间： 2011.06.19 报告成绩： 目录 摘要 3 第一章、设计题目 4 第二章、设计目的 4 第三章、设计要求 4 3.1设计指标 4 3.2设计要求 4 第四章、设计方案与论证 5 第五章、系统具体电路设计及原理 5 5.1抢答器电路的设计 5 5.2定时电路的设计 5 5.3报警电路的设计 (6) 5.4时序控制电路的设计 (6) 第六章、主要元器件介绍 (7) 6.1 74LS48 和74LS192的功能表 (8) 6.2 74LS148 (9) 6.3 74LS279 (10) 6.4 74LS121 (11) 6.5NE555 (11) 第七章、设计采用元件 (13) 第八章、电路设计仿真 (13) 第九章、实验心得 (15) 第十章、参考文献 (16) 摘要 本设计的抢答器是一种比较简易的抢答器，没有使用特别多的复杂的元器件。结合上机动手实验而完成的。它的特点是电路简单、制作方便、操作简单、方便、性能可靠，实用于多种智力竞赛活动。本抢答器的电路主要完成：设计一个六路抢答器，实现开始一定时间后，开始抢答状态，可以判定是哪个信号抢答的，同时封锁其他信号，如果过了抢答时间，仍然没有抢答或者出现抢答者同时抢答时，那么就报警。这个抢答器设计基本上满足了实际竞赛应用中的各种需要。在实际中有很大的用途。 无论是在学校、工厂、军队还是益智性电视节目，都会举办各种各样的智力竞赛，都会用到抢答器。目前市场上已有各种各样的智力竞赛抢答器，绝大多数是以模拟电路、数字电路或者模拟电路与数字电路相结合的产品。这部分抢答器已相当成熟，但功能越多的电路相对来说就越复杂，且成本偏高，故障高，显示方式简单。 数字抢答器由主体电路与扩张电路组成.优先编码电路,锁存器,译码电路将参赛队的输入信号在显示器上输出:用控制电路和主持人的开关启动报警电路,以上两部分组成主体电路.通过定时电路和译码电路将秒脉冲产生的信号在显示器上输出实现计时功能,构成扩展电路.经过布线,焊接,调试等工作后数字抢答器成型. 抢答器四周有安装孔,可以方便的安装在操作台上,外接抢答按钮接入相应的接线端子,如果需要外接电铃或指示灯,则接入继电器端子,安装完毕后就可以上电了,抢答器的电流输入为5V直流输入. 抢答器通上电后,蜂鸣器响,三个数码管都显示0,按下复位按钮后进入正常工作状态,这时可以设定抢答倒计时间,只要按动10进制编码按钮分别对时间的十位和个位设定,设定的时间在数码管上实时的显示出来.设定的时间范围为:0~30秒,设定完时间后,就可以按动开始按钮,表示抢答开始,这时蜂鸣器响0.1秒,提示各位选手,抢答已经开始,同时倒计时器开始从设定的时间进行倒计时. 若在抢答时间内有人抢答,则第三个数码管立即显示抢答位号,倒计时间停止倒计时,所用掉的时间就是抢答的时间,同时蜂鸣器响2秒,继电器吸合2秒,表示有人抢答,在这个按键之后按下的按键除了复位键外,其他按键均无效,只有主持人按下复位键后,可以进入下一轮抢答. 合肥学院 计算机科学与技术系 课程设计报告 2012 ～2013 学年第二学期 课程数据结构与算法 课程设计名称欧拉回路 学生姓名 学号 专业班级计算机科学与技术系11级4班 指导教师 2013 年3月 欧拉回路课程设计 一、课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一，是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用软件解决问题，培养良好的程序设计技能。 二、课程设计名称及内容 名称：欧拉回路 内容：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ 要求：输入：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。三、 三、算法分析 1.1、假设条件 连通图采用邻接表存储，，并且输入顶点信息。 输入的数据为无向图的顶点数和边数，顶点数为大于0小于1000的整数，边数为非负的整数，还有邻接表中结点的值（起点和终点），都为非负整数。 输入的无向图，可为连通也可不连通，也可输入单个顶点的图，程序会进行判断。 1.2、算法描述 1.2.1、无向图的存储结构和连通图的判定 采用邻接表存储无向图，利用graph表示邻接表用来存储无向图，输入结点数M和边数N，还有邻接表的值（起点和终点），即边的信息。 图的连通性的判断，用到图的深度优先搜索，采用深度优先搜索来遍历无向图中的点的信息，从图中某个顶点出发首先访问该顶点，然后任选一个该点未访问的邻接点出发，直到访问完成。计算出深度优先搜索到点的数目，然后与结点数进行比较，如果遍历到的数目小于结点数，则为非连通图，否则，为连通图。 1.22、无向图结点度的求法 在无向图建立时求图结点的度，当输入结点信息时用数组d[i]来存储各节点的度然后判断度得奇偶性for(i=1;i<=M;i++)//结点度的判断 { if(d[i]%2!=0)y++; } 1.23、欧拉回路的判断 判断欧拉回路时根据欧拉定理进行判断，首先要判断是否为连通图，不是连通图就不进行后面的判断。如果时连通图且图中M个顶点的度都为偶数则存在欧拉回路，因此，欧拉图一笔画的判定与求解就是对输入的无向连通图是度的判定。当连通图中所有顶点的度都为偶数时，连通图就存在欧拉回路。 利用深度优先遍历的基本操作来实现的欧拉算法求解欧拉回路。算法就是深度优先遍历连通图，然后求出连通图中各结点的度。 四、系统设计 1.1设计说明 该程序设计共包括四大模块：主函数模块，邻接表建立模块，连通图判定模块，欧拉回 多路数字式竞赛抢答器的设计与制作 课程设计报告 学院：自动化工程学院 班级：测控081 设计人：郭秋艳 学号：0807250103 指导老师：关硕黄俊峰张玉财 时间：2010年7月14日 目录 一．设计任务与技术要求 (3) 二．方案的论证及电路的工作原理 (3) 1.方案论证.................................................................... (3) 2. 工作原理 (4) 三：单元电路的设计及电路图 (4) 1.抢答器电路 (4) 2.定时电路 (6) 3报警电路 (7) 4. 时序控制电路 (7) 5计分电路 (8) 四．元器件的选择 (9) 1.74LS148 (9) 2，74LS279/R-S 锁存器.............................................................. . (10) 3. 74LS192 (11) 4.74LS48 (12) 5. 555定时器 (13) 6.74ls121 (14) 五，需要的元器件清单 (15) 六．心得体会 (16) 七．参考文献 (16) 一：设计任务与技术要求 1、设计任务 设计制作一个可供6组选手参加比赛的数字式竞赛抢答器。 2、技术要求 (1)抢答器同时供6组选手，分别用6个按钮S0—S5表示。 (2)设置一个系统清零（抢答显示数码管灭灯）和抢答控制开关S，该开关由主持人控制。 (3)抢答器具有第一个抢答信号的鉴别和数据锁存，显示的功能。抢答开始后，若选手按动抢答按钮，锁存相应编号，并在LED数码管上显示该编号，同时扬声器给出声响提示，封锁输入编码电路，禁止其他选手抢答。抢答选手的编号一直保持到主持人将系统清零为止。 (4)抢答器具有计分，显示的功能。预置分数可由主持人设定，并显示在每名选手的计分牌上，选手答对加10分，答错扣10分。 (5)抢答器具有定时抢答的功能，抢答时间由主持人设定。当主持人按下开始按钮后，定时器开始减计时，同时扬声器发出短暂的声响，声响持续时间0.5S 左右。 (6) 参赛选手在设定时间内抢答有效，抢答有效，定时器停止倒计时，抢答显示器上显示选手的编号，定时显示器上显示剩余抢答时间，并保持到主持人将系统清零为止。 (7) 如果抢答定时已到，却没有选手抢答时，本次抢答无效。系统扬声器报警并封锁输入编码电路，禁止选手超时后抢答，时间显示器显示“00”。 (8)抢答器具有犯规提示的功能，对提前抢答和超时抢答的选手，扬声器会发出警示信号，并在显示器上显示其编号。 二：方案的论证及电路的工作原理 1.方案论证 方案1：采用CD4511芯片作为抢答信号的触发、锁存和译码输出。这样虽然比较简便，但实际在实现锁存功能时比较繁琐难实现。 方案2：采用D触发器和译码器来完成抢答部分。虽然元件较多，但在实现锁存功能时可以简单的实现。 经过对比两方案的优缺点，决定采用抢答信号锁存简单实现的方案2。然后利用软件来进行仿真调试，再进行逐步改进。 2.工作原理 抢答器由输入电路，判别电路，显示电路，秒脉冲发生器，计时电路和报 填空题 1.算法描述方法：自然语言，流程图，程序设计语言，伪代码 2.算法的5个特性：输入，输出，确定性，有穷性，可行性 3.对程序设计的研究可以分为4个层次：算法、方法学、语言和工具。 4.算法研究的核心问题：时间问题 5.电商中，信息安全是最关键的问题，保证信息安全的一个方法：对需要保密的数据进行加密。 6.算法的有穷性意味着不是所有的计算机程序都是算法。 7.影响算法时间代价的最主要因素是问题规模；运行算法所需要的时间T是问题规模n的函数，记作T（n）。 8.反映算法的运行时间：用算法中基本语句的执行次数来度量算法的工作量。 9.基本语句：是执行次数与整个算法的执行次数成正比的语句，基本语句对算法运行时间的贡献最大，是算法中最重要的操作。 10渐进符号：大O、大八爪鱼、本田 大O：用来描述增长率的上限。当输入规模为n时，算法消耗时间的最大值，这个上限的阶越低，结果就越有价值。T（n）<=c*f（n）；O（n2）以n2为上限 大八爪鱼：用来描述增长率的下限，这个下限的阶越高，结果就越有价值。T（n）>=c*g（n）；大爪鱼（n2）以n2为下限。 本田：以为着T（n）与f（n）同阶，用来表示算法的精确阶；C1*f（n）>=T（n）>=C2*f（n），则T （n）=本田（f（n））； 11.最好最坏和平均情况：当最好情况出现的概率较大的时候，应分析最好情况；分析最差情况的一个好处：在实时系统尤其重要。 12.非递归算法时间复杂性的分析：关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 找算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体；用大O 13.递归算法的分析：是一种分而治之的方法；3种技术：猜测技术、拓展递归技术、通用分治递推式。 14.下界：能找到一个尽可能大的函数g（n），使得求解该问题的所有算法都可以在八爪鱼（g（n））的时间内完成，则函数g（n）称为该问题计算复杂性的下界。如果已知一个和下界的效率类型相同的算法，则称该下界是紧密的。 平凡下界：对算法读取所有要处理的元素并对所有的输出进行计数，这种计数方法所产生的是平凡下界；往往过小而失去意义，如TSP问题，因为它还没有找到一个多项式时间算法。 判定树模型：是以棵二叉树；成立，控制转移到该节点的左子树，否则右子树，每一个叶子节点表示问题的一个结果；通常忽略算数运算，只考虑分支执行时的转移次数，最坏情况下的时间复杂性不超树高。 最优算法：优于该问题的所有算法；两个算法最优则比较高阶项系数，系数较小的算法，时间性能优 15.易解问题：存在多项式时间算法的问题（排序问题、查找问题、欧拉回路）， 16.难解问题：需要指数时间算法解决的问题 17.把多项式时间复杂性作为易解问题和难解问题的分界线的原因：1)多项式函数与指数函数的增长率有本质的差别，具有多项式时间复杂性的算法是可使用的算法，而具有指数时间复杂性的算法，只有当问题规模足够小时才是可使用的算法。2)计算机性能的提高对多项式时间算法和指数时间算法的影响不同；3）多项式时间复杂性忽略系数，但不影响易和难的问题划分；4）多项式时间复杂性的闭包性、独立性 18.不可解问题：停机问题、计算机病毒检测 19.判定问题：仅仅要求回答yes或no的问题。例如停机问题就是一个判定问题，但是不能用任何计算机算法求解，所以，并不是所有的判定问题都可以在计算机上得到求解；还有个重要特性：虽然在计算上对问题求解是困难的，但在计算上判定一个待定解是否解决了该问题却是简单的，如哈密顿回路，是个难解问题，但是验证却很容易。 EDA技术实验4路抢答器课程设计报告 系部：自动化系 专业：电气工程及自动化 班级： 姓名： 一、设计要求 利用基本逻辑门电路、组合逻辑电路和触发器，设计一个四人抢答器。要求： （1）四个参加者编号为A、B、C、D，对应组号为1-4，每个参加者控制一个按键，用其发出抢答信号； （2）主持人有一个控制按键，用于将系统清零，即数码显示管灯灭，并控制抢答开始； （3）参加者按抢答按钮，蜂鸣器响铃，对应的指示灯亮，同时数码管上显示最先抢答者的组号； （4）电路具有互锁功能，有人优先抢答后系统能自动关闭其他路的输入信号。 二、设计过程 1、分析要求，规划实现模块。 2、设计框图 3、选用器件 这里采用了COMS器件4072BD、4069BD，4072BD为四输入或门电路，4069BD为反向器。 还采用了74LSXXX系列芯片,其中74LS1750为六D触发器集成电路，74LS32为二输入或门 设计电路原理图中J1-J4为抢答按钮，J5为复位按钮。 数码显示抢答器，由触发器、编译码电路、数码管、LED指示灯和蜂鸣器等组成，数码管用于显示抢答者的组号，LED灯用于显示对应抢答者的指示灯，蜂鸣器用于响铃。 响铃的时间由LM555触发器控制（下图为LM555的模块电路图） 定时器的电路原理图 三、整体电路图 电路原理图 当第三个人抢答时的电路状态 四、心得体会 本次实验做的是四路抢答器，根据设计的要求，将要涉及到电路、以及数字电路的知识。为了完成实验，我 重新温习了电路、以及数字电路的知识，并且通过在电 脑上的仿真，对这些知识有了更加深刻的认识。本次设 计是通过分模块的设计方法，把整个电路分为抢答电 路、定时电路、显示电路等几个模块，我分别从这几个 模块进行分块设计，步步为营，最终完成了实验的设计。 当然，在实验中，我也遇到了不少的困难，刚开始时， 学习报告 报告题目：图论的前世今生 报告要求涵盖以下内容： 1.图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”（如下图）。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 2.图论的发展 图论是数学领域中发展最快的分支之一，它以图为研究对象。图论中的图是有若干给定的点及连接两点的线所构成的图形，这种图形常用来描述某些事物之间的某种特定关系，用来代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立的建立过。关于图论的文字记载最早出现在欧拉1736年的论文中，他所考虑的原始问题有很强的实际背景。 数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的!这是拓扑学研究的先声。图的染色问题一直是图论研究的焦点问题。数学家赫伍德成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。美国伊利诺斯大学的黑肯和阿佩尔，经过四年的艰苦工作．终于完成了四色猜想的证明。正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。 四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯?格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图基于PLC的六路抢答器系统设计
离散数学第八章一些特殊的图知识点总结
四路抢答器课程设计报告
图的连通性总结
基于PLC的六路抢答器系统设计课程设计
题目: 基于 PLC 的六路抢答器系统设计
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教
师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加
以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研
究成果，也不包含我为获得
及其它教育机构的学位或学历
而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，
均已在文中作了明确的说明并表示了谢意。
作 者 签 名：
日 期：
指导教师签名：
日 期：
使用授权说明
本人完全了解
大学关于收集、保存、使用毕业设计（论
文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电
子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供
目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制
手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分
或全部内容。
作者签名：
日 期：
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。
作者签名：
日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，
同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，
允许论文被查阅和借阅。本人授权
大学可以将本学位
论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩
印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名： 导师签名：
日期： 年 月 日 日期： 年 月 日六人抢答器课程设计报告
图论学习报告
基于某AT89C51单片机六路抢答器的设计
noip算法总结2016
六路抢答器设计报告
数学文化报告
六路抢答器课程设计
欧拉回路设计报告
6路抢答器设计
算法总结
4路抢答器课设报告
数据结构图论学习报告
相关主题
文本预览