star

分类

随机文章

最新留言

最新评论

搜索

RSS

RSS Link

计数器

143620

N皇后问题

2010年8月10日 00:22 | Comments(22) | Category:C语言 | Tags:c 二进制 位运算 数学

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
static int upperlim, sum;
 
void binqueen(int row, int ld, int rd)
{
    int pos, p;
    if(row != upperlim)
    {
        pos = upperlim & ~(row | ld | rd);
        while (pos)
        {
            p = pos & -pos;
            pos -= p;
            binqueen(row+p, (ld+p)<<1, (rd+p)>>1);
        }
    }
    else sum++;
}
 
 
int main(void)
{
    int n;
    scanf("%d", &n);
    upperlim = (1<<n) - 1;
    binqueen(0, 0, 0);
    printf("%d", sum);
    return 0;
}

求一个数的二进制有多少个1？

2010年8月03日 02:29 | Comments(1) | Category:C语言 | Tags:c 分治 位运算 二进制

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*author:Star date:2010-08-02*/
#include <stdio.h>
#include <assert.h>
 
int CntBit(unsigned int n)  //分治思想
{
    n = ((n & 0xaaaaaaaa) >> 1 ) + (n & 0x55555555);
    n = ((n & 0xcccccccc) >> 2 ) + (n & 0x33333333);
    n = ((n & 0xf0f0f0f0) >> 4 ) + (n & 0x0f0f0f0f);
    n = ((n & 0xff00ff00) >> 8 ) + (n & 0x00ff00ff);
    n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff);
    return n;
}
 
int main(int argc, char *argv[])
{
    unsigned int N;
    int i, j;
    scanf("%u", &N);
    printf("%u:", N);
    i = CntBit(N);
    assert(i >= 0 && i <= 32);
    for(j = 31; j >= 0; --j)
        printf("%d", N&(1<<j) ? 1 : 0);  
    printf("\nhave %d bit that are \'1\'", i);
    return 0;
}

这里数以$$2^{32}-1$$的大小范围为例。

对于给定的N,求N！结果的位数

2010年8月01日 05:02 | Comments(606) | Category:C语言 | Tags:阶乘 位运算 数学 分治 斯特林

根据斯特林公式：$$n!$$~$$\sqrt{2\pi n}(\frac{n}{e})^n$$

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*calculate the number of digits in the factorial of the integer N.date:2010-07-31*/
#include <stdio.h>
#include <math.h>
#include <assert.h>
int main(void)
{
    const double PI = acos(-1.0);
    int T;
    while(1)
    {
        scanf("%d", &T);
        assert(T > 0 && T < (1<<30));
        printf("%d\n", (int)((T*log(T) - T + 0.5 * log(2*T*PI) ) / log(10)) + 1);
    }
    return 0;
}