Algorithms - 鸟语天空

矢量的点积

作者：追风剑情发布于：2016-5-22 19:07 分类：Algorithms

假设有二维矢量P=(x1,y1)，Q=(x2,y2)，则矢量的点积定义为： P●Q=x1*x2+y1*y2 向量点积的结果是一个标量，它的代数表示是： P●Q=|P||Q|cos(P,Q) (P,Q)表示向量P和Q的夹角，如果P和Q不共线，则根据上式可以得到向量点积的一个非常重要的性质，具体说明如下： (1) 如果P●Q>0，则P...

标签: Algorithms

评论(0) 浏览(4214)

矢量的叉积

作者：追风剑情发布于：2016-5-21 18:03 分类：Algorithms

计算矢量的叉积是判断直线和线段、线段和线段以及线段和点的位置关系的核心算法。假设有二维矢量P=(x1,y1), Q=(x2,y2)，则矢量的叉积定义为： P×Q=x1*y2-x2*y1 向量叉积的几何意义可以描述为由坐标原点(0,0)、P、Q和P+Q所组成的平行四边形的面积，而且是个带符号的...

标签: Algorithms

评论(0) 浏览(6109)

求最小公倍数

作者：追风剑情发布于：2016-5-5 10:30 分类：Algorithms

最小公倍数和最大公约数存在以下关系：最大公因数×最小公倍数=两数的乘积 using System; using System.Collections.Generic; using System.Text; namespace GCDTest { class Program { static void Main(string[...

标签: Algorithms

评论(0) 浏览(3758)

求最大公约数——辗转相除法

作者：追风剑情发布于：2016-4-30 12:53 分类：Algorithms

辗转相除的数学原理是朴素的欧几里得定理： GCD(a, b) = GCD(b, a mod b) (a mod b表示a除以b的余数) 代码实现 using System; using System.Collections.Generic; using System.Text; namespace GCDTest {...

标签: Algorithms

评论(0) 浏览(13465)

剩余类

作者：追风剑情发布于：2016-4-28 13:38 分类：Algorithms

一个整数被正整数n除后，余数有n种情形：0，1，2，3，...，n-1。我们把所有对模n同余的数构成的集合叫着模n的一个剩余类。例如: 12的剩余类，为12个集合。 {...,0,12,24,36,...} {...,1,13,25,37,...} {....2,14,26,38,...} ... {...,11,23,35,47,...} 注意：{...,-47,-35...

标签: Algorithms

评论(0) 浏览(5209)

蒙哥马利幂模运算

作者：追风剑情发布于：2016-4-26 14:33 分类：Algorithms

蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。数学原理 (a×b)%n = (a%n × b%n)%n (a+b)%n = (a%n + b%n)%n 示例: 求a^9%n a^9%n = (a^8 × a)%n = (a^8%n × a%n)...

标签: Algorithms

评论(0) 浏览(14039)

牛顿迭代法

作者：追风剑情发布于：2016-4-24 16:29 分类：Algorithms

一元非线性方程的求解是高等数学研究的重要课题之一，早在2000多年前，古巴比伦的数学家就能解一元二次方程了，中国的《九章算术》也有对一元二次方程求解的记载。目前人们普遍认为低阶(5阶以下)一元非线性方程可以通过求根公式求解，但是高于或等于5阶的一元非线性方程不存在求根公式，要精确求解非常困难。对高阶方程，一般采用迭代法近似求解，牛顿迭代法因为方法...

标签: Algorithms

评论(0) 浏览(7459)

求点到线段的最短距离

作者：追风剑情发布于：2016-2-25 20:42 分类：Algorithms

线段的向量表示 p=at+b (0≤t≤1) 向量b为线段的起点，向量a是延着线段的向量。问题：求点(x0, y0)到线段p的最短距离? 解题思路：将线段上的点p=at+b(0≤t≤1)与点(x0, y0)的距离表示为t的函数，然后对t进行微分，求得距离最小时的t。向量p=at+b (0≤t≤1)可分解表示为:...

标签: Algorithms

评论(0) 浏览(4544)

对数组随机排序

作者：追风剑情发布于：2016-1-13 20:15 分类：Algorithms

public static void RandSortArray(List<int> arr) { int size = arr.Count; int seed = 10000; //对给定数组随机排序, 每组排列的概率都为 1/size的阶乘 System.Random rand = new System.Ra...

标签: Algorithms

评论(0) 浏览(2684)

拓扑排序(一)

作者：追风剑情发布于：2015-12-6 19:34 分类：Algorithms

拓扑排序与AOV、AOE网主要用来处理工程管理的。在图论中，一个有向无环图的所有顶点可以排成一个线性序列，当这个线性序列满足以下条件时，称该序列为一个满足图的拓扑次序(topological order)的序列。（1）图中的每个顶点在序列中只出现一次；（2）对于图中任意一条有向边(u, v)，在该序列中顶点u一定位于顶点v之前。 ...

标签: Algorithms

评论(0) 浏览(3384)

历法

作者：追风剑情发布于：2015-11-22 14:02 分类：Algorithms

格里历(公历) 我国的官方历法是目前全球各国通用的公历，也就是公元纪年。公历实际上是从1582年10月15日开始实行的格里历(Gregorian Calendar)。这是一个比较简单的历法。历法规则: (1) 如果年份是4的倍数，且不是100的倍数，则是闰年(Leap Year...

标签: Algorithms

评论(0) 浏览(3516)

贪婪法——求解0-1背包问题

作者：追风剑情发布于：2015-11-17 23:19 分类：Algorithms

贪婪法(greedy algorithm)，又称贪心算法，是寻找最优解问题的常用方法。这种方法模式一般将求解过程分成若干个步骤，在每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择(局部最有利的选择)，并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。一般来说，...

标签: Algorithms

评论(0) 浏览(4853)

动态规划

作者：追风剑情发布于：2015-11-9 20:00 分类：Algorithms

动态规划(dynamic programming)是解决多阶段决策问题常用的最优化理论。动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。动态规划法通过将问题细分为一系列子问题，从而隐含地探...

标签: Algorithms

评论(0) 浏览(3610)

妖怪与和尚过河问题

作者：追风剑情发布于：2015-11-5 21:20 分类：Algorithms

有三个妖怪和三个和尚要利用唯一一条小船过河，这条小船每次至少载一个人最多载两个人，无论是在河的两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。 using System; using System.Collections.Generic; using ...

标签: Algorithms

评论(0) 浏览(3852)

斐波那契数列

作者：追风剑情发布于：2015-3-21 20:31 分类：Algorithms

定义: 第一项等于0，第二项等于1，以后的每项等于前两项之和。递推公式直接公式约等于公式

标签: Algorithms

评论(0) 浏览(2907)

求最大公约数

作者：追风剑情发布于：2015-2-7 20:26 分类：Algorithms

早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。 #include <stdlib.h> #include <stdio.h> //辗转相除法求最大公约数 int gcd(int m, int n) { int r; r=m%n; if(r == 0) return n; else ...

标签: Algorithms

评论(0) 浏览(2948)

约瑟夫环

作者：追风剑情发布于：2015-1-30 21:32 分类：Algorithms

问题：将编号为0~(N-1)这N个人进行圆形排列。按顺时针从0开始报数，报到M-1的人退出圆形队列，剩下的人继续从0开始报数，不断重复。求最后出列者最初在圆形队列中的编号。这N个人的原始编号为： 0, 1, 2, 3 ... N-3, N-2, N-1 第一个出列人的编号一定是(M-1)%N, 则第一个人出列后的列表为： ...

标签: Algorithms

评论(0) 浏览(2645)

余数性质

作者：追风剑情发布于：2015-1-15 21:25 分类：Algorithms

性质一余数小于除数。性质二 a=d×q+r (a为被除数，d为除数，q为商，r为余数) 性质三如果 a÷c=x...d b÷c=y...d 则有 (a-b)÷c=z...0 性质四如果 (a...

标签: Algorithms

评论(0) 浏览(3480)

哥德巴赫猜想

作者：追风剑情发布于：2015-1-4 21:53 分类：Algorithms

任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和。数值验证: C语言 #include <stdio.h> #include <stdlib.h> #include <conio.h> // Eratosthenes算法 // 将指定范围中的...

标签: Algorithms

评论(0) 浏览(3074)

树转换成二叉树

作者：追风剑情发布于：2014-12-7 14:25 分类：Algorithms

将一棵树转换成二叉树的过程如下。（1）树中所有相邻兄弟之间加一条连线。（2）对树中每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线。（3）以树的根结点为轴心，将整棵树顺时针转动45度，使其结构层次分明。

标签: Algorithms

评论(0) 浏览(4368)

拓扑排序(二)

作者：追风剑情发布于：2014-11-16 14:50 分类：Algorithms

拓扑排序是有向图的一种重要运算。设G=(V,E)是一个具有n个顶点的有向图，在图中顶点表示活动，用边表示活动间的优先关系，则这个有向图称为用顶点表示活动的网(Activity On Vertex Network)，简称为AOV网。在AOV网中，如果从顶点Vi到顶点Vj有一条有向路径，则Vi是Vj的前驱，Vj是Vi的后继；如果<Vi,Vj>是AOV...

标签: Algorithms

评论(0) 浏览(3216)

堆排序

作者：追风剑情发布于：2014-11-9 16:49 分类：Algorithms

堆是一棵顺序存储的完全二叉树，其中每个结点的关键字都不小于其孩子结点的关键字（称为大根堆，如果是进行从大到小的排序，则堆中每个结点的关键字都不大于其孩子结点的关键字，称为小根椎）。在堆排序过程中，关键字的比较次数等于初始建堆所需的比较次数与每次调整新堆所需的比较次数之和，堆排序在最坏情况下所需的比较次数不超过,显然，...

标签: Algorithms

评论(0) 浏览(5372)

1 2 3 4 5 6 7

Powered by emlog 蜀ICP备18021003号-1 sitemap

川公网安备 51019002001593号