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語言中交換a、b兩個數的一種演算法
a=a^b^(a^b)
定義兩個數int x,y;
如果x=0,y=0,x^y==0;
如果x=0,y=1,x^y==1;
如果x=1,y=0,x^y==1;
如果x=1,y=1,x^y==0;
③ 用C語言怎麼編一個a^n(a的n次方)的演算法
如果n比較小，可以吧
result
*=
a循環n次。。
如果n比較大，
可以逐步來算。
這樣考慮，f(n)
=
2^n
如果有了
f(m)的結果，
那麼
f(2m)和f(2m+1)
就分別等於
f(m)*f(m)和f(m)*f(m)*a
所以可以從最高位開始查看n的每一位，
如果這一位是1，
那麼
result
=
result
*
result
*
a;
如果這一位是0，那麼result
=
result
*
result;
其中result
的初始值是1。
這樣復雜度就是log(n)的
④ 求一個A*演算法的C語言或C++代碼，小弟不勝感激，謝謝
1#include <iostream>
2#include <queue>
3usingnamespace std;
4
5struct knight{
6int x,y,step;
7int g,h,f;
8booloperator< (const knight & k) const{ //重載比較運算符
9return f > k.f;
10 }
11}k;
12bool visited[8][8]; //已訪問標記(關閉列表)
13int x1,y1,x2,y2,ans; //起點(x1,y1),終點(x2,y2),最少移動次數ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8個移動方向
15priority_queue<knight> que; //最小優先順序隊列(開啟列表)
16
17boolin(const knight & a){ //判斷knight是否在棋盤內
18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)
19returnfalse;
20returntrue;
21}
22int Heuristic(const knight &a){ //manhattan估價函數
23return (abs(a.x-x2)+abs(a.y-y2))*10;
24}
25void Astar(){ //A*演算法
26 knight t,s;
27while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29if(t.x==x2 && t.y==y2){
30 ans=t.step;
31break;
32 }
33for(int i=0;i<8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35if(in(s) &&!visited[s.x][s.y]){
36 s.g = t.g +23; //23表示根號5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step +1;
40 que.push(s);
41 }
42 }
43 }
44}
45int main(){
46char line[5];
47while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56return0;
57}
58
⑤ c語言中a+=a-=a*=a這個表達式的演算法是怎麼算的
a的初值呢？
a初值為12時，a+=a-=a*=a結果為0
步驟：
這個表達式的運算是從右向左的：
1.
a*=a：a=a*a=12*12=144
2.
a-=144:
a=a-144=144-144=0
3.
a+=0:
a=a+0=0+0=0
⑥ C語言a=a++的運算順序是怎麼樣的
這兩個程序的輸出結果是相同的：
因為它們的操作都是：先取變數a的值，取完後a自增，最後取前面取到的值賦值給賦值號左邊的變數（所以最後輸出變數的值就都是1）。
⑦ a在c語言中是什麼意思
a-=a的意思為a=a-a，先用a減a,然後再將得到的結果賦值給a。-=實際上是一種縮寫形式，使得對變數的改變更為簡潔。
運算時，可以將其寫成熟悉的形式，從右向左依次計算，注意在每次計算時，變數的值會發生改變， 如不注意，就會導致錯誤的情況發生。
C語言
是一門面向過程的、抽象化的通用程序設計語言，廣泛應用於底層開發。C語言能以簡易的方式編譯、處理低級存儲器。C語言是僅產生少量的機器語言以及不需要任何運行環境支持便能運行的高效率程序設計語言。
盡管C語言提供了許多低級處理的功能，但仍然保持著跨平台的特性，以一個標准規格寫出的C語言程序可在包括類似嵌入式處理器以及超級計算機等作業平台的許多計算機平台上進行編譯。
⑧ c語言'a'和"a"有什麼區別
1、本質區別
雙引號裡面的是字元串， 而單引號裡面的代表字元。
2、輸出區別
str = 「a」輸出的就是a這個字母；
str = 『a』輸出的測試65
3、底層區別
用單引號引起的一個字元實際上代表一個整數，整數值對應於該字元在編譯器採用的字元集中的序列值。
(8)a演算法c語言擴展閱讀：
C 語言中，逗號（,）也可以是運算符，稱為逗號運算符（Comma Operator）。逗號運算符可以把兩個以上（包含兩個）的表達式連接成一個表達式，稱為逗號表達式。其一般形式為：
子表達式1, 子表達式2, ..., 子表達式n
例如：a + b, c = b, c++
逗號運算符的優先順序是所有運算符中級別最低的，通常配合 for 循環使用。逗號表達式最右邊的子表達式的值即為逗號表達式的值。上例中，c++ 的值（c 自增之前的值）即為該表達式的值。
逗號運算符保證左邊的子表達式運算結束後才進行右邊的子表達式的運算。也就是說，逗號運算符是一個序列點，其左邊所有副作用都結束後，才對其右邊的子表達式進行運算。因此，上例中，c 得到 b 的值後，才進行自增運算。