⑴ 人工智能的八数码问题，过程化的c语言编程方法，求解，好的话要多少分给多少分！！！
#include <stdio.h>
#include <stdlib.h>
#define TIME 50 //限定只搜索前50步，50步以后如果仍然没有搜索到结果，认为无解。
#define MAXSIZE 200
int n=1;
int result[9]={1,2,3,8,0,4,7,6,5};//所要达到的最终状态，0代表空格。
typedef struct{
int num[9];
char expension; //记录是否可以扩展，Y代表可以扩展，N代表不可以。
char banOperate; //表示不可以执行的操作，'L'代表不能左移，'R'代表不能右移，
//'U'代表不能上移，'D'代表不能下移，'C'代表可以任意移动。
int father; //记录父节点的下标。
}Node;
Node store[MAXSIZE]; //将搜索过的状态存储于该数组中。
int same(int temp) //判断是否达到了目标状态。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]!=result[j])
return 0;
return 1;
}
void printResult() //输出搜索结果。
{
for(int j=1;j<=n;j++)
{
printf("第%d步搜索后：\n",j);
printf("\t%d\t%d\t%d\n",store[j].num[0],store[j].num[1],store[j].num[2]);
printf("\t%d\t%d\t%d\n",store[j].num[3],store[j].num[4],store[j].num[5]);
printf("\t%d\t%d\t%d\n",store[j].num[6],store[j].num[7],store[j].num[8]);
printf("\n\n");
}
}
int left(int temp) //将空格进行左移操作。
{
for(int j=0;j<9;j++) //判断空格的位置。
if(store[temp].num[j]==0)
break;
if(j==0||j==3||j==6)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-1]; //将移动后的状态赋给store[n]
store[n].num[j-1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='R';
store[n].expension='Y';
store[n].father=temp;
if(same(n)) //判断store[n]是否为最终想得到的状态。
{
printResult();
exit(1);
}
n++;
return 1;
}
int right(int temp) //将空格进行右移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==2||j==5||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+1];
store[n].num[j+1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='L';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
int up(int temp) //将空格进行上移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==0||j==1||j==2)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-3];
store[n].num[j-3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='D';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
int down(int temp) //将空格进行下移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==6||j==7||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+3];
store[n].num[j+3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='U';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}
void init()
{
Node start;
printf("请输入初始状态，用空格分开，0代表空格:\n");//输入初始的状态。
for(int i=0;i<9;i++)
scanf("%d",&start.num[i]);
for(int k=0;k<9;k++)
if(start.num[k]==0)
break;
start.banOperate='C';
start.expension='Y';
start.father=-1;
store[0]=start; //将初始状态赋于store[0]。
}
void main(){
init();
if(same(0))
{
printf("没有必要进行搜索，初始状态即为最终状态!");
exit(1);
}
for(int i=0;i<TIME;i++) //开始进行宽度搜索，限定搜索上限为50步。
{
if(store[i].expension='Y')
{
if(store[i].banOperate=='L')
{
up(i);
right(i);
down(i);
}
if(store[i].banOperate=='R')
{
left(i);
up(i);
down(i);
}
if(store[i].banOperate=='U')
{
left(i);
right(i);
down(i);
}
if(store[i].banOperate=='D')
{
left(i);
up(i);
right(i);
}
if(store[i].banOperate=='C')
{
left(i);
up(i);
right(i);
down(i);
}
}
if(n>=TIME) //50步以后仍然没有达到所要求的状态，认为无解。
{
n--;
printResult();
printf("Sorry，在所在搜索范围内没有搜索到结果！");
exit(1);
}
}
}
⑵ 问： 40 人工智能及其应用期末作业 用A*算法解决下面的八数码难题。试定义估价函数，启发函数，
#pragma warning(disable:4786)
#include <algorithm>
#include <cstdio>
#include <set>
#include <utility>
#include <ctime>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
/*item记录搜索空间中一个结点
state 记录用整数形式表示的8数码格局
blank 记录当前空格位置，主要用于程序优化，
扩展时可不必在寻找空格位置
g, h 对应g(n), h(n)
pre 记录当前结点由哪个结点扩展而来 */
struct item
{
int state;
int blank;
int g;
int h;
int pre;
};
const int MAXSTEPS = 100000;
const int MAXCHAR = 100;
char buf[MAXCHAR][MAXCHAR]; //open表
item open[MAXSTEPS];
//vector<item> open;
int steps = 0;
//closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径
//每次只需得到对应f值最小的待扩展结点，用堆实现提高效率
pair<int, int> closed[MAXSTEPS];
//读入，将8数码矩阵格局转换为整数表示
bool read(pair<int,int> &state)
{
if (!gets(buf[0]))
return false;
if (!gets(buf[1]))
return false;
if (!gets(buf[2]))
return false;
//cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;
assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);
// astar.in中的每行数据长度必须为5
state.first = 0;
for (int i = 0, p = 1; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (buf[i][j] == '0')
state.second = i * 3 + j / 2; // state.second为0（空格）在节点中的位置
else
state.first += p * (buf[i][j] - '0');
p *= 10;
}
}
/* 若初试节点为:
1 2 3
8 0 4
7 6 5
则state.first为567408321，state.second为4
*/
return true;
}
//计算当前结点距目标的距离
int calculate(int current, int target) // return h=the sum of distances each block have to move to the right position,这里的each block不包括空格
{
int c[9], t[9];
int i, cnt = 0;
for (i = 0; i < 9; ++i)
{
c[current % 10] = t[target % 10] = i;
current /= 10;
target /= 10;
}
for (i = 1; i < 9; ++i)
cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);
return cnt;
}
//open表中结点间选择时的规则 f(n) = g(n) + h(n)
class cmp
{
public: inline bool operator()(item a, item b)
{
return a.g + a.h > b.g + b.h;
}
};
//将整数形式表示转换为矩阵表示输出
void pr(int state)
{
memset(buf, ' ', sizeof(buf));
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (state % 10)
buf[i][j] = state % 10 + '0';
state /= 10;
}
buf[i][5] = '\0';
puts(buf[i]);
}
}
//用于判断当前空格是否可以向对应方向移动
inline bool suit(int a, int b) //空格移动后的坐标为(a,b)
{
return (a >= 0 && a < 3 && b >= 0 && b < 3);
}
//递归输出搜索路径
void path(int index)
{
if (index == 0)
{
pr(closed[index].first);
puts("");
return;
}
path(closed[index].second);
pr(closed[index].first); //将整数形式表示转换为矩阵表示输出
puts("");
++steps;
}
int getNixuNum( int state ) //求节点的逆序对数
{
int sum = 0;
int result[9];
memset( result, 0, sizeof(result) );
//cout << result[8] << result[7] << endl;
char buf[10];
itoa( state, buf, 10 );
//cout << buf << endl;
int k = 0;
while( buf[k] != '\0' )
{
result[9-k-1] = buf[k] - '0';
k++;
}
for( int i = 0; i < 9; i++ )
{
for( int j = i + 1; j < 9; j++ )
{
if( result[i] && result[j] && result[i] > result[j] )
{
sum++;
}
}
}
return sum; //返回3*3方格数组的逆序对数
}
int main()
{
//cout << getNixuNum(87654321);
//open.resize(MAXSTEPS);
unsigned int t1 = clock();
//cout << open.size() << endl;
if( freopen("astar.in", "r", stdin) == NULL )
{
cout << "file not find\n";
exit(0);
};
freopen("astar2.out", "w", stdout);
set<int>states;
char tmp[100];
int i, x, y, a, b, nx, ny, end, next, index, kase = 0;
pair<int,int> start, target;
item head; //4个方向移动时的偏移量
const int xtran[4] = {-1, 0, 1, 0};
const int ytran[4] = {0, 1, 0, -1};
const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
while (read(start)) // 读取初试状态节点
{
unsigned int t2 = clock();
printf("Case %d:\n\n", ++kase);
gets(tmp);
read(target); // 读取目标状态节点
gets(tmp);
int targetNixuNum = getNixuNum(target.first);
//若两者的逆序对数不是同为奇数或同为偶数，则无解
if( !(getNixuNum(start.first)&1 && targetNixuNum&1 || !(getNixuNum(start.first)&1) && !(targetNixuNum&1)) )
{
cout << "无法从初始节点到终态节点\n";
exit(0);
}
//初始化open表，将初始状态加入
open[0].state = start.first;
open[0].h = calculate(start.first, target.first); // 计算当前节点到目标节点的估计距离
open[0].blank = start.second;
open[0].pre = -1; // 初始节点无父节点
open[0].g = 0; // 初始节点的g为0
index = 0;
states.insert(start.first); // 扩展过节点保存在states中，即出现过的状态保存在states中，states为set<int>类型，其中的states中的元素唯一
//提取open表中f值最小元素放入closed表，并对该结点进行扩展
for (end = 1; end > 0; ++index) // end为open表中的元素个数，一直循环到open表为空
{
assert(index < MAXSTEPS);
//临时存储
head = open[0]; // 由于使用pop_heap函数和push_heap函数，所以open[0]为g+h最小的元素
//放入closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在closed表中）
closed[index].first = open[0].state; //放入close表中，表示已经扩展完的节点，下面的for循环会扩展其节点
closed[index].second = open[0].pre; // index表示当前close表中当前扩展节点的下标
//从open表中删除该结点
pop_heap(open, open + end, cmp());//为algorithm文件中的函数，第一个参数指定开始位置，第二个指定结束，第三个指定比较函数
--end;
//得到结果，递归输出路径
if (head.state == target.first)
{
path(index);
break;
}
x = head.blank / 3;
y = head.blank % 3; //空格在3*3方格中的x,y坐标
/*
|2 0 3|
A = |1 8 4|
|7 6 5| // 看成3*3的数组
则head.blank=1
x=0,y=1,即空格的在3*3的数组中下标为(0,1)
*/
for (i = 0; i < 4; ++i)
{
nx = x + xtran[i];
ny = y + ytran[i];
/*
i=0时：(nx,ny）为当前空格向上移动一格后的坐标
i=1时：(nx,ny）为当前空格向右移动一格后的坐标
i=2时：(nx,ny）为当前空格向下移动一格后的坐标
i=3时：(nx,ny）为当前空格向左移动一格后的坐标
*/
if (suit(nx, ny)) // 判断是否能够移动
{
a = head.blank; // 空格当前位置,以上面矩阵A为例，a=1
b = nx * 3 + ny; // 空格移动后的新位置,开始是能够向右边移动，故b=0*3+2=2
//调换十进制表示整数对应两个数字位
next = head.state + ((head.state % p[a + 1]) / p[a] - (head.state % p[b + 1]) / p[b]) * p[b] + ((head.state % p[b + 1]) / p[b] - (head.state % p[a + 1]) / p[a]) * p[a];
// 如head.state=567481302,空格向右移动一次后，next=567481032,即为移动后的节点
// 判断能否由当前节点到达目标节点
if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )
{
//判断是否已经扩展过，即已经出现过
if (states.find(next) == states.end()) //没出现就保存一下，也存入open表
{
states.insert(next);
open[end].pre = index; //扩展后的子节点，其父节点为当前扩展节点
open[end].blank = b;
open[end].state = next;
open[end].h = calculate(next,target.first);
open[end].g = head.g + 1;
++end; //open表中元素加1
push_heap(open, open + end, cmp()); //压入堆中
}
}
}
}
}
if (end <= 0)
puts("No solution");
else
{
printf("Num of steps: %d\n", steps);
printf("Num of expanded: %d\n", index);
printf("Num of generated: %d\n", index + end);
printf("Time consumed: %d\n\n", clock() - t2);
}
states.clear();
steps = 0;
}
printf("Total time consumed: %d\n", clock() - t1);
return 0;
}
⑶ 八数码问题 C语言 广度优先 其他也OK
nclude "stdio.h"
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;
/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}
/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}
/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("请输入顶点数目：");
scanf("%d",&L->num);
printf("请输入各顶点的信息(单个符号）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("请输入边权矩阵的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("图已经创建完毕！");
}
/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n图的顶点数目为：%d",L.num);
printf("\n图的各顶点的信息为：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n图的边权矩阵的信息为：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("图已经输出完毕！");
}
/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))
else
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n广度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函数**********************/
void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
另外,虚机团上产品团购,超级便宜
⑷ 高分悬赏C语言高手帮我把这段C程序加注释
void print(int k) // 打印结果
{
if(out[k].pre != -1){
print(out[k].pre);
int i,j,f = out[k].data,tt;
printf("第%d步:\n",no++);
for(i = 2; i >= 0; i--){
for(j = 2; j >= 0; j--){
ot[i][j] = f%10;
f /= 10;
}
}
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
if(ot[i][j] == 0)
printf(" ");
else
printf("%d ",ot[i][j]);
}
printf("\n");
}
printf("\n");
}
}
int main(void)
{
int i,j,k,temp[9],s;
bool used[9] = {0};
char op[10];
printf("\t\t\t******************************\n");
printf("\t\t\t* 八数码问题A*搜索求解程序 *\n");
printf("\t\t\t* *\n");
printf("\t\t\t******************************\n\n\n");
printf("程序默认目标状态为：\n");
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
printf("%d ",ter[i][j]);
}
printf("\n");
}
while(1){
printf("确认请输入y，取消另输入目标状态请输入n:");
scanf("%s",op);
if(op[0] == 'n'){
printf("请参照上面的样式输入目标状态（空白位置以0代替）:\n");
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
scanf("%d",&ter[i][j]);
}
}
}
else if(op[0] != 'y')
printf("输入错误！\n");
else
break;
}
while(1){
printf("请参照上面的格式输入初始状态（空白位置以0代替）:\n");
k = 0;
bool error = false;
memset(used,0,sizeof(used));
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
scanf("%d",&sta[k]);
ot[i][j] = sta[k];
if(used[sta[k]]){
error = true;
}
used[sta[k]] = 1;
temp[k++] = ter[i][j];
}
}
int ts = nxnum(sta);
int tt = nxnum(temp);
if(error){
printf("输入错误(有相同数字出现)，请重新输入！\n");
continue;
}
if((ts&1) != (tt&1)){
printf("从初始状态无法到达目标状态，请重新输入。\n");
}
else break;
}
if(H(ot) == 0){
printf("所输入状态就是目标状态！\n");
return 0;
}
s = 0;
for(i = 0; i < 9; i++){
s = s*10 + sta[i];
}
astar(s);
print(pout);
printf("第%d步:\n",no);
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
if(ter[i][j] == 0)
printf(" ");
else
printf("%d ",ter[i][j]);
}
printf("\n");
}
printf("共走了%d步。\n",no);
long t = 10000000L;
clock_t start, finish;
double ration;
/* 测量一个事件持续的时间*/
start = clock();
while( t-- ) ;
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "搜索算法执行时间为：%f seconds\n", ration );
return 0;
}
我是提问者，这是代码，问题有字数限制，发不完
⑸ 为什么八数码问题用a*算法求解合适
其实A*算法也是一种最好优先的算法只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f'(n)=g'(n)+h'(n)这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
⑹ 八数码问题用C语言编程，注意C语言！！！
基于51的程序：
#include <reg52.h>
sbit sda=P0^5;
sbit scl=P0^6;
code char led_code[19]={0x11,0xd7,0x32,0x92,0xd4, // 0,1,2,3,4
0x98,0x18,0xd3,0x10,0x90, // 5,6,7,8,9
0x50,0x1c,0x39,0x16,0x38, // a,b,c,d,e,
0x78,0xfe,0xef,0xff}; // f - dot dark
void seperate(unsigned char second,minute,hour); //1调用拆分函数
void display(unsigned char second,minute,hour); // 2调用显示函数 一定要在各处强调unsignde吗？
void shift(unsigned char); //3调用移位函数
void delay_1s(unsigned int x); //4调用延时函数
unsigned char second,minute,hour;
unsigned char second0,second1,
minute0,minute1,
hour0,hour1; // 这三行表示了时、分、秒所占数码管的个数和位置。 叫形参？
void main()
{
while(1)
{
for(hour=0;hour<24;hour++) //三个for语句的安排妙啊！ 我们看到的钟表时分秒的变化
！
{
for(minute=0;minute<60;minute++)
{
for(second=0;second<60;second++)
{
display(second,minute,hour);
delay_1s(65535);
}
}
}
}
}
void display(unsigned char second,minute,hour) //2对显示函数的说明
{
seperate(second,minute,hour);
shift(second0);
shift(second1);
shift(16);
shift(minute0);
shift(minute1);
shift(16);
shift(hour0);
shift(hour1);
}
void seperate(unsigned char second,minute,hour) //1对拆分函数的说明
{
second0=second%10;
second1=second/10;
minute0=minute%10;
minute1=minute/10;
hour0=hour%10;
hour1=hour/10;
}
void shift(unsigned char n) //3对移位函数的说明
{
unsigned char dat,minute;
dat=led_code[n];
scl=0;
for(minute=0;minute<8;minute++)
{
if (dat&0x80) sda=1;
else sda=0;
scl=1;
scl=0;
dat<<=1;
}
}
void delay_1s(unsigned int a) //4对延时函数的说明
{
while(a--);
}
⑺ 求8数码A或A*算法（用C语言）
题目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1077
BFS:
#include <iostream>
using namespace std;
int fac[10]={1,1};
bool tflag[9];
struct bbit{
unsigned int val:4;
};
struct bbbit
{
unsigned int val:2;
};
struct Node
{
bbit s[9],pos;
int step;
bbbit path[21],tag;
int hashval()
{
int ret=0,i,j,tmp;
memset(tflag,false,sizeof(tflag));
for(i=0;i<8;i++)
{
tmp=0;
for(j=0;j<s[i].val;j++)
if(!tflag[j])
tmp++;
ret+=tmp*fac[8-i];
tflag[s[i].val]=true;
}
return ret;
}
bool up()
{
if(pos.val<=2)return false;
s[pos.val].val^=s[pos.val-3].val;
s[pos.val-3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-3].val;
path[step].val=0;
pos.val-=3;
return true;
}
bool down()
{
if(pos.val>=6)return false;
s[pos.val].val^=s[pos.val+3].val;
s[pos.val+3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+3].val;
path[step].val=1;
pos.val+=3;
return true;
}
bool left()
{
if(pos.val==0||pos.val==3||pos.val==6)return false;
s[pos.val].val^=s[pos.val-1].val;
s[pos.val-1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-1].val;
path[step].val=2;
pos.val--;
return true;
}
bool right()
{
if(pos.val==2||pos.val==5||pos.val==8)return false;
s[pos.val].val^=s[pos.val+1].val;
s[pos.val+1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+1].val;
path[step].val=3;
pos.val++;
return true;
}
bool operator==(const Node&x)const
{
int i;
for(i=0;i<9;i++)if(s[i].val!=x.s[i].val)return false;
return true;
}
}Q[362880],S,A,tmp,top;
struct Hash
{
bool d1,d2;
Node D;
}hash[362880];
inline void mkfac(){int i;for(i=2;i<=9;i++)fac[i]=fac[i-1]*i;}
inline int eval(char c){return c=='x'?0:c-'0';}
void o(Node x,Node y)
{
int i;
for(i=1;i<=x.step;i++)
{
switch(x.path[i].val)
{
case 0:putchar('u');break;
case 1:putchar('d');break;
case 2:putchar('l');break;
case 3:putchar('r');break;
}
}
for(i=y.step;i>=1;i--)
switch(y.path[i].val){
case 0:putchar('d');break;
case 1:putchar('u');break;
case 2:putchar('r');break;
case 3:putchar('l');break;
}
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i<=7;i++)A.s[i].val=i+1;A.s[8].val=0;A.pos.val=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t].val=eval(buf[i]);
if(S.s[t].val==0)
S.pos.val=t;
t++;
}
l=r=0;
flag=false;
for(i=0;i<362880;i++)hash[i].d1=hash[i].d2=false;
S.step=0;S.tag.val=1;
A.step=0;A.tag.val=2;
Q[r++]=S;//tag.val:1
Q[r++]=A;//tag.val:2
while(l<=r)
{
top=Q[l++];
top.step++;
tmp=top;
if(tmp.up())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.down())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.left())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.right())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
A*:
#include <iostream>
#include <queue>
using namespace std;
int fac[10]={1,1};
struct Node
{
int s[9],step,pos;
char path[501];
int hashval()
{
int ret=0,i,j,tmp;
bool flag[9];
memset(flag,false,sizeof(flag));
for(i=0;i<8;i++)
{
tmp=0;
for(j=0;j<s[i];j++)
if(!flag[j])
tmp++;
ret+=tmp*fac[8-i];
flag[s[i]]=true;
}
return ret;
}
bool up()
{
if(pos<=2)return false;
s[pos]^=s[pos-3];
s[pos-3]^=s[pos];
s[pos]^=s[pos-3];
path[step]='u';
pos-=3;
return true;
}
bool down()
{
if(pos>=6)return false;
s[pos]^=s[pos+3];
s[pos+3]^=s[pos];
s[pos]^=s[pos+3];
path[step]='d';
pos+=3;
return true;
}
bool left()
{
if(pos==0||pos==3||pos==6)return false;
s[pos]^=s[pos-1];
s[pos-1]^=s[pos];
s[pos]^=s[pos-1];
path[step]='l';
pos--;
return true;
}
bool right()
{
if(pos==2||pos==5||pos==8)return false;
s[pos]^=s[pos+1];
s[pos+1]^=s[pos];
s[pos]^=s[pos+1];
path[step]='r';
pos++;
return true;
}
bool operator==(const Node&x)const
{
int i;
for(i=0;i<9;i++)if(s[i]!=x.s[i])return false;
return true;
}
void show()
{
int i,j;
for(i=0;i<=6;i+=3,cout<<endl)
for(j=i;j<=i+2;j++)
cout<<s[j];
}
bool operator<(const Node&x)const
{
int la=0,lb=0,i;
for(i=0;i<8;i++)if(s[i]!=i+1)la++;la+=(s[8]!=0);
for(i=0;i<8;i++)if(x.s[i]!=i+1)lb++;lb+=(x.s[8]!=0);
return la>lb;
}
}S,A,tmp,top;
priority_queue<Node> Q;
bool hash[362880];
void mkfac(){int i;for(i=2;i<=9;i++)fac[i]=fac[i-1]*i;}
int eval(char c){return c=='x'?0:c-'0';}
void output(Node x)
{
int i;
for(i=1;i<=x.step;i++)
putchar(x.path[i]);
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i<=7;i++)A.s[i]=i+1;A.s[8]=0;A.pos=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t]=eval(buf[i]);
if(S.s[t]==0)
S.pos=t;
t++;
}
l=r=0;
flag=false;
memset(hash,false,sizeof(hash));
S.step=0;
while(!Q.empty())Q.pop();
Q.push(S);
while(!Q.empty())
{
top=Q.top();
Q.pop();
top.step++;
tmp=top;
if(tmp.up())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.down())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.left())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.right())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
⑻ 用c语言或c++实现，用深度优先算法，宽度优先算法和A算法求解把数码问题，请高手帮忙写出代码
看着懂，写出来就困难了
⑼ 八数码问题用c语言或者c++写的程序，麻烦在附带上算法 谢了发到[email protected]
<html>
<head>
<script type="text/javascript">
function disPlay(){
var b1 = document.getElementById("box1");
var b2 = document.getElementById("box2");
if(window.location.href = "http://www.abc.com/"){
b1.style.display = "none";
b2.style.display = "block"
}
else{
b1.style.display = "block";
b2.style.display = "none"
}
}
</script>
</head>
<body onload="disPlay();"> //页面加载以后及调用函数
<div id="box1">
box1需要显示的内容
</div>
<div id="box2">
box2需要显示的内容
</div>
</body>
</html>