分类 算法 下的文章

python练习


其实有很多这样的活动都有一个相同的模式:N 种人物卡片,每次买一包干脆面随机得到一张。当你集齐这 N 种人物时,就会有相应的奖励。 那时候还不懂怎么计算概率,白白给人家送了好多钱,吃了好多干脆面。 现在的任务是,给你一个正整数 N (1 <= N <= 10^4),请你帮我从期望的角度计算平均需要买多少包干脆面才能集齐这 N 种人物。 提醒:由于结果可能不是整数,所以结果只保留到小数点后两位。


Sprague–Grundy theorem


翻译自维基

定义

Sprague-Grundy理论针对信息充分、满足结束条件(所有游戏都有结果:不存在无限循环的游戏)和正常游戏条件(不能移动的玩家失败)的双人游戏。 类似于Nim这样完全公平的游戏,任何时刻每个玩家都有完全一样的可行步骤。而对于tic-tac-toe(井字棋),象棋这些游戏不是完全公平游戏。在象棋里,玩家只能移动自己的棋子,不能移动对方的棋子。而在tic-tac-toe中,一名玩家画X,另一名玩家只能画O。公平游戏只有两类结果:要么先手赢(N-position),要么后手赢(P-position). 在这个证明里,一个状态由当前状态能一步到达的状态集合确定(这些状态称为选项)。例如,状态{}是一个P-position(必败态),在正常游戏里,当前玩家因为不能移动而失败。而状态则相反,是一个N-position(必胜态);当前玩家只有一个选择,而这个转移对于对方是一个必败状态。 一个nimber是一个特殊状态用*n表示序数n.*0是{}。其他nimber类似地由*(n+1)=*n∪{*n};此外,*1={*0},*2={*0,*1}等。因此*n对应一个有n个数的nim堆。 两个状态G和H能够组合成一个新状态G+H在当前玩家能够选择移到状态G或H的组合游戏中。集合G+H用规则G+G={G+h|h∈H}∪{g+H|g∈G}计算, 这个规则表明状态叠加是可交换和可结合的。 两个状态G和G'被认为相等当且仅当,对于每个状态H,状态G+H和G'+H有相同结果,写为G≈G'。


FP-growth算法简介


  参考:FP-growth

  FP-growth算法是一种高效的频繁集挖掘算法。它基于Apriori,但不同之处在于将数据集存储在FP树结构中,从而加快执行效率。FP-growth只需要对数据进行两次扫描,Apriori对潜在的频繁项集都会扫描,从而降低了效率。

  那么什么是FP数结构?