迭代加深演算法
㈠ 埃及分數
埃及分數
埃及分數是指分子是1的分數，也叫單位分數。古代埃及人在進行分數運算時，只使用分子是1的分數。因此這種分數也叫做埃及分數，或者叫單分子分數。
中文名
埃及分數
發明地
埃及
快速
導航
相關傳說
現代探索
演算法解決
未來發展
歷史考證
埃及同中國一樣，也是世界上著名的文明古國。人們在考察古埃及歷史時注意到像阿基米德這樣的數學巨匠，居然也研究過埃及分數。本世紀一些最偉大的數學家也研究埃及分數，例如，沃爾夫數學獎得主，保羅-歐德斯，他提出了著名的猜想 4/n=1/x+1/y+1/z. 難倒了世界上第一流的數學家。當9個麵包要平均分給 10個人的時候，古埃及人不知道每個人可以取得 9/10，而是說每人1/3+1/4+1/5+1/12+1/30。真叫人難以想像，古埃及人連9/10都搞不清楚，怎麼知道9/10=1/3+1/4+1/5+1/12+1/30。所以幾千年來，數學史家一直堅持認為，古埃及人不會使用分數。 1858年，蘇格蘭考古學家萊登買到了一份古埃及草紙文件，經過鑒定這是繁生於尼羅河泛濫形成的池塘和沼澤地里的草製成的紙，成文年代約在公元前1700年。
埃及分數
在我們現今所使用的分數中，當有2個物品要平均分給3個人的時候，每個人可以取得2個1/3。你可以算成2/3 = 1/3 + 1/3。那麼，古埃及的人們，是怎麼算的呢？首先，把 2 個物品分成 4 個 1/2，先給每個人 1 個 1/2，剩下的 1 個1/2 再分成 3 等分，均分結果，每人分到 1/2 加 1/2 的 1/3，也就是 1/2 + 1/6 = 2/3。這份至今保存在大英博物館的「萊登」草紙，用很大的篇幅記載著將真分數分解成單分子分數，這種運算方式，遭到現代數學家們紛紛責難，認為埃及人之所以未能把算術和代數發展到較高水平，其分數運算之繁雜也是原因之一。
相關傳說
埃及金字塔是舉世聞名的，表明古埃及人具有高超的建築技巧和超凡的智力，難道最簡單的現代分數也不懂？金字塔所蘊含的難道是一篇粗劣的作品？
現代數學已經發展到十分抽象和復雜的程度，而埃及分數卻是這樣粗糙，在人們的記憶里早該煙消雲散了，然而，它產生的問題直到今天仍然引起人們的重視。
四川大學已故老校長柯召寫道：「埃及分數所產生的問題有的已成為至今尚未解決的難題和猜想，他們難住了許多當代數學家」。柯召本人至死都沒有能夠證明這個猜想。
一個古老的傳說是：
老人彌留之際，將家中11匹馬分給3個兒子，老大1/2，老二1/4，老三1/6。二分之一是5匹半馬，總不能把馬殺了吧，正在無奈之際，鄰居把自己家的馬牽來，老大二分之一，牽走了6匹；老二四分之一，牽走了3匹；老三六分之一，牽走了2匹。一共11匹，分完後，鄰居把自己的馬牽了回去。即11/12=1/2+1/4+1/6。
奇妙的埃及分數終於調動自己的潛在難度擊敗了敢於輕視他們的人們。並且給與嘲笑他的人以難堪的回答。
現代探索
相關發現
兩千多年後的數學家終於發現：2/n=1/[(n+1)/2]+1/[(n+1)n/2]； 1/n=1/(n+1)+1/[n(n+1)]；1=1/2+1/3+1/6。此時才大夢初醒。埃及分數以旺盛的生命力屹立在世界數壇，使三千年後的數學家也自嘆弗如。例如，分馬問題，能否設計出（n-1)/n=1/x+1/y+1/z .。經過2000多年的努力，終於揭開其中的奧秘：有6種可能，共7種分法。7/8=1/2+1/4+1/8；11/12=1/2+1/4+1/6=1/2+1/3+1/12；17/18=1/2+1/3+1/9；19/20=1/2+1/4+1/5；23/24=1/2+1/3+1/8；41/42=1/2+1/3+1/7。原先人們以為，這樣的情況大概有無窮多個，可是，繼續追擊卻一無所獲，真是難以預料。黑龍江的關春河發現共有43種情況。這是正確的。
求解過程
當限定分母為奇數時，把「1」分解為埃及分數，項數限定為9項，共有5組解：
1=1/3+1/5+1/7+1/9+1/11+1/15+1/35+1/45+1/231。
1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/135+1/10395。
1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/165+1/693。
1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/231+1/315。
1=1/3+1/5+1/7+1/9+1/11+1/15+1/33+1/45+1/385。
以上5組解是在1976年才找到。限定為11項時，發現了1組解 最小分母是105。若大於105則有很多的解。
1/n型分數還可以表示成為級數分解式：
1/n=1/(n+1)+1/(n+1)^2+1/(n+1)^3+1/(n+1)^4+....+1/(n+1)^k+1/n(n+1)^k.
埃及分數成為不定方程中一顆耀眼的明珠。
埃及分數最著名的猜想是Erods猜想：1950年Erods猜想，對於n〉1的正整數，
總有：
4/n=1/x+1/y+1/z. （1）
其中，x，y，z。都是正整數。
Stralss進一步猜想，當n≥2時，方程的解x，y，z滿足x≠y，y≠z，z≠x。x〈y〈z。
1963年柯召，孫奇，張先覺證明了Erods猜想stralss猜想等價。幾年後yamanot又把結果發展到10的7次方。以後一些數學家又把結果推向前去，始終未獲根本解決。對於4/n=1/x+1/y+1/z，只需要考慮n=p為素數的情況，因為若（1）式成立，則對於任何整數m，m<1，
4/pm=1/xm+1/ym+1/zm，（2）
也成立。
一切奇素數都可以表示為4R+1與4R+3型。對於p=4R+3型，（參見《單位分數》人民教育出版社1962年）：（1）式是顯然的。
2002年王曉明提出：
如果設X=AB,Y=AC,Z=ABCP,
即：
4/P=1/AB+1/AC+1/ABCP.（3）
對於p=4R+3型，（3）式是顯然的。
因為這時A=(p+1)/4 ，B=1。C=P+1.。
即：
4 /P = { 1/ [(P+1)/4] } + { 1 / [(P+1)(p+1)/4] } + { 1/ [p(p+1)(p+1)/4] }。 (4)
例如：4/7=1/2+1/16+1/112
對於p=4R+1 型的素數，把（3)式整理成 ：
4ABC=PC+PB+1 (5)
A = (PC+PB+1)/4BC (6)
在（6）式中，若要 B|(PC+PB+1)，需使得B|(PC+1)，設PC+1=TB；若要C|(PC+PB+1)，需使得C|(PB+1)，設PB+1=SC；對於P=4R+1形，若要4|p(C+B)+1],需C+B=4K-1，對於P=4R+3形，若要4|[P（C+B）+1]，需C+B=4K+1。於是，形成一個二元一次不定方程組：
-PC+TB=1 (7)
SC+(-P)B=1 (8)
例如p=17時，A=3，B=2，C=5，T=43，S=7，k=2 。
4 /17=[1/(2×3)]+[1/(3×5)]+[1/(3×2×5×17 )]
即4/17=1/6+1 /15+1/510.
等價於下面的式子:
（-17）×5+43×2=1
7×5+（-17）×2=1
注意：P=(4ABC-1)/(B+C). (9)
由於4ABC-1是4R+3型，所以，當P=4R+1型時，B+C=4K-1型；P=4R+3,B+C=4K+1型。.
因為對於二元一次不定方程組，我們有得是辦法。根據《代數學辭典》上海教育出版社1985年（376頁）：「
方程組:ax+by=c
a'x+b'y=c'
公共解（整數解）x,y的充分必要條件是(ab'-a'b)不等於0，並且 (ab'-a'b) | (bc'-b'c) 和 (ab'-a'b) | (ca'-c'a)。」
我們把（7）（8）式的C與B當成上面的x,y. 在（7）式中，只要（P,T）=1；就有無窮多組B和C整數解;在（7）中，只要（P,S）=1，就有B和C的整數解。根據已知的定理（柯召，孫奇《談談不定方程》）13 至17頁，聯立二元一次不定方程，就知道（7）（8）式必然有公共整數解（用到矩陣，單位模變換等知識）。即ST-P×P≠0，(ST-P×P) | (P+T)； (ST-P×P) | (P+S)。為什麼說是必然有解，只要有一個素數有解，其它素數必然有解。在中國象棋中，「馬」從起點可以跳到所有的點，那麼，馬在任何一個點就可以跳到任何點。因為馬可以從任何一個點退回的起點。
下面是一些p值的解：
--p---|---A---|---B---|----C-----|------T-----|------S-------|-------K-----|
------------------------------------------------------------------------------|
--5---|--2----|---1----|---2------|-----11-----|----3---------|------1------|
-29--|---2----|---4----|---39----|----283----|----3---------|------11-----|
-37--|---2----|---5----|--62-----|---459-----|----3---------|-------17----|
-53--|---2----|---7----|--124----|---939-----|----3--------|-------33----|
-61--|---2----|---8----|--163----|---1243----|----3--------|-------43----|
-173-|--2----|----22--|--1269---|--9979----|----3--------|------323----|
-----------------------------------------------------------------------------------------
以上是P=4R+1，R為奇數時的解，此時，A=2；S=3。
---------------------------------------------------------------------------------
-17--|--3-----|---2----|-----5------|----43-----|-----7--------|-----2-------|
-41--|--12----|---1----|----6-------|---247----|----7---------|-----2-------|
-41--|--6------|---3----|----4-------|---55-----|-----31-------|-----2-------|
-73--|---10----|---2----|---21------|----767--|-----7---------|-----6-------|
- 97--|---17---|---2----|----5-------|---243---|----39--------|-----2-------|
-113-|--5------|---6----|---97------|--1827---|----7---------|----26-------|
-409-|--59-----|---2---|----13------|--2659---|----63-------|----4--------|
-409-|--22-----|---5---|-----66-----|--5399---|----31-------|-----18-----|
-409-|--11-----|---11--|----60-----|---2231--|----75-------|-----18-----|
---------------------------------------------------------------------------------------
以上是p=4R+1，R是偶數時的解。
41有兩組解；409有三組解。就是說4/41=1/（12×1）+1/（12×6）+1/（12×1×6×41）=1/12+1/72+1/2952
4/41=1/（6×3）+1/（6×4）+1/（6×3×4×41）=1/18+1/24+1/2952。
-41×6+247×1=1
7×6+（-41）×1=1
和第二組解；
-41×4+55×3=1
31×4+（-41×3）=1
（2）式是對於所有的p值都有解，但不是全部解。(例如，4/41有7組解，而（2）式只求證4/p=1/AB+1/AC+1/ABCP
的形式解。請注意普遍解與全部解的區別。
在七十年代，人們又提出了5/P的情況，所有的素數P都可以表示成5R+1；5R+2；5R+3；5R+4形。
對於P= 5R+4形，5/（5R+4）=1/（R+1）+1/[（5R+4）（R+1）]
其中任何一個：1/N=1/（N+1）+1/[N（N+1）]。
例如，5/9=1/2+1/18，而1/2=1/3+1/6；或者1/18=1/19+1/（18×19）。
對於P=5R+3形，5/（5R+3）=1/（R+1）+2/[（5R+3）（R+1）]
其中任何一個：2/N=1/[（N+1）/2]+1/[N（N+1）/2]
例如，5/13=1/3+2/39，而2/39=1/[（39+1）/2]+1/[39×（39+1）/2]。
對於P=5R+2形，5/（5R+2）=1/（R+1）+3/[（5R+2）（R+1）]
R必然是奇數，（R+1）必然是偶數。
而：3/[（5R+2）（R+1）]=1/[（5R+2）（R+1）]+1/[（5R+2）（R+1）/2]
例如，5/37=1/8+3/（37×8）；而3/（37×8）=1/（37×8）+1/（37×4）。
對於P=5R+1形，
設5/P=1/AB+1/AC+1/ABCP （8）。
5ABC=PC+PB+1 （9）
A=（PC+PB+1）/5BC （10）。
同樣可以整理成（6）（7）式，同樣有解。B+C=5K-1形。
下面是一些p=5R+1形的素數的解。
5/11=1/3+1/9+1/99，A=3，B=1，C=3，T=34，S=4；
5/31=1/7+1/56+1/1736，A=7，B=1，C=8，T=248，S=4；
5/41=1/9+1/93+1/11439，A=3，B=3，C=31，T=424，S=4；
5/61=1/14+1/95+1/81130，A=1，B=14，C=95，T=414，S=9；
5/71=1/15+1/267+1/94785，A=3，B=5，C=89，T=1264，S=4；
5/101=1/21+1/531+1/375417，A=3，B=7，C=177，T=2554，S=4；
5/131=1/27+1/885+1/1043415，A=3，B=9，C=295，T=4294，S=4；
方法同4/P一樣。請讀者自己完成。
為什麼（6）（7）式可以必然有解？
兩聯二元一次不定方程：
a1x+b1y=1
a2x+b2y=1.
有解的充分條件是(a1b2-a2b1)|(a1-a2);(a1b2-a2b1)|(b2-b1).
我們考察一聯二元一次不定方程：
ax+by=1.(14)
根據已知定理，只要（a,b)=1,(14)式就有整數x,y的解。並且是有無窮多組解。
例如，5x-2y=1.
x; y
-----------------
1, 2;
3, 7;
5, 12;
7, 17;
9, 22;
11，27；
13，32；
15，37；
17, 42;
19, 47;
...........
換句話說，（14）式中，x與y也互素。這就是聯立方程組有公共解的基礎。我們把a,b與x,y互換，
以上例為例子，5x-2y=1換成5a-2b=1,x=5,y=2.
3x-7y=1
17x-42y=1
形成二聯二元一次不定方程。
5x-12y=1
19x-47y=1
7x-17y=1
形成三聯二元一次不定方程。
（4）式可以表示成一個素數的式子：
p=(4ABC-1)/(C+B)。例如p=41時，41=（4x6x3x4-1）/（4+3）；41=（5x3x3x31-1）/（31+3）；
41=(6x1x8x47-1)/(8+47)；41=(7x1x7x36-1)/(7+36)；41=(8x6x1x6-1)/(1+6)；41=(9x1x6x19-1)/(6+19)；
41=(10x1x6x13-1)/(6+13)；41=(11x1x4x55-1)/(4+55);；41=(12x4x1x6-1)/(1+6);；41=(13x1x4x15-1)/(4+15)；
41=(14x1x3x124-1)/(3+124).。到n=15就沒有了：41= (nABC-1)/(B+C)都有效。
人們於是問：是否一切n<p/3,對於任何一個素數p都有 ：
p=(nABC-1)/(B+C).
有三個未知變數的素數公式，可以求得一切素數：
P=(4ABC-1)/(B+C).(15)。
（15）式對於一切p=4r+1形式的素數都可以。
例如，17.：17=（4x3x2x5-1)/(2+5)。
（15）式對於一切p=4r+3形式的素數，A=(P+1)/4，,B=1,，C=P+1。例如11=（4x3x1x12-1)/(1+12).。
對於合數n=4r+3形式。n=（4xBXC－1）/（B+C）．
例如51=（4x13x664－1）/（13+664）。B=（P+1）/4，C=n（n+1）/4+1．
演算法解決
題目
埃及分數
在古埃及，人們使用單位分數的和（形如 1/a 的，a 是自然數）表示一切有理數。 如：
2/3=1/2+1/6，但不允許 2/3=1/3+1/3，因為加數中有相同的。 對於一個分數 a/b，表示方
法有很多種，但是哪種最好呢？
首先，加數少的比加數多的好，其次，加數個數相同的，最小的分數越大越好。 如：
最好的是最後一種，因為 1/18 比 1/180、1/45、1/30、1/180 都大。
【輸入文件】
給出兩個正整數 a、b（0 < a < b < 1000），編程計算對於分數 a/b 最好的表達方式。
【輸出文件】
若干個數，自小到大排列，依次是單位分數的分母。
【樣例輸入】
19 45
【樣例輸出】
5 6 18
pascal 代碼（迭代加深，有更好的演算法）
var
temp,ans:array[1..20]of longint;
flag:boolean;
aim:extended;
a,b,te,maxd:longint;
function gcd(a,b:longint):int64;
begin
if b=0 then exit(a);
exit(gcd(b,a mod b));
end;
function lcm(a,b:longint):int64;
var
t:longint;
begin
if a<b then
begin
t:=a;a:=b;b:=t;
end;
exit(a div gcd(a,b)*b);
end;
procere sum(var s1,s2:int64;m:longint);
var
t:int64;
begin
t:=lcm(s2,m);
if t>100000 then
begin
s1:=10000;
s2:=1;
exit;
end;
s1:=t div s2*s1+t div m;
s2:=t;
t:=gcd(s1,s2);
s1:=s1 div t;
s2:=s2 div t;
end;
procere fc(s1,s2:longint);
var
i:longint;
begin
if (s1=a)and(s2=b) then
begin
flag:=true;
if ans[maxd]>temp[maxd] then
ans:=temp;
end;
end;
procere dfs(s:extended;s1,s2,m,i:int64);
var
j:longint;
up,down,t1,t2:int64;
begin
if s1/s2>aim then exit;
if i>maxd then begin fc(s1,s2); exit;end;
up:=trunc(1/(aim-s));
if up<m then up:=m;
down:=trunc((maxd-i+1)/(aim-s))+100;
for j:=up to down do
begin
temp[i]:=j;
t1:=s1;t2:=s2;
sum(t1,t2,j);
dfs(s+1/j,t1,t2,j+1,i+1);
end;
end;
procere print;
var
i:longint;
begin
for i:=1 to maxd-1 do
write(ans[i],' ');
writeln(ans[maxd]);
end;
begin
fillchar(ans,sizeof(ans),$3f);
read(a,b);
te:=gcd(a,b);
a:=a div te;
b:=b div te;
aim:=a/b;
maxd:=1;
flag:=false;
while not flag do
begin
inc(maxd);
dfs(0,0,1,2,1);
end;
print;
end.
還有更基礎的解法，初學者可用：
var a,b,c:integer;
begin
write('a,b=');readln(a,b);
write(a,'/',b,'=');
repeat
c:=b div a +1;
a:=a*c-b;
b:=b*c;
write('1/',c);
write('+');
until (a=1) or (b mod a=0);
if (b mod a=0)and(a<>1)
then write('1/',b div a);
if a=1 then write('1/',b);
readln;
end.
未來發展
實際上這個問題還遠遠沒有解決。但是已經給出了前進的方向。
.埃及分數，一個曾被人瞧不起的，古老的課題，它隱含了何等豐富的內容，許多新奇的謎等待人們去揭開
㈡ 用C++實現尋找迷宮里最短路線
你找 QQ為85141512 的QQ空間里有 ，那個是我的
我是公司的網，上不了QQ抱歉。
有什麼疑問發到網路我的消息里
都是數據結構的問題
我找到了，貼過來:
#include<iostream.h>
#include <stdlib.h>
#include<iomanip.h>
#define STACK_INIT_SIZE 100 //初始棧大小
#define STACKINCREAMENT 10 //添加棧的長度
#define SIZE_OF_MAPH 20 //迷宮高度
#define SIZE_OF_MAPW 20 //迷宮長度
////////////////////////////////////////////////////////////////////////////////
// 結構體名稱：MazeCell
// 功能：用來描述迷宮組成單元的信息
// 成員：Pass: 當Pass為1時，表示導通塊；為0則表示障礙塊；
// Footprint: 當 Footprint為1時，表示留下足跡，反之，表示未經此地。
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int Pass;
bool Footprint;
}MazeCell;
////////////////////////////////////////////////////////////////////////////////
// 結構體名稱：SElemType
// 功能： 此為棧的元素，用來表示當前位置，（棧用來描述當前路徑）
// 成員： ord: 通道塊的序號
// x : 當前位置的橫坐標
// y : 當前位置的縱坐標
// di : 搜索方向 1向東，2向南，3向西，4向北
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int ord;
int x;
int y;
int di;
}SElemType;
////////////////////////////////////////////////////////////////////////////////
// 結構體名稱： SqTack
// 功能： 此為棧，用來記錄當前路徑
// 成員： *base 棧底指針，指向起點
// *top 棧頂指針，指向路徑的末點
// stacksize 棧的容量
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
////////////////////////////////////////////////////////////////////////////////
// 結構體名稱： Seat
// 功能： 用來記錄迷宮坐標，此結構體為中間變數，純粹為方便編程而建立
// 成員： x: 用來記錄橫坐標
// y: 用來記錄縱坐標
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int x;
int y;
}Seat;
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： InitStack
// 功能： 此函數用於初始化一個棧，即在類存中找一塊大小為STACK_INIT_SIZE個棧
// 元素的空間,將其首址賦給棧底指針，此時棧頂指針與棧底指針重合。棧的容
// 量為 STACK_INIT_SIZE。操作成功則函數返回1，若類存空間不足，函數返回
// 0，表示初始化失敗。
// 函數參數： SqStack &S
// 函數返回值類型： bool
////////////////////////////////////////////////////////////////////////////////
bool InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 0;
}
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： BuideMaze
// 功能： 此函數的功能是用於根據用戶要求建立一個迷宮地圖，將用戶輸入的整形數組
// 形狀給迷宮數組
//
// 函數參數： MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP]
// Seat &start 起點坐標
// Seat &end 終點坐標
// 函數返回值類型： bool 建立成功則返回1，反之返回0。
////////////////////////////////////////////////////////////////////////////////
void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],int ma[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
for(int i=0;i<SIZE_OF_MAPH;i++)
{
for(int j=0;j<SIZE_OF_MAPW;j++)
{
Map[i][j].Pass=ma[i][j];
Map[i][j].Footprint=0;
}
}
}
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： Pass
// 功能： 此函數用於判斷當前點是否可通，如果可通則返回1，反之返回0。
// 所謂可通是指當前位置為導通塊並且當前位置沒有留下腳印。
// 函數參數： Seat curpos 當前塊的坐標
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宮地圖
// 函數返回值類型： bool 若當前塊可通則返回1，反之則返回0。
////////////////////////////////////////////////////////////////////////////////
bool Pass(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
if(Map[curpos.x][curpos.y].Pass==0)
{
return 0;
}
else if(Map[curpos.x][curpos.y].Footprint==1)
{
return 0;
}
else
{
return 1;
}
}
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： FootPrint
// 功能： 此函數用於在當前路徑下留下腳印。
// 函數參數： Seat curpos 當前坐標
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宮地圖
// 函數返回值類型： 無
////////////////////////////////////////////////////////////////////////////////
void FootPrint(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
Map[curpos.x][curpos.y].Footprint=1;
}
bool Push(SqStack &S,SElemType e)//棧插入函數
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREAMENT;
}
*S.top++=e;
return 1;
}
bool Pop(SqStack &S,SElemType &e)//棧取出最上面的元素，將值給e
{
if(S.base==S.top)return false;
S.top--;
e=*S.top;
return true;
}
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： NextPos
// 功能： 此函數用於將坐標為x,y位置的di方向位置切換為當前位置。
// 函數參數： Seat curpos 當前坐標
// int di 方向
// int x,y 坐標
// 函數返回值類型： 無
////////////////////////////////////////////////////////////////////////////////
void NextPos(int x,int y,Seat &curpos,int di)
{
if(di==1)
{
curpos.y=y+1;
curpos.x=x;
}
else if(di==2)
{
curpos.x=x+1;
curpos.y=y;
}
else if(di==3)
{
curpos.y=y-1;
curpos.x=x;
}
else if(di==4)
{
curpos.x=x-1;
curpos.y=y;
}
}
///////////////////////////////////////////////////////////////////////////
// 函數名稱： PutIn
// 功能： 向數組里輸入元素
// 函數參數： int map[] 將得到的數組給map
// int Wei 迷宮的長度
// int Hig 迷宮的高度
// 函數返回值類型： 無
///////////////////////////////////////////////////////////////////////////
void PutIn(int map[],int &Wei,int &Hig)
{
int w,h;
cout<<"如果您想輸入的迷宮大於所規定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAP"<<endl;
cout<<"請輸入迷宮的長度(長度小於等於"<<SIZE_OF_MAPW-2<<")：";
cin>>w;
cout<<"請輸入迷宮的高度(高度小於等於"<<SIZE_OF_MAPW-2<<")：";
cin>>h;
cout<<"1表示導通塊；0表示障礙塊"<<endl;
Wei=w;
Hig=h;
for(int i=0;i<SIZE_OF_MAPH;i++)
for(int j=0;j<SIZE_OF_MAPW;j++)
*(map+i*SIZE_OF_MAPW+j)=0;
for(int is=1;is<h+1;is++)
{
cout<<"請輸入第"<<is<<"行:";
for(int js=1;js<w+1;js++)
{
int point;
cin>>point;
*(map+is*SIZE_OF_MAPW+js)=point;
}
cout<<endl;
}
}
///////////////////////////////////////////////////////////////////////////
// 函數名稱： Display
// 功能： 用於顯示棧中所有元素
// 函數參數： 無
// 函數返回值類型： 無
///////////////////////////////////////////////////////////////////////////
void Display(SqStack S)
{
int i=1;
SElemType *p;
p=S.base;
cout<<"從base到top:"<<endl;
cout<<"di搜索方向:di=1向東，di=2向南，di=3向西，di=4向北"<<endl;
while(p!=S.top) //從base到top列印元素
{
cout<<"第"<<i<<"步: ";
cout<<"("<<(*p).y;
cout<<","<<(*p).x;
cout<<","<<(*p).di<<")"<<endl;
p++;
i++;
}
}
void DisplayMaze(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h)
{
cout<<"迷宮為(1代表可以通過；0代表不可以通過): "<<endl;
for(int i=0;i<h+2;i++)
{
for(int j=0;j<w+2;j++)
{
cout<<ma[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
///////////////////////////////////////////////////////////////////////////
// 函數名稱： MazePath
// 功能： 組織所有子函數，求解迷宮
// 函數參數： 無
// 函數返回值類型： int 迷宮有解則返回1，反之則返回0；
////////////////////////////////////////////////////////////////////////////
int MazePath(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],Seat start,Seat end)
{
SElemType e;
SqStack S; //定義一個棧
InitStack(S); //初始化棧
Seat curpos; //定義當前位置
int curstep; //計步器
curstep=1; //計步器計1
curpos.x=start.x; //
curpos.y=start.y; //當前位置設為起點
cout<<"起點是:"<<start.y<<" "<<start.x<<endl;
cout<<"終點是:"<<end.y<<" "<<end.x<<endl;
///////////////////////////////////////////////////////////////////////////
//
// 下面的循環是求解迷宮的核心程序
////////////////////////////////////////////////////////////////////////////
do
{
if(Pass(curpos,Map)) //如果當前塊可通，則進行如下操作
{
FootPrint(curpos,Map); //留下腳印
e.ord=curstep; //記下計步器
e.x=curpos.x; //記下行數
e.y=curpos.y; //記下列數
e.di=1; //設一個方向為東方
Push(S,e); //壓棧操作，將當前位置納入當前路徑
if(curpos.x==end.x&&curpos.y==end.y) //如果當前塊為終點，進行如下操作
{ //
cout<<"ok!"; //
Display(S); //調用顯示棧的子程序顯示結果
return 1; //函數返回1
} //
else //如果當前位置不是終點，進行如下操作
{ //
NextPos(curpos.x,curpos.y,curpos,1); //切換東方向的位置為當前位置
curstep++; //計步器自增1
}
}//if
else
{
if(S.base!=S.top) //如果當前塊不通，且棧不為空（說明還有解）
{
Pop(S,e); //將棧頂元素彈出進行觀察
while(e.di==4&&(S.top-S.base)) //如果棧頂元素四方均不通
{
Pop(S,e); //彈出下一個棧頂元素進行觀察
}//while
if(e.di<4) //如果棧頂元素還有其他方向沒有走過
{ //
e.di++; //切換下一個方向為當前方向
Push(S,e); //壓入棧
NextPos(e.x,e.y,curpos,e.di); //切換下一個方向位置為當前位置
}//if
}//if
}//else
}while(S.base!=S.top); //只要棧不空則說明有解，重復循環
cout<<"沒找到路徑"<<endl;
}
////////////////////////////////////////////////////////////////////////////////
// 函數名稱： main
// 功能： 組織所有子函數，求解迷宮
// 函數參數： 無
// 函數返回值類型： bool 迷宮有解則返回1，反之則返回0；
//
////////////////////////////////////////////////////////////////////////////////
void main()
{
MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]; //定義一個迷宮數組
/*int migong[SIZE_OF_MAPH][SIZE_OF_MAPW]= {
{ 0,0,0,0,0,0,0,0,0,0},
{ 0,1,1,0,0,0,0,0,0,0}, //1
{ 0,0,1,1,1,0,1,1,1,0}, //2
{ 0,0,1,0,1,1,1,0,1,0}, //3
{ 0,0,1,0,0,0,0,0,1,0}, //4
{ 0,0,1,0,1,1,1,0,0,0}, //5
{ 0,0,1,1,1,0,1,1,1,0}, //6
{ 0,0,0,0,0,0,0,0,0,0},
}; //以數組表示的迷宮*/
int w,h;
int migong[SIZE_OF_MAPH][SIZE_OF_MAPW];
PutIn(migong[0],w,h);
BuideMaze(Map,migong); //調用建立迷宮的子函數
DisplayMaze(migong,w,h); //顯示迷宮的形狀
Seat start,end; //定義當前位置，起點位置，終點位置的結構體
/*start.x=1; //起點
start.y=1; //
end.x=2; //終點
end.y=2; //*/
cout<<"起點橫坐標:";
cin>>start.y;
cout<<"起點縱坐標:";
cin>>start.x;
cout<<"終點橫坐標:";
cin>>end.y;
cout<<"終點縱坐標:";
cin>>end.x;
MazePath(Map,start,end);
}
程序大部分分成函數了，你只要把函數的功能弄清楚了，就差不多了
祝你成功！我當時弄了3天才寫出來的
㈢ 四子棋的AI演算法求助，懸賞500一分不少
我寫過五子棋程序，也思考過棋類程序的演算法，希望能給樓主參考
雙方對弈棋類演算法，其基本思想就是人工智慧中關於 最小-最大問題 的 alpha-beta 剪枝，樓主可搜索一下，這個隨便一本人工智慧書里都有講。
下面就是具體程序中該如何實現其思想
一般都要先有一個招法生成器，用於給出當前局面下所有可走的行棋可能。對四子棋來說就相當簡單了，只要看一下每一列，只要未滿即可。
然後要有一個局面評估函數，大體評價下雙方局勢的分數。此函數盡量簡單能反映優劣即可，因為後面的 alpha-beta 演算法要大量調用此函數
最後實現 alpha-beta 的演算法，採用迭代加深的廣度優先搜索能有效剪枝。(剪枝效率取決於前面的局面評估函數，如果評估函數能非常准確的估值，那麼將會大大減小搜索范圍，但復雜的評估函數又會增加開銷，這是一個兩難的抉擇)
不過對於四子棋由於非常簡單，樓主也可以嘗試僅用簡單的廣度優先搜索。按每個局面 7 列只有 7 種走法來算，5步深的全搜索也只有 1 萬多種情況。對一般人來說5步深也足夠強了。不滿意的話再考慮上面的正統演算法。
然後是一點小技巧，關於棋盤的存儲和運算，盡量採用位棋盤和位運算來完成，多利用位運算的並行性來提高效率
這里畢竟字數有限，如果還想更深入了解的話推薦來這里看看：http://www.elephantbase.net/computer.htm
一個相當好的棋類演算法網站
雖然是講象棋的，但基本思路都一樣，絕對能學到很多東西。
㈣ noip pascal借書問題 用深搜時間太長啊……
廣搜得到的往往是最優值，因為它是按照節點深度遞增的次序訪問的。但由於需要記錄當前深度的所有節點，因而需要的空間開銷大。
深搜只需要記錄當前路徑上的節點，因而開銷較小，但沒有廣搜「遞增」的次序，無法高效地求出最優解，因此一般用作求所有解。
只需要遍歷所有點或所有情況的時候，兩者都可以。
有種折中的方法 叫做迭代加深。 它限制每次搜索的深度，如果無解再增加允許搜索的深度，逐步逼近最優解，不會佔用廣搜那樣太大空間，也不至於像深搜那樣一路走到死胡同。
加：
如果選用廣搜，則節點數最多有20!≈2*10^18個節點，則很難存儲狀態，而且本題只要求求出任意解，並非最優解，因此選用深搜
㈤ 機算機專業英語(英譯漢) (人工智慧搜索方法P1)
在本章我們在開始以盲目的詳盡的方法的AI將探索查尋方法然後轉向啟發式和優選的方法，本章的第二個一半將集中於並行法。 報道的方法將包括(為非優選，未接到通知的方法)狀態空間查尋，引起和測試，意味結束分析，問題減少，並且，深度首先搜尋，並且廣度首先搜尋。 在啟發式的保護下(消息靈通的方法)是，最好第一次查尋、雙向搜索、分支和一定的演算法和帶寬查尋。
搜索演算法為比賽被證明是研究的一個富有的來源和經驗數據關於啟發性方法。 報道的方法包括minimax做法，阿爾法beta演算法，重申加深， SSS*演算法
報道的優選的方法包括A*演算法和重申加深的A* (IDA*)提出與相對地最近並行演算法的分類包括PIA*演算法，
平行的重申加深的演算法(PIDA*)，平行的窗口查尋(PWS)，主要變異分裂的演算法(PVS)和等待概念。
㈥ 貪心演算法
埃及分數的演算法叫做「迭代加深搜索」
那個問題用貪心我認為是不能的。
貪心一般是一種顯而易見的演算法應用在問題當中而得到最優解或較優解。（我的理解）
是否可以解決您的問題？
㈦ 埃及分數的演算法解決
題目
埃及分數
在古埃及，人們使用單位分數的和（形如 1/a 的，a 是自然數）表示一切有理數。 如：
2/3=1/2+1/6，但不允許 2/3=1/3+1/3，因為加數中有相同的。 對於一個分數 a/b，表示方
法有很多種，但是哪種最好呢？
首先，加數少的比加數多的好，其次，加數個數相同的，最小的分數越大越好。 如：
最好的是最後一種，因為 1/18 比 1/180、1/45、1/30、1/180 都大。
【輸入文件】
給出兩個正整數 a、b（0 < a < b < 1000），編程計算對於分數 a/b 最好的表達方式。
【輸出文件】
若干個數，自小到大排列，依次是單位分數的分母。
【樣例輸入】
19 45
【樣例輸出】
5 6 18
pascal 代碼（迭代加深，有更好的演算法）
var
temp,ans:array[1..20]of longint;
flag:boolean;
aim:extended;
a,b,te,maxd:longint;
function gcd(a,b:longint):int64;
begin
if b=0 then exit(a);
exit(gcd(b,a mod b));
end;
function lcm(a,b:longint):int64;
var
t:longint;
begin
if a<b then
begin
t:=a;a:=b;b:=t;
end;
exit(a div gcd(a,b)*b);
end;
procere sum(var s1,s2:int64;m:longint);
var
t:int64;
begin
t:=lcm(s2,m);
if t>100000 then
begin
s1:=10000;
s2:=1;
exit;
end;
s1:=t div s2*s1+t div m;
s2:=t;
t:=gcd(s1,s2);
s1:=s1 div t;
s2:=s2 div t;
end;
procere fc(s1,s2:longint);
var
i:longint;
begin
if (s1=a)and(s2=b) then
begin
flag:=true;
if ans[maxd]>temp[maxd] then
ans:=temp;
end;
end;
procere dfs(s:extended;s1,s2,m,i:int64);
var
j:longint;
up,down,t1,t2:int64;
begin
if s1/s2>aim then exit;
if i>maxd then begin fc(s1,s2); exit;end;
up:=trunc(1/(aim-s));
if up<m then up:=m;
down:=trunc((maxd-i+1)/(aim-s))+100;
for j:=up to down do
begin
temp[i]:=j;
t1:=s1;t2:=s2;
sum(t1,t2,j);
dfs(s+1/j,t1,t2,j+1,i+1);
end;
end;
procere print;
var
i:longint;
begin
for i:=1 to maxd-1 do
write(ans[i],' ');
writeln(ans[maxd]);
end;
begin
fillchar(ans,sizeof(ans),$3f);
read(a,b);
te:=gcd(a,b);
a:=a div te;
b:=b div te;
aim:=a/b;
maxd:=1;
flag:=false;
while not flag do
begin
inc(maxd);
dfs(0,0,1,2,1);
end;
print;
end.
還有更基礎的解法，初學者可用：
var a,b,c:integer;
begin
write('a,b=');readln(a,b);
write(a,'/',b,'=');
repeat
c:=b div a +1;
a:=a*c-b;
b:=b*c;
write(Ƈ/',c);
write('+');
until (a=1) or (b mod a=0);
if (b mod a=0)and(a<>1)
then write(Ƈ/',b div a);
if a=1 then write(Ƈ/',b);
readln;
end.
㈧ 在地圖上查詢兩個點之間的線路，有誰做過啊
google地圖已經自帶了尋路功能了，內嵌一個web就OK了三這個跟尋路演算法沒有關系，google不會暴露資料庫給用戶的，沒有原始數據，什麼搜索都使不上的。當然了，如果夠牛的話，還真有方法：1.模式匹配，找出十字路口2.測量十字路口之間的距離，構建一張無向圖3.搜索之........（普通搜索可以處理小地圖，迭代加深深搜處理中等規模的應該問題不大，大規模的就用遺傳演算法吧），不過無論用蝦米演算法，即使是用了ndk，在ANDROID手機上面跑，依然一點都不靠譜。
㈨ Pascal語言在什麼軟體上編寫我是一點都不知道，比較菜鳥。。一直有個問題想問，JAVA和Pascal在什麼上編
我是一個搞NOIP競賽的人 也搞過一點開發，你可以聽聽我的意見（全手打的，很累啊）
我學的就是Pascal語言，面向過程，用的是Free Pascal
如果是面向對象，就用Delphi
至於Java的編譯器，可以試試NetBeans或者sun公司的jdk
像C也有面向過程和面向對象
面向過程是GCC
面向對象就是VC之類的了
Pascal的確是一個起步很好的語言，一開始就學C或C++會很累的
語言一般分3種：機器語言 匯編語言 高級語言
機器語言：能直接被CPU執行，效率極高，但是可移植性極差（換台電腦可能就不行了），寫起來也很麻煩
匯編語言：不能直接被CPU執行，加入了一些人性化的東西，如加法用ADD、減法用SUB，但還是很麻煩
高級語言：效率最低，但是很人性化，可移植性很強 像Pascal C C++ JAVA都是高級語言
高級語言不能直接被計算機執行，所以就需要編譯器來幫忙，把這些語句翻譯一下，讓CPU能執行
高級語言執行方式分兩種：解釋執行和編譯執行
解釋執行：編譯器運行一句翻譯一句，調試的時候就是這樣的
編譯執行：編譯器將源文件編譯成.exe的可執行文件，然後執行
像Free Pascal、Delphi、VB、VC這種，都是IDE
不僅可以編輯源代碼，編譯源代碼，還可以調試程序等等
要學好編程，個人覺得分三塊（把我下面講的東西全學透，要1-2年）
①語法：學好語法是基礎！學好了語法，才知道語言如何使用，這個不用我說吧
②數據結構（數據結構是脫離語言的，也就是說這些數據結構每個語言都好實現）：這是一個很抽象的東西，有 線性表、棧、隊列、堆、數、圖、串、集合 等等。
分為4種：線性結構（一對一，如 棧、隊列）、樹形結構（一對多，如 樹）、離型結構（沒有連接）、網狀結構（多對多，如 圖）
像棧就是一種FILO表，只運行在一頭進行輸入輸出操作，應用在 表達式求值、撤銷恢復操作上面
隊列是FIFO表，允許在一頭進行插入操作，另一頭錯刪除操作
樹 就復雜了 樹和二叉樹是兩種概念，具體的自己去看書吧
二叉樹有許多特殊形態，如滿二叉樹 完全二叉樹 哈夫曼樹 最優二叉樹（哈夫曼樹不等於最有二叉樹！這點有許多人弄錯。因為哈夫曼樹不一定是二叉的）
二叉樹的三種遍歷方式一定要會：前序遍歷（也稱先根遍歷）根左右， 中序遍歷（也稱中根遍歷）左根右， 後序遍歷（也稱後根遍歷）左右根
圖就更復雜了，分 連通與不連通 帶權與不帶權 有向與無向，所以就有了 （不）連通有（無）向（不）帶權圖這種說法 還有什麼強連通圖，弱連通圖的，自己看書吧！
③演算法（演算法是脫離語言的，也就是說這些演算法每個語言都好寫）：
1.低級演算法（立意上的，就像初等數學和高等數學）：窮搜、深度優先搜索（DFS）、廣度優先搜索（BFS，也稱寬度優先搜索），是三種不同的遍歷方式
2.高級演算法:貪心，分支，動態規劃（DP）。其他兩個不介紹了，就介紹一下動態規劃吧！
動態規劃：記憶化搜索，利用以前搜索留下的數據，加快解決多階段決策最優化問題的速度。要能動態規劃，問題必須滿足兩個條件（我背了好長時間才背出來）
①：最優化原理（也稱最優性原理）：無論過去的狀態或決策如何，對於當前的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。
②：無後效性：一旦一個狀態的決策確定，則此後過程的演變不再受此前各狀態及決策的影響，當前狀態時此前歷史的完整總結，此前歷史只能通過當前狀態去影響過程未來的演變。
學DP一般從背包開始，背包一共有8個：01背包、完全背包、多重背包、混合三種背包、二維費用背包、分組背包、有依賴的背包、泛化物品背包。
然後再學樹形動態規劃
還有排序演算法：冒泡排序，選擇排序，插入排序，快速排序，堆排序，希爾排序，基數排序，序數排序，桶排序，鴿巢排序，二叉樹排序（應用二叉排序樹），雞尾酒排序（就是雙向冒泡，在一次初賽的完善程序里出現過）
還有數論演算法（不展開介紹了）
圖論演算法：
最短路（顧名思義，就是一個點到另一個點的最短路程）：迪傑斯特拉（Dijkstra）、弗洛伊德（Floyd）、SPFA（國人設計的，很不錯）等等 還會要解決SPFA的負權迴路問題 這幾個演算法都是解決單源最短路徑問題的，就是一個點到所有點的最短路)
最小生成樹（應用在無向連通圖中，就是拿掉一些邊，在保證圖連通的情況下，使得剩下的邊權值之和最小）：普利姆（Prim）、克魯斯卡爾（Kruskal）
關鍵路徑（在生產生活中應用很廣，注意關鍵路徑之前一定要拓撲一次！）、拓撲排序（可用於是否有環路的檢測）、網路流等等
如果以上你都會了，那麼恭喜你，你已經可以算是一名初級程序員了！
可以繼續學 雙向深搜、雙向廣搜、周界搜索、迭代加深搜索、迭代加寬搜索、A*廣度優先啟發搜索、A*迭代加深搜索 等高級的演算法。
㈩ 人工智慧的搜索方式就搜索策略是否被預先確定一般可以分為
人工智慧中的搜索策略大體分為兩種：無信息搜索和有信息搜索。無信息搜索是指我們不知道接下來要搜索的狀態哪一個更加接近目標的搜索策略，因此也常被成為盲目搜索；而有信息搜索則是用啟發函數f（n）來衡量哪一個狀態更加接近目標狀態，並優先對該狀態進行搜索，因此與無信息搜索相比往往能夠更加高效得解決問題。
要衡量一個搜索策略的好壞，我們需要從四個方面對其進行判斷：完備性、時間復雜度、空間復雜度和最優性。因此以下通過這四個方面來比較常見搜索策略之間的優劣。
無信息搜索策略
寬度優先搜索（BFS）
首先擴展根節點，然後擴展根節點的所有後繼，接著再擴展它們的後繼，從而一層一層的對節點進行擴展。BFS是一個簡單的搜索策略，在搜索過程中會對所有狀態進行遍歷，因此它是完備的；假設搜索樹每個節點有b個後繼，深度為d，則時間復雜度和空間復雜度均為O(bd)；最後考慮最優性，因為我們總會在最淺那一層找到目標狀態，因此當且僅當每一步的代價都一致的時候，BFS可以得到最優解。
一致代價搜索
在BFS的基礎上，一致代價搜索不在擴展深度最淺的節點，而是通過比較路徑消耗g（n），並選擇當前代價最小的節點進行擴展，因此可以保證無論每一步代價是否一致，都能夠找到最優解。
深度優先搜索（DFS）
DFS擴展根節點的一個後繼，然後擴展它的一個後繼，直到到達搜索樹的最深層，那裡的節點沒有後繼，於是DFS回溯到上一層，擴展另外一個未被擴展的節點。在有限狀態空間中，DFS是完備的，因為它可以把所有空間遍歷一遍；而在無限空間中，DFS則有可能會進入深度無限的分支，因此是不完備的。DFS的時間復雜度為為O(bd)，而空間復雜度僅為O（d），因為我們只需要保存當前分支的狀態，因此空間復雜度遠遠好於BFS。然而DFS並不能保證找到最優解。
深度受限搜索
深度受限搜索設定一個最大深度dmax，當搜索深度大於dmax的時候立即回溯，從而避免了在無窮狀態空間中陷入深度無限的分支。
迭代加深的深度有限搜索
迭代加深的深度有限搜索也設定一個最大深度dmax，開始我們把dmax設為1，然後進行深度受限搜索，如果么有找到答案，則讓dmax加一，並再次進行深度有限搜索，以此類推直到找到目標。這樣既可以避免陷入深度無限的分支，同時還可以找到深度最淺的目標解，從而在每一步代價一致的時候找到最優解，再加上其優越的空間復雜度，因此常常作為首選的無信息搜索策略。
有信息搜索
貪婪最佳優先搜索
貪婪最佳優先搜索總是擴展距離目標最近的節點，其啟發函數f（n）=h（n）其中:
f（n）=節點n到目標節點的最小代價路徑的估計值
貪婪最佳優先搜索的最大問題是它往往不能找到最優解。
A*
為了找到最優解，A*演算法對一個節點的評估結合了h（n）和g（n）從開始節點到節點n的路徑代價，即f（n）=g（n）+h（n）
f（n）=經過節點n的最小代價解的估計代價
因為A*搜索總是搜索f（n）最小的點，因此它總能找到最優解。