算法第四章作业
1.你对贪心算法的理解
答:贪心算法并不从整体最优上加以考虑,它所做的选择只是在某种意义上的局部最优选择。顾名思义,贪心算法总是做出在当前看来是最好的选择。
2.请说明汽车加油问题的贪心选择性质
答:汽车加油问题是找最少加油次数的问题;找到汽车满油量时可以行驶的最大路程范围内的最后一个加油站,加油后则继续用此方法前进。需要检查每一小段路程是否超过汽车满油量时的最大支撑路程,即汽车加油问题中,每一次贪心选择即为选择当前状态下能行驶到最远的加油站加油。贪心选择只有在解出相关子问题后,才能做出选择,在汽车加油问题中,子问题就是在未达到目的地时,找到汽车油量支撑不了下一次路程的站点加油,故选择这个站点即可。
3.请说明在本章学习过程中遇到的问题及结对编程的情况
答:问题:贪心算法思想基本掌握了,第四章实践题的第一三题都有思路,第三题代码比较难打出来,第二题当时没想出思路来
结对编程的情况:同伴在打完她的代码之后,她给我讲她的思路,然后我自己再消化,有时会给建议,最后再一起讨论。