煮酒论英雄 众高手进来坐坐
C论坛热闹有余，但精彩论题不多。基本是新人雀跃，老将藏刀旁观。大概是高手们厌倦了这里到处都是的入门级（还有部分智障级）的提问，给分也提不起他们的兴趣了。
一旦众高手对这里完全失去了兴趣，这将是论坛的重大损失。（恐怕已经损失不少了）
兄弟斗胆提议，众高手有没有兴趣来下下棋？
当然，各位身在大江南北，想聚大家到一起品茗弈棋是不太可能了。
在网上对弈还是可以的。
不过就这么人和人下棋也没什么意思。不如让我们的程序和程序下棋如何？
众高手要是有兴趣的话就进来咱们议一议。
准备下什么棋、怎么下、程序的通讯接口方式等等。
或哪位有更有趣的并可实现的提议也不妨进来谈谈。（黑五角大楼主机这样的议题就免了，兄弟没那水平）
众英雄，廉颇老矣，尚能饭否？
最后顺道说说有容《大家用计算机解决个实际问题吧。》贴子中提到的问题。原贴见https://bbs.bccn.net/thread-370746-1-1.html
在原贴中我个人悬赏100专家分想激励坛友参与。可惜没什么达到预期的效果。
部分有能力的朋友这两天好像不在，还有一部分可能是不屑于解决这样的问题。
总之，到现在也没有出现让人满意的回答。这让我有一点失望。
在原贴中我说过这个问题的难度分两层。
第一层，找出满足要求的排列。
这一层很基础，不管算法如何，大家基本还是能做到的。
第二层，计算“找到的满足要求的排列”变换到“题目中给出的排列”所需的最少的交换次数。
这一层其实也不难，可惜到现在也没见一个可行的算法模型出来。众坛友的问题建模能力还有待提高。
其实这一层可以归结为图中的最短路径问题。属于图论的知识范畴，我记得以前就有人讨论过Dijkstra算法，完全可以直接应用到这里。
每一个排列可以看作是一个状态结点。
如果一个排列通过交换一对元素的位置可以变成另一个排列，那么用一条边关联这两个排列的状态结点。
由此构成一个图。
在这个理论模型上，连接两个点的最少的边数（也称两点的距离，可以认为每条边的权为1）即是从一个排列变换到另一个排列需要的最少次数。
对于原题，就是找从“728196345”到一个满足第一层要求的结点的距离。
关于最短路径算法我也不想在这里详述了。没学过但有兴趣的朋友，随便找本图论或算法的书看看，里面都会讲到。
最后送上我的代码给各位参考。我使用队列来存储点集，而队列以单向链表构成。各位也可以按自己的想法用数组等等来实现。
程序代码：#include<stdio.h>
#include<malloc.h>
typedef struct _node
{
int state;
int value;
struct _node * next;
}NODE;
typedef struct
{
NODE * head;
NODE * tail;
}QUEUE;
void queue_clear(QUEUE * q)
{
NODE *p, *t;
for(p = q->head; p != NULL;)
{
t = p;
p = p->next;
free(t);
}
q->head = NULL;
q->tail = NULL;
}
int queue_push(QUEUE * q, int state, int value)
{
NODE *p, *t;
if((p = (NODE *)malloc(sizeof(NODE))) == NULL) return 0;
p->state = state;
p->value = value;
p->next = NULL;
if(q->head == NULL) q->head = p; else q->tail->next = p;
q->tail = p;
return 1;
}
int queue_pop(QUEUE * q, int * state, int * value)
{
NODE * p;
if(q->head == NULL) return 0;
*state = q->head->state;
*value = q->head->value;
p = q->head;
q->head = q->head->next;
free(p);
return 1;
}
int queue_find(QUEUE q, int state)
{
NODE * p;
for(p = q.head; p != NULL && p->state != state; p = p->next);
return p != NULL;
}
int is_legal(int state)
{
int a, b;
a = state / 1000000;
a = a / 100 * (a % 100);
b = state / 1000 % 1000;
if(a != b) return 0;
a = state % 1000;
a = a / 10 * (a % 10);
return a == b;
}
int swap(int state, int i, int j)
{
const int e[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
100000000};
int a, b;
a = state / e[i] % 10;
b = state / e[j] % 10;
state -= a * e[i];
state -= b * e[j];
state += a * e[j];
state += b * e[i];
return state;
}
int test(int initState, int * finalState, int * value)
{
int s, v, ts, i, j;
QUEUE q = {NULL, NULL};
queue_push(&q, initState, 0);
while(queue_pop(&q, &s, &v))
{
for(i = 0; i < 9; i++)
for(j = i + 1; j < 9; j++)
{
ts = swap(s, i, j);
if(is_legal(ts))
{
*finalState = ts;
*value = v + 1;
queue_clear(&q);
return 1;
}
if(!queue_find(q, ts)) queue_push(&q, ts, v + 1);
}
}
return 0;
}
int main()
{
int state, value;
if(test(728196345, &state, &value))
printf("%d step %d\n", state, value);
else
printf("no match.\n");
return 0;
}[ 本帖最后由 beyondyf 于 2012-6-6 20:07 编辑 ]
