算法分析与设计.doc

《算法分析与设计.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、重庆邮电大学研究生堂下考试答卷2013学年第1学期考试科目算法分析与设计姓名学号S130101200专业通信与信息工程得分2013年12月1日第一题一、问题的提出某国王对囚犯进行大赦，让一名狱吏〃次通过一排锁看的间房，每通过一次，按所定规则转动“间牢房屮的某些门锁，每转动一次，原来锁着的门被打开，原来打开的门被锁上,通过〃次后，门锁打开的，牢房屮的犯人得以释放，否则犯人不得释放。转动门锁的规则是这样的：第一次通过牢房，从第1问房开始要转动每一把锁，即把全部锁打开；第二次通过牢房时，从第二间房开始转动，每隔一间开始转动；第£次通过牢房时，从第R间房开始转动，但每隔

2、鸟-1间转动一次；问通过斤次后，哪些牢房的锁仍然是打开的？二、问题的求解1A、算法分析设计：1)由学习的数组技巧，可以想到设置〃个元索的一维数组a[n],用每个元索记录每把锁的状态，1表示被锁上，0表示被打开。2)用数学运算技巧，用数学运算模拟开关锁的技巧，“对第i锁进行一次开关锁”可以转化为算术运算a[i]=abs(-a[i])。3)由题意知，得到每次转动的具体牢房号如下：第一次转动的是123,4,5,6,7,8,9〃号牢房；第二次转动的是246.8,9号牢房；第三次转动的是3,6,9,号牢房；第i转动的是j,2i,3i,4i号牢房，他们的起点是八公差为i的

3、等差数列。综上所述，不做其他的优化，数组元素d[i](i=l,2,3,4况)的初值均为1,用蛮力法通过循环模拟狱吏的开关锁过稈，战示当第厂号牢房对应的数组元素。卩]为0时，该牢房的囚犯得到释放。B、算法效率的分析算法1的策略是蛮力算法，模拟了狱吏开关锁的全过程。主要操作是a[i]=abs(l-a[i])f由一次开关锁计算,算法的时间复杂度为：宛(1+丄+丄+丄)=0(hlogn)。23n三、问题的求解2A、算法分析与设计：将以上蛮力法加入更多的人脑思维，转动门锁的规则可以有另一种的理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三

4、次转动的是编号为3的倍数的牢房........则狱吏转动门锁的问题是一个关于因了个数的问题。令〃仇)为自然数刃的因了个数，这里不重复计算重复的因了，如4的因了为1,2,4共三个，而并不是1,2,3,4.则对于不同的,d(〃)有的为奇数，有的为偶数，见下表表1编号与因了个数的关系n1234567891011OGOd(n)12232424342■QQQ表1屮的〃⑺)有的额奇数，有的为偶数，由于牢房的门开始是关肴的，这样编号的为，的牢房，所含1至UiZ间的不重复的因子个数为奇数时，牢房报后是打开的，反Z,牢房是关闭的。由以上的分析，算法应该是求出每个牢房编号的不重复的

5、因了个数，当它为奇数时，这里边的囚犯得到大赦。由于一个数的因子没有规律可循，只能从1到/?枚举尝试。B算法的效率分析：算法I的策略是蛮力算法，模拟了狱吏开关锁的全过稈。主要操作是ai=abs({-ai),时间的近似复杂度为O(nlog(n))o使用了〃个空间的一维数组。而算法2没有使用辅助空间，但是求一个编号的因了个数也很复杂,其主要操作是i%丿是否为0,H2总共执行了1+2+3+++〃次，时间复杂度为0(牙)。由此可见，蛮力法并不总是因为减少了人脑的思维，就一定是效率最差的算法。对规模不是很大大的问题，蛮力法还是一直比较好的算法策略。四、问题的求解3A

6、算法的分析与设计仔细观察表1,不难发现这样的一个规律，当且仅当/?为完全平方数时，〃(册为奇数。这是因为非完全平方数的因子总是成对出现，当。是并的因子时，b=n/a-定也是n的因子。〃为非完全平方数时，〃为非完全平方数时，所以cifb,因此斤的因子总是成对出现的。而当/?为完全平方数时，^n=a无论d是否为素数，斤的因子总是单独出现的，其他因了对总是成对出现的，因此d(n)为奇数。例如：6的因子为(1,6),(2,3)两对；而25的因了为(1,25),5；36的因子为(1,36),(2,18),(3,⑵,(4,9),6。B算法的效率分析该算法无需存储任何数据，

7、只需依次判断是否为平方数，基本操作为判断i*i

8、丰又丰又丰又丰又丰亍匚/