Tobary book

麻将听牌算法 [下篇]

在上篇中分析了听牌可能有关字牌的情形, 具体包括字牌中有一个单张, 而剩下的数牌全能构成面子的单骑醒, 或者字牌中有个对子, 而剩下某数牌含有一个对子的双碰型或一个搭子的边/嵌张听牌. 这篇要讨论字牌全是刻子时的类似情况. 之所以说类似是由于此时数牌只可能有以下两种情况

某一色数牌的牌总数模 3 余 1, 其它两个色都能恰好构成面子
某两色数牌的牌总数摸 3 余 2, 剩下一色能恰好构成面子

体现成代码就是, 需要解决以下两个函数

def _waits_4groups(tiles):
    # 前略
    # 在前面情况不满足时, 调用如下实现
    return (_detect_numeric_suit_with_one_more(tiles) +
            _detect_2_numeric_suits_with_2_more(tiles))

# 找一个花色, 它的数量模 3 余 1
def _detect_numeric_suit_with_one_more(tiles):
    pass

# 找两个花色, 它们各自的牌的数量模 3 都余 2
def _detect_2_numeric_suits_with_2_more(tiles):
    pass

在上一篇代码的支援下, 后一个函数的实现相对容易一些, 如下

Created at 2014-07-16 14:43:49

Permanent Link: /p/522/

Post tags:

作为一个人类经常在打清一色的时候望着手牌不知道听牌没不知道听了哪几张也不知道切哪一张会让听牌数量最大化是一件不愉快的事情, 除了九莲宝灯之类的定式役给背下来好像没别的有效方法. 或者, 写个程序来搞吧.
首先是数据结构, 这里用如下类来描述

Created at 2014-07-02 19:13:02

Permanent Link: /p/521/

Post tags:

二叉检索树的查询与检索操作看这里

从二叉检索树中删除一个元素分多个步骤:

找到节点
将节点移动到容易删除的位置
删除节点

找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1.
下面是这一部分的实现

void remove_by(key_type const& key)
{
    remove_by_from(key, &root);
}

void remove_at(int position)
{
    remove_at_from(position, &root);
}

static void remove_by_from(key_type const& key, node** parent)
{
    --((*parent)->load);
    if (key < (*parent)->t.key()) {
        remove_by_from(key, &((*parent)->left));
        return;
    }
    if ((*parent)->t.key() < key) {
        remove_by_from(key, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove_at_from(int position, node** parent)
{
    --((*parent)->load);
    int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
    if (position < left_load) {
        remove_at_from(position, &((*parent)->left));
        return;
    }
    if (left_load < position) {
        position = position - left_load - 1;
        remove_at_from(position, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove(node** n);

这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改.

找到了节点之后将会有下面 3 种情况

节点是叶子
节点只有一侧子树
节点两侧子树健全

前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)

Created at 2012-01-24 14:42:01

Permanent Link: /p/481/

Post tags:

堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短

按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构

    前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述.

    较之堆更加全能的索引数据结构非二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况.

    首先还是把二叉树的架子给搭出来

template

class binary_search_tree {
    struct node {
        T t;
        node* left;
        node* right;
        int load;

        explicit node(T const& rhs)
            : t(rhs)
            , left(NULL)
            , right(NULL)
            , load(1)
        {}
    };

    node* root;

    typedef typename T::key_type key_type;
public:
    binary_search_tree()
        : root(NULL)
    {}
public:
    void insert(T const& e);

    void remove_by(typename T::key_type const& key);
    void remove_at(int position);

    T& element_by(typename T::key_type const& key);
    T& element_at(int position);
};

Created at 2012-01-23 14:04:23

Permanent Link: /p/479/

Post tags:

下面是一个简单的单链表节点结构

struct node {
    int value;
    struct node* next;
};

那么如何将这个链表反转过来呢?
void reverse(struct node* head);

下面采用递归的方式实现, 废话少说, 直接上代码

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

上面的实现假定传入的 head 不会是空节点. 如果要检测, 可以加入一个判断

void reverse(struct node* head)
{
    if (NULL != head)
        *_reverse(head) = NULL;
}

下面来验证一下吧

#include


struct node {
    int value;
    struct node* next;
};

void reverse(struct node* head);

void print_list(struct node const* head);

int main(void)
{
    struct node a = { 0, NULL },
                b = { 1, &a },
                c = { 2, &b }; // c(2) -> b(1) -> a(0) -> NULL
    print_list(&c);
    reverse(&c); //    changed to a(0) -> b(1) -> c(2) -> NULL
    print_list(&a);
    return 0;
}

void print_list(struct node const* head)
{
    printf("[");
    for (; NULL != head; head = head->next) {
        printf(" %d", head->value);
    }
    printf(" ]\n");
}

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

Created at 2011-12-21 13:59:53

Permanent Link: /p/475/

Post tags:

Algorithm

Data Structure

日常的数据结构 - 堆的实现与第 K 最小堆

在前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式.
从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如

+---+ | 4 | +---+ / \ +---+ +---+ | 5 | | 9 | +---+ +---+ / \ +---+ +---+ | 8 | | 5 | +---+ +---+

这样一棵完全二叉树可以被转换成

.----. /--. \ +---+---+---+---+---+---+----- | - | 4 | 5 | 9 | 8 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是

.----. /--. \ +---+---+---+---+---+---+----- | 0 | 1 | 2 | 3 | 4 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如

.----. /--. \ +---+---+---+---+---+---+----- | - | 0 | 1 | 2 | 3 | 4 | ... +---+---+---+---+---+---+----- \______/ / \________/

也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).
既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架

template

class heap {
    std::vector<_T> array;
    _Less const less;
    typedef typename std::vector<_T>::size_type size_type;
public:
    heap()
        : array(1) /* insert a placeholder, array[0] */
        , less(_Less())
    {}

    void push(_T const& value);
    _T pop();
};

向堆中加入元素实现为插入并修正, 修正的过程, 也就是向父节点方向移动, 是递归实现的

Created at 2011-10-07 18:23:13

Permanent Link: /p/441/

Post tags:

    如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构.
    这个数据结构建立在满二叉树 (full binary tree)和完全二叉树 (complete binary tree)的概念上.
    "满" 这个字眼提示在树的每一层都摆满了节点, 而这恰好又是个充要条件, 即如果一棵二叉树每一层都堆满了节点, 那么它就是满二叉树. 满二叉树的定义干脆就按节点个数来: 一棵二叉树如果深度为 K, 而拥有 2^K-1 个节点, 那么它就是一棵满二叉树. 如下面是 2 层和 3 层满二叉树, 分别拥有 3 个和 7 个节点

+---+ | a | +---+ +---+ | a | .---' `---. +---+ +---+ +---+ / \ | b | | c | +---+ +---+ +---+ +---+ | b | | c | / \ / \ +---+ +---+ +---+ +---+ +---+ +---+ | d | | e | | f | | g | +---+ +---+ +---+ +---+

而如果一棵二叉树满足

除了最后一层, 其余层构成一棵满二叉树
最后一层从右起缺少 0 个或多个连续的节点

那么它就是一棵完全二叉树. 更直观一些, 将一个满二叉树的节点按照广度优先 (即逐层向下) 遍历的方式顺序编号, 编号从 1 开始 (而不是从 0 开始), 如

Created at 2011-10-03 22:01:06

Permanent Link: /p/434/

Post tags:

顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)

template

_Iterator find_min(_Iterator begin, _Iterator end)
{
    _Iterator min = begin;
    for (++begin; begin != end; ++begin) {
        if (*begin < *min) {
            min = begin;
        }
    }
    return min;
}

将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数.
在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出

+-------+-----------+----- | begin | begin + 1 | ... +-------+-----------+----- | | +--( < )--+ / \ / \ +----------+ +-------------+ +-----+ | less one | | greater one |--( < )--| max | +----------+ +-------------+ +-----+ | | +-----+ +-------------------------( < )--| min | +-----+

这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
下面是实现的例子

Created at 2011-09-30 18:20:03

Permanent Link: /p/426/

Post tags:

无限区间上 n 个不同的点可以把该区间分为多少段?

答案很明显, 当然是 (n + 1) 段啦. 另一个稍有难度的题目是, 无限平面上有n条直线, 问这些直线至多能把平面分成多少份? 在平面上画啊画就能归纳出解来的. 那么, 用 n 个平面, 最多能将无限三维空间划分成几个部分呢? 这个就略复杂了, 难道先建个 3D 模型, 然后归纳? 这个方法可行, 不过太浪漫和浪费了. 另外, 如果这个问题开始讨论维度更高的情形, 这种方法就行不通了. 那么, 问题来了:

使用 n 个 d 维 "*平整*" 的几何体, 来对无限 (d + 1) 维空间进行划分, 最多可以得到多少个部分?

不知道这个问题是否有官方名称了, 暂时称之为划分问题吧. 在这里, "平整" 指的是在该维度的空间中, 这些几何体的方程应该是线性的, 比如在 3 维空间中, 平面方程都可以表示为线性方程组 { $A_1 * x + B_1 * y = C_1$; $A_2 * x + B_2 * y = C_2$ }, 而在 1 维空间中的点就比较惨了, 就是 x = C, 不过还算是线性的. 其实大家只要有个基本的认识就行了, 不必这么刻板深究, 这篇文章中介绍的方法是没有严格证明的, 只是说说思路.

对能够画出来的各种维度进行一下归纳, 可以发现这样一个规律, 最开始开始的几次, 划分得到的空间区域是指数增长的:

1 点分直线可以把直线分为 2 份
1 直线分平面可以把平面分为 2 份, 2直线分平面可以把平面分为 4 份
1 平面分空间可以把空间分为 2 份, 2平面分空间可以把空间分为 4 份, 3 平面分空间

可以把空间分为 8 份

这些规律可以*不完全归纳*假设为: n 个 d 维平整无限体分 (d + 1) 维无限体, 当 $n <= d$ 时, 可以分为 $2^n$ 份.

此外, 已知的结论有:

n 个点分直线至多将直线分为 (n + 1) 份;
n 条直线分平面至多将平面分为 ($(n^2) / 2 + n / 2 + 1$) 份;
n 个平面分空间至多将空间分为 ($(n^3) / 6 + 5 * n / 6 + 1$) 份;

所以再*不完全归纳*假设: n 个 d 维平整无限体分 (d + 1) 维无限体, 得到的份数 m 是 n 的一个幂多项式, 最高次项次数为 (d + 1).

由这些假设, 划分问题将可以用非常暴力的代数手段来解. n 个 d 维平整无限体分 (d + 1) 维无限体, 分得的空间数目 m 满足:

$ m = a_d * n^(d+1) + a_(d-1) * n^d + ... + a_0

这里 $a_x$ 是该多项式的系数.

现在代入 (n, m) = {(0, 1), (1, 2), ..., (d, $2^d$)}, 得到一个 (d + 1) 元一次方程, 这样就可以唯一地解出 $a_d$, $a_(d-1)$, ..., $a_0$ 这 (d + 1) 个系数.

类似的 (未经证明的) 方法同样可以用来连续自然数幂求和问题: 对于自然数 m 和给定的自然数 n, 求通项公式

$ a(m) = 0^n + 1^n + 2^n + ... + m^n

同样, 设出通项公式方程 (注: 没有常数项)

$ a(m) = a_k * m^(k+1) + a_(k-1) * m^k + ... + a_0 * m

然后根据没有化简的普通方程, 代入 m = { 1, ..., k }, 计算出前 k 个 a(m) (这个过程会很痛苦), 然后代入通项公式解方程 (唔, 这会更痛苦).

当然这只是另一个替代方案而已. Bernoulli 对自然数幂和公式的也做过研究, 他的方式是递推的, 运动量没有这个暴力方法大.

Created at 2009-11-29 10:39:18

Permanent Link: /p/45/

Post tags:

已经转移到

http://zlo.gs/p/neuront/leap-year-test-algorithm

Created at 2009-11-17 09:33:38

Permanent Link: /p/25/

Post tags:

Algorithm

已知两圆圆心坐标及半径求两圆交点

在一个二维平面上给定两个圆的圆心横纵坐标、半径共 6 个参数, 求交点. 即实现下面的 C 函数

int intersect(struct circle_t const circles[], struct point_t intersections[]);

其中 point_t 与 circle_t 的定义分别是

Code Snippet 0-0

struct point_t {
    double x;
    double y;
};

struct circle_t {
    point_t center;
    double r;
};

函数 intersect 的输入参数为两个圆, 返回交点个数, 另外, 交点详细信息将被存入另一个参数数组 intersections 中. 由于两个圆之多有 2 个交点, 因此该函数可以如下形式调用:

Code Snippet 0-1

#include 


int main(void)
{
    struct circle_t circles[2];
    struct point_t points[2];

    /* 从 stdin 输入圆参数
     * 按照如下格式
     * $(x_0, y_0, r_0)$
     * $(x_1, y_1, r_1)$
     */
    scanf("%lf%lf%lf%lf%lf%lf",
          &circles[0].center.x, &circles[0].center.y, &circles[0].r,
          &circles[1].center.x, &circles[1].center.y, &circles[1].r);

    // 如果两个圆相同
    // *注意:* 由于 x, y, r 都是浮点数, 使用 == 进行判同可能导致问题
    // 作为示例代码还是姑且这么写了
    if (circles[0].center.x == circles[1].center.x
        && circles[0].center.y == circles[1].center.y
        && circles[0].r == circles[1].r)
    {
       puts("The circles are the same.");
       return 0;
    }

    switch (*intersect(circles, points)*) {
        case 0:
            puts("No intersection.");
            break;
        case 1:
            printf("(%.3lf %.3lf)n", points[0].x, points[0].y);
            break;
        case 2:
            printf("(%.3lf %.3lf) (%.3lf %.3lf)n",
                   points[0].x, points[0].y,
                   points[1].x, points[1].y);
    }
    return 0;
}

用程序实现求交点方法可以有多种, 比较极端的甚至可以用到二分逼近, 反正计算机的计算能力跟笔算是两个世界; 不过本文还是老实一点, 仍试着来解方程. 在求解过程中, 除了用到圆的标准方程

$ (x - x_0)^2 + (y - y_0)^2 = r_0^2

(其中 $(x_0, y_0)$ 是其中一个圆的圆心, $r_0$ 是其半径; 当然对另一圆也是如此, 此处省略之) 圆的参数方程也将会被用到

$ x = r_0 * cos(A) + x_0

$ y = r_0 * sin(A) + y_0

现在, 设其中其中至少有一个交点 (没有交点的情况可以简单利用圆心距大于半径之和来判定), 换言之存在某个 $A_s$ 使得存在对应的点 $(x_s, y_s)$ 于两个圆的方程都成立, 即

Created at 2009-11-15 23:56:09

Permanent Link: /p/14/

Post tags:

Algorithm

Geometry

All 11

	Back to Tobary book
	Tobary book - Copyright (C) ZhePlus @ Bit Focus
	About