博文
gcc3(2007-04-18 15:24:00)
摘要：#include <iostream.h>
#include <stdio.h>
#define M 20
char a[M][M];
int fuback(int k,int n,char u)
{
int i;
if(k==0) u='T';
if(k==1) u='J';
for(i=k;i<n;i++)
{
a[k][i]=u;
a[i][k]=u;
a[i][n-1]=u;
a[n-1][i]=u;
}
if(k==1)u='0';
if(k!=((M+1)/2)){fuback(k+1,n-1,u+1);}......
gcc2(2007-04-18 15:23:00)
摘要：#include <stdio.h>
/*
2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
人参加了竞赛：
（１）Ａ参加时，Ｂ也参加；
（２）Ｂ和Ｃ只有一个人参加；
（３）Ｃ和Ｄ或者都参加，或者都不参加；
（４）Ｄ和Ｅ中至少有一个人参加；
（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。
*/
int main()
{
int a,b,c,d,e; /*其中值1为参加，0为不参加*/
for(a=0;a<=1;a++)
for(b=0;b<=1;b++)
for(c=0;c<=1;c++)
for(d=0;d<=1;d++)
for(e=0;e<=1;e++)
if(((b&&!c)||(!b&&c))&&((c&&d)||(!c&&!d))&&(d||e))
/*分别代表条件2~4*/
if((a&&b||!a)&&(e&&(a&&d)||!e))/*代表条件1和5，特别注意a，e不一定参......
gcc1(2007-04-18 15:22:00)
摘要：// gcc1.cpp : Defines the entry point for the console application.
/*
1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不
D F G 同字母。编程求出这些数字并且打出这个数字的
+ D F G 算术计算竖式。
───────
X Y Z D E
*/
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
int f=5,g=0,a,b,c,d,e,x,y,z=0;
void Search(int n)
{
for(c=1;c<10;c++)
{
if(c==5) continue;
for(d=1;d<10;d++)
{
......
求割顶－－ZJU1311(2007-04-18 15:17:00)
摘要：
求割点（关键点）
首先，对于单独的一个点，或者2个点，我们不予考虑，因为我们没法认定。
分情况：
如果待确定的点不是搜索树的根节点，那么关键点可以认为是这样的点V，他的子孙节点中存在一个节点P，从P出发继续向下拓展（也就是不再走已经走过的边，而是向下兜圈子，然后通过某个后向边回到前面已经访问过的点，这里可以看出后向边的价值，后向边在dfs中是不允许扩展的，但是我们说的“兜回到祖先”就是通过某个后向边实现的）dfs不能达到V的祖先，事实上，只要有任意一个子孙节点符合这个特性，那么v就是关键点，因为原本子孙和祖先是连通的，删除它之后，他的子孙至少无法走到他的祖先（包括它的兄弟姐妹。。。）
如果是根节点，他如果只有一个子树，那么他不是关键点，如果有多于一个的子树，那么他必然是关键点
具体实现：
具体实现是这样的，我们定义一个点上的函数dfn(v)，表示v这个点在dfs过程中第一次访问的顺序，然后，为了达到上面的定义，我们再定义一个点上的函数low(v)，low(v)表示从v出发，继续向下拓展搜索，所能达到的最早的点，也就是dfn最小的点
显然，low(v)有：
low(v)=min(dfn(v),low(s),dfn(w))
其中，s是所有儿子节点，w是v的后向边
割顶：
连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。
最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。
注意：完全图的连通度为总顶点数－1；
牵一发而动全身的点称为割点
边连通度：
连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。
含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。
注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；
连通图的两个特征：
1 连通度<=边连通度<=顶点数
2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)
块的概念：
没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障
至少两个站点同时发生故障，这种二连通分......
四种寻路算法并比较 (2007-04-18 15:16:00)
摘要：四种寻路算法并比较
好久没搞这些东西了...想了十分钟才勉强回忆起来...
写了三个钟头...好累啊...
四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*)
用了两张障碍表，一张是典型的迷宫：
char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,1,0,1,0,0,0,1 },
{1,0,1,1,0,0,1,0,0,1,1 },
{1,0,1,0,1,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,1,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,1,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};
第二张是删掉一些障碍后的:
char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,0,0,1,0,0,0,1 },
{1,0,0,1,0,0,1,0,0,1,1 },
{1,0,1,0,0,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,0,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,0,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};
结果：
尝试节点数 合法节点数 步数
深度优先 416/133 110/43 19/25
广度优先 190/188 48/49 19/15
深度+启发 283/39 82/22 19/19
广度+启发 189/185 48/49 19/15
所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。
附：dfs+heu的源程序，bc++ 3.1通过
......
一个图和其中两点.求出该两点间的所有路径 (2007-04-18 15:15:00)
摘要：一个图和其中两点.求出该两点间的所有路径
void lookingforway(graph g){
bool visitedp[max]
for (v=0;v<g.vertex_number; v ) visited[v]=false;
input your start point: special_vertex;
visited[special_vertex]=true;
for (v=first_adjacent_vertex(g,special_vertex);v; v=next_adjacent_vertex(g,v){
if (!visited[v]){
visited[v]=true;
search(g,v);
}
}
}
void search(graph g, int v){
visited[v]=true;
if v=end_point {
打印路径
return;
}
for (w=first_adjacent_vertex(g,v);w;w=next_adjacent_vertex(g,v)){
if (!visited[w]) search(g,w);
}
} ......
图的相关算法(2007-04-18 15:15:00)
摘要：在广度优先搜索的基础上求图中两结点的最短路径需
1,将链队列的结点改为“双链”结点，即结点中包含next和priou两个指针；
2，修改入队列的操作，插入新的队尾结点时，令其priou域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；
3，修改出队列的操作，出队列时，仅移动队头指针，而不将队头结点从链表中删除。
由于普里姆算法的时间复杂度为O( N的平方)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为o(eloge)，则适于稀疏图。
7.5重（双）连通图和关节点
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。
没有关节点的连通图为双连通图。
关节点的特征：
假设从某个顶点V出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。
若生成树的根结点，有两个或两个以上的分支，则此顶点（生成树的根）必为关节点；
对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。
如何求关键点：
1)对根结点来说深度优先遍历看count是否小于结点数，如果小于则该根结点为关节点。
2)对生成树上的顶点定义一个函数：
low(v)=Min{visited[v],low[w],visited[k]}（k为和v有回边相通的顶点）
对顶点v，若（在生成树上）存在一个子树根w,且low[w]>=visited[v]则顶点v为关节点
对深度优先遍历算法作如下修改：
1，visited[v]的值改为遍历过程中顶点的访问次序count值
2,遍历过程中求得
low(v)=Min{visited[v],low[w],visited[k]}
3,从子树遍历返回时判别low[v]是否>=visited[v]
7.6两点之间的最短路径问题
从源点到其余各点的最短......
深度优先搜索算法（ＤＦＳ）源代码(2007-04-18 15:12:00)
摘要：深度优先搜索算法（ＤＦＳ）源代码，Ｃ＋＋的，
/*深度搜索，用邻接矩阵存储*/
void DFSTraverse(Graph *G)
{
int v;
for(v=1;v<=G->vexnum;v++)
visited[v]=false;
for(v=1;v<=G->vexnum;v++)
if(visited[v]==false)
DFS(G,v);
}
void DFS(Graph *G,int v)
{
int w;
visited[v]=true;
visitfunc(G,v);
for(w=FirstAdjex(G,v);w>=0;w=NextAdjex(G,v,w))
if(visited[w]==false)
DFS(G,w);
}
int FirstAdjex(Graph *G,int v)
{
int i;
for(i=1;i<=G->vexnum;i++)
if(G->Garr[v][i])
return i;
return -1;
}
int NextAdjex(Graph *G,int v,int w)
{
int i;
for(i=w+1;i<=G->vexnum;i++)
if(G->Garr[v][i])
return i;
return -1;
}
......
ACM竞赛之新人向导(2007-04-18 15:12:00)
摘要：ACM竞赛之新人向导
2007-04-05 20:49
原创：怒火之袍
2003年4月29日
我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C......
[算法] 算法总汇(2007-04-18 15:10:00)
摘要：路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
可以用Dijkstra解决问题的特征
负边权最短路径
Bellman-Ford
Bellman-Ford的Yen-氏优化
差分约束系统
Floyd
广义路径问题
传递闭包
极小极大距离 / 极大极小距离
Euler Path / Tour
&n......