位运算求子集树 - skyli

友情链接

最新评论

1. re: 优先队列用法
评论内容较长,点击标题查看
--tanti
2. re: 优先队列用法
给力！！
--***
3. re: pow函数的性能测试
Pow 函数要处理各种非整数次幂情况，比如0.5就等于开根号了，0.2就等于开5次方了。当然比直接乘慢的多。
--YYX
4. re: istringstream用法[未登录]
@gong
cin是标准输入，在std中已经声明了。
--mm
5. re: istringstream用法[未登录]
您好，为什么这里的getline(cin, line）中的cin没有定义就直接使用了呢？
--gong

阅读排行榜

评论排行榜

以前求子集树都是用回溯法，
今天在topcoder做SRM时学到一种求子集树的新方法：位运算。
第一重循环是枚举所有子集，共2^n个，即1 << n个
第二重循环求集合所有j个元素的值，0或1。
求一下1 & (1 << j)的值就可以知道它的原理。

#include<iostream>

using namespace std;

const int n = 4;

int x[n];

//回溯法

void backtrack(int t)

{

if(t >= n)

{

for(int i = 0; i < n; i++)

cout<<x[i];

cout<<endl;

}

else

{

for(int i = 0; i <= 1; i++)

{

x[t] = i;

backtrack(t + 1);

}

//位运算

void bitOperate()

{

for(int i = 0; i < (1 << n); i++)

{

for(int j = 0; j < n; j++)

{

if( (i & (1 << j) ) == 0)

x[j] = 0;

else

x[j] = 1;

}

for(int j = 0; j < n; j++)

cout<<x[j];

cout<<endl;

}

int main()

{

backtrack(0);

cout<<endl;

bitOperate();

return 0;

}

posted on 2007-07-22 02:59 beyonlin 阅读(1738) 评论(0) 编辑收藏引用所属分类: C++之路

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 一道算法题引发的动态内存管理的思考再谈子集树位运算求子集树字符串hash函数优先队列用法计数排序《C++ Primer》之读书笔记七插入排序泛型算法《C++ Primer》之读书笔记六《C++ Primer》之读书笔记五

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜