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;
}
评论