過河卒演算法java實現

❶ 過河卒，24點 pascal語言程序。（我是初學者寫的易懂點 能省過程、函數盡量省）

program E1_1; {knight}
const
dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);
這個就是傳說中的增量矩陣。其實也沒那麼神秘，就是一張表，有8種變化狀態，每種狀態對應了一個delta
x和y，比如第一種變化，x坐標減小2，y坐標加1。表示在棋盤上的8種行走方式。
var
n,m,x,y,i,j: byte;
g:array[0..20,0..20] of 0..1;
c:longint;
infile,outfile:text;
//這邊是關鍵步驟
procere sol(x,y:integer);
var i:integer;
begin
if (x=n) and (y=m) then c:=c+1（當前x,y坐標都為目標坐標，那麼總路徑c +1，c為統計的路徑條數） else
begin//深搜，只有2個法則，向上y+1,向左x+1。並且判斷有沒有出界。
if (y<m) and (g[x,y+1]=0) then sol(x,y+1);
if (x<n) and (g[x+1,y]=0) then sol(x+1,y);
end;
end;

begin
assign(infile,'knight.in');
assign(outfile,'knight.out');
reset(infile);
readln(infile,n,m,x,y);
close(infile);

g[x,y] := 1;
for i:=1 to 8 do
if (x+dx[i]>=0) and (x+dx[i]<=n) and (y+dy[i]>=0) and (y+dy[i]<=m) then
g[x+dx[i],y+dy[i]]:=1;//給地圖賦值，0為可走，1為被馬控制，如g[1,1]=1說明坐標（1，1）點被控制了。
sol(0,0);//從坐標（0，0）開始走。

rewrite(outfile);
writeln(outfile,c);
close(outfile);
end.
/----------------------------------------------------/
type arr=array [1..4] of integer;
var i,result,n,len:integer;
d:arr;
r:array [1..3,1..4] of integer;
procere print; //打答案用的，r[i,1],r[i,3]為運算數字,r[i,2]為運算符，r[i,4]為答案
var i,j:integer;
begin
assign(output,'point.out'); rewrite(output);
for i:=1 to 3 do
begin
for j:=1 to 3 do
if j<>2 then write(r[i,j])
else case r[i,j] of
1:write('+');
2:write('-');
3:write('*');
4:write('/')
end;
writeln('=',r[i,4])
end;
close(output);
end;
procere try(k:integer;var d:arr); //枚舉，d數組暫存結果
var a,b,i,j,l,t:integer;
e:arr;
begin
if k=1 then
if d[1]=24 then begin print;halt end
else
else begin
for i:=1 to k-1 do
for j:=i+1 to k do
begin
a:=d[i]; b:=d[j]; //枚舉要用的兩個數
if a<b then begin t:=a;a:=b;b:=t end;
t:=0;
for l:=1 to k do if (l<>i) and (l<>j) then begin t:=t+1;e[t]:=d[l] end; //將剩下的數放好
r[5-k,1]:=a;
r[5-k,3]:=b;
r[5-k,4]:=-1;
for l:=1 to 4 do //枚舉運算符
begin
case l of
1:r[5-k,4]:=a+b;
2:r[5-k,4]:=a-b;
3:r[5-k,4]:=a*b;
4:if b<>0 then if a mod b=0 then r[5-k,4]:=a div b
end;
r[5-k,2]:=l;
if r[5-k,4]<>-1 then
begin
e[t+1]:=r[5-k,4];
try(k-1,e)
end
end
end
end;
end;
begin
assign(input,'point.in');reset(input);
for i:=1 to 4 do read(d[i]);
close(input);
try(4,d);
assign(output,'point.out');rewrite(output);
writeln('No answer!');
close(output);
end.

❷ 兩段簡單pascal程序求演算法分析【急！！】

兩個都是經典題。

第一題：最大連續子段和，DP。f(i)表示1~i的以i結尾的最大連續子段和是多少（也就是你程序中的t）。那麼當f(i)<0的話，顯然下一個數就不要與f(i)連起來了，為什麼呢？比如說，現在數列的1 -3 1。那麼f(2)=-2。這時候算f(3)的話，顯然f(3)=1比f(3)=-2+1=-1優。最後答案就是所有f(i)的最大值。

第二題：還是DP。先把兵不能走的地方標記出來（也就是馬能到的地方）（也就是程序中的b數組）。然後f(i,j)表示兵走到(i,j)這個格子的方案數（也就是程序中的a數組）。那麼f(i,j)=f(i-1,j)+f(i,j-1)。因為只有(i-1,j)和(i,j-1)可以走到(i,j)這個格子。最後就輸出f(n,m)就可以了。

❸ 我用java寫了一個商人過河的程序，但是有一個錯誤，大家幫我找一下

if((isavilable(a,stage[i],b))&&(mark[i]!=0))

❹ 用java實現野人傳教士過河問題

//CrossRiverQuestion.java
importjava.util.ArrayList;
importjava.util.List;

publicclassCrossRiverQuestion{
publicstaticvoidmain(String[]args){
CrossRiverQuestionq=newCrossRiverQuestion(5,4);
q.solveQuestion();
}
privateintpeoNum;
privateintsavageNum;
privateList<Node>resultList=newArrayList<Node>();
publicList<Node>solveQuestion(){
Noden=newNode(peoNum,savageNum,0,0,0,newArrayList<Integer>(),0,0);
booleandfsResult=dfs(n);
if(dfsResult){
resultList.add(0,n);
for(Nodenode:resultList){
System.out.println("左岸傳教士："+node.getLeftPeo()+"左岸野人："+node.getLeftSavage()+"右岸傳教士："+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上傳教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());
}
returnresultList;
}
returnnull;
}

publicCrossRiverQuestion(intpeoNum,intsavageNum){
super();
this.peoNum=peoNum;
this.savageNum=savageNum;
}

privatebooleandfs(Noden){
if(n.hasVisited())returnfalse;
n.addCheckSum();
if(n.getLeftPeo()==0&&n.getLeftSavage()==0)returntrue;
if(n.getLeftPeo()<0||n.getRightPeo()<0||n.getLeftSavage()<0||n.getRightSavage()<0){
returnfalse;
}
if(n.getLeftPeo()<n.getLeftSavage()&&n.getLeftPeo()>0)returnfalse;
if(n.getRightPeo()<n.getRightSavage()&&n.getRightPeo()>0)returnfalse;
if(n.getCURR_STATE()==n.getStateBoatLeft()){
Noden1=newNode(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);
if(dfs(n1)){
resultList.add(0,n1);
returntrue;
}
Noden4=newNode(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);
if(dfs(n4)){
resultList.add(0,n4);
returntrue;
}
Noden5=newNode(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);
if(dfs(n5)){
resultList.add(0,n5);
returntrue;
}
}
else{
Noden6=newNode(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);
if(dfs(n6)){
resultList.add(0,n6);
returntrue;
}
Noden7=newNode(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);
if(dfs(n7)){
resultList.add(0,n7);
returntrue;
}
Noden1=newNode(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);
if(dfs(n1)){
resultList.add(0,n1);
returntrue;
}
Noden4=newNode(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);
if(dfs(n4)){
resultList.add(0,n4);
returntrue;
}
Noden5=newNode(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);
if(dfs(n5)){
resultList.add(0,n5);
returntrue;
}
}
returnfalse;
}
publicList<Node>getResultList(){
returnresultList;
}

}

Node.java

importjava.util.ArrayList;
importjava.util.List;

publicclassNode{
privateList<Integer>nodesCheckSum=newArrayList<Integer>();
privateintleftPeo;
privateintrightPeo;
privateintleftSavage;
privateintrightSavage;
privateintCURR_STATE=0;
privateintonBoatPeoNum=0;
privateintonBoatSavageNum=0;
privatefinalintSTATE_BOAT_LEFT=0;
privatefinalintSTATE_BOAT_RIGHT=1;
publicNode(intleftPeo,intleftSavage,intrightPeo,intrightSavage,intstate,ListcheckSumList,intonBoatPeoNum,intonBoatSavageNum){
this.CURR_STATE=state;
this.leftPeo=leftPeo;
this.leftSavage=leftSavage;
this.rightPeo=rightPeo;
this.rightSavage=rightSavage;
this.nodesCheckSum.addAll(checkSumList);
this.onBoatPeoNum=onBoatPeoNum;
this.onBoatSavageNum=onBoatSavageNum;
}
publicintgetLeftPeo(){
returnleftPeo;
}
publicvoidsetLeftPeo(intleftPeo){
this.leftPeo=leftPeo;
}
publicintgetRightPeo(){
returnrightPeo;
}
publicvoidsetRightPeo(intrightPeo){
this.rightPeo=rightPeo;
}
publicintgetLeftSavage(){
returnleftSavage;
}
publicvoidsetLeftSavage(intleftSavage){
this.leftSavage=leftSavage;
}
publicintgetRightSavage(){
returnrightSavage;
}
publicvoidsetRightSavage(intrightSavage){
this.rightSavage=rightSavage;
}
@Override
publicStringtoString(){
returnleftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;
}
publicintgetCURR_STATE(){
returnCURR_STATE;
}
publicvoidsetCURR_STATE(intcURR_STATE){
CURR_STATE=cURR_STATE;
}
publicintgetStateBoatLeft(){
returnSTATE_BOAT_LEFT;
}
publicintgetStateBoatRight(){
returnSTATE_BOAT_RIGHT;
}
publicintcalcCheckSum(){
return1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();
}
publicvoidaddCheckSum(){
intcheckSum=calcCheckSum();
nodesCheckSum.add(checkSum);
}
publicbooleanhasVisited(){
intsum=calcCheckSum();
for(IntegercheckSum:nodesCheckSum){
if(checkSum==sum)returntrue;
}
returnfalse;
}
publicList<Integer>getNodesCheckSum(){
returnnodesCheckSum;
}
publicintgetOnBoatPeoNum(){
returnonBoatPeoNum;
}
publicvoidsetOnBoatPeoNum(intonBoatPeoNum){
this.onBoatPeoNum=onBoatPeoNum;
}
publicintgetOnBoatSavageNum(){
returnonBoatSavageNum;
}
publicvoidsetOnBoatSavageNum(intonBoatSavageNum){
this.onBoatSavageNum=onBoatSavageNum;
}

}

❺ 簡單過河卒問題

/*
A點有一個卒，需要走到目標B點。行走規則：可以向下（共4步）或者向右（共8步）。
要求計算從A能夠到達B的路徑的條數，並輸出每一條路徑.

解：
題目描述的是一種在二維空間中情形。設 X 軸為從左到右，Y軸為從上到下。
有 A 和 B 兩點，第 1 維(X軸)距離d[1]=8，第 2 維（Y軸）距離 d[2]=8，
因此沿著點A到點B的向量為(8,4) 。每次沿著向量的一個方向（X軸或Y軸）運動一個單位，
也就是每次可以移到（1,0）或者(0,1)。計算從A到達B的路徑條數。

一般的情形是：
在 D 維空間中，有A，B兩點，
這兩點在第 1 維距離d[1]，第 2 維距離d[2]，...，第D維的距離d[D],
因此沿著點A到點B的向量為(d[1],d[2],...,d[D])。每次沿著向量的一個方向運動一個單位，
也就是每次可以移動(±1,0,...,0)或者(0,±1,...,0),...,或者(0,0,...,±1)，
這里的第 i 個 ±1，實際只能取+1或者-1，具體正負性和相應的 d[i] 一樣。
計算從A到達B的路徑條數。

解決的方案：
我們針對題目描述的二維空間的情形進行分析。
點A到點B的向量為(8,4) 定下來後，因為每次只能沿著向量的一個方向（X軸或Y軸）運動一個單位，
而這兩個方向是正交的，也就是互不影響的。
不管先走X方向，還是先走Y方向， 最後都一定是向X方向走 8 步，向 Y 方向走 4 步。

假設開始沿 X 方向運動一個單位，我們假設到達了點 A' 。
那麼點 A' 到點 B 的向量為(7,4) ，下面問題就是計算 A' 到達 B 的路徑條數。
可以發現，問題「計算 A 到達 B 的路徑條數」和問題「計算 A 到達 B 的路徑條數」是同一類問題。

假設開始沿 Y 方向運動一個單位，我們假設到達了點 A'' 。
那麼點 A'' 到點 B 的向量為(8,3) ，下面問題就是計算 A'' 到達 B 的路徑條數。
可以發現，問題「計算 A 到達 B 的路徑條數」和問題「計算 A'' 到達 B 的路徑條數」是同一類問題。

通過上面的兩個假設可以發現，不管第一步怎麼走，接下來都產生了一個相似的子問題。
這就是分治的策略，也就是把一個大問題，分解成若干個相似的子問題。

上面的兩個假設，最後的一個子問題必定是某點到 B 的向量為(1,0)，
或者某點到 B 的向量為(0,1)，這是能立即解決的子問題。
*/

#include <stdio.h>
#include <stdlib.h>

// 當前需要的維度，可以修改這個值進行擴展（不用改動演算法）
#define DIMENSION 2
// 每個維度的最大長度
#define MAX_LENGTH_PER_DIMENSION 100

// 空間最小的移動向量。一次只能在一個維度移動一個單位。
struct Step
{
// 維度索引
int index;
// 移動距離
int d;
};

/*
根據向量距離 distance ，計算每個維度上的最小移動單位。
通過 steps 和 stepsAmount 返回。

注意：如果向量距離某個維度上的的距離為 0 ，那麼這個維度上不會返回最小移動單位。
*/
void getSteps(int distance[],struct Step steps[],int *stepsAmount)
{
int i;
*stepsAmount=0;
for(i=0;i<DIMENSION;i++)
{
// 在維度 i 上距離不為 0 ，需要計算最小移動單位
if(distance[i] != 0)
{
steps[*stepsAmount].index = i;
steps[*stepsAmount].d = distance[i]>0 ? 1 : -1;

(*stepsAmount) ++;
}
}
}

// 列印最小移動單位
void printStep(const struct Step* step)
{
int i;
// 對於小於等於二維的坐標系，可以為每一步指定上下左右四個方向
if(DIMENSION <= 2)
{
if(step->index == 0)
{
if(step->d > 0)
printf("右");
else
printf("左");
}
else if(step->index == 1)
{
if(step->d > 0)
printf("下");
else
printf("上");
}
}
// 對於大於二維的坐標系，直接輸出移動向量。
else
{
printf("[");
for(i=0;i<DIMENSION;i++)
{
printf("%d",i==step->index ? step->d : 0);
if(i != DIMENSION-1)
printf(",");
}
printf("]");
}
}

void getPath(int distance[],
struct Step path[],int pathLength,int *totalSchemeAmount)
{
int i,j,k,d;

struct Step steps[DIMENSION];
int stepsAmount;

// 計算需要移動的總距離
for(i=0,d=0;i<DIMENSION;i++)
d += abs(distance[i]);

if(d == 0)
{// 已經走完全程，輸出路徑

for(i=0;i<pathLength;i++)
{
printStep(&path[i]);

if(i!=(pathLength-1))
printf(" ==> ");
else
printf("\n");
}

// 統計路徑條數
(*totalSchemeAmount) ++;
}
else
{
// 獲取最小移動單位
getSteps(distance,steps,&stepsAmount);
for(i=0;i<stepsAmount;i++)
{
// 任選一個維度，運動一個最小單位
path[pathLength++] = steps[i];
distance[steps[i].index] -= steps[i].d;

// 解決成子問題
getPath(distance,path,pathLength,totalSchemeAmount);

// 回溯
pathLength--;
distance[steps[i].index] += steps[i].d;
}
}
}

int main(int argc, char *argv[])
{
/* DIMENSION = 1 */
//int distance[DIMENSION]={-5};

/* DIMENSION = 2 */
int distance[DIMENSION]={8,4};

/* DIMENSION = 3 */
//int distance[DIMENSION]={1,1,1};

struct Step steps[DIMENSION],path[DIMENSION*MAX_LENGTH_PER_DIMENSION];
int stepsAmount,totalSchemeAmount=0;

// 計算路徑
getPath(distance,path,0,&totalSchemeAmount);
printf("一共 %d 條路徑。\n",totalSchemeAmount);

return 0;
}

❻ C語言——馬攔過河卒。看看我的演算法錯哪了，並改正。

我發網路消息你咋老不回呢？除了你所說的那個問題以外，
if(abs(mx-dx)==1&&abs(my-dy)==2||abs(mx-dx)==2&&abs(my-dy)==1)這一句有問題
你判斷掉了馬所在的控制點
改成
if(abs(mx-dx)==1&&abs(my-dy)==2||abs(mx-dx)==2&&abs(my-dy)==1 || dx==mx && dy==my)
結果就是對的了
你的程度風格有點別扭，有些控制語句是多餘的，還有就是在某些情況下，該演算法還有bug，

❼ 急！Pascal編程：過河卒（無馬攔）

遞歸演算法，適合m、n較小的情況。僅供參考：

const
	m=13;n=15;
var
	num:longint;
	
procerenext(x,y:integer);
begin
	if(x=m)and(y=n)thenbegin
		inc(num);
		ifnum>10000000thenbegin
			writeln('路徑太多，請採用更優演算法');
			halt;
		end;
	end	
	elsebegin
		if(y+1<=n)thennext(x,y+1);
		if(x+1<=m)thennext(x+1,y);
	end;
end;

begin
	num:=0;
	next(1,1);
	writeln(num);
end.
	

❽ pascal編程：過河卒

【問題分析】

跳馬是一道老得不能再老的題目，每位編程者都學過，一般是在學習回溯或搜索演算法時，很多書上也有類似的題目，一些比賽中也經常出現這一問題的變形（如NOIP1997初中組第三題）。有些同學一看到這種類型的題目就去盲目搜索，但事實證明：當n，m=15就會超時。

其實，對本題稍加分析就能發現，到達棋盤上的一個點，只能從左邊過來（我們稱之為左點）或是從上面過來（我們稱之為上點）。根據加法原理，到達某一點的路徑條數，就等於到達其相鄰的上點或左點的路徑數目總和。因此我們可以使用逐列（逐行）遞推的方法來求出從起點到終點的路徑數目。障礙點（馬的控制點）也完全適用，只要將到達該點的路徑數目設置為0即可。

假設用F[I,J]到達點（I,J）的路徑數目用G[I,J]表示點(I,J)是否為對方馬的控制點，G[I,J]=0表示不是對放馬的控制點，G[I,J]=1表示是對方馬的控制點。則，我們可以得到如下的遞推關系式：

F[I,J]=0{G[I,J]=1}

F[I,0]=F[I-1,0]{I>0,G[I,0]=0}

F[0,J]=F[0,J-1]{J>0,G[0,J]=0}

F[I,J]=F[I-1,J]+F[I,J-1]{I>0,J>0,G[I,J]=0}

上述遞推式邊界是：F[0,0]:=1。考慮到最大情況下：n=20，m=20，路徑條數可能會出現超出長整型範圍，所以要用int64或comp類型計數或者高精度運算。

（來源：http://hi..com/zhouqh_1997/item/c1b886861d0b6a1dc3162786）

【參考程序】

const dx:array[1..8] of integer=(-2, -1, 1, 2, 2, 1, -1, -2);

dy:array[1..8] of integer=(1, 2, 2, 1, -1, -2, -2, -1);

var n,m,x,y,i,j:integer;

g:array[0..20, 0..20] of boolean;

f:array[0..20, 0..20] of int64;

begin

readln(n,m,x,y);

g[x,y]:=true;

for i:=1 to 8 do

if(x+dx[i]>=0)and(x+dx[i]<=n)and(y+dy[i]>=0)and(y+dy[i]<=m)then

g[x+dx[i],y+dy[i]]:=true;

f[0,0]:=1;

for i:=1 to n do

if not(g[i,0]) then

f[i,0]:=f[i-1,0];

for i:=1 to m do

if not(g[0,i]) then

f[0,i]:=f[0,i-1];

for i:=1 to n do

for j:=1 to m do

if not(g[i,j]) then

f[i,j]:=f[i-1,j]+f[i,j-1];

writeln(f[n,m]);

end.

❾ 軟體開發工作人員必讀的書籍有哪些，特別是剛剛工作的

《人月神化》
《人件》
《軟體發布方法》
《數據倉庫項目管理》
《自適應軟體開發》
《功能點分析》
《創建軟體工程文化》
《OO項目開發》（這本書的名字記得不是很清楚）
這些書是一個系列叢書。清華大學出版社出的
《微軟項目：求生法則》
《微軟研發：致勝策略》
《微軟團隊：成功秘訣》
原來關於微軟開發的系列叢書。很難買到了，但網上的下載很多

《微軟的秘密》
很不錯的一本書。質量保證人員應該看得一本書。也是在網上下載吧

《軟體工程：實踐者的研究方法》
最經典的軟體工程書籍。十分難讀，但的確是經典,英文已經到今天為止版了,中文版,很多大學拿它做教材,可以本科很難理解它的重要性,建議5年以上工作經驗的同志們好好讀一下,
《重構》
《重構手冊》
這兩本書是中國電力出版社的書，一套，使開發人員改進自己代碼的教科書

《過河卒》
開發人員如何確定自己的技術人生，一本不錯的書，

《borland傳奇》
想了解PC軟體的發展，讀這個書最好，使你對軟體的發展和計算機系統有一個更深刻的了解。

《Java夜未眠》
不僅僅是講java語言的數，其中許多深刻的道理對質量保證人員也有很大的幫助

《計算機程序設計藝術》1，2，3卷
不知道怎麼評價這三本書，開發人員的床頭必備的書籍，就是一個字---牛

《軟體工藝》
告訴你什麼是軟體開發，什麼是程序員，讓我們知道我們是怎麼回事

《IT項目管理》（機械出版社）
PMP的管理書籍。項目組長必讀的東西，如何從開發人員變為項目管理人員，這個書寫的不錯

《高質量軟體項目管理》（清華大學出版社）
這本書將項目管理,軟體工程都寫到一起了,對於希望做項目管理和質量保證的人員很有用,對於一般的開發人員,你可以了解你以後的技術生涯需要那些技能和技巧,為以後的發展打下一個基礎
最後一個系列
軟體與系統思想家溫伯格精粹譯叢（清華大學出版社）
《質量、軟體、管理---協調管理》
《質量、軟體、管理---系統思維》
《程序員開發心理學》
《走查、審查、技術復審手冊》
還有其他的書，但我只有這幾本
《代碼大全I,II》
軟體編碼最經典的書籍,是兩本經典中的經典.

❿ java一個過河搭橋游戲，若木樁之間有木板則小人能到木板上，怎麼記住木板位置以及判斷木樁之間有無木板

判斷木樁的兩點左邊是否在木板上。你用swing。有發放判斷