基于数字基础系统的算法？

 

我最近注意到，有很多算法都是基于数字在创意基础中的部分或全部使用。 例如：

  • 二项堆是基于二进制数的，而更复杂的偏斜二项堆则基于二进制斜数。
  • 一些用于生成字典顺序排列的算法基于事实数字系统。
  • 尝试可以被看作是一次只查看一个字符串的树木，以作为适当的基础。
  • 霍夫曼编码树被设计为使树中的每个边缘在某些二进制表示中编码为0或1。
  • 斐波那契编码用于斐波那契搜索并反转某些类型的对数。

    • 我的问题是： 还有哪些其他算法使用巧妙的数字系统作为其直觉或证明的关键步骤？ 。 我正在考虑就这个主题进行一次谈话，所以我必须从更多的例子中得到更好的结果。

    Chris Okasaki在他的着作“Purely Functional Data Structures”中讨论了“数值表示”一书中的一个非常不错的章节：本质上，对数字进行一些表示并将其转换为数据结构。 给一个风味，这里是该章的部分：

  • 位置号码系统
  • 二进制数（二进制随机访问列表，无零表示，延迟表示，分段表示）
  • 偏斜二进制数（偏斜二进制随机访问列表，偏斜二项堆）
  • 三位和第四数字

    • 一些最好的技巧，蒸馏：

  • 区分数字的稠密和稀疏表示（通常您可以在矩阵或图表中看到这一点，但它也适用于数字！）
  • 冗余号码系统（具有多个号码表示的系统）很有用。
  • 如果您将第一个数字设置为非零或使用无零表示，则检索数据结构的头部可能很有效。
  • 避免级联借入（从列表的尾部开始）并通过分割数据结构来承载（从列入列表中）

    • 这也是该章的参考清单：

  • Guibas，McCreight，Plass和Roberts：线性列表的新表示。
  • 迈尔斯：一个适用的随机访问栈
  • Carlsson，Munro，Poblete：具有恒定插入时间的隐式二项式队列。
  • Kaplan，Tarjan：纯粹功能列表通过递归减速来链接。

    • “三元数字可以用来传达像Sierpinski Triangle或Cantor设置的自相似结构。” 资源

    “二维希尔伯特曲线的表​​示中使用了四元数。” 资源

    “四位数假设数字系统最早由Donald Knuth在1955年提交给高中科学人才搜索，它是一个非标准的位置数字系统，它以虚数2i为基数，它能够以仅使用数字0,1,2和3来表示每个复数。“ 资源

    “罗马数字是一个biquinary系统。” 资源

    “在研究素数时，Senary可能被认为是有用的，因为当所有素数以6为基数表示时，除2和3以外，都有1或5作为最终数字。” 资源

    “六十一位数字（基数60）是一个以六十为基数的数字系统，起源于公元前3千年的古代苏美尔人，它被传给了古代巴比伦人，并且仍然用于修改形式 - 用于测量时间，角度和角度的地理坐标。“ 资源

    等等...

    这份清单是一个很好的起点。

    我前几天读到你的问题，今天遇到了一个问题：我如何生成一组的所有分区？ 我遇到的解决方案和我使用的解决方案（可能是因为阅读您的问题）是这样的：

    对于具有（n）个元素的集合，我需要（p）个分区，通过基数（p）中的所有（n）个数字进行计数。

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

    这不是很了不起，但它很整洁。 它是完整的，不会造成冗余，并使用任意的基础。 您使用的基础取决于具体的分区问题。

    链接地址: http://www.djcxy.com/p/40011.html

    上一篇: Algorithms based on number base systems?

    下一篇: Is O(logn) always a tree?