首页 > 试题广场 >

猜数游戏

[编程题]猜数游戏
  • 热度指数：2049 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛和羊羊在玩一个有趣的猜数游戏。在这个游戏中,牛牛玩家选择一个正整数,羊羊根据已给的提示猜这个数字。第i个提示是"Y"或者"N",表示牛牛选择的数是否是i的倍数。
例如,如果提示是"YYNYY",它表示这个数使1,2,4,5的倍数,但不是3的倍数。
注意到一些提示会出现错误。例如: 提示"NYYY"是错误的,因为所有的整数都是1的倍数,所以起始元素肯定不会是"N"。此外,例如"YNNY"的提示也是错误的,因为结果不可能是4的倍数但不是2的倍数。
现在给出一个整数n,表示已给的提示的长度。请计算出长度为n的合法的提示的个数。
例如 n = 5:
合法的提示有:
YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY
YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY
所以输出12

输入描述:
输入包括一个整数n(1 ≤ n ≤ 10^6),表示已给提示的长度。


输出描述:
输出一个整数,表示合法的提示个数。因为答案可能会很大,所以输出对于1000000007的模
示例1

输入

5

输出

12
算法知识视频讲解
添加回答
Java
越努力越幸运。头像 越努力越幸运。
分享一个思路，如果输出排成一个数列A，那么可以看出规律
可分4种情况：(n为数列下标)
1.n=1
2.n为质数
3.n为素数的幂次
4.n为其他情况
4种情况对应规律：
1.A(1)=1
2.A(n)=2*A(n-1)
3.A(n)=A(n-1)*(j+1)/j     //  其中 i的j次方等于n,i为质数  例如8是2的3次方，所以n=8时，A(8)=A(7)*4/3
4.A(n)=A(n-1)
有一个缺点是这样写代码可能会使算法复杂度增大,我试着写了下，很可惜运行超时
======================================================================
import java .util.Scanner;
public class Main{
public static void main(String [] args){
int count=1;
Scanner input=new Scanner(System.in);
int n=input.nextInt();
for(int i=2;i<=n;i++){
if(n==1){
count=count;
}else if(isPrime(i)){
count=2*count;
}else if(Method(i)>1){
count=(int) (count*Method(i));
}else{
count=count;
}
}
System.out.println(count);
}
//当n为质数的幂次的情况
public static double Method(int N){
for(double i=2;i<N;i++){
for(double j=2;j<=N;j++){
if(Math.pow(i,j)==N){
return (j+1)/j;
}
}
}
return 0;
}
//判断n为质数的情况
public static boolean isPrime(int N){
boolean flag=true;
if(N<2){
return false;
}else{
for(int i=2;i<N;i++){
if(N%i==0){
flag=false;
break;
}
}
}
return flag;
}
}
======================================================================
如果思路有错或者代码有可以优化的地方，还请大佬指点指点。


编辑于 2017-08-13 21:23:49 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 动态规划 测试开发工程师 数学 大数据开发工程师 Java工程师 牛客
来自：【2017】牛客模考编...
难度：
1条回答 11225浏览

热门推荐

通过挑战的用户

相关试题

猜数游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号