蓝桥杯算法题目-垒骰子-使用 C++ 解法 - sbw Blog

蓝桥杯算法题目-垒骰子-使用 C++ 解法

来源: sbw Blog | 浏览: 453 | 评论: 0 发表时间: 2020-02-23

做了道蓝桥杯算法题:赌圣atm晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥! 我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。 假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 由于方案数可能过多,请输出模 10^9 + 7 的结果。



解题思路

先分析一下最简单情况,不考虑互斥问题:假如只有一个骰子,由于有6个面,每个面朝上的时候侧面都可以旋转得到4个不同的摆放结果,所以总共有4*6=24种结果。 那么现在再增加一个骰子,两枚骰子来摆的话,那就总共可以有(4*6)*(4*6)=576种摆法。


再考虑题目中说的“互斥”问题:6个面可以互斥,由于A与B互斥时,B也与A互斥,所以总共有21种互斥可能(1+2+3..+6)。由于题目规定1对面是4,不妨先测试除了[1,4]和[4,1]以外,其它面都互斥的情况。 当有1个骰子时,互斥条件不存在,所以依然是24。当有2个骰子时,两个骰子贴合的地方只可能是(1, 4)或者(4, 1)。当为(1, 4)时,有4*4种组合,当为(4, 1)时,也有4*4种组合,总共32种。


当有3个骰子时,依此类推,有4*4*4*2种组合。


这样就可以看出规律了:当新加一个骰子时,就会在上一个情况的基础上再乘以当前骰子能带来的变化数量,而这个变化数量又依赖与上一个骰子哪个面向上,以及数据所给出的互斥条件。同时,由于在第一个骰子时不存在和上一个骰子的互斥,所以第一个骰子需要额外处理一下。


推导

所以大概程序的构思就是这样:假设现在已经排列好了K-1个骰子,我们当前要计算的结果是K个骰子,最终结果是N个骰子。那么我们需要先知道第K-1个骰子向上的是哪个面,然后根据这个数据和条件所给的互斥数据,遍历第K个骰子可以向下的面的列表。假设有一个不互斥的面,那么就会产生f(K-1)*4种摆法。将所有不互斥的面的摆法相加,即可得到最终结果。


另外,除了当骰子只有一个时,不计算互斥条件以外,还有另一个边界条件,那就是在某条排列路径上,一个骰子的顶面可能会导致接下来的骰子无法摆放,即与下一个骰子的所有面都会造成互斥。


实现代码

具体实现代码如下,注释已经写的很详细了,应该不需要额外说明了。




没有人评论过此文,还不快抢个沙发
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml