算法设计与分析（试题A卷）

得分 评卷人

四、算法设计题（1小题10分、2小题12分、3小题10分，共32分）

1、老板有一袋金块（共n块，n是2的幂（n>=2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。（要求：用二分法解决问题。）

四川师范大学成教×××专业×××层次半脱产形式期末考试期末试卷第5页( 共6页)

2、部分背包问题：一个商人带着一个能装M千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现在已知有多种货源，知道每一种货物的重量和获利情况。请编写算法帮助商人收购货物，以获取最高的利润。

3、百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？

四川师范大学成教××专业××层次××形式期末考试 ××试卷 第6页( 共6页)