首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

拼图初始化算法兑现

2012-08-30 
拼图初始化算法实现定理:图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于

拼图初始化算法实现
定理:图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述,把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。(参考http://www.cppblog.com/lemene/archive/2007/10/04/33405.html)

排列 1 3 2 6 0 5 4 7 8,它的逆序数为8,0元素行号为2,列号为2。逆序数加行号,列号的奇偶性为偶。
排列 1 2 3 4 5 6 7 8 0,它的逆序数为8,0元素行号为3,列号为3。逆序数加行号,列号的奇偶性为偶。两个图形的奇偶性相同,根据定理判断它们等价。

    for (int i=0; i<NODE_COUNT; i++) {        nodes[i] = i;    }        shuffle(NODE_COUNT, nodes);    if (parityCheck(NODE_COUNT, nodes) != parityCheck(NODE_COUNT, target)) {        //若不满足定理,则交换数组最后两个值,使其奇偶性改变。        int i = nodes[NODE_COUNT-2];        nodes[NODE_COUNT-2] = nodes[NODE_COUNT-1];        nodes[NODE_COUNT-1] = i;    }

热点排行