《Python 算法教程》笔记

# 找明星问题 # 10个人中只有一个明星，大家都认识明星，明星不认识任何人。 from random import randrange #直接法，两两判断 def naive_celeb(G): n = len(G) for u in range(n): for v in range(n): if u == v: continue if G[u][v]: break if not G[v][u]: break else: return u #优化思路：G[u][v]为真，说明u肯定不是明星，否则v肯定不是明星 def celeb(G): u,v = 0,1 n = len(G) for c in range(2,n+1): #从第3个开始 以次判断 if G[u][v]: #如果u认识v，则u肯定不是明星，往后累加 u = c else: v = c #否则u可能是明星，v肯定不是明星，往后累加 if u == n: #累加到最后，只剩下u和v，u不是明星，说明v是明星 c = v else: c = u #其实到这里已经能确定c就是明星了，下面的过程再判断一遍 for v in range(n): if c == v: continue if G[c][v]: break if not G[v][c]: break else: return c return None n = 10 #人数 # 构造数据结构，使用二维数组 G = [[randrange(2) for i in range(10)] for i in range(10)] c = randrange(10) # 指定一位明星 print(c) #设置关系 for i in range(10): G[i][c] = True #所有人都认识明星 G[c][i] = False #明星不认识所有人 for i in G: print(i) cc = naive_celeb(G) print(cc) cc = celeb(G) print(cc)

免责声明：本内容来自平台创作者，博客园系信息发布平台，仅提供信息存储空间服务。

0

0

网址：《Python 算法教程》笔记 https://m.mxgxt.com/news/view/1994375

相关内容

python A star算法
零Python基础也能驾驭的PPT自动化教程
python画明星
基于Python的明星关系网络构建与可视化分析教程
Python实现刷youtube、B站、爱奇艺、西瓜视频等视频网站播放量（Python教学文章)
基于Python的社交网络分析与图论算法实践
Python流行历程揭秘：从学术宠儿到编程界明星，时间线解读编程语言崛起之路
Python全局变量操作详解
Python编写统计选票的程序 python统计票数
【视频】支持向量机算法原理和Python用户流失数据挖掘SVM实例（下）

随便看看