本文主要是介绍008 matlab语言实现一点到对角的路径PART1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
昨天，同学在群里发了一个数据结构及算法方面的题目（如下图），由于最近在学习MATLAB，所以突发奇想，能不能借助MATLAB强大的绘图功能把所有路径画出来。经过几次失败的探索，终于算是完整的实现了最初的想法，收获也是相当之多。
这里我并没有一开始就考虑有特殊P点的情况，而是研究从一个顶点到对角顶点的所有路径（考虑P点的情况将在以后给出）。
首先，对这个问题做一些数学分析（感谢高中的东西还没完全忘记）：对于一个m*n的格子，从（1,1）到（m,n）只能向左或向下走，其实相当于（m-1）次向下加上（n-1）次向右一共有多少种排列组合。又考虑到这些向下和向右其实是暗含次序的，所以，路径一共有A(m+n-2,m+n-2)/[A(m-1,m-1)*A(n-1,n-1)](注：A(M,N)表示排列组合公式M为上标，N为下标)。这里介绍一个MATLAB中求阶乘的函数**factorial**,所以总路径数=factorial(m+n-2)/(factorial(m-1)*factorial(n-1))。
然而，如果要画出所有路径，这样显然是不行的，既然要画出所有路径，就要**枚举**出所有情况，这里，难点就在于如何有条理的枚举出来，在经历了几次失败之后，终于找到了一个不错的方法（如果谁看到本文并且有更好的想法，欢迎评论留言）：
可以看出，从(1,1)到(m,n)一共要走m+n-2步，所以可以用一个2行m+n-2列的矩阵来表示所走的的路径，矩阵的每一列只能有一行为1（表示向下或向右走了一步），另一行相对应为0（这里本质也就是说对1和0进行排列）。考虑第一行（表示向下），应该有m-1个1以及n-1个0，其十进制最大值应该是**2^(m+n-2)-2^(n-1)**，如m=6,n=4,则2^(m+n-2)-2^(n-1)=2^8-2^3=248=11111000;这样，我们从1遍历到2^(m+n-2)-2^(n-1)，将每个十进制数转化为二进制，考察其中1的个数，如果1的个数满足条件，则是一条可行的路径。而且从1到2^(m+n-2)-2^(n-1)可保证不漏（没记错的话，枚举法的精髓就是不重不漏，分类合理）。如果满足条件，则将这一组二进制数转化为矩阵，进而画出路径。以下是完整的matlab程序：
%version 1.0 no specia point that can't reach at
%show different path form (1, 1) to (m, n)
%date: 2015-12-2 && 2015-12-3
%author: Zhao Yu
clear
clc
%set parameters
m = input('input number of row:\nm = ');
n = input('input number of column\nn = ');
Matrix = zeros(m, n);
Matrix(1, 1) = 2;
Matrix(m, n) = 2;
Paths = zeros(2, m+n-2);
Max = 0;
%for k=(m-1):(m+n-3)
% Max = Max + 10^k;
%end
%Max = bin2dec(num2str(Max));
Max=2^(m+n-2)-2^(n-1);
for k=1:MaxNumBin = str2double(dec2bin(k));for j=1:length(dec2bin(k))Paths(1,m+n-j-1) = floor(mod(NumBin,10));NumBin=floor(NumBin/10);endif length(find(Paths(1,:)==1))==(n-1)Paths(2,:) =~ Paths(1,:);Matrix = zeros(m, n);Matrix(1, 1) = 2;Matrix(m, n) = 2;x=1;y=1;for j=1:length(Paths(1,:))x=x+Paths(2,j);y=y+Paths(1,j);%I'm in chaosMatrix(x,y)=1;imagesc(Matrix)pause(0.05)endend
end
效果图
算法思想已经基本讲清楚，在介绍一下，几个MATLAB实现的技巧：
1、dec2bin()将一个十进制数转换成一个二进制的**字符串**
2、str2double()将一个数字字符串转换成一个数字
3、length()计算一个字符串的长度
4、mod()取余函数
5、floor()取一个浮点数的整数部分
6、find()找出矩阵中满足条件的数的位置，这些位置组成新的一维矩阵
7、=~：取反。如a=1,b=~a,则b=0
8、imagesc(A),二维矩阵A，按不同数字不同颜色画图
9、pause(t)程序暂停t s
这些函数光看还是很难深刻掌握的，建议自己动手，多尝试多探索。才能真正成为自己的东西。
一些反思：
1、一定要先写流程图设计好算法，再写代码，自己昨晚写了一个多钟头，后来到床上一想发现全都是错的（当时是想用随机产生，无限尝试，甚至没考虑1的个数是固定的），今天一开始又没考虑如00110这样的数会被计算机直接当成110.所以，不要一头扎进代码里。
2、数学真的很重要，无论是前面排列组合的分析还是对二进制与十进制关系的那段分析，都需要数学基础。**为自己大学以来没好好学数学惭愧**，幸好为时不晚。此外，一开始并没注意到Max=2^(m+n-2)-2^(n-1);而是直接
for k=(m-1):(m+n-3)Max = Max + 10^k;
end
Max = bin2dec(num2str(Max));这样导致输入的m,n稍大一点计算机就会出错，因为那个01序列是被直接当成十进制对待的。而且这样做增加了很多运算，降低了效率。而直接用公式不仅简洁而且效率高，由此可见数学的重要性啊！直达本质。满满的简洁美。还有，深入思考！
3、有时候还是懒点好，真是因为懒，才挖出了一堆matlab内建函数，本来好几行代码，现在一个函数就搞定了。主要还是敢想，多想想为什么不能简单点呢，为什么不能用更精炼的代码呢？懒，让世界更美好！！现在看上面代码还是很懒的，不过懒得很简洁、很优美。哈哈！！！
这篇关于008 matlab语言实现一点到对角的路径PART1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
