3
30
2013
74

负整数的整除和取余运算

负整数间是怎么整除和取余数的呢?

数学上貌似没定义,但计算机确实能算。于是就试了试,想总结一下规律。

一不小心发现,C/C++ 和 Python 下的结果是不同的:

  C/C++ Python 精确值
-14/3 -4 -5 -4.67
-14%3 -2 1 /
14/-3 -4 -5 -4.67
14%-3 2 -1 /
-14/-3 4 4 4.67
-14%-3 -2 -2 /

总结规律如下:

  1. 两种语言中,商和余数都符合 被除数=商x除数+余数 这一数学规律。
  2. 两种语言中,整除的方法不同:C/C++ 是向零取整(负数向上、正数向下取整),Python 是下取整

 

以 n/3 和 n%3 为例,看看这两种处理方法的区别。

C 的情况,两种运算结果都关于0对称和反号

n -5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5
-1 -1 -1 0 0 0 0 0 1 1 1
余数 -2 -1 0 -2 -1 0 1 2 0 1 2

Python 的情况,运算结果是完全连续的:

n -5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5
-2 -2 -1 -1 -1 0 0 0 1 1 1
余数 1 2 0 1 2 0 1 2 0 1 2

不知道那种在数学上更好用。个人觉得 Python 的处理方式更优美一些吧。

 

至于其他语言的处理方法,应该也出不了这两种。我所知道的:

  • C/C++ “向零取整式整除”:C/C++、Java、bash
  • Python “下取整式整除”:Python、Perl、Lua
Category: 计算机 | Tags: python c/c++ 编程 数学
9
10
2011
4

凸包郁闷死我了

郁闷啊郁闷,写了两个凸包的题目,都折戟在一两个NB数据上了。

tyvj上P1462的程序,赤果果的求凸包。自己写的Graham扫描法,极角顺序,从最下最右的点开始:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

typedef struct {
    double x, y, tg;
} coord;

// 算极角
inline double calc_tg (const coord b, const coord n)
{
    double ret = atan2(n.y-b.y, n.x-b.x);
    return ret >= 0 ? ret:ret+2*M_PI;
}

// 判断是否左转
#define tleft(a,b,c) \
        (((b).x-(a).x)*((c).y-(a).y)-((c).x-(a).x)*((b).y-(a).y) <= 0.0)

// 快排之比较
int comp (const void *pa, const void *pb)
{
    const coord *a = (const coord*)pa, *b = (const coord*)pb;
    if (a->tg > b->tg)
        return 1;
    else if (a->tg != b->tg)
        return -1;
    else
        return a->x > b->x ? 1:-1;
}

int main ()
{
    int n, i, stktail;
    coord *p, **stk, minc = {0.0, 1.0E22};

    // 读入数据
    scanf("%d", &n);
    p = malloc(n*sizeof(coord));
    stk = malloc(n*sizeof(coord*));
    for (i=0; i<n; i++)
    {
        scanf("%lf %lf", &(p[i].x), &(p[i].y));
        if ((p[i].y < minc.y) ||
           ((p[i].y == minc.y) && (p[i].x < minc.x)))
            minc = p[i];
    }

    // 求凸包
    for (i=0; i<n; i++)
        p[i].tg = calc_tg(minc, p[i]);

    qsort(p, n, sizeof(coord), comp);

    stk[0] = p;
    stk[1] = p+1;
    stk[2] = p+2;
    stktail = 2;
    for (i=3; i<n; i++)
    {
        while (stktail >= 1)
        {
            coord *base = stk[stktail-1],
                  *last = stk[stktail];
            if (tleft(*base, *last, p[i]))
                stktail--;
            else
                break;
        }

        stk[++stktail] = p+i;
    }

    while (stk[stktail]->tg == stk[stktail-1]->tg)
        stktail--;

    // 按要求的顺序输出
    int st = 0;
    double minx = stk[0]->x;
    for (i=stktail; i>=0; i--)
    {
        if (stk[i]->x < minx)
            minx = stk[i]->x,
            st = i;
        else
            break;
    }

    i = st;
    do
    {
        printf("%.4lf %.4lf\n", stk[i]->x, stk[i]->y);
        if (--i < 0)
            i = stktail;
    } while (i != st);

    return 0;
}

运行结果:

#01: Accepted (0ms, 196KB)
#02: Accepted (0ms, 196KB)
#03: Accepted (0ms, 200KB)
#04: Accepted (0ms, 196KB)
#05: Accepted (0ms, 200KB)
#06: Accepted (0ms, 332KB)
#07: Accepted (293ms, 2936KB)
#08: Wrong Answer (637ms, 2936KB)
#09: Accepted (0ms, 224KB)
#10: Accepted (0ms, 304KB)
#11: Time Limit Exceeded (?, 2388KB)

错的那个可能是精度问题(但我尝试了,long double也过不去,所以也可能是写错了)。

最后一个超时。我已经各种优化了:把C++程序改成C,动态申请内存(不清0了),手动define内联函数,使用double而非long double…… 但还是超时。难道是qsort太慢了?

郁闷啊。可能我的实现比较烂,求神牛指导实现细节。

Category: 计算机 | Tags: 算法 凸包 C/C++ 编程 OI

| Theme: Aeros 2.0 by TheBuckmaker.com