首页 › 题库 › 信息学奥赛 › 10.2 排列组合

信息学奥赛-入门级 题库

共 22 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 10.2 排列组合 清除
21 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

积木游戏:设有n 个小木块排成一排,如下图:

游戏开始时,每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种(约定:0表示红色,1表示黄色,2表示兰色)。要求通过翻看与交换方式对小木块重新排列(翻看的规则为每个小木快只能看一次),最终成为下面的形状:

即相同颜色的木块排列在一起,设计一个翻看与交换的方案,使得用最少的交换次数实现上面的要求。

[算法描述]  翻看小木块时,可以从两端进行。

例如,设中间状态如下:

此时,可以从两个方向看,即从A或B处开始:

(1)若看A则有三种可能性:

为红色,则不用交换

为兰色,交换一次,即A与B交换

为黄色,交换两次,即C与B交换一次,然后A与C再交换一次

此时,平均交换次数为1。


(2)若看B,也有三种可能性:

为兰色,则不用交换

为红色,交换一次,即B与A交换。

为黄色,交换一次,即B与C交换。

此时,平均交换次数为2/3。

由此可见,从B处翻看直到游戏结束,次数最少符合题目要求。

[程   序]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
22 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

灯的排列问题:设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N1,N2,……Nk(k表示不同颜色灯的个数)。

   放灯时要遵守下列规则:

①同一种颜色的灯不能分开;

②不同颜色的灯之间至少要有一个空位置。

   例如:N=8(格子数)

         R=2(红灯数)

         B=3(蓝灯数)

   放置的方法有:

放置的总数为12种。

    数据输入的方式为:

N

P1(颜色,为一个字母) N1(灯的数量)

P2                     N2

   ……

Q(结束标记,Q本身不是灯的颜色)

    程序要求:求出一种顺序的排列方案及排列总数。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情