1701007271
1701007272
图5-56 一颗红心永流传
1701007273
1701007274
我们都不敢相信，我们的计算机采用程序编码，能够再现心形的三维曲面图。图5-56相当逼真的实现了我们眼中的心形纪念品，我们不得不佩服我们自己，心形图形的美，让我们有了去实现它、拥有它的动力。如果你喜欢什么，尽力去尝试，你将得到你所想要的，真的不是幻想。
1701007275
1701007276
1701007277
1701007278
1701007279
我和数学有约：趣味数学及算法解析 [:1701004219]
1701007280
我和数学有约：趣味数学及算法解析 第6章 思考的乐趣
1701007281
1701007282
思考是人类进步的阶梯，学习可以让人掌握更多知识，进步更快。用思考的眼光去面对生活，可以发现很多灵光一现的东西，从而促进自身提高。不登高山，不知天高；不临深溪，不知地之厚也。一个人只有勤于思考才能开阔视野，才能拥有宽广的胸怀。因为思考，人类涉足于宇宙，探索未来；因为思考，人类越来越注重自身的提高；因为思考，才会乐趣横生。
1701007283
1701007284
1701007285
1701007286
1701007287
我和数学有约：趣味数学及算法解析 [:1701004220]
1701007288
我和数学有约：趣味数学及算法解析 6.1 八皇后问题
1701007289
1701007290
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出。
1701007291
1701007292
【问题】在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
1701007293
1701007294
【分析】
1701007295
1701007296
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
1701007297
1701007298
具体的国际象棋盘如图6-1所示。
1701007299
1701007300
1701007301
1701007302
1701007303
图6-1 国际象棋盘
1701007304
1701007305
经典的解法是回溯法，但效率较低，编程较困难。现采用随机算法，效率要提高一倍多，但算法有可能失败，成功的近似概率为0.99。
1701007306
1701007307
具体的算法流程如下。
1701007308
1701007309
Step1：置k＝1，在第一行随机选择一个位置放置一个皇后，k＋＋；
1701007310
1701007311
Step2：计算k行所有可行的位置，即在这些位置放置一个皇后不会与前面已经放置的皇后相互攻击；
1701007312
1701007313
Step3：如果找不到可行的位置，则返回失败，程序结束；否则从可行的位置中随机选择一个位置放置一个皇后，k＋＋；
1701007314
1701007315
Step4：如果k＞8，则返回成功并输出八皇后放置的结果，程序结束；否则转Step2。
1701007316
1701007317
相应程序如下：
1701007318
1701007319
function ysw1_8 %八皇后问题 clc,clear,close all %清屏和清除变量 warning off %消除警告 Q= Queens(8) %调用函数 end function Q= Queens(n) global Indexes; %全局变量 A=ones(n,n); %初始化棋盘 Indexes=zeros(1,n); %记录皇后的位置坐标 i=1; %行号 j=1; %列号 count=0; %统计解的个数 while (i>0) while j<=n if canPlace(i,j) %找不会攻击其他皇后的位置 A(i,j)=8; %8代表皇后 Indexes(i)=j; break; %跳出本循环 else j=j+1; %探查下一个位置 end end if j<=n %如果找到合适的位置，则找下一个 i=i+1; j=1; else %如果找不到合适的位置，则回溯，退回到上一行 i=i-1; if i~=0 j=Indexes(i); A(i,j)=1; %还原值 Indexes(i)=0; %去掉保留的坐标 j=j+1; %从上一个皇后的后面一个位置开始找 end end if (Indexes(n)~=0) %如果找到一个解 count=count+1; disp(A); %输出矩阵 end end disp([num2str(n),‘皇后问题解的个数为:’,num2str(count)]); %输出解的个数 end %子函数，判断能否放在位置（x,y） function p=canPlace(x,y) global Indexes; %判断是否会攻击已放置的皇后（位于同一对角线或同一行列上） for a=1:x-1 %a为行号 b=Indexes(a);%b为已放置皇后所在列号 % if (x-y==a-b || x+y==a+b || x==a || y==b)%判断是否位于同一对角线和同一行列上 if (x-y==a-b || x+y==a+b || y==b)%判断是否位于同一对角线和同一列上，^_^ p=0; return; %退出子函数 end end p=1; end
1701007320