( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230192{main}( ).../view.php:0
20.0001230936include( '/var/www/html/head.php' ).../view.php:2
30.0016250296isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(14)-决策树

小学计算思维课程(14)-决策树

小学计算思维课程(14)-决策树

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第十四课:决策树

上节课,我们介绍了一种度量信息量多少的方法,就是通过猜中一个词语的次数来衡量。使用相同的办法,我们来进行一个猜数字的游戏。

首先,我们需要一个搭档,让他在1—100中任意选一个数字,而你来猜。你可以向你的搭档提出任何问题,但你的搭档只能回答“是”或“不是”。试着用最少的次数猜中这个数字。

问题:

1.你需要猜几次才能猜中数字?(对比其他人的成绩)

2.如果提问策略是“是1吗?是2吗?是3吗?……”则最多需要几次才能猜中?最少要几次才能猜中?

3.怎样提问可以最快猜中?使用这种方法最多要问几次?

现在让我们变个花样再玩一次这个游戏。让你的搭档用它的出生年份的后两位作为那个数字(如2008年出生,就取8),这时怎样猜可以最快猜中?对比两次猜测的过程,你认为哪个信息的“惊奇值”更大?

猜数字游戏有一个有趣的特点,如果数字的范围扩大10倍(1—1000),但你猜测的次数并不会增加10倍,而是只需要多问3个问题。比如90这个数,大于500吗?(不是)大于250吗?(不是)大于125吗?(不是)3个问题后,我们就把范围锁定在1-125,也就是每次提问,都能将目标数字的范围缩小一半。

现在让你的搭档从1—10000中任选一个数字。看看你最少能用几次猜中这个数字。

现在我们就可以用猜中数字的次数来衡量这个数字的信息量,如果每猜一次算一个比特(“是”用1表示,“不是”用0表示),那么就可以用二进制位来表示这个数字。比如1—8的数,一定可以通过问3次猜中,那么这个数字的信息量就是3比特。

上面这个猜测的过程可以形象化的用一棵“决策树”表示:

从上面的决策树中可以看到,从0到7每个数字都有一条路径,每个路径都可以用二进制表示,比如3的路径是“否是是”,写成二进制是011。上图初看起来并不像树,但只要把图倒过来,就会发现它是一棵从上往下生长的“树”,并且每次都有两个分叉。

问题:

1. 数字5的“是否”路径是什么?写成二进制是多少?

2. 如果数字在0到7之间,你最多需要猜几次“是否”?

3. 请你设计一棵决策树,用来猜0—15的目标数字。