Category: 数据结构与算法

N个自然数(从1到N), 全排列就有 N! 种方法 (第1位有N种可能, 第2位有N-1种可能… 第N位有1种可能, 这样乘起来就是 N阶乘). 如果规定 数字1不能在第1位, 数字2不能在第2位.. 数字N不能在第N位的话, 所有可能的排列数就是 错位排列, 英文可以用 derangement 来表示. 动态规化 我们可以用 动态规化 (Dynamic Programming) 来解决这个问题. 我们可以用 F(n) 来表示 n 个数的错位排列总数. …

老小的时候就玩这个 24点扑克游戏. 说来很简单 就是随机抽取4张扑克牌(除掉大小王), 然后需要以最快的速度用这4张牌 加减乘除 来得到 24的一个算式. 这需要脑子运算快, 是个很好的脑力训练. 周末闲来无事, 刚好那天在电视上看到 花样少年 里明星也在玩. 于是就很快的写了这么一个程序. 当然提供免费 API 地址是 https://helloacm.com/api/24/ 第一张扑克牌 第二张扑克牌 第三张扑克牌 第四张扑克牌 新的游戏! 计算24点! 原理和代码 代码在 英文网页上: https://helloacm.com/24/ …

计算圆周率是个老掉牙的课题. 最为简单的 直接易懂的无非就是通过 Monte Carlo 来随机撒点 然后 计算 在圆内的点和总共的点数的比例再乘于4就能得到一个估计的值. 当然随机数的产生一定要质量好 虽然计算机没有真正的随机算法 但是一些 伪随机 算法 比如 xorshift 就很不错. 单机版本的计算 简单明了. int monte_carlo_count_pi(int n) { int c = 0; for (int …

Delphi XE7 之后 语法就加了 Parallel.For 用于多线程编程. 有一个第三方开源的库 OmniThreadLibrary (OTL) 也可以用 但是在 D2007 下由于没有 匿名函数和通用模板 一些OTL的高级语法就都不能用了. The AsyncCall 也是第三方开源的 库 支持 D2006到 XE2 但是也没有 Parallel.For 语法. 下面就简单在 D2007 下实现了 多线程 …

现在的编译器已经非常强大, 在大多数情况下, 开发者无需手动进行底层代码优化. 正如计算机科学家 Donald Knuth 所说: “过早优化是万恶之源”. Pre-optimisation is the root of evil. 过早关注细节优化, 反而可能导致代码复杂度增加, 降低可读性和可维护性. 与其过度纠结于微小的性能提升, 不如专注于编写清晰/可扩展的代码, 并在真正的性能瓶颈显现后, 基于数据进行针对性的优化. 现代软件开发更强调架构设计/算法选择和合理的数据结构, 这些往往比局部优化更能带来实质性的性能提升. 以下测试是基于: Benchmark. 计算PI的程序在这里能找到 源代码. 测试机器的性能配置如下: 16GB …

背景 经理叫我优化一段代码. 因为发现当数据量太大时 运行时间则会变得很久. 这个代码在软件里已经存在 4年之久了. 最开始我们都不知道是谁写的这代码 但之后发现 竟然是经理自己 4年前写的代码. 他自己都不记得了(代码里没有注释). 算法的目的是将一个密集点集重新按照一定的分辨率筛选. 使得任意两点之间的距离要大于这个采样分辨率 并且点的个数要尽量的多. 原始的实现算法 经理原始的算法 是通过迭代每次选出一个点(为了方便 就选第一个点) 然后把候选集中和此点距离大于分辨率的点记录下来做为下一轮的候选集. 实现则用了LINQ的where 看起来只有O(n) 循环但是 其实是 O(n^2) 因为每次LINQ从当前候选集选出新的点这个操作就是 O(n). public List<Point3F> Resampling(double …

RTB 也就是 Real Time Bidding 是近几年新兴的广告行业.拿 adsense 来说吧, 我们在博客上比如放上 336×280 的广告位, 同时 adsense 设置里又允许 Ads Networks. 这样在用户打开该页面时, adsense 会联系 比如 pinyou 广告交易平台 (Ads Exchange), 那么 AdX 会组织一次竞价,可以理解成广告出租位拍卖.并会将多家 DSP (也就是 …