首页 > 分享 > 腾讯2019技术岗笔试花匠小Q 花匠小Q养了两种花，一种白花，一种红花，现在小Q用这些花进行摆放，摆放的时候连续的白花的数量只能是K的倍数（倍数可以是0），不然就会枯萎。现在给出a和b，小Q想知道长

腾讯2019技术岗笔试花匠小Q 花匠小Q养了两种花，一种白花，一种红花，现在小Q用这些花进行摆放，摆放的时候连续的白花的数量只能是K的倍数（倍数可以是0），不然就会枯萎。现在给出a和b，小Q想知道长

花匠小妙招
2024-11-28 20:00

花匠小Q养了两种花，一种白花，一种红花，现在小Q用这些花进行摆放，摆放的时候连续的白花的数量只能是K的倍数（倍数可以是0），不然就会枯萎。现在给出a和b，小Q想知道长度为[a,b]的摆花方案中有多少种。
在这里插入图片描述

分析：
1.设当前长度为X，X属于[a,b]之间。
2.当X<K,只能全是红花，一种
3.当X=K，只能全是白花或者全是红花。
4.当X>K，需要分情况，
1.白花为0 * k朵，
2.白花为1 * k朵，
3.白花为2*k朵……
这时候，把k朵白花视为一朵，当前问题简化为下面的例子：

例：将5盆红花和3盆黄花摆在一排，这些花除了颜色，其他都一样，要求黄花不相邻，共有最终多少种方法? 解析：因为黄花要求不相邻，所以考虑插空法。先把红花摆好，红花长得一样，所以无论怎么摆放都是一样的，只有一种方法。因为黄花也长得一样，所以将黄花插空进去红花的6个空，共有C3 6=20种方法。 123456

但是这里的白花是可以相邻的，所以：
在这里插入图片描述

例：将3盆红花和2盆黄花摆在一排，这些花除了颜色，其他都一样，共有最终多少种方法? 解析：考虑含有可重复元素的排列问题。按照公式：有（5！）/（3！2！）=10种，完全ok rrrhh hhrrr rhrhr rhrrh rrhrh hrhrr rrhhr hrrhr rhhrr hrrrh 1234567

接下来写代码就很简单了：
我写了过程的输出，便于理解。
在这里插入图片描述

#include <stdio.h> #include <stdlib.h> int calculateN(int num) { int i=1; int calcu=1; do { calcu*=i; i++; } while(i<=num); //printf("%d n!=%dn",num,calcu); return calcu; } int main() { int t=0; int k=0; scanf("%d %d",&t,&k); int flowerlength[2000][2]; int i=0; for(i=0; i<t; i++) { scanf("%d %d",&flowerlength[i][0],&flowerlength[i][1]); } for(i=0; i<t; i++) { int x=0; int sum=0; for(x=flowerlength[i][0]; x<=flowerlength[i][1]; x++) { printf("对于区间：[%d,%d],当前x值：%dn",flowerlength[i][0],flowerlength[i][1],x); if(x<k) { sum+=1; printf("%d朵花,%d 朵红花,组合数：%dn",x,x,sum); } else if(x==k) {sum+=2; printf("%d朵花,%d 朵白花，%d 朵红花,组合数：%dn",x,x,x,sum); } else if(x>k) { int n=0;//对白花的数量进行限制 while(n*k<=x) { int cal=calculateN(n+x-n*k)/(calculateN(n)*calculateN(x-n*k)); sum+=cal; printf("视为%d朵花的组合，%d 组白花，%d 朵红花,组合数：%dn",n+x-n*k,n,x-n*k,cal); n+=1; } } else { printf("error!n"); } } printf("sum:%dn",sum); } return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970