Homework2 实验报告

Post:2014-07-05 18:03 Update:2014-07-05 20:50

一、实验环境：

  • 系统：MAC OS X 10.9
  • 浏览器：Chrome 35.0.1916.153

二、QUIZ

2.1-2.5 基础部分

略

2.6 中国队是冠军><

2.6.1 问题

实现一个方法forecast，预测世界杯冠军，要求提供如下功能：

  • 参数有两个：第⼀个参数是一个对象，分别表⽰示进⼊16强的各个队的能⼒力值，键为下图的国家编码，值为使⽤用这个函数的球迷⼼心⺫⽬目中这 个国家的实⼒力(⼀个⾮负整数)，且实⼒和胜率成正⽐(淘汰赛无平局)。第二个参数是使用这个函数的球迷希望获得的某⽀球队最终夺冠的概率，是某个国家的代码(如A1)。
  • 根据下图的对阵情况，返回第⼆个参数对应的国家能够取得最终冠军的概率。

2.6.2 思路

  1. 由于国家编码在实现过程中会带来不便，故利用encode对象将国家由原来的编码变为0-15编码，其中编码顺序为从上到下，从左到右，即0-7为上半区，8-15为下半区。
  2. 此问题可采用递归算法解决，即在2^n个球队决出冠军。因此利用function getChampion(data, candidate, total)递归解决。
  3. function getChampion(data, candidate, total)
  • 参数含义：
    • total：球队总数，是2的幂
    • data：total只球队的实力构成的数组
    • candidata：目标球队的下标
    • 返回值：目标球队在total只球队中夺冠的概率
  • 实现方法：
    • 递归边界：total==2，返回值等于目标球队的实力除以两队的实力和
    • 递归过程：total>2，依据概率论乘法原理可把夺冠分为两步：一是目标球队从自己所在的半区的total/2只球队中胜出，概率通过递归调用获得；二是与另外半区的球队进行决赛获胜。第二部分再利用全概率公式，将该事件划分为另外半区每只球队胜出的事件的并集，再在每个子集上计算目标球队与该球队进行决赛获胜的概率，最后取加权和即为第二部分的概率。然后把一二两部分的概率相乘即为结果。

补充：进行了容错性判断，确保参数为两个，第一个参数为16只球队的正确编码，第二个参数为某一只球队编码的字符串。

2.7 找呀找呀找同学

2.7.1 问题

实现一个方法search，search⽅法有两个参数：第⼀个是由上⾯数据结构为元素组成的数组。第⼆个参数是⼀个可变参数,其值可以是：

  • 数字：表⽰查找所有年龄和这个数字相同的同学信息组成的数组，找不到的情况下返回false;
  • 字符串：表⽰返回名称和该字符串同名的⼀一个同学的信息，找不到返回false;
  • 对象：可以是包含name，age和hometown任意一个或多个信息的对象(比如{name: xxx, hometown: xxx})。要求找到和这个对相匹配的同学信息组成的数组，如果找不到，返回false。

2.7.2 思路

  1. 首先检查参数个数是否为2以及第一个参数是否为对象类型，若不满足则返回false；
  2. 根据第二个参数的类型分别遍历数组：
    • number类型：检查数组中每个元素的age属性，将满足的结果加入数组，遍历结束，如果数组长度大于0，则返回数组，否则返回false；
    • string类型：检查数组中每个元素的name属性，如果某元素name属性等于第二个参数，则返回该元素。若找不到这样的对象，则返回false；
    • object类型：检查数组中每个元素，如果该对象的属性不是undefined，则检查与元素对应属性的值是否相同，将满足的结果加入数组，遍历结束，如果数组长度大于0，则返回数组，否则返回false；
    • 如果不是上述类型，则返回false。

2.7.3 改进

  1. 采用switch语句进行判断；
  2. 数组操作换用原生的方法，如push等；
  3. object类型在判断时，通过for...in...语句遍历condition的每个属性，并与学生信息数组的元素的对应属性比较，如此可以不用判断那些属性是undefined。

三、BONUS

3.1 找呀找呀找不同

3.1.1 问题

实现一个diff函数，参数为两个同学信息数组，返回⼀个数组——包含那些存在于第⼆个数组但是却不存在于第⼀个数组中的同学信息(⽐较时只看name)组成的数组。

3.1.2 思路

  1. 首先检查参数个数是否为2以及两个参数是否为对象类型，若不满足则返回false；
  2. 两重循环，第一重遍历第二个数组，第二重遍历第一个数组，检查元素的name属性是否相同，若相同则跳出第二重循环。如果第二重循环结束都未曾跳出，说明该同学未在第一个数组中出现，则加入结果数组。
  3. 两重循环结束后返回结果数组。

3.1.3 改进

  1. 数组操作换用原生的方法；
  2. 声明nameset对象，将第一个数组同学的名字作为nameset的一个属性，值设为1，遍历第一个数组得到nameset；
  3. 遍历第二个数组，将同学的名字作为属性名，判断nameset的该属性是否为空，若为空，说明该同学的名字在第一个数组中未出现。

3.2 排呀排呀排个序

3.2.1 问题

用JavaScript实现冒泡、插入以及选择排序。

3.2.2 思路

参见《算法导论》

3.3 Untrusted游戏：

Tips:

  • 利用if(false)和/**/可以使部分源代码失效；
  • 在补充函数体时，提前加上}可以在函数外添加代码；
  • 颜色是多个关卡的关键点；
  • 自定义Object会很有用，可以不受各种限制；
  • 最后一关。。。不知道咋提示了~就那样吧。