迭代加深算法
㈠ 埃及分数
埃及分数
埃及分数是指分子是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）最小的点，因此它总能找到最优解。