首页 > 试题广场 >

#include #include...

[填空题]
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE = 10000;
const int LENGTH = 10;
int n, m, a[SIZE][LENGTH];
int h(int u, int v) {
    int ans, i;
    ans = 0;
    for (i = 1; i <= n; i++)
        if (a[u][i] != a[v][i])
            ans++;
    return ans;
}
int main( ) {
    int sum, i, j;
    cin >> n;
    memset(a, 0, sizeof(a));
    m = 1;
    while (1) {
        i = 1;
        while ((i <= n) && (a[m][i] == 1))
            i++;
        if (i > n)
            break;
        m++;
        a[m][i] = 1;
        for (j = i + 1; j <= n; j++)
            a[m][j] = a[m - 1][j];
    }
    sum = 0;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
            sum += h(i, j);
    cout << sum << endl;
    return 0;
}

输入:7
输出:1
while(1){}部分相当于一般状压干的枚举0~2^n-1的事
h()是在两两统计不同位的数量
数有2^n个
两个for就是2^n*2^n
每个数有n位
所以一共有2^n*2^n*n次if
0 1不相同概率是1/2
所以答案是
2^n*2^n*n/2
n=7带入
ans=57344
发表于 2019-10-18 13:27:18 回复(0)