88

我最近注意到有很多算法部分或全部基于创造性基础中对数字的巧妙使用。例如：

  • 二项式堆基于二进制数，更复杂的倾斜二项式堆基于倾斜二进制数。
  • 一些用于生成按字典顺序排列的算法是基于阶乘数系统的。
  • 尝试可以被认为是一次查看字符串的一位数字的树，以获得适当的基数。
  • 霍夫曼编码树旨在让树中的每条边以某种二进制表示形式编码一个零或一。
  • 斐波那契编码用于斐波那契搜索并反转某些类型的对数。

我的问题是：还有哪些其他算法使用聪明的数字系统作为其直觉或证明的关键步骤？. 我正在考虑组织一个关于这个主题的演讲，所以我必须借鉴的例子越多越好。

4

16 回答 16

39

Chris Okasaki 在他的书Purely Functional Data Structures中有一个非常好的章节，讨论了“数值表示”：本质上，采用数字的一些表示并将其转换为数据结构。为了说明一下，这里是该章的部分：

  1. 位置编号系统
  2. 二进制数（二进制随机访问列表、无零表示、惰性表示、分段表示）
  3. 倾斜二进制数（倾斜二进制随机访问列表、倾斜二项式堆）
  4. 三进制和四进制数

一些最好的技巧，提炼：

  • 区分数字的密集和稀疏表示（通常您会在矩阵或图形中看到这一点，但它也适用于数字！）
  • 冗余数字系统（具有不止一种数字表示的系统）很有用。
  • 如果您将第一个数字安排为非零或使用无零表示，则检索数据结构的头部可能会很有效。
  • 通过分割数据结构来避免级联借用（从列表的尾部）和进位（从 consing 到列表中）

这也是该章的参考列表：

  • Guibas、McCreight、Plass 和 Roberts：线性列表的新表示。
  • Myers：一个适用的随机访问堆栈
  • Carlsson、Munro、Poblete：具有恒定插入时间的隐式二项式队列。
  • Kaplan，Tarjan：具有通过递归减速的连接的纯功能列表。
于 2011-03-20T00:37:12.553 回答
20

“三元数可用于方便地传达自相似结构，如谢尔宾斯基三角形或康托集。” 资源

“四元数用于表示二维希尔伯特曲线。” 资源

“四位虚数系统由 Donald Knuth 于 1955 年首次提出，在提交给高中科学人才搜索的文件中。它是一种以虚数 2i 为基础的非标准位置数字系统。它能够仅使用数字 0、1、2 和 3 来表示每个复数。” 资源

“罗马数字是双五进制。” 资源

“Senary 可能被认为在研究素数方面很有用，因为所有素数在以六为基数表示时，除了 2 和 3 之外，最后一位都是 1 或 5。” 资源

“六进制（以 60 为底）是一个以 60 为底的数字系统。它起源于公元前 3 世纪的古苏美尔人，它被传给了古代巴比伦人，它仍然以一种修改的形式被用于测量时间、角度以及作为角度的地理坐标。” 资源

ETC...

这个列表是一个很好的起点。

于 2011-03-18T19:11:04.143 回答
9

前几天看了你的问题，今天遇到了一个问题：如何生成集合的所有分区？我想到的解决方案，我使用的（可能是由于阅读了你的问题）是这样的：

对于具有 (n) 个元素的集合，我需要 (p) 个分区，计算基数 (p) 中的所有 (n) 个数字。

每个数字对应一个分区。每个数字对应于集合中的一个元素，该数字的值告诉您将元素放入哪个分区。

这并不令人惊讶，但它很整洁。它是完整的，不会导致冗余，并且使用任意基数。您使用的基数取决于特定的分区问题。

于 2011-03-23T03:07:51.037 回答
7

我最近遇到了一个很酷的算法，用于根据 0 到 2 n - 1 之间数字的二进制表示按字典顺序生成子集。它使用数字的位来确定应该为集合选择哪些元素并在本地重新排序生成的集合以使它们按字典顺序排列。如果你好奇，我在这里贴了一篇文章。

此外，许多算法都基于缩放（例如 Ford-Fulkerson 最大流算法的弱多项式版本），它使用输入问题中数字的二进制表示来逐步将粗略近似细化为完整的解决方案。

于 2011-03-21T04:44:31.300 回答
6

不完全是一个聪明的基本系统，而是对基本系统的巧妙使用：范德科普特序列是通过反转数字的 base-n 表示形成的低差异序列。它们用于构建看起来像这样的二维 Halton 序列。

于 2011-03-19T01:02:34.440 回答
6

我隐约记得一些关于双基系统用于加速某些矩阵乘法的事情。

双基数系统是一种冗余系统，它为一个数字使用两个基数。

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

冗余意味着可以通过多种方式指定一个数字。

您可以查找 Todor Cooklev 的 Vassil Dimitrov 的文章“矩阵多项式计算的混合算法”。

尽量给出最好的简短概述。

他们试图计算矩阵多项式G(N,A) = I + A + ... + A^{N-1}。

假设 N 是复合G(N,A) = G(J,A) * G(K, A^J)的，如果我们申请 J = 2，我们得到：

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

还，

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

由于“显然”（开玩笑地）其中一些方程在第一个系统中很快，而在第二个系统中更好——所以根据N. 但这需要对 2 和 3 进行快速模运算。这就是双基出现的原因 - 您基本上可以对它们进行快速模运算，从而为您提供一个组合系统：

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

查看文章以获得更好的解释，因为我不是这方面的专家。

于 2011-03-20T10:02:15.980 回答
5

这是一篇关于使用三进制数解决“假币”问题的好帖子（您必须在一袋普通硬币中检测出一枚假币，尽可能少使用天平）

于 2011-03-19T23:17:36.767 回答
5

RadixSort 可以使用各种数字基数。 http://en.wikipedia.org/wiki/Radix_sort 非常有趣的 bucketSort 实现。

于 2011-03-18T19:48:13.063 回答
5

散列字符串（例如在Rabin-Karp算法中）通常将字符串评估为由 n 位组成的 base-b 数字（其中 n 是字符串的长度，b 是选择的足够大的基数）。例如，字符串“ABCD”可以散列为：

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

将字符替换为 ASCII 值并将 b 设为 256，这将变为，

65*256^3+66*256^2+67*256^1+68*256^0

但是，在大多数实际应用中，结果值取模某个合理大小的数字，以保持结果足够小。

于 2011-03-20T10:30:54.943 回答
4

平方取幂基于指数的二进制表示。

于 2011-03-21T05:38:51.943 回答
4

在Hackers Delight（我眼中每个程序员都应该知道的一本书）中有一个完整的章节介绍了不常用的基数，例如 -2 作为基数（是的，右负基数）或 -1+i（i 作为虚数单位 sqrt(-1)）根据。我也很好地计算了最好的基础是什么（就硬件设计而言，对于所有不想阅读它的人：方程的解是 e，所以你可以选择 2 或 3，3 会好一点（因素比 2) 好 1.056 倍——但在技术上更实用）。

我想到的其他事情是灰色计数器（当你在这个系统中只计算 1 位变化时，你经常在硬件设计中使用这个属性来减少亚稳态问题）或已经提到的 Huffmann 编码的推广 - 算术编码。

于 2011-04-02T19:53:35.850 回答
3

我真的很喜欢这个将二进制数转换为格雷码的方法：http: //www.matrixlab-examples.com/gray-code.html

于 2011-03-18T23:36:10.757 回答
3

密码学广泛使用整数环（模算术）和有限域，它们的操作直观地基于具​​有整数系数的多项式的行为方式。

于 2011-03-18T19:58:38.607 回答
1

好问题。名单确实很长。告诉时间是混合基数的简单实例（天|小时|分钟|秒|上午/下午）

如果您有兴趣了解它，我已经创建了一个元基枚举 n 元组框架。对于基本编号系统来说，这是一些非常甜美的语法糖。它还没有发布。通过电子邮件发送我的用户名（在 gmail）。

于 2011-03-20T03:25:39.003 回答
1

我最喜欢使用 base 2 的方法之一是Arithmetic Encoding。它不寻常，因为算法的 hart 使用二进制表示 0 和 1 之间的数字。

于 2011-12-30T02:28:05.777 回答
0

可能AKS就是这样。

于 2012-04-20T15:35:44.160 回答