江西瑞昌,努卡卡盟,新乡窝窝团购网
从周三课开始总算轻松了点,下午能在宿舍研究点题目啥的打一打,还好,刚开学的课程还算跟得上,刚开学的这些课程也是复习以前学过的知识,下半学期也不敢太划水了,被各种人寄予厚望之后瑟瑟发抖,只能努力前行了~自己好多地方还做得不够好,真的是要提升的方面太多了,加油吧~
今日兴趣新闻:
网易回应裁员:公司确实正在进行结构性优化
链接:https://baijiahao.baidu.com/s?id=1626619207432301200&wfr=spider&for=pc
偶尔反新闻经常看到这些大公司的裁员,谷歌、微软、华为、百度都出现过大幅度的裁员,现在网易也开始了,这会不会加剧了未来毕业职业出口的紧张呢?
------------------------------------------------题目----------------------------------------------------------
343 49 3599 610 62 36
49 610 62
------------------------------------------------题目----------------------------------------------------------
原意说的是有一到一百个葡萄,有两个人去吃这些葡萄,每个葡萄上面有数字,每个人吃到的葡萄乘积之和就是自己的答案,获得最大的数就是胜利,但有人为了胜利会假报自己的数字,让你去识破他。
简单来说,就是一个游戏:
有两个人玩游戏a、b人,a和b都报一个数,其中最大的人是被挑战者,最小的那个人是挑战者,然后两人的数通过因式分解,若挑战者中总存在一种分解,是被挑战者总有的因子,那么说明被挑战者说谎,判挑战者胜利。
举例:
a = 343 b = 49 显然a>b,那么a是被挑战者,b是挑战者,正常来说较小的人不说假话,因为如果他要说假话为何不往大的数说呢,好让自己赢。
所以对a、b进行因式分解,对于b来说,你只能吃49才能得到,所以a不能再使用49了,但是a可以因式分解成49 * 7,所以可以看得出来a说了假话,判b胜利~
这道题有点小难度对于新手的我来说,查阅了一些解法加之自己的理解,是需要用到递归的dfs深搜方法去实现的。
首先建立一个数组,用来存储100个葡萄,value为0则说明还没被吃,1说明已经吃过不能再吃了,通过这种方法来判断a、b是否有因子重复。
然后对挑战者进行因式分解,得到挑战者的因式分解,然后再对被挑战者进行因式分解,如果被挑战者能够顺利的因式分解,那么被挑战者获胜,否则挑战者获胜。
后面我会简单整理一下深搜笔记~
第一步:分清挑战者和被挑战者:
if(a>b) { attacker = b; victim = a; } else { attacker = a; victim = b; }
第二步:对挑战者进行因式分解:
result_dfs = dfs(attacker);
这里需要自己定义dfs深搜函数,那么下面开始定义深搜dfs:
第三步:dfs函数构造:分解因式:
if(number > 100) size = 100; else size = number; for(i = 2 ; i<= size ; i++) { if( number %i == 0 && already[i] == 0) { already[i] = 1; if(dfs( number / i ) == 1) return 1; already[i] = 0; } }
第四步:dfs函数构造:判断挑战者和被挑战者的因式分解情况:
if(number == 1) { if(vic_divided == 0) { vic_divided = 1; vic_divide = 1; if(dfs(victim) == 1) return 1; else{ vic_divided = 0; return 0; } } return 1; }
第五步,根据dfs返回的结果判断胜负:
if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0) winner = victim; else winner = attacker;
#include<stdio.h> #include<string.h> int attacker,victim; int vic_divided,vic_divide; int already[101]; int dfs(int number) { int i,size; if(number == 1) { if(vic_divided == 0) { vic_divided = 1; vic_divide = 1; if(dfs(victim) == 1) return 1; else{ vic_divided = 0; return 0; } } return 1; } if(number > 100) size = 100; else size = number; for(i = 2 ; i<= size ; i++) { if( number %i == 0 && already[i] == 0) { already[i] = 1; if(dfs( number / i ) == 1) return 1; already[i] = 0; } } return 0; } int main() { int a,b,result_dfs,winner; while(scanf("%d %d",&a,&b) != eof) { vic_divide = vic_divided = 0; memset(already, 0, sizeof(already)); if(a>b) { attacker = b; victim = a; } else { attacker = a; victim = b; } result_dfs = dfs(attacker); if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0) winner = victim; else winner = attacker; printf("%d\n",winner); } return 0; }
这道题用到了深搜,即深度优先搜索,简称dfs,对应的还有bfs,广度优先搜索。
事实上,深度优先搜索属于图算法的一种,英文缩写为dfs即depth first search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。
如果我们从a点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是b也可以是c,d),则我们可能得到如下的一个访问过程:a->b->e(没有路了!回到a)->c->f->h->g->d(没有路,最终回到a,a也没有未访问的相邻节点,本次搜索结束)
参考:https://baike.baidu.com/item/深度优先搜索/5224976
做了几道题之后,简单悟到一些使用bfs、dfs的一些方式,但还很浅显,需要加强题量练习提升自己:
=》bfs是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解。
=》dfs不需要保存搜索过程中的状态,而bfs在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。
=》dfs适合搜索全部的解,因为要搜索全部的解,那么bfs搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,dfs搜索也会搜索全部,但是相比dfs不用记录过多信息,所以搜素全部解的问题,dfs显然更加合适。
注:我还是个渣渣辉,代码可能写得不够高效不够好,我也会努力优化,如果有更好的解法,真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论