牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。 最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。-笔试面试资料

这是qklbishe.com第18809 篇笔试面试资料
提供答案分析,通过本文《牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。

牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。   最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。 零葬
正常分析先枚举从1到4的情况
  1. 牛牛直接吃了,niu
  2. 牛牛吃一份草,羊羊吃了剩下的一份,yang
  3. 牛牛吃一份草,羊羊也只能吃一份,剩下一份牛牛吃,niu
  4. 牛牛吃4份草,niu

1~4的时候只有2是羊羊赢,其他的都是牛牛赢,所以对于牛牛而言,如果此时有n份草摆在它面前,它可以从1开始尝试n以内的4的次幂:4,16,64,……。然后把剩下的草扔给羊羊,然后羊羊重复这个步骤。

于是写了个递归版本如下:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException;  public class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int t = Integer.parseInt(br.readLine());         for(int i = 0; i < t; i++){             int n = Integer.parseInt(br.readLine());             System.out.println(winner(n));         }     }          private static String winner(int n) {         if(n < 5) return n == 2? "yang": "niu";         int base = 1;         // 牛牛不断尝试4的次方         while(base <= n){             // 牛牛吃base份然后往下扔给羊羊             if(winner(n - base).equals("yang")) return "niu";             // 防止乘以4后溢出             if(base > n / 4) break;             base *= 4;         }         // 尝试了各种方案牛牛都没赢,则羊羊赢         return "yang";     } }

结果第二个case上来就给我个上亿的数据量,直接导致栈溢出。没办法,只能用骚操作——打表法,先尝试一下1~50的情况,打印出了如下结果

1:niu
2:yang
3:niu
4:niu
5:yang
6:niu
7:yang
8:niu
9:niu
10:yang
11:niu
12:yang
13:niu
14:niu
15:yang
16:niu
17:yang
18:niu
19:niu
20:yang
21:niu
22:yang
23:niu
24:niu
25:yang
26:niu
27:yang
28:niu
29:niu
30:yang
31:niu
32:yang
33:niu
34:niu
35:yang
36:niu
37:yang
38:niu
39:niu
40:yang
41:niu
42:yang
43:niu
44:niu
45:yang
46:niu
47:yang
48:niu
49:niu
50:yang
得到规律:每5个就是一组niu,yang,niu,niu,yang。所以改出一个复杂度为O(1)的算法
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException;  public class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int t = Integer.parseInt(br.readLine());         for(int i = 0; i < t; i++){             int n = Integer.parseInt(br.readLine());             System.out.println(winner(n));         }     }          private static String winner(int n) {         return (n % 5 == 0 || n % 5 == 2)? "yang": "niu";     } }

像这种输入一个整数,输出也是一个整数的题目。左神表示大概4成的题目可以用这种方式找规律,刚开始不要纠结它的数学原理,只要这样暴力出来能AC,再去通过数学的方式解释这个策略。

今天 10:04:32 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。 最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情