About
RSS

Bit Focus


划分问题与连续自然数幂和之通项公式

无限区间上 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 对自然数幂和公式的也做过研究, 他的方式是递推的, 运动量没有这个暴力方法大.

Permanent Link: /p/45 Load full text

Post tags:

 Algebra
 Algorithm
 Geometry

闰年判定

已经转移到

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

Permanent Link: /p/25 Load full text

Post tags:

 Algorithm

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

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

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

其中 point_tcircle_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 <stdio.h>

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)$ 于两个圆的方程都成立, 即

Permanent Link: /p/14 Load full text

Post tags:

 Algorithm
 C
 Geometry

0 Page 1


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site