star

搜索

RSS

RSS Link

计数器

139737

N皇后问题

2010年8月10日 00:22 | Comments(22) | Category:C语言 | Tags:

#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:

/*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$$的大小范围为例。