| « | November 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | | | |
|
公告 |
在此正式宣布，这个Blog下的地盘，都是偶的啦  这个版面专用于技术...别的就先不贴了！ |
| 信息 |
|
blog名称:技术至上
日志总数:4
评论数量:1
留言数量:0
访问次数:73246
建立时间:2004年12月11日 |
| |
|
 [Algorithms]脱线MIN算法
读书笔记, 软件技术
Stanley 发表于 2005/1/16 2:16:42 |
Union-Find算法的应用与推广
指令Insert(i)：把元素i插入集合S中。
指令Extract_min：从集合S中找出最小元并进行删除。
两种指令的简单表示法：
用i表示Insert(i)，用E表示Extract_min。
例：7，2，5，9，E，6，E，E，3，E，1，4，E
这种序列满足两个性质：
1）任一i (1≤ i ≤n) 在序列中最多出现一次（元素之间互不相同）；
2）从左起任意一段中，插入指令条数要大于等于E指令条数。
（否则无元素可删。）
脱线MIN问题：
给定一个Insert与Extract_min的指令序列σ之后，
对在序列中出现的每个i，
算法要输出i是被第几条E指令删除的。
（对于序列中未出现的i，算法应输出相应信息。）
上例中有：1(5), 2(1), 3(4), 4(未被删除)，5(2)，6(3)，
7，9与4一样未被删除，8未出现。
因要对合并后的集合进行强制命名，
故采用Aho书中的UNION(i,j,k)算法（可强制命名为k）：
wlg assume COUNT[ROOT[i]] ≤ COUNT[ROOT[j]]
(otherwise interchange i and j in the following lines)
LARGE←ROOT[j];
SMALL←ROOT[i];
FATHER[SMALL]←LARGE;
CO |
|
|
[Algorithms]KMP、Monte Carlo、Las Vegas 匹配算法 (用C++ & STL实现)
原创空间, 软件技术
Stanley 发表于 2004/12/11 19:59:02 |
// StrMatcher.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include "basicmatcher.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define STRING_NUM 10000
//素数(Prime Number)产生器，这里利用讲义中提供的7素数分类，而非自行产生
//PNM is short for "Prime Number Matrix"
namespace PNM{
//不同范围内的素数矩阵
int pnm[6][7]={
{211,223,227,229,233,239,241},
{461,463,467,479,487,491,499},
{953,967,971
(下面还有174字) |
|
« 1 ›
|