算法设计与分析实验1.docVIP

实 验 内 容 一、实验内容 狼找兔子问题：一座山周围有n个洞，顺时针的编号为0,1,2,3,4，...，n-1,。一只狼从0号洞开始 ，顺时针方向计数，每当经第m个洞时，就进洞找兔子。例如n=5，m=3，狼经过的洞依次为0, 3, 1, 4, 2, 0。输入m，n。试问兔子有没有幸存的机会？如果有应该藏在哪儿？ 问题分析：设置两个数组，一个数组用于循环，演示狼每次经过的洞，如果每个洞都被经过，则兔子没有幸存的机会。如果最后经过的洞的数目小于总的数目，则比较两个数组，数组中不同的值代表被狼经过的洞，相同的值代表兔子可以藏身的洞。本题使用C++编写。 实验代码： 运行结果： 有52张牌，使它们全部正面朝上。第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下，第二轮从第3张牌开始，凡是3的倍数的牌，正面朝上的翻成正面朝下，正面朝下的牌翻成正面朝上。第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同的规则反转，以此类推，直到翻过的牌超过104张为止。统计最后有几张牌正面朝上，以及它们的位置号。 问题分析：设置一个数组，数组中每一个数的初始值都为1，当某张牌被翻转的时候，用0表示。每翻转一次，用一个变量count累计加1，然后检查变量的值，当count超过104的时候，跳出循环体。本题使用Java编写。 实验代码： 运行结果： A,B,C,D,E5人为某次竞赛的前五名，他们在名次公布前猜名次。 A说：B得第三名，C得第五名。 B说：D得第二名，E得第四名。 C说：B得第一名，E得第四名。 D说：C得第一名，B得第二名。 E说：D得第二名，A得第三名。 结果每个人都猜对了一般，实际名次是什么呢？ 问题分析：本题使用多重嵌套循环，ABCDE每个人可能获得的名次分别是1,2,3,4,5，分别使ABCDE遍历每一种可能，当每个人的两个预言只有一个为真时，循环结束。本题使用C++编写。 实验代码： 运行结果： 计算机科学与工程学院 2 《算法设计与分析》实验报告