xueyan0096-CSDN博客

原创 DFA词法分析器

词法分析器定义关键字有if、else、while、continue、break、true、false、int、char、bool； if和while语句同c#；四则运算、逻辑运算、关系运算同c#; 基本数据类型char、bool、int；不支持注释。DFALexer Token、TokenType、Integer、Char、Work、Type等class参考《词法分析器》。public class DFALexer{ public int LineNumb..

2020-11-03 16:14:24 1798

原创词法分析器

词法分析器定义假设语言循环结构有if...else...和while...，数据类型有bool、int、char和数组，数组只支持char[]和int[]，四则运算、关系运算和逻辑运算同c#，则其定义如下： program block block { decls stmts } decls decls decl |ε decl type ID; bype ...

2020-11-02 12:05:09 416

原创测试字符串是否匹配DFA

Regex to MFAprivate (int[, ] dfa, int[] finalStates) RegexToMFA(string regex){ var regexDoted = UseDotForConcatenation(regex); var regexPostfix = InfixToPostfix(regexDoted); var enfa = new RegexToENFA(); enfa.Regex2ENFA(regexPostfix);

2020-10-28 15:00:59 2567 1

原创 DFA to MFA

DFA化简步骤将DFA状态集分为结束状态集F和非结束状态集S。F为DFA结束状态，S为结束状态以外的所有其它DFA状态。F和S构成状态集G；对G的每个子集T，对子集T的每个状态S执行move(S, a)得到状态，找到状态所属G的子集，根据将子集T划分为n个子集；重复2直到不能再划分子集；对G中状态个数大于一的子集T，只保留一个状态，去掉T多余的状态。private NFAToDFA dfa;public IEnumerable<int[]> DFA2MFA...

2020-10-26 15:59:37 632

原创 ε-NFA to DFA

辅助方法假设一个NFA状态集T，NFA初始状态，标识a，定义 ε-closure() 从初始状态经由ε能到达的所有状态集合 ε-closure(T) 从状态集T中的每个状态经由ε能到达的所有状态集合 move(T, a) 从状态集T中的每个状态经由a能到达的所有状态集合 private Tuple<int, int>[] edges;//nfa所有ε边的出发state、到达state/// <summar...

2020-10-25 13:34:40 538

原创 Regex to ε-NFA

Regex预处理假设只处理连接、或和*闭包这三种基本的Regex。因为Regex的连接格式为ab，为了方便计算机识别，得添加连接标识符。在计算机处理Regex时，一般都使用stack，为了方便计算机识别，通常将人类习惯的中缀表达式（1+1）转换为后缀表达式（11+)。添加连接标识符/// <summary>/// 给正则表达式加入连接标识符“.”<br/>/// e.g.<br/>/// (ab|ba)*ab ——> (a...

2020-10-24 13:08:46 317

原创【笔记】汉字拼音互转（带音标和笔顺）共20842字

1 爬取拼音和笔顺拼音爬自https://zidian.900cha.com/。数据文件汉字拼音带音标和笔顺共20842字（“壭亪寽兯嚸”这五个字没收）笔顺爬自http://bs.kaishicha.com/。数据文件汉字笔顺共20842字（“壭亪寽兯嚸”这五个字没收）2 vs2019新建.net core console项目，NuGet导入Microsoft.EntityFrameworkCore //ef coreMicrosoft.EntityFram..

2020-09-04 19:00:52 935

原创【笔记】EFCore & SQLite 拼音汉字互换

1 vs2019新建.net core console项目，NuGet添加包Microsoft.EntityFrameworkCore //ef coreMicrosoft.EntityFrameworkCore.Design //在nugetMicrosoft.EntityFrameworkCore.Tools //控制台中管理数据迁移Microsoft.EntityFrameworkCore.Sqlite //sqliteM.

2020-09-01 10:56:11 66169

原创【笔记】EFCore & Mysql

1 官网下载mysql免安装版，修改my.ini为[mysql]default-character-set = UTF8MB4[mysqld]basedir ="C:\Users\huang\Downloads\mysql-8.0.20-winx64"datadir ="C:\Users\huang\Downloads\mysql-8.0.20-winx64\data"port=3306max_connections = 20character-set-server = UTF.

2020-08-28 21:16:35 619

原创【笔记】Big Integer - Karatsuba & Toom-Cook-3 Multiplication

Karatsuba Multiplication给定大数x和y，取两者二进制长度最大值n，将大数分成二进制长度为k = ceil(n/2)的两部分，这样一直减半下去，当大数二进制长度减少到32位以下时直接返回乘积，最后再对每部分的结果进行调整即可得最终乘积。假设x1,y1表示大数前半部分，x0,y0表示大数后半部分则x = x1*2^k + x0y = y1*2^k + y0x...

2019-01-08 12:15:53 1305

原创【笔记】Factoring - Pollard rho Algorithm

给定合数n和附加项a，令g(x) = x^2 + a (mod n)。重复计算g(x)、g(g(x))和gcd = gcd(g(x)-g(g(x)), n)直到gcd != 1且gcd != n为止，这时的gcd即为n的一个因子。参考wiki 下面是微改版本，当gcd = n时会换一个附加项(a + 1)。/// <summary>/// return factor o...

2018-12-12 14:11:45 297

原创【笔记】Big Integer - FFT Multiplication

Discrete Weighted Transform FFT MultiplicationFFT时间复杂度时O(nlgn)，当输入向量长度减半时时间复杂度为O(n/2lg(n/2)) < O((nlgn)/2)，所需时间几乎减半。调用FFT时，对于整数型向量，可以把向量的前半部分放入实部，后半部分放入虚部，比全部放入实部更快。也就是对于长度为N的向量，0,1...N/...

2018-12-06 18:20:47 612

原创【笔记】Cooley–Tukey FFT Algorithm - Iterative Edition

DFTIDFTFFT1 当输入向量长度为2^k时参考《Introduction to Algorithms》chapter 30.3每次迭代的元素赋值及辅助方法reorder/// <summary>/// Radix-2 Step Helper Method/// </summary>/// <param name...

2018-12-06 15:55:35 1009

原创【笔记】Cooley–Tukey FFT Algorithm - Recursive Edition

DFTIDFTFFT1 当输入向量长度为2^k时参考wiki FFT有如下代码/// <summary>/// Cooley–Tukey FFT algorithm,/// length of <paramref name="data"/> is power of 2./// <paramref name="left"/>...

2018-12-06 14:56:08 1792

原创【笔记】Big Integer - Miller-Rabin Primality Test

Miller-Rabin Testbase可以查表，当n不够大时private static readonly BigInteger[][] TEST_BASE ={ new BigInteger[] { 2 }, new BigInteger[] { 2, 3 }, new BigInteger[] { 31, 73}, new BigIn...

2018-11-19 15:11:51 239

原创【笔记】Big Integer - Modular Exponentiation

Montgomery Reduce/// <summary>/// <paramref name="left"/> * <paramref name="right"/> * R ^ -1 (mod <paramref name="modulo"/>)/// (R = 2 ^ bitLength(<paramr

2018-11-19 13:38:26 254

原创【笔记】Big Integer - Modular Inverse

Modular Inverseax + by = gcd(a, b)，gcd(a, b) = 1时，ax + by = 1，ax = 1 (mod b)，x = a^-1 (mod b)，x即a的模逆。Shifting/// <summary>/// <paramref name="value"/> ^ -1 (mod <paramref name="...

2018-11-18 15:41:38 237

原创【笔记】Big Integer - Lehmer's Euclidean Algorithm

Lehmer's Euclidean Algorithm给定正整数a, b (a >= b)，重复取二进制前32位进行欧几里得算法，直到a和b的二进制长度小于等于32位，这时用uint版本的欧几里得算法求得的gcd就是原来的a和b的gcd;/// <summary>/// 计算<paramref name="a"/>和<paramref name...

2018-11-16 15:49:08 291

原创【笔记】Big Integer - Binary Euclidean Algorithm

BigInteger to/from (uint[], bool)用(uint[], bool)来表示有符号大数，其中uint[]是大数的绝对值，bool为false时是负数。/// <summary>/// (<see cref="uint"/>[], <see cref="bool"/>) to <see cref="BigInteger&quo

2018-11-15 15:05:15 211

原创【笔记】Java BigInteger - Division

BigInteger to/from (uint[], bool)用(uint[], bool)来表示有符号大数，其中uint[]是大数的绝对值，bool为false时是负数。/// <summary>/// (<see cref="uint"/>[], <see cref="bool"/>) to <see cref="BigInteger&quo

2018-11-14 18:09:21 851

原创【笔记】Java BigInteger - Square

(uint[], bool)表示大数，uint[]大数的绝对值，bool为false时是负数。Classical Square/// <summary>/// Classical平方，数组第一个<see cref="uint"/>存放最高32位，最后一个<see cref="uint"/>存放最低32位。/// </summary>p...

2018-11-10 12:04:16 509

原创【笔记】Java BigInteger - Multiplication

BigInteger to/from uint[]用uint[]来表示非负大数，其中数组开头是大数的最高32位，数组结尾是大数最低32位。/// <summary>/// <see cref="uint"/>数组转为非负大整数/// </summary>private static BigInteger ValueOf(uint[] value)...

2018-11-09 15:47:34 436

原创【笔记】Java BigInteger - Addition/Subtraction

BigInteger to/from uint[]用uint[]来表示非负大数，其中数组开头是大数的最高32位，数组结尾是大数最低32位。/// <summary>/// <see cref="uint"/>数组转为非负大整数/// </summary>private static BigInteger ValueOf(uint[] value)...

2018-11-08 18:33:38 624

原创【笔记】TAOCP Vol4 - Combination

组合个数/// <summary>/// <paramref name="n"/>个元素集合中所有<paramref name="m"/>个元素组合的个数。/// <paramref name="m"/> &gt;= 0; <paramref name="n"/&gt

2018-11-06 17:56:01 206

原创【笔记】TAOCP Vol4 - Permutation

Lexicographic(字典顺序)给定一个[2,12]之间的整数n，升序返回int[]集合，数组里的数字代表索引。譬如n = 4时，返回0123,0132,0213,0231,0312,0321,1023,1032,1203,1230,1302,1320,2013,2031,2103,2130,2301,2310,3012,3021,3102,3120,3201,3210对于任...

2018-11-06 16:36:28 141

原创【笔记】Hacker's Delight - Some Elementary Functions

Newton's MethodInteger Square Root难点在于计算x0，第一种方法x0 = 2^k >= sqrt(n)，k取最小值/// <summary>/// 返回<paramref name="n"/>平方根,向下取整/// </summary>public static int IntegerSquare...

2018-11-06 15:40:28 276

原创【笔记】Hacker's Delight - Counting Bits

Counting 1-Bits(二进制1的个数)/// <summary>/// <paramref name="n"/>二进制1的个数/// </summary>public static int Population(uint n){ n -= (n >> 1) & 0x5555_5555; n = (n...

2018-11-06 14:26:29 497

原创【笔记】Hacker's Delight - Power-Of-2 Boundaries

Rounding Up/Down to a Multiple of a Known Power of 2（上下取整为2的n次方）Rounding Down/// <summary>/// greatest power of 2 less than or equal to <paramref name="n"/>/// </summary>...

2018-11-06 13:20:18 273

原创【笔记】Modular Inverse

扩展欧几里得方法可以求解ax + by = gcd(a, b)，当gcd(a, b) = 1时，ax + by = 1。ax = 1 (mod b), x即a的模逆。by = 1 (mod a)，y即b的模逆。最简单的模逆运算就是调用扩展欧几里得方法，扩展欧几里得方法见另一篇笔记。/// <summary>/// <paramref name="value"...

2018-11-06 11:41:23 583 1

原创【笔记】Binary Extended Euclidean Algorithm

扩展欧几里得算法给定非负整数a, b，求解向量(u1, u2, u3)，使得au1 + bu2 = u3 = gcd(a, b)。扩展欧几里得算法的除法版本引入辅助向量(v1, v2, v3)，使得av1 + bv2 = v3 代码如下：/// <summary>/// 返回{x, y, gcd}, 使得<paramref name="a"/>x + &...

2018-11-04 16:56:26 529

原创【笔记】Binary Euclidean Algorithm

欧几里得算法u，v都是偶数时 gcd(u, v) = 2gcd(u/2, v/2)u，v只有一个偶数时，偶数u时 gcd(u, v) = gcd(u/2, v)；偶数v时 gcd(u, v) = gcd(u, v/2)u，v都是奇数时，u > v时 gcd(u, v) = gcd((u - v)/2, v); u < v时 gcd(u, v) = gcd(u, (v ...

2018-11-02 12:10:47 342

原创【日记】Eratosthenes Sieve

原理：偶数不可能是素数，素数的倍数也不可能是素数。参考wiki——https://en.wikipedia.org/wiki/Eratosthenes因为空间开销是Ω(n)，所以当n比较大时，效率会很低。private static readonly int ERATOSTHENES_THREADHOLD = 10_000;/// <summary>/// 埃...

2018-11-02 08:19:35 320

原创【日记】Miller-Rabin Primality Test

Miller-Rabin Test 参考wiki—— https://en.wikipedia.org/wiki/Miller–Rabin_primality_test其中a的选择：所以base可以查表，当n不够大时： private static readonly uint[][] TEST_BASE = { ...

2018-11-01 18:00:05 506

原创【日记】Montgomery Modular Inverse

(r, k) = AlmMonInv(a, m) = (a^-1)(2 ^k) (mod m)/// <summary>/// 返回{x, k}；x = <paramref name="value"/>−1 * 2^k (mod <paramref name="modulo"/>) /// if gcd(<paramref name="value...

2018-11-01 16:23:38 237

原创【日记】Montgomery Moduluar Exponentiation

对正整数x, y, m, R, m'，如果存在如下约束：0 <= x, y < R*mR = 2 ^ n, R > mgcd(m, 2) = 1R^-1*R - m'*m = 1则MonPro(x, y, m, m') = (xy)R^-1 (mod m)。function REDC(x, m, m') a <- (x (mod R))m' (...

2018-11-01 12:02:03 294

原创【日记】c# 读取网页json数据

例：读取双色球官网历史开奖号码数据准备工作web url: http://www.cwl.gov.cn/kjxx/ssq/kjgg/按F12在网络面板得到json url:http://www.cwl.gov.cn/cwl_admin/kjxx/findDrawNotice?name=ssq&issueCount=30json request header:...

2018-03-14 20:56:08 1539

汉字笔顺共20842字（“壭亪寽兯嚸”这五个字没收）

冈萨雷斯《数字图像处理》全家桶

离散数学及其应用第6版答案（奇数题和偶数题）

空空如也