AKSZ-枚举算法
2024-03-17 17:31:18
发布于：广东
12阅读
0回复
0点赞
进制转换
常见的计算机进制
int x=0b111; // 二进制数
int y=0711; // 8进制数
int z=0x34; // 16进制数
十进制转n进制
小数部分：乘n取整，顺序排列
整数部分：除n取余，逆序排列
枚举算法
三要素：枚举对象；枚举范围（重要）；判定条件；
递归套循环
const int maxn=10;
int a[maxn];
void dfs(int x){
if(x==n){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
puts("");
return;
}
for(int i=1;i<=k;i++){
int ok=1;
for(int j=1;j<=x;j++){
if(a[j]==i){
ok=0;
break;
}
}
}
if(ok){
a[x+1]=i;
dfs(x+1);
}
}
全排列O（n）
do{
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+n));
排列时间复杂度：O(n!)
c++测试时间的代码
clock_t start,end;
start=clock();
//主程序
end=clock();
printf("%.2lf MS",double(end-start)/CLOCKS_PER_SEC*1000);
枚举子集
void solve(int x){
for(int i=0;i<n;i++){
if((1<<i) & x){
cout<<a[i]<<" ";
}
}
}
int main(){
int n;
cin>>n;
for(int i=0;i<=(i<<n)-1;i++){
solve(i);
}
埃式筛法
void init(){
for(int i=2;i<=n;i++){
if( !p[i]){
for(int j=2*i;j<=n;j+=i){
p[j]=1;
}
}
}
}
有帮助，赞一个