Archive for ‘边走编程’ Category

April 20, 2010
单源最短路径Dijkstra算法

Dijkstra算法简述

　　Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点U = V – T，其中V为图G的点集。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。若要处理含有负权值边的情况，就需要使用Bellman-Ford算法了。

Dijkstra算法流程

　　在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]

  • 初始化：源的距离Closest[start]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
  • 以下过程循环n-1次：
    在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
    对于每个与u相邻的点v，如果Closest[u]+Adj[u,v] < Closest[v]，那么把Closest[v]更新成更短的距离Closest[u]+Adj[u,v]。此时到点v的最短路径上，前一个节点即为u。
  • 结束。此时对于任意的u，Closest[u]就是start到u的距离。
Tags: ,. 967 views
Filed under: 之算法神奇,边走编程 — dutor @ 7:36 pm Comments (2)
[C++]覆盖std内的名字

　　在现行的C++标准中有这么一个名字，std，它是一个namespace(命名空间)。C++标准库的所有类型/对象/函数/模板都定义在这个命名空间中。关于”What namespace? Why namespace? How namespace?” 的问题，任何一本基础的C++读物中都会有介绍，此处略过。为了使用std内定义的对象，可供使用的语法无非是

1
2
3
4
5
6
7

std::vector<int> ivec;
//~ or
using std::vector;
vector<int> ivec;
//~ or
using namespace std;
vector<int> ivec;

　　现在有这样一种需要，我想为std内的某种类型(比如string)重载操作符，而不想使用std内为我们提供的版本。

Tags: . 79 views
Filed under: 之语言特性,边走编程 — dutor @ 4:07 pm Comments (0)
April 19, 2010
最小生成树之Kruskal算法

　　一个无向、加权、连通图的生成树是指这样一棵树，它包含该图所有的n个顶点，和该图边集E中的n-1个边。最小生成树就是该图所有生成树中各边权值之和（构造代价）最小的生成树。求指定图的最小生成树有多种算法，除了这里要介绍的Kruskal算法，还有Prim算法、Sollin算法等。

Kruskal算法描述

　　用Kruskal算法为无向加权连通图G构造最小生成树T的步骤如下：首先初始化T为一个包含所有n个顶点、0个边的森林，E为G的边集。每次从E中取出一条具有最小权值的边（并从E中删除该边），如果该边不与T中其他边构成回路，则将该边加入T，否则舍弃该边。重复上述操作至T中含有n-1条边，此时T即Kruskal算法构造出的最小生成树。

Kruskal算法证明

　　易证，对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树中肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。
　　设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边中最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。

Tags: ,. 1,580 views
Filed under: 之算法神奇,边走编程 — dutor @ 10:56 am Comments (0)
April 18, 2010
Visual Studio中的Functional

　　今天在VS中遇到一个十分诡异的事情，先看下面这个简单的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class cmp
{
public:
	bool operator()(long long l, long long r)
	{
		//~ 此间内容可略去不看。
		//~ 如果l和r含有的digits完全相同则返回false,
		//~ 如125 vs. 512
		char tmp1[1024], tmp2[1024];
		sprintf(tmp1,"%ld",l);
		sprintf(tmp2,"%ld",r);
		sort(tmp1, tmp1+strlen(tmp1));
		sort(tmp2, tmp2+strlen(tmp2));
		if (!strcmp(tmp1, tmp2))
		{
			return false;
		}
		return true;
	}
};
Tags: . 67 views
Filed under: 之语言特性,边走编程 — dutor @ 5:04 pm Comments (4)
April 14, 2010
[算法]物不知数 – 中国剩余定理

　　设”此物”为x，则x满足同余方程组：
\left\{\begin{array}{c}x\equiv 2 (\mod 3)\\x\equiv 3 (\mod 5) \\x\equiv 2 (\mod 7)\end{array}\right.
　　若存在x满足上述方程组，则x + k*3*5*7也满足该方程其中k任意整数，方程的最小正整数解满足x\mod{3*5*7}，即对3,5,7的最小公倍数求余。
　　在介绍求x的具体方法之前，先介绍两个简单的定理(证明从略)：

  1. 被除数增加(或减少)除数的倍数，除数不变，则余数电不变；
  2. 被除数扩大(或缩小)指定的倍数，除数不变，则余数扩大(或缩小)同样的倍数(余数总小于除数)。
Tags: ,. 181 views
Filed under: 之算法神奇,数理空间,边走编程 — dutor @ 7:59 pm Comments (0)
April 10, 2010
[C++]函数调用与变量定义的二义性

　　首先，你知道下面的语句的语义是什么吗？

int (a);

或许写成这样你会更明白一点：

int (a) = 0;

它等同于

int a = 0;
Tags: . 102 views
Filed under: 之算法神奇,边走编程 — dutor @ 3:26 pm Comments (6)
March 30, 2010
标准库 & 系统调用 & 缓冲

　　本文通过一个文件拷贝程序的三个不同实现，来说明标准库fread/fwrite、系统调用read/write在缓冲机制上的不同。系统调用没有缓冲(这里不考虑内核缓冲)，拿write来说，它的原型int write(int fd, char *buf, size)。write将buf处的size个字节立即写入文件描述符fd指名的文件，而不经过任何缓冲。而C标准库中的f系列函数(fwrite/fread/fgetc/fputc)在FILE结构中内部维护了一个缓冲区(大小是多少？)，通常情况下只有当这个缓冲区被写满时才会调用write将其真正地写入文件，fflush(FILE* stream)会强制将缓冲区内容写出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int
main (int argc, char **argv)
{
    int c; //~ fgetc()返回int
    FILE* fdin = fopen("51.tar.gz", "r");
    FILE* fdout = fopen("51.tar.gz.bak", "w");
    if (!fdout || !fdin)
    {
        fprintf(stderr, "open failure\n");
        exit(1);
    }
    while ((c = fgetc(fdin)) != EOF)
    {
        fputc(c, fdout);
    }
    fclose(fdout);
    fclose(fdin);
    return 0;
}
Tags: . 130 views
Filed under: 边走编程 — dutor @ 8:46 am Comments (0)
March 27, 2010
[C++]优先级队列priority_queque

　　好久没写C++没用STL了，今天在STLChina泡了一下午。完整的代码只写了这么一个，贴上来吧。
　　写了两个类，Max_Heap和Min_Heap，以他们特例化priority_queue，可以方便地实现最大、最小堆。写完了忽然又觉得这俩类似乎是多此一举了，完全可以用greater来实现最小堆，但由priority_queue的模板定义看出，那样就必须提供一个容器类型，比如vector。
　　最后还写了测试用例：找出ｎ个数中最大的k个。

1
2
3
4
5
6
7
8
9
10
11

/*
template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;
 
explicit priority_queue ( const Compare& x = Compare(),
                          const Container& y = Container() );
template <class InputIterator>
         priority_queue ( InputIterator first, InputIterator last,
                          const Compare& x = Compare(),
                          const Container& y = Container() );
*/
Tags: ,,. 265 views
Filed under: 之语言特性,边走编程 — dutor @ 7:15 pm Comments (0)
March 14, 2010
一个关于大小端的问题

　　所谓大小端模式，就是一个关于数据字节在存储顺序的问题。在某些编程环境中，了解大小端是非常重要的，比如汇编和网络编程中，对存取和发送、接收数据的字节序都有严格的要求。当然，在高层次，你很少会需要考虑到这些。为什么会有大小端模式之分呢？这是因为在计算机系统中，我们是以字节为单位的，每个地址单元都对应着一个字节。在许多计算机语言中，许多数据类型都是多字节的，这就产生了多字节数据在内存中存放数据的问题。在大端模式（Big-endian）中，数据的低位（就是权值较小的后面那几位）保存在内存的高地址中，而数据的高位，保存在内存的低地址中；在小端模式（Little-endian）中，数据低位就存放在内存的低位。了解了什么是大小端，看下面的程序，输出结果是什么？

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>
int
main()
{
    int a[] = {1, 2, 3, 4, 5};
    int *ptr1 = (int*) (&a + 1) - 1;
    int *ptr2 = (int*) ((int)a + 1);
    printf("%x, %x\n", *ptr1, *ptr2);
    return 0;
}
Tags: . 87 views
Filed under: 之语言特性 — dutor @ 5:14 pm Comments (3)
March 6, 2010
[C++]虚 静态函数

　　C++类的静态函数是属于类型的，而不是某个对象的，因此把它声明成Virtual也没什么实际意义。那么运行下面这段程序，会产生什么样的结果呢？

1
2
3
4
5
6
7
8

#include <iostream>
using namespace std;
class Base
{
public:
    static void foo() { cout<<"Base"<<endl; }
    virtual void bar() { foo(); }
};
Tags: . 51 views
Filed under: 之语言特性,边走编程 — dutor @ 6:44 pm Comments (5)
Page 4 of 1612345678910...Last »