首页 > 代码库 > 一天一道算法题---6.8--数学题

一天一道算法题---6.8--数学题

感谢微信平台:一天一道算法题---每天多一点进步----明天 考离散了

明天 高考结束了

看上去都是 好日子.....

上题目了:

  求出用1 , 2 ,5这三个数不同个数的组合的和为100的组合个数。

  如:100个1是一个组合;5个1+19个5是一个组合

OK:--- 几天折磨后 终于来了个 我能做的....

PS:  关于6.7--栈中O(1)实现min函数等的  应该会在今晚贴上..

平台上关于这题的分析很到位:

  设 1的个数为X 2的个数为Y 5的个数为Z 和为100的组合总数为cnt

1. 最容易实现的 应该是o(n^3) 1 2 5分别3层for .... 这样去做的话 在我们学校的C++期末考试 应该是可以拿分的(真讽刺...) 我这边就不给出它的伪代码了..

2.

x+2y+5z = 100;

x + 5z = 100-2y; // 所以 x+5z一定是偶数

z = 0    x = 100,98,96……,0  ---- 100以内的偶数

z = 1    x = 95,93,91……,1 --- 95以内的奇数

z = 2    x = 90,88,86……,0 --- 90以内的偶数

…… …… ……

z = 19   x = 5 3 1

z = 20   x = 0  ---  数量为1

 

这有2个很重要的计算公式:

 

某个偶数m以内的偶数个数(含0)的计算公式为:

  m/2+1 = (m+2)/2

某个奇数n以内的奇数个数的计算公式为:

  (n+2)/2

so the cnt‘s sum:

 

int cnt = 0;

for( int i = 0 ; i<=100 ; i+=5 )

{

  cnt+=(i+2)/2;

}

cout<<cnt<<endl;

 

today:

  我自倾怀 君且随意

  有生之年 欣喜相逢