精华内容
下载资源
问答
  • 在弄明白“树形图”是怎么回事后,我一开始认为没有必要引进“树形图”,因为其把简单问题搞复杂化了,可是后来仔细想一下,对于一个刚接触概率的初中生来说,“树形图”还是有其必要性的。 下面用一个例子来说明...

    今天听一个教初中的朋友说,现在新教材中的概率问题都用“树形图”来求解了。在弄明白“树形图”是怎么回事后,我一开始认为没有必要引进“树形图”,因为其把简单问题搞复杂化了,可是后来仔细想一下,对于一个刚接触概率的初中生来说,“树形图”还是有其必要性的。

    下面用一个例子来说明什么是“树形图”。

     

    题:现有一黑一白两双袜子,从这4只袜子里任意取2只,颜色恰好一样的概率是多少?

    解:将4只袜子分别编号为:黑1,黑2,白1,白2. 则树形图如下:

    袜子

    从图中可以看出,总共有12根连线,其中袜子颜色相同的有4根连线,所以概率 P = 4/12 = 1/3.

    解毕。

     

    我们再来看看用传统解法(即排列组合方法)如何做。由于上下标不好打,将从n个里面选m个的组合数表示成C(n,m)的形式。

     

    解:从4只袜子里选2只,总共有 C(4,2) = 6 种可能:(黑1, 黑2), (黑1,白1), (黑1,白2), (黑2,白1), (黑2,白2), (白1,白2).

    其中颜色相同的有2种,所以概率 P = 2/6 = 1/3.

    解毕。

     

    这样看来,传统方法更简洁,也不难理解,为什么还要引入树形图呢?我觉得是因为树形图表达形式直观,方法简单易掌握,更有利于引领初学者跨过概率那道门槛。我们之所以觉得传统方法简单,是因为我们已经做过很过概率题,对概率了解比较多了。对于一个刚接触概率的初中生来说,概率是一种全新的描述事情的方式,由于传统方法比较抽象,初学者想初步驾驭它需要比较长的时间,而不少人的信心会被这个过程中的挫折给慢慢磨掉。古人云,迟则生变,所以入门的过程越短越好。

     

    下面,我将通过分析传统方法可能带来的错误答案来说明树形图对于初学者的优势所在,这些错误在长期的教学过程中会经常遇到,很有代表性。

    • 错误解一:将选2只袜子看成每次选1只,选2次,则结果总共有4种可能:(黑,黑), (黑,白), (白,黑), (白,白). 所以概率 P = 2 /4  =1/2.
    • 错误解二:2只袜子的颜色配对总共有3种可能:全黑、全白、一黑一白,所以概率 P = 2/3.

    我们先来看下这些错误是发生在哪个环节的。

    初中概率题目都为古典概率问题,做此类题时总共有三个步骤:

    • 确定样本空间,即找出“所有可能出现的结果
    • 在样本空间中找出问题所对应的“基本事件”
    • 相除算出概率
    古典概率(classical probability),又称经典概率,它有如下特征:
    
    (1) 样本空间的元素(即基本事件)只有有限个。不妨设为n个,并记为w1, w2, …, wn.
    
    (2) 每个基本事件出现的可能性是相等的,即P(w1) = P(w2) = … = P(wn).

    可以看出,第一步才是解题过程中最核心的和最难的,而且绝大部分错误都发生在这一环节(上面的两个错误也是),由于其他两步的错误很容易得到纠正,所以提高正确率的关键就在于提高第一步的正确率。

     

    提高第一步正确率的方法说起来也很简单,就两条:

    1. 提高学生的智力水平。比如让学生喝点“智力+10”的药水,或是改造大脑,提升大脑利用率之类的,当然,这些方法目前还是impossible mission,所以我们只能依靠第二个方法。

    2. 降低第一步的难度。呃,这不是废话。我们仔细想一下,为什么传统方法会带来很多错误?我想一个原因就是传统方法没有一个直观的表现方式,是个比较抽象的方法,所以它依赖学生对于方法的理解程度。用传统方法教学时,老师会说这个题我们这样看,那个题那样看……,每个题都有实质相同却形式不同的看法,对于一个没有掌握其本质的初学者来说,你让他怎么认清众多看法中的相同之处,怎么从众多角度中选出正确的角度,怎么能不被搞蒙?如果能让可供选择的角度减少,甚至减至只有一种角度,难度是不是就大大降低了呢?那么,谁能办到?树形图说:“我能!”

     

    为什么树形图可以办到?我认为有以下几个原因:

    1. 树形图的实质是排列。它实际上就是排列方法的图形化表现方式,这点从前面的例子中就可以看出,所以用树形图解题时,不管题目是组合问题,还是排列问题,树形图把它们都当成排列问题来解了。这样讲解题方法就统一成了排列,相当于减少了可供选择的角度,从而降低了难度。

    至于为什么可以用排列的方法来解组合问题,这里简单说一下。相信大家都知道,组合就是由排列去重后得来的,这点从公式中就可以看出:C(n,m) = A(n,m) / m!. 虽然用排列方法来解组合问题时,会使样本空间中有很多从现实意义上讲“重复”了的元素,但是没关系,这些“重复”都是成倍出现的,且倍数为m!,由于计算概率用的是除法,倍数m!最后会被约掉,所以我们能用排列的方法来解组合问题。

    2. 由于树形图的实质是排列,所以它继承了用排列来解组合问题的优势,即避免了由排列转化为组合的过程中可能发生的错误。

    为了说明这点,让我们回到之前列举的两个错误解法,仔细分析下这些错误是如何产生的。

    首先,我们需要认为4只袜子是各不相同的。呃,我不是霸道地宣布它们就是不同的,因为袜子不仅只有颜色这个属性,还有长短、重量、褶皱程度……,各种属性,所以即使是同一双袜子,也总能找出其不同的地方。正如同世界上没有两片完全相同的树叶,也同样没有两只完全一样的袜子,:-) . 当然,我们做题时不用考虑这么多属性,我啰嗦这么多只是想说明即使是颜色相同的两只袜子也是不同的(这一点很重要). 那么,我们将这4只袜子重新编号为A, B, C, D, 且只考虑其颜色属性。为了方便表述,将它们用如下符号记录:(A: 黑), (B: 黑), (C: 白), (D: 白).

    其次,由于我们研究的是由排列转化为组合的过程中错误是如何产生的,那么我们就要先用排列的视角来看“选了两只袜子”这个事情。众所周知,排列都是有顺序的。一般我们是用时间来区分不同的顺序,例如说,“第一次拿了一只黑色的袜子,第二次拿了白色的袜子。”如果非要有人和你较劲,说他能同时拿两只袜子,问你怎么区分(这种较劲行为是值得鼓励的,有助于发现问题的本质). 我想即使从时间上无法区分,那我还可以从空间上区分,因为你总不可能在现实中把两只袜子合到一起吧。那么,总会存在一个合适的方向,使得你在观察两只袜子时,会发现一只在前,另一只在后,这样顺序就有了,于是袜子又多了一个属性:顺序。我们将该属性的值定义如下,1:顺序一; 2:顺序二。

    最后,我们就得到了由排列解法生成的样本空间Ω中的元素在新定义下的形式:

    • {(A: 黑, 1), (B: 黑, 2)}, {(A: 黑, 1), (C: 白, 2)}, {(A: 黑, 1), (D: 白, 2)}
    • {(B: 黑, 1), (A: 黑, 2)}, {(B: 黑, 1), (C: 白, 2)}, {(B: 黑, 1), (D: 白, 2)}
    • {(C: 白, 1), (A: 黑, 2)}, {(C: 白, 1), (B: 黑, 2)}, {(C: 白, 1), (D: 白, 2)}
    • {(D: 白, 1), (A: 黑, 2)}, {(D: 白, 1), (B: 黑, 2)}, {(D: 白, 1), (C: 白, 2)}

    每一行对应之前图中的一棵树,每个元素都是由两只袜子组成,其中红色的是满足条件的元素。有了抽象的数学表示形式之后,我们就可以方便的讨论“转化过程”了。

    我们知道,排列和组合唯一的区别在于:是否有顺序。也就是说,由排列转化为组合,只需要也只能丢弃“顺序”这个属性,如果丢弃错了属性,就会生成错误的样本空间。下面将展示正确方法和错误方法在转化过程中的区别。

    正确方法:只丢弃“顺序”属性,通过排列生成的样本空间Ω转化为组合方法的样本空间,新空间元素如下(合并了相同的元素):

    • {(A: 黑), (B: 黑)}, {(A: 黑), (C: 白)}, {(A: 黑), (D: 白)} , {(B: 黑), (C: 白)}, {(B: 黑), (D: 白)} , {(C: 白), (D: 白)}

    错误一:形式上貌似是用了组合的方法,实际用的是排列,但是它丢弃了袜子的身份标识,认为只要颜色相同就是同一种袜子,所以得到了如下的样本空间:

    • {(黑, 1), (黑, 2)}, {(黑, 1), (白, 2)}, {(白, 1), (黑, 2)}, {(白, 1), (白, 2)}

    错误二:虽然是用组合的方法看问题,也丢弃了顺序属性,但同时也丢弃了袜子的身份标识,所以得到了如下的样本空间:

    • {(黑), (黑)}, {(黑), (白)}, {(白), (白)}

    经对比发现,两种错误都是由于丢弃了袜子的“身份标识”而产生的,而这个题目中隐含有不能丢弃“身份标识”的条件:那就是我们需要通过袜子的“身份标识”来区分最后选出的2只袜子,因为同一种颜色的袜子各有2只。

    至此,我们已经弄明白了这些错误是怎么产生的,同时我们可以看到,如果直接用排列的方法解组合问题,就能避免这些错误的产生,这就是排列方法天生的优势所在。

    3. 树形图是一种图形化表现形式,图形方法由于其直观性,相对于抽象的排列方法,它很容易被初学者掌握。

    经过以上分析,我们已经能很清晰的看到为什么树形图有降低难度的能力了,所以新教材中采用这个方法也是合情合理,因为对初学者来说,首先也是最重要的是先跨过那道门槛。

     

    前面谈了树形图这么多优点,现在来说说其缺点吧。由于树形图的实质是排列,所以它在继承排列优点的同时,也继承了排列的缺点:随着n的增长,A(n, m) 成阶乘倍增长!

    当A(n, m)比较大的时候,用树形图解题就是个悲剧,下面我们看个“选边组成三角形”的例子。

     

    题:从长度为1, 3, 5, 7, 9 的5条线段中任取三条,恰好能组成三角形的概率是多少?

    解:由题意知,树形图中共有5棵树,根节点分别为1, 3, 5, 7, 9,画出树形图如下:

    三角形

    从图中可以看出,总共有5*12=60条路径,其中满足条件的路径有18条,所以概率 P = 18/60 = 3/10.

     

    上图中共有85个节点,60条路径。先不说画出来有多麻烦了,就算画出来了,判断的时候只要漏掉一两条,答案就错了。

    树形图用来处理情况较少的题目时还可以,碰到情况较多的题目就歇菜了。只会一种方法毕竟有其局限性,如果多数学生都学有余力,可以尝试教授传统方法。另外,我觉得如果教材改革了,相应的试题也应该改革,尽量少出情况很多的题目,否则就失去了改革的意义。

     

    PS:在写本文时想到了一些其他内容,但和本文关联度不是很大,而且想法不是很成熟,如果日后有机会会再整理一片续出来。续篇中比较有意思的是:你会发现本文中出现的两种错误解法在某种意义下其实是正确的。

    -------------------------------------------
    作者:兔纸张   来源:博客园 ( http://www.cnblogs.com/geiliCode )

    转载于:https://www.cnblogs.com/geiliCode/archive/2012/02/12/2211028.html

    展开全文
  • 树形图可以表示独立事件(例如多次掷硬币)和条件概率(例如不放回的抽卡)。 PS:树形图的数据由name和children形成的。children内包含分支。 参数含义 tooltip. triggerOn = ‘mousemove|click’ string 提示框...

    PS:所用数据纯属虚构!

    树形图

    树形图(Tree Diagram)是用来表示一个概率空间。树形图可以表示独立事件(例如多次掷硬币)和条件概率(例如不放回的抽卡)。

    PS:树形图的数据由name和children形成的。children内包含分支。

    参数含义

    tooltip. triggerOn = ‘mousemove|click’

    string

    提示框触发的条件,可选:

    • 'mousemove'

      鼠标移动时触发。

    • 'click'

      鼠标点击时触发。

    • 'mousemove|click'

      同时鼠标移动和点击时触发。

    • 'none'

    verticalAlign

    string

    文字垂直对齐方式,默认自动。

    可选:

    • 'top'
    • 'middle'
    • 'bottom'

    series-tree. expandAndCollapse = true

    boolean

    子树折叠和展开的交互,默认打开 。由于绘图区域是有限的,而通常一个树图的节点可能会比较多,这样就会出现节点之间相互遮盖的问题。为了避免这一问题,可以将暂时无关的子树折叠收起,等到需要时再将其展开。如上面径向布局树图示例,节点中心用蓝色填充的就是折叠收起的子树,可以点击将其展开。

    series-tree.data. animationDuration = 1000

    number Function

    初始动画的时长,支持回调函数,可以通过每个数据返回不同的时长实现更戏剧的初始动画效果。

    series-tree.data. animationDurationUpdate = 300

    number Function

    数据更新动画的时长。

    支持回调函数,可以通过每个数据返回不同的时长实现更戏剧的更新动画效果。


    代码如下:

    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <script src="/static/js/echarts.min.js"></script>
        <!-- cdn -->
        <!-- <script src="https://cdn.jsdelivr.net/npm/echarts@4.8.0/dist/echarts.min.js"></script> -->
    </head>
    <body>
        <div id="tree" style="width: 900px; height: 400px;"></div>
        <script>
            var tree_chart = echarts.init(document.getElementById("tree"));
            var data = {
                    "name": "flare",
                    "children": [{
                        "name": "analytics",
                        "children": [{
                            "name": "cluster",
                            "children": [{
                                "name": "AgglomerativeCluster",
                                "value": 3938
                            }, {
                                "name": "CommunityStructure",
                                "value": 3812
                            }, {
                                "name": "HierarchicalCluster",
                                "value": 6714
                            }, {
                                "name": "MergeEdge",
                                "value": 743
                            }]
                        }, {
                            "name": "graph",
                            "children": [{
                                "name": "BetweennessCentrality",
                                "value": 3534
                            }, {
                                "name": "LinkDistance",
                                "value": 5731
                            }, {
                                "name": "MaxFlowMinCut",
                                "value": 7840
                            }, {
                                "name": "ShortestPaths",
                                "value": 5914
                            }, {
                                "name": "SpanningTree",
                                "value": 3416
                            }]
                        }, {
                            "name": "optimization",
                            "children": [{
                                "name": "AspectRatioBanker",
                                "value": 7074
                            }]
                        }],
                        "collapsed": true
                    }, {
                        "name": "animate",
                        "children": [{
                            "name": "Easing",
                            "value": 17010
                        }, {
                            "name": "FunctionSequence",
                            "value": 5842
                        }, {
                            "name": "interpolate",
                            "children": [{
                                "name": "ArrayInterpolator",
                                "value": 1983
                            }, {
                                "name": "ColorInterpolator",
                                "value": 2047
                            }, {
                                "name": "DateInterpolator",
                                "value": 1375
                            }, {
                                "name": "Interpolator",
                                "value": 8746
                            }, {
                                "name": "MatrixInterpolator",
                                "value": 2202
                            }, {
                                "name": "NumberInterpolator",
                                "value": 1382
                            }, {
                                "name": "ObjectInterpolator",
                                "value": 1629
                            }, {
                                "name": "PointInterpolator",
                                "value": 1675
                            }, {
                                "name": "RectangleInterpolator",
                                "value": 2042
                            }]
                        }, {
                            "name": "ISchedulable",
                            "value": 1041
                        }, {
                            "name": "Parallel",
                            "value": 5176
                        }, {
                            "name": "Pause",
                            "value": 449
                        }, {
                            "name": "Scheduler",
                            "value": 5593
                        }, {
                            "name": "Sequence",
                            "value": 5534
                        }, {
                            "name": "Transition",
                            "value": 9201
                        }, {
                            "name": "Transitioner",
                            "value": 19975
                        }, {
                            "name": "TransitionEvent",
                            "value": 1116
                        }, {
                            "name": "Tween",
                            "value": 6006
                        }]
                    }]
                };
            var tree_option = {
                tooltip:{
                    trigger: 'item',
                    triggerOn: 'mousemove',
                },
                series:[
                    {
                        type:'tree',
                        data:[data],
                        top:'1%',
                        left:'15%',
                        bottom:'1%',
                        right:'7%',
                        symbolSize: 7,
                        orient: 'RL',
                        label: {
                            position: 'right',
                            verticalAlign:'middle',
                            align:'left',
                        },
                        leaves:{
                            label:{
                                position: 'left',
                                verticalAlign: 'middle',
                                align:'right',
                            }
                        },
                        expandAndCollapse: true,
                        animationDuration: 550,
                        animationDurationUpdate: 750,
                    }
                ]
            };
            tree_chart.setOption(tree_option);
        </script>
    </body>
    </html>
    

    如图所示:
    在这里插入图片描述

    关系图

    参数含义

    series-graph. animationEasingUpdate = cubicOut

    string

    数据更新动画的缓动效果。

    series-graph. layout = ‘none’

    string

    图的布局。

    可选:

    • 'none' 不采用任何布局,使用节点中提供的 xy 作为节点的位置。
    • 'circular' 采用环形布局
    • 'force' 采用力引导布局

    series-graph. edgeSymbol = [‘none’, ‘none’]

    Array string

    边两端的标记类型,可以是一个数组分别指定两端,也可以是单个统一指定。默认不显示标记,常见的可以设置为箭头,如下:

    edgeSymbol: ['circle', 'arrow']
    

    series-graph. edgeSymbolSize = 10

    Array number

    边两端的标记大小,可以是一个数组分别指定两端,也可以是单个统一指定。

    series-graph.lineStyle. curveness

    number

    边的曲度,支持从 0 到 1 的值,值越大曲度越大。


    代码如下:

    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <script src="/static/js/echarts.min.js"></script>
        <!-- cdn -->
        <!-- <script src="https://cdn.jsdelivr.net/npm/echarts@4.8.0/dist/echarts.min.js"></script> -->
    </head>
    <body>
        <div id="graph" style="width: 600px; height: 400px;"></div>
        <script>
            var graph_chart = echarts.init(document.getElementById('graph'));
            var graph_option = {
                title:{
                    text:'graph入门'
                },
                tooltip:{},
                animationDurationUpdate: 1500,
                animationEasingUpdate: 'quinticInOut',
                series:[
                    {
                        type:'graph',
                        layout:'none',
                        symbolSize: 50,
                        roam: true,
                        lable:{
                            show:true
                        },
                        edgeSymbol:['circle', 'arrow'],
                        edgeSymbolSize: [4, 10],
                        edgeLabel:{
                            fontSize: 20
                        },
                        data: [{
                            name: '节点1',
                            x: 300,
                            y: 300
                        }, {
                            name: '节点2',
                            x: 800,
                            y: 300
                        }, {
                            name: '节点3',
                            x: 550,
                            y: 100
                        }, {
                            name: '节点4',
                            x: 550,
                            y: 500
                        }],
                        links: [{
                            source: 0,
                            target: 1,
                            symbolSize: [5, 20],
                            label: {
                                show: true
                            },
                            lineStyle: {
                                width: 5,
                                curveness: 0.2
                            }
                        }, {
                            source: 1,
                            target: 0,
                            label: {
                                show: true
                            },
                            lineStyle: {
                                curveness: 0.2
                            }
                        }, {
                            source: '节点1',
                            target: '节点3'
                        }, {
                            source: '节点2',
                            target: '节点3'
                        }, {
                            source: '节点2',
                            target: '节点4'
                        }, {
                            source: '节点1',
                            target: '节点4'
                        }],
                        lineStyle: {
                            opacity: 0.9,
                            width: 2,
                            curveness: 0
                        }
                    }
                ]
            };
            graph_chart.setOption(graph_option);
        </script>
        
    </body>
    </html>
    

    如图所示:
    在这里插入图片描述

    词云图

    “词云”这个概念由美国西北大学新闻学副教授、新媒体专业主任里奇·戈登(Rich Gordon)于近日提出。戈登做过编辑、记者,曾担任迈阿密先驱报(Miami Herald)新媒体版的主任。他一直很关注网络内容发布的最新形式——即那些只有互联网可以采用而报纸、广播、电视等其它媒体都望尘莫及的传播方式。通常,这些最新的、最适合网络的传播方式,也是最好的传播方式。 因此,“词云”就是通过形成“关键词云层”或“关键词渲染”,对网络文本中出现频率较高的“关键词”的视觉上的突出。

    PS:词云图需要在官网的字符云下载echarts-wordcloud.min.js
    https://github.com/ecomfe/echarts-wordcloud

    也可以私信找我

    参数含义

    drawOutOfBound

    boolean

    设置为true,以允许部分在画布外部绘制单词。
    允许绘制大于画布大小的单词


    代码如下(数据纯属虚构)

    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <script src="/static/js/echarts.min.js"></script>
        <!-- cdn -->
        <!-- <script src="https://cdn.jsdelivr.net/npm/echarts@4.8.0/dist/echarts.min.js"></script> -->
        <script src="/static/js/echarts-wordcloud.min.js"></script>
    </head>
    <body>
        <div id="wordcloud" style="width: 600px; height: 400px;"></div>
        <script>
            var wordcloud_chart = echarts.init(document.getElementById('wordcloud'));
            var wordcloud_option = {
                series:[
                    {
                        type: 'wordCloud',
                        gridSize: 2,
                        sizeRange: [12, 50],
                        shape: 'pentagon',
                        width: 600,
                        height: 400,
                        drawOutOfBound: true,
                        textStyle: {
                            normal: {
                                color: function() {
                                    return 'rgb(' + [
                                        Math.round(Math.random() * 255),
                                        Math.round(Math.random() * 255),
                                        Math.round(Math.random() * 255)
                                    ].join(',') + ')';
                                }
                            },
                            emphasis: {
                                shadowBlur: 10,
                                shadowColor: '#333'
                            }
                        },
                        // 数据纯属虚构
                        data:[
                            {
                                name:'学校',
                                value: 10000,
                            },
                            {
                                name:'学生',
                                value: 9800,
                            },
                            {
                                name:'老师',
                                value: 7000,
                            },{
                                name:'人民日报',
                                value: 100,
                            },
                            {
                                name:'体侧',
                                value: 4100,
                            },
                            {
                                name:'开学',
                                value: 11000,
                            },
                            {
                                name:'返校',
                                value: 8430,
                            },
                            {
                                name:'疫情',
                                value: 2345,
                            },
                            {
                                name:'教室',
                                value: 234,
                            },
                            {
                                name:'上课',
                                value: 3456,
                            },
                            {
                                name:'网课',
                                value: 6789,
                            },
                            {
                                name:'中暑',
                                value: 1233,
                            },
                            {
                                name:'感受',
                                value: 2300,
                            },
                            {
                                name:'家长',
                                value: 3444,
                            },
                            {
                                name:'宿舍',
                                value: 2666,
                            },
                            {
                                name:'回去',
                                value: 1566,
                            },
                            {
                                name:'隔离',
                                value: 7786,
                            },
                            {
                                name:'考虑',
                                value: 4576,
                            },
                            {
                                name:'意义',
                                value: 1266,
                            }
                        ]
                    }
                ]
            };
            wordcloud_chart.setOption(wordcloud_option);
        </script>
    </body>
    </html>
    

    如图所示:
    在这里插入图片描述

    展开全文
  • 应用故障树形图分析法对点火源和油气泄漏的基本原因进行了分析,建立了油罐火灾爆炸故障树形图。采用布尔代数化简法求出系统的最小径集,给出了故障树顶上事件发生概率和基本事件的3种重要度分析。通过对系统的故障树...
  • HDU 4443 Lost 树形概率DP

    2015-03-16 19:47:34
    很容易考虑到将环拆开成之多30个在上做概率DP, 不过细节真的很多, 很容易出错, 细节见代码注释 代码如下: Result : Accepted Memory : 8660 KB Time : 280 ms /* * Author: Gatevin * Create

    题目大意:

    就是现在给出一个有且仅有一个环的图, 顶点数<= 10^5, 环的大小在3~30之间, 现在初始的时候随机选一个点作为起点, 然后每次选择与当前所在的点相邻的没有走过的点进入, 直到不能走为止, 求最终停在各个点的概率, 输出其中最大的5个的和


    大致思路:

    很容易考虑到将环拆开成之多30个在树上做概率DP, 不过细节真的很多, 很容易出错, 细节见代码注释


    代码如下:

    Result  :  Accepted     Memory  :  8660 KB     Time  :  280 ms

    /*
     * Author: Gatevin
     * Created Time:  2015/3/16 18:29:36
     * File Name: Kotori_Itsuka.cpp
     */
    #include<iostream>
    #include<sstream>
    #include<fstream>
    #include<vector>
    #include<list>
    #include<deque>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    #include<bitset>
    #include<algorithm>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<iomanip>
    using namespace std;
    const double eps(1e-8);
    typedef long long lint;
    
    #define maxn 100010
    int n, pre[maxn], nxt[maxn];
    vector <int> G[maxn];
    vector <int> circle;
    bool vis[maxn], inCircle[maxn];
    double up[maxn], down[maxn], ans[maxn], p;
    
    bool findCircle(int now, int father)//dfs寻找环, father表示上一个经过的点
    {
        for(int i = G[now].size() - 1; i >= 0; i--)
        {
            int nex = G[now][i];
            if(nex == father) continue;
            if(!vis[nex])
            {
                vis[nex] = 1;
                pre[nex] = now;
                nxt[now] = nex;
                if(findCircle(nex, now))
                    return true;
                vis[nex] = 0;
            }
            else
            {
                pre[nex] = now;
                nxt[now] = nex;//pre和nxt数组分别两个方向记录环的节点的相邻关系
                circle.push_back(nex);//环上的点存储在circle里
                inCircle[nex] = 1;
                while(now != nex)
                    circle.push_back(now), inCircle[now] = 1, now = pre[now];
                return true;
            }
        }
        return false;
    }
    
    /*
     * Up函数计算某棵环上的子树中的点从下向上到达点i的概率up[i]
     * 从下向上是从叶子节点向根节点(环上的点)的方向
     * 从下向上时根节点往叶节点的方向
     */
    void Up(int now, int father)
    {
        for(int i = G[now].size() - 1; i >= 0; i--)
        {
            int nex = G[now][i];
            if(nex == father || inCircle[nex]) continue;
            Up(nex, now);
            if(G[nex].size() > 1)//不是叶子节点
                up[now] += up[nex]/(G[nex].size() - 1);//nex作为过渡
            up[now] += p/G[nex].size();//nex被直接选中
        }
        return;
    }
    
    /*
     * 从其他子树出发到这棵子树的点作为终点
     */
    void Down1(int now, int father)//计算从其它子树节点出发往这棵子树下走到尽头的概率
    {
        int cnt = 0;
        if(inCircle[now])//起点(往树下走的概率在之前已经算了)
            cnt = 1;//cnt = 1, 不影响到向下走的概率
        else
            for(int i = G[now].size() - 1; i >= 0; i--)
                if(!inCircle[G[now][i]] && G[now][i] != father)
                    cnt++;//可以走的点数
        for(int i = G[now].size() - 1; i >= 0; i--)
        {
            int nex = G[now][i];
            if(nex == father || inCircle[nex]) continue;
            down[nex] += down[now]/cnt;//这里不能 + p/G[now].size()了(这个情形分类下now不能作为起点)
            Down1(nex, now);
        }
        if(!inCircle[now] && G[now].size() == 1)//叶子节点
            ans[now] += down[now];
        return;
    }
    
    /*
     * 从自己这棵子树的点(包括自己的根节点)出发在自己这棵树走到终点的情况
     */
    void Down2(int now, int father)
    {
        int cnt = 0;
        for(int i = G[now].size() - 1; i >= 0; i--)
            if(!inCircle[G[now][i]] && G[now][i] != father)
                cnt++;
        for(int i = G[now].size() - 1; i >= 0; i--)
        {
            int nex = G[now][i];
            if(nex == father || inCircle[nex]) continue;
            down[nex] += p/G[now].size();//now作为起点
            if(!inCircle[now])//now不是根节点就可以是路径上的点
                down[nex] += down[now]/(G[now].size() - 1);//从上向下的路径
            //接下来是从下往上到达now之后再往下到达nex的概率
            double tmp = up[now] - p/G[nex].size();//从up[now]中减去来自nex的部分
            if(G[nex].size() > 1) tmp -= up[nex]/(G[nex].size() - 1);
            down[nex] += tmp/(G[now].size() - 1);
            Down2(nex, now);
        }
        if(!cnt && !inCircle[now])
            ans[now] += down[now];
        return;
    }
    
    void init()
    {
        for(int i = 1; i <= n; i++) G[i].clear();
        circle.clear();
        p = 1./n;//p是某个节点被选中作为初始的概率
        int tx, ty;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d", &tx, &ty);
            G[tx].push_back(ty);
            G[ty].push_back(tx);
        }
        memset(vis, 0, sizeof(vis));
        memset(inCircle, 0, sizeof(inCircle));
        memset(up, 0, sizeof(up));
        memset(down, 0, sizeof(down));
        memset(ans, 0, sizeof(ans));
        return;
    }
    
    int main()
    {
        while(scanf("%d", &n), n)
        {
            init();
            vis[1] = 1;
            findCircle(1, -1);
            for(int i = circle.size() - 1; i >= 0; i--)
            {
                int now = circle[i];
                Up(now, -1);
                /* 
                 * 接下来计算对于环上的每个点作为过渡点往下前进的转折点的概率
                 * 也就是每棵子树上的点不作为起点但是这棵子树上的点作为终点时到达其根节点的概率
                 * 以及换上的可以作为终点的点的概率
                 */
                double tmp = up[now]/(G[now].size() - 1) + p/G[now].size();
                while(nxt[now] != circle[i])
                {
                    if(nxt[nxt[now]] != circle[i])
                        down[nxt[now]] += tmp/(G[nxt[now]].size() - 1);//往下走
                    else if(G[nxt[now]].size() != 2)
                        down[nxt[now]] += tmp/(G[nxt[now]].size() - 2);//环的尽头往下走
                    else ans[nxt[now]] += tmp;
                    /*
                     * 当circle[i]是上来的起点时只有左或者右边的点的度数是2的时候
                     * 转一圈那个点才会是终点
                     */
                    now = nxt[now];
                    tmp = tmp/(G[now].size() - 1);
                }
                now = circle[i];
                tmp = up[now]/(G[now].size() - 1) + p/G[now].size();
                while(pre[now] != circle[i])
                {
                    if(pre[pre[now]] != circle[i])
                        down[pre[now]] += tmp/(G[pre[now]].size() - 1);
                    else if(G[pre[now]].size() != 2)
                        down[pre[now]] += tmp/(G[pre[now]].size() - 2);
                    else ans[pre[now]] += tmp;
                    now = pre[now];
                    tmp = tmp/(G[now].size() - 1);
                }
            }
            for(int i = circle.size() - 1; i >= 0; i--)
                Down1(circle[i], -1);
            memset(down, 0, sizeof(down));
            for(int i = circle.size() - 1; i >= 0; i--)
                Down2(circle[i], -1);
            sort(ans + 1, ans + n + 1);
            double result = 0;
            for(int i = 0; i < 5; i++)
                result += ans[n - i];
            printf("%.5f\n", result);
        }
        return 0;
    }
    


    展开全文
  • lxhgww 现在在一个树形图的点1上(此树形图共n个点,编号从1到n) 现在在第i点有 Ki%的概率被杀死回到点1, 有Ei%的概率逃出迷宫, 剩下的1 - Ki% - Ei%就是什么都没发生了,需要转到下一位置,其中K0 = E0 = 0, 现在...
    题目大意:
    lxhgww 现在在一个树形图的点1上(此树形图共n个点,编号从1到n) 现在在第i点有 Ki%的概率被杀死回到点1, 有Ei%的概率逃出迷宫, 剩下的1 - Ki% - Ei%就是什么都没发生了,需要转到下一位置,其中K0 = E0 = 0, 现在给出树形图,定点数n <= 10000求lxhgww走出迷宫需要走多少次的期望


    大致思路:
    由于n <= 10000直接解线性方程组的复杂度不能接受,需要递推,递推公式及过程见代码


    代码如下:

    Result  :  Accepted     Memory  :  1588 KB     Time  :  203 ms

    /*
     * Author: Gatevin
     * Created Time:  2014/12/2 17:57:35
     * File Name: Asuna.cpp
     */
    #include<iostream>
    #include<sstream>
    #include<fstream>
    #include<vector>
    #include<list>
    #include<deque>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    #include<bitset>
    #include<algorithm>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<iomanip>
    using namespace std;
    const double eps(1e-10);//这里刚开始开eps = 1e-8 WA了...
    typedef long long lint;
    
    /*
     * 很好的一道概率题, 首先不难发现如果用dp[i]表示从节点i到达目标状态需要的步数,有方程:
     * dp[i] = ∑(dp[j] + 1)/G[i].size()*(1 - K[i] - E[i]) + K[i]*(dp[1] + 0) + E[i]*0;
     *       = ∑(dp[j] + 1)/G[i].size()*(1 - K[i] - E[i]) + K[i]*dp[1]
     * 其中G[i]为与点i相邻的点组成的vector, K[i]为在i节点被杀死的概率, E[i]为出去的概率,j为与i相邻的点
     * 这样对于dp[1~n]一共有n个方程,可见一定是可解的,但是由于n的范围太大,需要递推求解
     * 这里由于dp[1]为起点,将其视作整棵树的根节点,那么原来的方程需要写为
     * dp[i] = ∑dp[son[i]]/G[i].size()*(1 - K[i] - E[i]) + dp[father[i]]/G[i].size()*(1 - K[i] - E[i]) + K[i]*dp[1] + (1 - K[i] - E[i])
     * 其中son[i]是i的子节点,father[i]是i的父节点,那么对于叶子节点
     * dp[i] = dp[father[i]]*(1 - K[i] - E[i]) + K[i]*dp[1] + 1 - K[i] - E[i]
     * (因为对于叶子节点,没有继续下去的儿子,且G[i].size() = 1)
     * 那么可以发现从叶子节点往上看,每一个儿子节点都可以表示成A*dp[1] + B*dp[father] + C的形式,那么对于一个点的所有子节点
     * 不难发现其father是一样的,并且带入当前的father节点可以算出相应的father节点满足的关系那么从叶节点开始后序遍历这棵树即可最终递推出dp[1]
     * 并且dp[1] = ∑dp[son[1]]/G[1].size()*(1 - 0 - 0) + 0*dp[1] + 1 - 0 - 0
     * 于是dp[1]便可以解出
     * 这里我的代码是将每个节点的A,B,C参数用dp1表示多少倍dp[1], dpfa表示多少倍其父节点,cons表示常数项
     * 递推求解即可
     */
    
    double K[10010], E[10010];
    vector <int> G[10010];
    bool vis[10010];
    int father[10010];
    int n, x, y;
    
    struct Node
    {
        double dp1, dpfa, cons;
        Node(double a = 0, double b = 0, double c = 0)
        {
            dp1 = a; dpfa = b; cons = c;
        }
    };
    
    Node operator + (Node n1, Node n2)
    {
        return Node(n1.dp1 + n2.dp1, n1.dpfa + n2.dpfa, n1.cons + n2.cons);
    }
    
    void dfs(int now)
    {
        vis[now] = 1;
        for(unsigned int i = 0; i < G[now].size(); i++)
        { 
            if(!vis[G[now][i]])
            {
                father[G[now][i]] = now;
                dfs(G[now][i]);
            }
        }
        return;
    }
    
    Node solve(int now)
    {
        if(G[now].size() == 1) return Node(K[now], 1 - K[now] - E[now], 1 - K[now] - E[now]);
        Node ret;
        for(unsigned int i = 0; i < G[now].size(); i++)
            if(G[now][i] != father[now])
                ret = ret + solve(G[now][i]);
        double tmp = (1 - ret.dpfa/G[now].size()*(1 - K[now] - E[now]));
        ret.dp1 /= G[now].size(); ret.dp1 *= (1 - K[now] - E[now]); ret.dp1 += K[now];
        ret.dpfa = (1 - K[now] - E[now])/G[now].size();
        ret.cons /= G[now].size(); ret.cons *= (1 - K[now] - E[now]); ret.cons += 1 - K[now] - E[now];
        return Node(ret.dp1/tmp, ret.dpfa/tmp, ret.cons/tmp);
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        for(int cas = 1; cas <= t; cas++)
        {
            scanf("%d", &n);
            for(int i = 1; i <= n; i++) G[i].clear();
            for(int i = 1; i <= n - 1; i++)
            {
                scanf("%d %d", &x, &y);
                G[x].push_back(y);
                G[y].push_back(x);
            }
            for(int i = 1; i <= n; i++)
            {
                scanf("%d %d", &x, &y);
                K[i] = x*1.0/100; E[i] = y*1.0/100;
            }
            memset(vis, 0, sizeof(vis));
            dfs(1);
            Node one;
            for(unsigned int i = 0; i < G[1].size(); i++)
                one = one + solve(G[1][i]);
            if(G[1].size() - one.dp1 - one.dpfa < eps)
            {
                printf("Case %d: impossible\n", cas);
                continue;
            }
            double ans = (one.cons + G[1].size())/(G[1].size() - one.dp1 - one.dpfa);
            if(ans < eps) printf("Case %d: impossible\n", cas);
            else printf("Case %d: %.6f\n", cas, ans);
        }
        return 0;
    }
    


    展开全文
  • 看了题解后才明白,应该按照期望设状态,而且需要在树上进行状态转移,最开始的状态转移方程最后化简即可消除影响(貌似就是树形DP+概率DP) 设dp[i]表示从i号结点走出迷宫时走过边数的概率,par[i]表示i号结点的...
  • 题意:有n个城市,n-1条路(从任一城市出发都能够到达任意城市,故该),求从1点到各个叶子点的期望长度 思路:假设dp[x]为到达x节点后还要走的期望长度,则其父节点的期望长度dp[fa] = ∑(dp[x]+1); 因为...
  • 首先它的限制关系是一个树形图 首先考虑如果它是一个外向树该怎么做。 这是很简单的,我们相当于每个子树的根都是子树中最早出现的点,概率是容易计算的。 设DP状态\(f[i][j]\)为做到以i为根的子树,子树中权值W的和...
  • 进入游乐园后,小Z看了看游乐园的地图,发现可以将游乐园抽象成有n个景点、m条道路的无向连通,且该中至多有一个环(即m只可能等于n或者n-1)。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩,于是他...
  • 中文翻译描述Famil Door的城市地图看起来像一棵(无向无环)所以其他人叫他Treeland。城市里有n个由n-1条双联通边连接起来的节点。 Famil Door有m个朋友生活在这城市。第i个朋友住在uiu_i而且在viv_i工作。在...
  • 我们详细说明了条件概率对通常树形图的替代表示。 我们称其为“龟背图”,因为它与龟壳上的图案相似。 采用事件和样本空间的集合理论视图,龟背图使用来自维恩图的元素(集合相交,补码和分区)进行条件化,另外的...
  • 你现在有一个 nnn 个结点 mmm 条边的无向带权连通,现在你有 qqq 个等概率发生的改变,每次会将原中某一条原先存在的边权变大,但只会改变其中的一条,问你在这样的情况下,中生成最小生成权值的期望是多少...
  • HDU - 5886 给定一棵树,每条边都有一个权值 定义一条边的战术价值为割去这条边后 剩下的中最长链的长度 求随机割掉一条边,战术价值的期望 题目要求乘以 N−1N-1,所以直接...这个简单地做一次树形dp就能得出
  • 我的理解:dfs+dp=树形DP 【Key】建树+dfs+更新dp[i][j] dp[i][j] : j个士兵进攻房间i可获得的最大概率,final 我们求dp[1][m] 水平有限,不明白为什么要建立无向,有些细节还是不懂 #include using ...
  • 题意:风暴斗篷现在要攻打雪漫城。雪漫城有n(n≤100000)个哨塔防守,哨塔... 分析:这就是一个树形dp,和期望没什么关系。求的就是n-1种划分后的最长路之和。对于一个结点x,无非要求两个东西,以它作为根的子树中的
  • 题目链接: ... 题目意思: 给一,n个点,m条边,每条边有个花费,给出q条可疑的边,每条边有新的花费,每条可疑的边出现的概率相同,求不能经过原来可疑边(可以经过可疑边新的花费构建...树形dp+MST。 先用krusk...
  • 题意:给一个树状,从屋子1开始,等概率选择一条路走过去,对于屋子 i 会有概率 ki 被杀死(被传送到屋子1),ei逃脱(结束),问逃脱的期望是多少。 思路:用 dp [ i ] 表示在屋子 k 逃脱的期望步数,那么有以下...
  • 现在已知某条边要发生突变,再给q个三元组,每个三元组(a,b,c),(a,b)表示中可能发生突变的边,该边一定是中的边。c表示该边新的权值,c只可能比原来的权值大。给的q条边发生突变的概率是一样的。求突变后连通n...
  • 5.1 overview5.1.1 提出问题 ... 有例如确定性CPDs、树结构CPDs、逻辑CPDs&一般化、含有OR/AND噪声、线性高斯&一般化5.2 Tree-Structured CPDs5.2.1 普通树形CPD  树形CPD指叶子节点是CPD,内部节点是变量,变量指向
  • 现在已知某条边要发生突变,再给q个三元组,每个三元组(a,b,c),(a,b)表示中可能发生突变的边,该边一定是中的边。c表示该边新的权值,c只可能比原来的权值大。给的q条边发生突变的概率是一样的。求突变后连通n...
  • 1、模型的树形结构分类: a)动态贝叶斯网络(DBN):用于处理随时间变化的动态系统中的推断和预测问题。 其中因马尔科夫模型(HMM)在语音识别、汉语自动粉刺与词性标注和统计机器防疫等若干语音语言处理任务中...
  • 表示:常用序贯树形图等序贯模型表示样本空间的试验结果 概率公理 非负性:∀A,P(A)≥0\forall A, P(A)\geq0∀A,P(A)≥0 可加性:∀A,B,A∩B=∅,P(A∪B)=P(A)+P(B)\forall A,B, A\cap B= \varnothing ,

空空如也

空空如也

1 2 3 4 5 6
收藏数 119
精华内容 47
关键字:

概率树形图