本文主要是介绍【贪心枚举】拨钟问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
有9个时钟，排成一个3*3的矩阵。现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。
移动 影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
输入
从标准输入设备读入9个整数，表示各时钟指针的起始位置。0=12点、1=3点、2=6点、3=9点。
输出
输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果。
样例输入
3 3 0
2 2 2
2 1 2
样例输出
4 5 8 9
解题思路：
假设时钟指针位置对应的值为clock_time，那么顺时针旋转90°就是clock_time = (clock_time+1)%4这一组时针就用一个数组表示。9种操作对应一个二维数组。这一题实质类似熄灯问题和画家问题。其共通点在于：操作对环境的改变是无序的，每个操作都会影响到周围的状态。同时每一种操作都有周期性限制，也即最多需要几次操作，多于这个次数产生循环。熄灯问题中，每个灯最多熄灯一次，因为灯只有两种状态，并且循环。而这里，有4种循环的状态，因此每个移动操作顶多使用3次。我们对移动方法1,2,3进行枚举，每种方法无非实施0-3次，也即一共4^3=64种情况。这些情况之间并非没有关系。例如，我们确定了1,2,3的情况数，那么得到一个灯A,B,C的状态，而只有移动4能够改变A，移动5能够改变B，移动6能够改变C，那么移动4-6的次数也确定了。同样，这时只有移动7能够改变D，移动9能够改变F，这时移动7和9的次数也确定了。最后，时钟A,B,C,D,F都已经到达12点，E,G,H,I还没确定，只剩下移动8能够改变GHI，所以只要检查E是否已经到达12点以及，GHI的时钟数是否相等就行了。最后找到一个移动次数最小的情况。
这题也可以用暴力搜索，因为最多有4^9个组合，不会超时。
这题还可以列出一个方程组，九个未知数，通过高斯消元法来解方程组。
(一开始用枚举法写了，至于上面的这种方法，稍后再补上吧)
代码：
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
}
这篇关于【贪心枚举】拨钟问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
