赵天泽

用户名：uq_99534628713

访问量：2972

签　名：

全体目光向我看齐，我宣布个事，我是个傻⚪

等　　级
排　　名	6828
经　　验	1375
参赛次数	2
文章发表	9
年　　龄	0
在职情况	学生
学　　校	sumhs
专　　业	大数据

　　自我简介：

已退站

TA的其他文章

C语言dp算法
浏览：388

链表解法，但会运行错误
浏览：421

你可能喜欢

C语言二进制问题，思路清晰（一生之敌——时间超限）

　　作者: 赵天泽　　　　发表时间：2022-04-14 01:45:13 浏览：757　|　评论：0　

原题链接：蓝桥杯2021年第十二届国赛真题-二进制问题

#题解（后文有思路）：
这个题大概是自我从汉诺塔入门递归算法和对分法求最大子序列以来，用脑子用的最多的题。虽然10%的时间就想出了算法思路，然后90%的时间来处理时间超限和优化算法，而且我的错误百分比中时间超限快追上答案错误了。
```c
#include<stdio.h>
long long C(int n, int k)
{
	if (k > n||k<=0||n<=0)
		return 0;
	long long ans = 1;
	for (int i = 1; i <= k; i++)
		ans = ans*((long long)n - (long long)k + (long long)i) / (long long)i;
	return ans;
}

unsigned long long digui(unsigned long long n, int k)
{
    unsigned long long sum1 = 0, sum2 = 0, sum = 0, t = 0x8000000000000000;
    int i = 64;
    while (~n & t) 
    {
        t = t >> 1;
        i--;
    }
    if (k == 1) 
		return i;
    if ((i - 1) < k) 
		return 0;
    sum1 = C(i - 1, k);
    sum2 = digui(n - t, k - 1);
    sum = sum1 + sum2;
    return sum;
}

int main()
{
    unsigned long long n, sum = 0;
    int k;
    scanf("%lld%d", &n, &k);
    sum = digui(n, k);
    printf("%lld", sum);
	return 0;
}
```
#总体思路
看到题，首先排除正常做法，只有可能找规律才行得通。
再观察，找比N小且含有k个1的数，可以想到确定N二进制的位数后，再用组合数，组合数的代码放在后面。很容易想到N二进制的最高位为1，否则就不是最高位了
然后新的问题来了，设N的位数为n，Cnk的话，可能会排列出大于N的数，那么怎样能只排列比N小的数呢？
首先，将小于N的数分为两类，一类为最高位为0，即第n位为0，这一类一定小于N，所以很好求；另一类最高位，即第n位为1，这一类可能存在大于N的，所以要想办法筛选。既然第n位为1，那么剩下要排列的个数就为k-1了，然后找到N的第二个为1的位数，设这个位数为n2，我们只要在n2位内排列k-1个1即可，排列的方法再次重复以上步骤，直到要排列的1的个数只有一个，此时不需要再次分类。不断重复同一个做法，所以可以使用递归。

```c
//只是展示大体思路的代码，并不能执行
unsigned long long digui(unsigned long long n, int k)
{
	if (k == 1) 
		return i;
	if ((i - 1) < k) 
		return 0;
	sum1 = C(i - 1, k);
	sum2 = digui(n - t, k - 1);
	sum = sum1 + sum2;
	return sum;
 }
```
#求最高位
最开始的思路是用次方数，即pow函数比较，但此方法计算量大，效率比较低，所以排除
然后想到用数组以二进制的形式存储N，但需要的数组长度很长，处理起来也很麻烦，效率依然低下，排除
最后想到了位操作，用&运算与>>运算可以很容易找到N的最高位，不断将t右移，然后与N进行&运算，最终得到第一个1的位数。代码如下：
```c
unsigned long long  t = 0x8000000000000000;//0x表示t为16进制数，8表示t的开头四位为1000，后面每一个0表示二进制的四个0，也就是二进制的1后面跟63个0
int i = 64;
while ((N & t)==0) //若n当前的位数上不是1，就会继续循环，直到找到第一个为1的位数
	{
		t = t >> 1;
		i--;
	}
```
#组合数函数
求组合数有很多办法，但是首先应该排除照搬公式的办法，因为要处理多个阶乘，计算量非常大
我思考了很久，想到了很多方法，因为我觉得时间超限是因为这里的算法不够巧妙（题解中的方法为方法三）

方法一：此方法用递归，为了提高效率，会将之前运算过的组合数存储起来，若调用运算过的组合数时，便直接返回。
```c
long long f[70][70] = { 0 };//f[n][k]即C(n,k)
long long C(long long n, int k)
{
	if (f[n][k] != 0)
		return f[n][k]
	if (n < k || n < 0 || k < 0)
		return 0;
	if (k == 0)
	{
		f[n][k] = 0;
		return f[n][k]
	}
	if (n == k)
	{
		f[n][k] = 1;
		return f[n][k]
	}
	f[n][k] = C(n - 1, k) + C(n - 1, k - 1);//组合数的递推公式，忘记的可以百度
}

```
方法二：将方法一改为了循环
```c
long long f[70][70] = { 0 };
long long int C(int n, int k)
{
	int i, j;
	if (n < k || k < 0 || n < 0)
		return 0;
	if (f[n][k] != 0)
		return f[n][k];
	else
	{
		for (i = 2; i <= p; i++)
			for (j = 1; j <= k; j++)
			{
				if (j > i)
					break;
				f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
			}
		return f[n][k];
	}
}
```
方法三：将公式整理后，可以得到（n-k+i）/i的阶乘，i从1到k。正是题解中使用的方法。
```c
long long C(int n, int k)
{
	if (f[n][k] != 0)
		return f[n][k];
	if (k > n||k<0||n<0)
		return 0;
	long long ans = 1;
	for (int i = 1; i <= k; i++)
		ans *= (((long long)n - (long long)k + (long long)i) / (long long)i);
	return ans;
}
```
写到这我又个大胆的想法，把这个方法算出来的结果也存到数组里怎么样？不过是不是有点画蛇添足？

方法四：脑洞大开的想法，我都不好说这个算法是不是绕弯路了，就觉得挺离谱的,把乘法换成对数的加法。
```c
double C1(int n, int k)
{
	if (k > n）
		return 0;
	if (k > n/2)
		k = n-k;
	double s1 = 0;
	for (int i=n; i>n-k; i--)
		s1 += log((double)i);
	double s2 = 0;
	for (int i=1; i<=k; i++)
        s2 += log((double)i);
	return s1-s2;
}

double C(int n, int k)
{
	if (k > n)
		return 0;
	return exp(C1(n, k));
}
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

赵天泽

TA的其他文章

你可能喜欢

图形输出（Java代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

1268:P1001

C二级辅导-阶乘数列（C语言代码）

C语言二进制问题，思路清晰（一生之敌——时间超限）

评论区

精彩推荐

回文数字（C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-陶陶摘苹果2 （C++代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

赵天泽

TA的其他文章

你可能喜欢

图形输出 （Java代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

1268:P1001

C二级辅导-阶乘数列 （C语言代码）

C语言二进制问题，思路清晰（一生之敌——时间超限）

评论区

精彩推荐

回文数字 （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-陶陶摘苹果2 （C++代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

图形输出（Java代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

回文数字（C++代码）