蓝桥杯题目——带分数中包含的方法与思想(上)
前言
本文介绍蓝桥杯题目——带分数,并且对其中包含的方法与思想进行总结,本文是上半部分。
参考题目:带分数
解题思路
本题虽麻烦,但有一个思想上很简单的做法(代码上很复杂),设N=a+b/c。
第一步先将1~9全排列,把每一种情况中的9个数分成三份,分别令其为a,b,c。
这样,你就获得了一组满足条件的abc,然后让a+b/c与N判断一下是否相等,每出现一个相等的情况,就让计数变量+1,打印计数变量,就能得出最后的答案。
但是,因此也引出了第一个问题,怎样把1~9全排列? 亦或是更具一般性的说法,怎样把1~n全排列?
全排列方法
递归实现
递归实现的思想很简单,拿本题举例,一共有九个位置,每个位置放一个数,第一个位置有9种情况,第二个位置有8种情况,第三个位置有7种情况.....
因为每个数只能使用一次,所有你在某个位置存在一个数据时,要先判断这个数有没有被用过。
创建arr数组保存每一种情况,创建used数组,利用哈希表的思想记录每个数是否被用过,创建step变量记录当前正在操作第几个位置,输入一个n代表要全排列1~n。
注意: 这四个变量或数组的作用域须为全局,或用static修饰。
int arr[10];
int used[10];
int step = 0;
int n = 0;
int main()
{
scanf("%d", &n);
A(n);
return 0;
}
随后,我们在函数A内部对每个位置都进行1~n的枚举,枚举好一个数了,就在used数组中记录这个数已经被用过了,同时让step+1,代表我们该枚举下一个位置了。
注意: 枚举的时候不要忘记判断这个数是否被用过,且递归返回之时不要忘记恢复现场。
void A(int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
if (used[i + 1] == 0)
{
used[i + 1] = 1;
arr[step] = i + 1;
step++;
A(n);
step--;
used[i + 1] = 0;
}
}
}
最后,当step与n相等,即所有的位置都选完数了,打印arr数组即可。(设step=8,则arrstep为第九个数,因此本题中step为9时满足打印条件)
void A(int n)
{
if (step == n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return;
}
int i = 0;
for (i = 0; i < n; i++)
{
if (used[i + 1] == 0)
{
used[i + 1] = 1;
arr[step] = i + 1;
step++;
A(n);
step--;
used[i + 1] = 0;
}
}
}
如此,便完成了1~n的全排列,如果你想对这些排列数进行使用,直接把打印函数换成需要的函数进行操作即可。
循环实现
至于用循环实现1~n全排列,其本质就是一遍遍地遍历,n较小时使用比较合适,推荐在3以下使用,再大的话代码就会很冗杂。
伪代码如下:
int main()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
for (int k = 0; k < 9; k++)
......
return 0;
}
组合数方法
上文说到的解题方法中,当我们排列出了一种情况后,接着要把这种情况的9个数分成三部分,分别令其为a、b、c,那么,就引出了下一个问题,怎样分割这九个数呢? 亦或更具一般性的说法,怎样将数组中的n个数分割成不同的部分?
中学数学中有个章节叫排列组合,其中有一种解题方法叫做隔板法,即把n个数排成一排,往它们之间放隔板,每放一个隔板就能把一排数分成两部分,每加一个隔板,就多一个部分,像这样:
这里,我有九个球。
九个球之间共有八个空,如果要放3个隔板,我们只需要在8个空之间选择3个即可,也就是组合数C83。
如图,放了三个板子,把原来一排的球,分成了四个部分。
因此,若想把1~9分成三部分,只需要在其间的空内,放入两个隔板即可,也就是组合数C82。
循环实现
相比排列,组合因其的性质,在大多数情况下更适合用循环完成。
C97=C92,C86=C82...
与排列相比,组合数多数情况可以凑出一个较小的m,因此,即使用循环写,代码也不会太复杂。
当然,如果m无论怎样凑也到不了3以下,该用递归还得用递归。
以本题举例,在8个数中选取2个数,用循环遍历即可:
注意: 利用循环完成组合数的前提是已经知道n和m分别是多少,如果n和m还等着用户去输入,那么循环实现就不可取了。
int main()
{
int i = 0;
for (i = 1;i<=7; i++)
{
int j = 0;
for (j = i + 1; j <= 8; j++)
{
printf("%d %d\n", i, j);
}
}
return 0;
}
递归实现
首先创建arr存储枚举的信息,创建step记录当前正在枚举第几位,创建fir当前位置从第几个数开始枚举,创建n表示总数,创建m表示需要组合的个数,创建num表示当前还需要选取几位。
int arr[10];
int step = 0;
int fir =0;
int n = 0;
int m = 0;
int num = 0;
int main()
{
scanf("%d %d", &n, &m);
num = m;
C(n, m);
return 0;
}
随后从fir开始对arrstep开始枚举,枚举好一位后step要+1,表示要开始枚举下一位了。
fir赋为当前位被枚举值,以便于下一位的枚举时不包含上一位的数。例如此时的arrstep被赋为1,则就让fir等于1,那么下一位的枚举时,就会从arr[1]开始,即第二个数。
每枚举成功一个位置,就要让num--,当num等于0时,代表已经枚举完毕,可以打印了。
下面代码中有一部分代表剪枝,其中n-fir表示还有几个数可以选择,num表示还需要选几个数,如果满足前者小于后者,则无解,可以先返回。
例如:如果你第一个位置枚举一个8,那么你在下一个位置时将从9开始枚举,但是n也是9,因此只有一个数可以用了,但是num还是3,所以这种情况无解。
void C(int n, int m)
{
if (n-fir<num)//剪枝,加快速度
{
return;
}
if (num==0)
{
int i = 0;
for (i = 0; i < m ;i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
int i = 0;
for (i = fir; i < n; i++)
{
arr[step] = i + 1;
step++;
fir = i + 1;
num--;
C(n, m);
num++;
step--;
}
}
如此,便知道如何实现从八个空中选两个空,插入隔板了。
利用组合数找出两个下标,利用这两个下标进行分割即可。
浮点转整型思想
众所周知,计算机中的浮点型是用SME方法存储,其精度是有限的,不能准确的表示一个小数,因此判断时会有误差。
所以,遇到式子包含浮点型数据时,可以优先考虑能否把一个浮点型式子,转换成都是由整型构成的式子,这样就可以准确无误了,例如本题:
可以转化为:
这样就完全是整型的式子,也不用考虑精度丢失的问题。
感谢您的阅读与耐心~
相关文章
- EasyDSS提示所配置路径不能包含中文的处理方法
- Python index()方法:检测字符串中是否包含某子串
- 解决Linux系统无法获取IP的方法(linux无法获取ip)
- 上载EXCEL到SAP系统的方法之一详解编程语言
- 空值解决Oracle字段包含空值的方法(oracle字段包含)
- Mysql中定义数组变量的方法(mysql定义数组变量)
- Oracle:检查表是否存在的方法(oracle表是否存在)
- 解决方法MySQL如何查询不包含某个字的数据(mysql 不包含某个字)
- 困扰JSP的一些问题与解决方法
- asp多关键词搜索的简单实现方法
- VC++开发中完美解决头文件相互包含问题的方法解析
- Jquery修改页面标题title其它JS失效的解决方法
- PHP数组遍历知识汇总(包含遍历方法、数组指针操作函数、数组遍历测速)
- C#实现判断字符串中是否包含中文的方法
- Mysql字符串字段判断是否包含某个字符串的2种方法