报数游戏(2)--【英雄会】

新年快乐!送上蛇年的最后一篇博客,迎接马年...

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,通过了

新年快乐!

(*∩_∩*)

报数游戏(2)--【英雄会】

上一篇:SRM 606 DIV2 1000 EllysCandyGame


下一篇:UVa 11361 Investigating Div-Sum Property / 数位DP