问题描述:给你一万副扑克(一共540000张乱序)和一万个人,请设计一种算法,能够有效的将一万副扑克都分出来,并且每一副牌都是按数字和花色排好序的。
总任务:将一万副扑克都分出来,并且每一副都排好序 一万人:类比一万个CPU 分牌:操作系统干的活 人与人之间的交流:CPU之间的通信
步骤一:任务划分 任务1:局部的排序任务,也就是按照数字、花色进行的排序 任务2:一副一副牌分出来的任务
步骤二:任务调度与分配 首先,将540000张牌平均分给7300个人,有的人有73张,有的人74张; 然后每个人按照数字、花色排好序
然后剩余的2700人分成50个组,每个组54人,每个人手中只拿一种数字和花色的牌,按顺序站好队,其中每个组中选取出一个记忆力超级好的人(在计算机中搞一个缓存就行,存下所有状态),这个人负责对外联系并且记住所有人手中牌的数量,比如组内红桃A特别多的时候,就拒绝接收,总之要保持每个人手里的牌不会差太多。
然后对7300人进行归并排序,每两两归并一次后又将牌平分,然后,所有人就往50个小组中分别分牌,当遇到拒绝接收的小组后,就换另一个小组分,每个人分10张牌。
一个小组接收牌之后,按照事先预定好的规则,再在组内分发牌,比如小明就只收红桃A,、小红就只收黑桃A…
八次归并分牌之后,牌就都分往了50个组
步骤三:结果整合
然后50个组就能同时源源不断的组合出一副一副的排好序的牌了。
最后50个组再通信一下,将剩余的零数凑起来就行