4．满足条件的m的个数 给出一个数字n和k，请找出有多少个不同的整数m满足： 1） m<2^n 2） m>=0 3） |f(m,n)|<=k 其中f(x,n)的定义如下： f(0,n)=n; f(x,n)=f([x/2],n),x为偶数 f(x,n)=f([x/2],n)-2,x为奇数   Input 每组一行，分别给定n,k(1<=n<=62,2<=k<=5)   Output 每组一行，给出满足条件的m的个数   Sample Input 1 2 4 3   Sample Output 2 14   主函数： #include <iostream> #include <time.h>   using namespace std;   int Fun(int n, int k);   int main() {     time_t startTime;     time_t endTime;     time(&startTime);       for (int i=1; i<=20; i++)         for (int j=2; j<=5; j++)             cout << i << "," << j << ": " << Fun(i, j) << "\t";     cout << endl;           time(&endTime);     cout << difftime(endTime, startTime) << endl;       getchar();     return 0; }   方法一：最直接的算法，根据题意递归求解。 int f(int x, int n) {     if (x == 0)         return n;     if ((x&1) == 0)           //x为偶数         return f(x/2, n);     else                    //x为奇数            return f(x/2, n) - 2; }   int Fun(int n, int k) {     long long max = 1<<n;     long long s = 0;         for (int m=0; m<max; m++)     {         if (abs(f(m, n)) <= k)             ++s;     }     return s; }   方法二：以空间换时间，把所有的f(m, n)值存储到一个数组中,然后查表；由于max的值太大了，不可能建立这么大的数组， 但是可以建立一个较小的数组（长度为400000）， 存储对应的f(m, n)值，当m较小时，可以直接查表； 当m >= M时，递归减小m的值，直到m < M ，然后查表。  void Table(int a[], int max, int n)//建立一个表，把所有的f(x, n)值存储到一个数组中 {     a[0] = n;     a[1] = n - 2;     for (int i=2; i<max; i++)     {         if ((i&1) == 0)             a[i] = a[i/2];         else             a[i] = a[i/2] - 2;     } }   long long Fun(int n, int k) {     const int M = 400000;     int a[M];    Table(a, M, n);//建表         long long max = 1<<n; //2^n     long long s = 0;         if (max < M)//当m较小时，可以直接查表     {         for (int m=0; m<max; m++)         {             if (abs(a[m]) <= k)                 ++s;         }     }     else//当m >= M时，递归减小m的值，直到m < M ，然后查表     {         for (int m=0; m<M; m++)//先计算前面小于M的部分         {             if (abs(a[m]) <= k)                 ++s;         }         long long t;         int f;         for (long long m=M; m<max; m++)//计算大于M的部分         {             f = 0;             t = m;             while (t >= M)//递归减小m的值，累积奇数的个数，如果是奇数要减去2             {                 if ((t&1) == 1)                     ++f;                 t >>= 1;             }             f = a[t] - f * 2;//查表             if (abs(f) <= k)                 ++s;         }     }         return s; }   补充一个算法： 这是http://www.programfan.com/club/的sarrow得到的算法。 由        | n;                 x == 0 f(x, n) = | f([x / 2], n);     x even number           | f([x / 2], n) - 2; x odd number 观察x的二进制数，用ones_in_x表示x的二进制数中'1'的个数，zero_in_x表示x的二进制数中'0'的个数， 可以得到 f(x, n) = n - 2 * ones_in_x         = n - 2 * (n - zero_in_x)         = 2 * zero_in_x - n 所以|f(m,n)|<=k 就是 | 2 * zero_in_m - n | <= k 即     -k <= 2 * zero_in_m - n <= k 也即 (n - k) / 2 <= zero_in_m <= (n + k) / 2 又  0 <= m < 2^n 即满足条件的m，其二进制数中'0'的个数应该大于等于i，小于等于j，其中       i = max{(n - k) / 2, 0};对(n - k) / 2应该四舍五入       j = max{(n + k) / 2, n}; 所以求满足条件的m的个数，相当于解一个排列组合题目：分别求从n个'0'取出k个'0'的取法， 其中（i<=k<<j），再求所有取法之和， 即  set_of_m = c(i, n) + ... + c(j, n);   int Gcd(int m, int n)//求最大公约数 {     int temp;         while (n > 0)     {         temp = m % n;         m = n;         n = temp;     }     return m; }   long long Combination(int m, int n)//求组合C(m, n)，注意不能直接按定义求，否则会溢出，先约分再除 {       int *pm = new int[m];     int *pn = new int[m];         for (int i=0; i<m; ++i)         pm[i] = i + 1;     for (int i=0; i<m; ++i)         pn[i] = n - i;         int g;     for (int i=0; i<m; ++i)         for (int j=0; j<m; ++j)         {             g = Gcd(pm[i], pn[j]);//求最大公约数             pm[i] /= g;             pn[j] /= g;         }             long long numerator = 1;     long long denominator = 1;         for (int i=0; i<m; ++i)         numerator *= pn[i];     for (int i=0; i<m; ++i)         denominator *= pm[i];             return numerator / denominator; }   long long Fun(int n, int k) {       int low  = (n < k) ? 0 : ((((n-k)&1) == 0) ? (n-k)/2 : (n-k)/2 + 1);     int high = (n < k) ? n : (n+k)/2;     long long s = 0;         for (int i=low; i<=high; ++i)         s += Combination(i, n);       return s; }

评论