通过位运算来枚举子集的疑惑
查看原帖
通过位运算来枚举子集的疑惑
818226
alma楼主2022/12/6 15:16

背景

根据《深入浅出》书中的表述,题目可以表述为:考虑如何枚举由n个元素组成的集合中含由k个元素;如果用n位二进制数表示子集,那么目标就是找到所有恰好只有k个1的二进制数。

因此书中给出的AC代码为下

#include<iostream>
#include<cstdio>
using namespace std;
int num[30];
bool check(int n){
    if(n<2)return false;
    for(int i=2;i<=n/i;i++)
        if(n%i==0)return false;
    return true;
}
int main(){
    int n,k,m=0,cnt=0;
    cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",&num[i]);
   //for(int i=1;i<=n;i++)scanf("%d",&num[i]);为什么不能这样改?
    int U=1<<n;
    for(int S=0;S<U;S++){
        if(__builtin_popcount(S)==k){
            int sum=0;
            for(int i=0;i<n;i++){
            //for(int i=1;i<=n;i++){为什么不能这样改?
                if(S&(1<<i))sum+=num[i];
            }
            if(check(sum))cnt++;
        }
    }
    cout<<cnt<<endl;

    return 0;
}

我的疑惑

在上面的AC代码中,如果把两处for()语句(代码中注释的部分)改为for(int i=1;i<=n;i++),结果就会出错。这是为什么?有没有大佬可以赐教一下?

2022/12/6 15:16
加载中...