以下所有程序均通过编译与调试，应该没问题
第一题是经典的广度优先搜索问题，如果想要效率更高一点可以采用双向广度优先搜索，不过总共才9!=362880种状态，没太大必要，偷懒不写了
#include <iostream>
#define MAXN 362880
const int ftl[]={40320,5040,720,120,24,6,2,1,1};//阶乘
const int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
//约定用三行三列的二维数组表示一种状态，其中用0表示空位
int Code(int a[3][3])//特定状态转化为编号
{
int A[9];
int i,j;
int ans;
ans=0;
for (i=0;i<9;i++) A[i]=a[i/3][i%3];
for (i=0;i<9;i++)
{
ans+=A[i]*ftl[i];
for (j=i+1;j<9;j++)
if (A[j]>A[i]) A[j]--;
}
return ans;
}
int head,tail;
int queue[MAXN][3][3];
int tar[3][3],tarid;
int pi[MAXN];//记录队列中各节点的前趋节点
bool hash[MAXN];
int length;
int path[MAXN];//记录操作步骤
void Print(int i)//输出步骤
{
int j,k;
length=0;
while (i!=-1)
{
path[length++]=i;
i=pi[i];
}
std::cout<<"Total steps: "<<length-1<<std::endl;
for (k=length-1;k>=0;k--)
{
std::cout<<"Step "<<length-k-1<<":"<<std::endl;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++) std::cout<<queue[path[k]][i][j]<<' ';
std::cout<<std::endl;
}
}
return;
}
int main()
{
int i,j,k;
for (i=0;i<9;i++) std::cin>>queue[0][i/3][i%3];//约定输入时用0表示空格，读取初始状态
for (i=0;i<9;i++) std::cin>>tar[i/3][i%3];//读取目标状态
tarid=Code(tar);
pi[0]=-1;
memset(hash,true,sizeof(hash));
hash[Code(queue[0])]=false;
head=0;
tail=1;
while (head<tail && hash[tarid])
{
int x,y;//当前节点中空格的位置
for (i=0;i<9;i++)
if (queue[head][i/3][i%3]==0)
{
x=i/3;
y=i%3;
break;
}
for (i=0;i<4;i++)
{
int x2,y2,id;//新生成节点的空格位置以及编号
x2=x+dir[i][0];
y2=y+dir[i][1];
if (x2>=0 && x2<3 && y2>=0 && y2<3)
{
for (j=0;j<9;j++) queue[tail][j/3][j%3]=queue[head][j/3][j%3];
queue[tail][x][y]=queue[tail][x2][y2];
queue[tail][x2][y2]=0;
id=Code(queue[tail]);
if (hash[id])
{
hash[id]=false;
pi[tail]=head;
if (id==tarid) Print(tail);
tail++;
}
}
}
head++;
}
if (hash[tarid]) puts("No Solution!");
return 0;
}
第二题楼主的说明不是太明确，姑且做一些这样的约定吧：
输入数据的时候，不是直接输入多项式，而是多项式的项数，之后跟着一组一组的（系数，指数）组，并且为了方便，所有的系数、指数都是整数
输出按照多项式格式降幂输出
比如这样的输入
4
1 5 3 6 -2 2 4 0
2
1 1 1 0
#include <iostream>
struct Node//链表节点，也就是多项式的项
{
int c;//系数
int e;//指数
Node *next;//下一项
Node()
{
next=0;
}
};
void Insert(Node *p,int c,int e)//按降幂插入一项到多项式中
{
Node *q;
if (c==0) return;
while (p->e>e)
{
q=p;
p=p->next;
}
if (p->e==e)
{
p->c+=c;
if (p->c==0)//删除系数为0的项
{
q->next=p->next;
p->next=0;
delete p;
}
}
else
{
q->next=new Node;
q=q->next;
q->c=c;
q->e=e;
q->next=p;
}
return;
}
void Print(Node *p,bool first)//first为真表示p是多项式的第一项
{
if (p->e==0x80000000)
{
if (first) std::cout<<0;
std::cout<<std::endl;
}
else
{
if (!first && p->c>0) std::cout<<'+';
if (p->c!=1 && p->c!=-1) std::cout<<p->c;
else if (p->c==-1) std::cout<<'-';
if (p->e<0) std::cout<<'/';
if (p->e!=0)
{
std::cout<<'x';
if (abs(p->e)!=1) std::cout<<'^'<<abs(p->e);
}
Print(p->next,false);
}
return;
}
Node *p;//存放结果的链表
int main()
{
int n,c,e;
p=new Node;
p->c=1;
p->e=0x7FFFFFFF;
p->next=new Node;
p->next->c=1;
p->next->e=0x80000000;//设置指数很大和很小的两项作哨
std::cin>>n;//读取多项式1
while (n--)
{
std::cin>>c>>e;
Insert(p,c,e);
}
std::cin>>n;//读取多项式2
while (n--)
{
std::cin>>c>>e;
Insert(p,c,e);
}
Print(p->next,true);
return 0;