新年快乐!送上蛇年的最后一篇博客,迎接马年...
N个人(编号1-N),站成一排,进行报数游戏。报数过程可能进行很多轮,有如下规则:
(1) 如果剩余人数不超过3个人,则游戏结束。
(2) 大家报数,然后留下报奇数的人从第一个人继续游戏,或者留下报偶数的人继续游戏。
重复如此(1)(2)两步骤,到游戏结束。
问:最终剩下的三人组有多少种情况?(注意是三人组,例如如果最后剩下2个或者1个人,不计入结果中)。
输入n, (0<n<=10000000) ,输出最终结果。
闲暇时间来刷刷题,这是昨天看到的,感觉这题还不错,能力范围之内,规则很简单,
(1) 如果剩余人数不超过3个人,则游戏结束。
(2) 大家报数,然后留下报奇数的人从第一个人继续游戏,或者留下报偶数的人继续游戏。
若是三个人则统计加1,一个人,两个人则不计入。例如5,奇数为1,3,5计入,2,4不够则不计;
了解到题意后,即可进行操作了,输入n;
若n是偶数,则报数结束之后有n/2是报出奇数的,有n/2是报出偶数的,进行判断,继续进行报数;
若n是偶数,则报数结束之后有n/2 + 1是报出奇数的,有n/2是报出偶数的,进行判断,继续进行报数;
得出递归:
int howmany (int n) { static int count; if(n == 3) //三人组 count++; else if(n > 3) // { if(n % 2 == 0) //当人数为偶数 { howmany(n/2); //取奇偶数 howmany(n/2); // } else //奇数 { howmany(n/2+1); //取奇 howmany(n/2); //偶 } } else ; return count; }
刚开始还担心递归内存可能会出现问题,但是把10000000都测试了,没问题;
满心欢喜的交上去...结果很尴尬啊,连4这个测试点都未过;可是算来算去4这个测试点都不会出现问题啊,带着这个遗憾过了昨晚,今天再次提交了一遍,依然不对...
跑到交流群里面质疑去了,感谢@绿色夹克衫的倾情提醒,"缓存的问题..."
以前从未考虑过这个问题,认为hero的测试点是一个一个的将数据代入的,即每运行一次程序代入一个数据,发现是个误区,main里面应该是个while循环,一次运行程序,不断测试数据;
所以,将递归修改了:
#include<stdio.h> #include<stdlib.h> int howmany (int n) { int *dp = (int *)malloc(( n + 1 ) * sizeof(int)); int i; dp[1] = 0; //一个人 dp[2] = 0; //两个人 dp[3] = 1; //三个人 for(i = 4; i <= n; i++) { if (i % 2 == 0) //偶数个 { dp[i] = dp[i / 2] + dp[i / 2]; //奇偶 } else //奇 { dp[i] = dp[i / 2 + 1] + dp[i / 2]; // } } return dp[n]; } //start 提示:自动阅卷起始唯一标识,请勿删除或增加。 int main() { printf("%d",howmany(8)); } //end //提示:自动阅卷结束唯一标识,请勿删除或增加。非递归的程序,没用静态变量或是全局变量,不存在数据的缓存的问题,so,通过了
新年快乐!
(*∩_∩*)