第08章 递归与搜索(上)(精品).ppt

《第08章 递归与搜索(上)(精品).ppt》由会员分享，可在线阅读，更多相关《第08章 递归与搜索(上)(精品).ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息学院信息技术教研室程序设计方法及在线实践第8章 递归与搜索(上)2第8章 递归与搜索递归是一种重要的算法思想。递归既可以实现递推过程递推过程递推过程递推过程，也可以实现求解诸多问题的通用思路搜索搜索搜索搜索。38.1 递归的基本思想8.1.1 什么是递归在数学上，求n的阶乘，有两种表示方法：n n！=n(n-1)(n-2)21=n(n-1)(n-2)21 n n！=n(n-1)=n(n-1)！这两种表示方法实际上对应到两种不同的算法思想。第种表示方法中，求n！要反复把1、2、3、(n-2)、(n-1)、n累乘起来，是循环的思想，要用循环结构循环结构循环结构循环结构来实现，代码如下：int

2、n,F=1;scanf(%d,&n);for(i=1;i=n;i+)F=F*i;printf(%d的阶乘为%d,n,F);4第种表示方法，求n！时需要用到(n-1)！。如果有一个函数FactorialFactorial(intint n)n)能实现求n的阶乘，则该函数在求n！时要使用到表达式：n*Factorial(n-1)n*Factorial(n-1)，Factorial(n-1)表示调用Factorial()函数去求(n-1)！。具体代码例8.1。例例例例8.1 8.1 递归求阶乘递归求阶乘递归求阶乘递归求阶乘#include int Factorial(int n)if(n0)retu

3、rn-1;else if(n=0|n=1)return 1;else return n*Factorial(n-1);/递归调用Factorial函数int main()int A;scanf(%d,&A);printf(%d!=%dn,A,Factorial(A);return 0;该程序的运行示例如下：该程序的运行示例如下：44!=245int Factorial(int n)if(n0)return-1;else if(n=0|n=1)return 1;else return n*Factorial(n-1);Factorial()函数有一个特点，它在执行过程中又调用了Factorial

4、()函数，这种函数称为递归函数递归函数递归函数递归函数。具体来说，在执行一个函数过程中，又直接或间接地调用该函数本身直接或间接地调用该函数本身直接或间接地调用该函数本身直接或间接地调用该函数本身，如图8.1所示，这种函数调用称为递归调用递归调用递归调用递归调用；包含递归调用的函数称为递归函数递归函数递归函数递归函数。6假设要求3!，其完整的执行过程如图8.2所示，具体过程为：执行mainmain函数的开头部分；当执行到Factorial函数调用“Factorial(3)Factorial(3)”时，流程转而去执行Factorial(3)Factorial(3)函数，并将实参3传递给形参n；执行

5、Factorial(3)Factorial(3)函数的开头部分；当执行到递归调用Factorial(n-1)函数时，此时n-1=2，所以要转而去执行Factorial(2)Factorial(2)函数；执行Factorial(2)Factorial(2)函数的开头部分；当执行到递归调用Factorial(n-1)函数时，此时n-1=1，所以要转而去执行Factorial(1)Factorial(1)函数；7执行Factorial(1)Factorial(1)函数，此时因为n的值为1，所以返回1，而不是再递归调用下去，即，Factorial(1)函数执行完毕，返回到上一层，即返回Factoria

6、l(2)Factorial(2)函数中；执行完Factorial(2)Factorial(2)函数的剩余语句，返回到Factorial(3)Factorial(3)函数中；执行完Factorial(3)Factorial(3)函数的剩余语句，返回到mainmain函数中；继续执行mainmain函数的剩余部分直到整个程序执行完毕。88.1.2 递归例题解析例例例例8.2 8.2 猴子吃桃问题猴子吃桃问题猴子吃桃问题猴子吃桃问题。猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早

7、上想再吃时，就只剩下一个桃子了。求第1天共摘了多少个桃子。分析：分析：分析：分析：假设Ai为第i天吃完后剩下的桃子的个数，A0A0表示第一天共摘下表示第一天共摘下表示第一天共摘下表示第一天共摘下的桃子的桃子的桃子的桃子，本题要求的是A0。有以下递推式子：A0=2(A1+1)A0=2(A1+1)A1：第1天吃完后剩下的桃子数A1=2(A2+1)A1=2(A2+1)A2：第2天吃完后剩下的桃子数A8=2(A9+1)A8=2(A9+1)A9：第9天吃完后剩下的桃子数A9=1A9=1以上递推过程可分别用循环结构循环结构循环结构循环结构和递归函数递归函数递归函数递归函数实现。9用循环结构实现：用循环结构

8、实现：用循环结构实现：用循环结构实现：如果x1，x2表示前后两天吃完后剩下的桃子数，则有递推关系：x1=(x2+1)*2x1=(x2+1)*2。从第9天剩下1个桃子，反复递推9次，则可求第1天共摘下的桃子数。这里包含了反复的思想，可以用循环结构来实现，代码如下：#include int main()int day,x1,x2;day=9;x2=1;while(day0)x1=(x2+1)*2;/第1天的桃子数是第2天桃子数加1后的2倍 x2=x1;day-;printf(total=%dn,x1);return 0;该程序的输出结果：该程序的输出结果：total=153410用递归思想实现：用

9、递归思想实现：用递归思想实现：用递归思想实现：前面所述的递推关系也可以采用下面的方式描述。假设第n天吃完后剩下的桃子数为A(n)A(n)，第n+1天吃完后剩下的桃子数为A(n+1)A(n+1)，则存在的推关系：A(n)=(A(n+1)+1)*2A(n)=(A(n+1)+1)*2。这种递推关系可以用递归函数实现，代码如下：#include int A(int n)if(n=9)return 1;else return(2*(A(n+1)+1);int main()printf(total=%dn,A(0);return 0;该程序的输出结果：该程序的输出结果：total=1534思考：思考：思考

10、：思考：以上递推关系式存在什么特点，为什么可以用递归函数实现？11例例例例8.3 8.3 采用递归思想递推Fibonacci数列中的每一项，并输出前20项的值。分析：分析：分析：分析：Fibonacci数列各项的递推关系是：F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+F(n-2)，这种递推关系式很适合适合适合适合用递归函数递归函数递归函数递归函数实现。代码如下：#include int Fibonacci(int n)if(n=0|n=1)return 1;else return(Fibonacci(n-1)+Fibonacci(n-2);void main()int i;in

11、t f20=0;for(i=0;i20;i+)/调用递归函数求每项 fi=Fibonacci(i);for(i=0;i20;i+)if(i%10=0)printf(n);/每行输出10个数据printf(%6d,fi);/每个数据占6个字符的宽度printf(n);该程序的输出结果：该程序的输出结果：(空一行)1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 89 144 233 377 610 987 1597 2584 4181 676512例例例例8.4 8

12、.4 输入两个正整数，求其最大公约数分析：分析：分析：分析：数论中有一个求最大公约数的算法称为辗转相除法辗转相除法辗转相除法辗转相除法，又称欧几里德欧几里德欧几里德欧几里德(Euclid)Euclid)算法算法算法算法。其基本思想及执行过程为(设m为两正整数中较大者，n为较小者)：(1)(1)令令令令u=mu=m，v=nv=n；(2)(2)取取取取u u对对对对v v的余数的余数的余数的余数，即r=u%v，如果如果如果如果r r的值为的值为的值为的值为0 0，则此时，则此时，则此时，则此时v v的值就是的值就是的值就是的值就是mm和和和和n n的的的的最大公约数最大公约数最大公约数最大公约数，

13、否则执行第(3)步；(3)(3)u=vu=v，v=rv=r，即即即即u u的值为的值为的值为的值为v v的值，的值，的值，的值，而而而而v v的值为余数的值为余数的值为余数的值为余数r r。并转向第并转向第并转向第并转向第(2)(2)步步步步。思考：思考：思考：思考：在初等数学里是如何求两个数的最大公约数？13分析分析分析分析(continue)continue)：例如，假设输入的两个正整数为18和33，则m=33，n=18。辗辗辗辗转相除法转相除法转相除法转相除法求最大公约数的过程如下图所示。r=u%v=15u=v=18v=r=15r=u%v=3u=v=15v=r=3u=m=33v=n=18

14、因此18和33的最大公约数是v=3r=u%v=014辗转相除法可以采用非递归非递归非递归非递归的方法，即循环方法循环方法循环方法循环方法实现，如下面的代码：#include int gcd(int u,int v)/求u和v的最大公约数int r;while(r=u%v)!=0)u=v;v=r;return(v);int main()int m,n,t;printf(Please input two positive integers:);scanf(%d%d,&m,&n);if(mB(表示将 A柱 最上面的 1 个盘子移到 B柱 上)l AC(将 A 此时最上面的 1 个盘子移到 C 上)l

15、 BC(将 B 上的盘子移到 C 上)v 又如：移动 3 个盘子的情况，需要 7 步l AC l ABl CBl ACl BAl BCl AC思考：思考：思考：思考：请尝试写出当盘子数 n=5时具体的移动的步骤。18思考：思考：思考：思考：n个盘子至少需要移动多少步？比如n=64。现在我想不出移完64个盘子的步骤，但如果有另外一个人能想出怎样移完63个盘子，我只要移最后1个盘子就可以了！646362ABC12 646362ABC12 646362ABC12 646362ABC12 19第一个人移动64个盘子(AC)的过程：1.命令第 2 个人将 63 个盘子从 A 移到B 上；2.自己将剩余的

16、最底下最大的那 1 个盘子从 A 移到 C 上；3.再命令第 2 个人将 63 个盘子从 B 移到 C 上；4.完成任务！第2个人移动63个盘子(AB)的过程：1.命令第 3 个人将 62 个盘子从 A 移到C 上；2.自己将剩余的最底下最大的那 1 个盘子从 A 移到 B 上；3.再命令第 3 个人将 62 个盘子从 C 移到 B 上；4.完成任务！第第3个人移动个人移动62个盘子个盘子(AC)的过程：的过程：1.命令第命令第 4 个人将个人将 61 个盘子从个盘子从 A 移到移到B 上；上；2.自己将剩余的最底下最大的那自己将剩余的最底下最大的那 1 个盘子从个盘子从 A 移移到到 C 上

17、；上；3.再命令第再命令第 4 个人将个人将 61个盘子从个盘子从 B 移到移到 C 上；上；4.完成任务！完成任务！层层下放！递归调用！层层下放！递归调用！20 A Answer:nswer:v递归的结束条件：l 最后 1 个人（第 64 个人）只需要移动 1 个盘子。v 注意：l 第 1 个人完成任务的前提是：第 2 个人完成了任务l 第 2 个人完成任务的前提是：第 3 个人完成了任务l l 第 63 个人完成任务的前提是：第 64 个人完成了任务v 所以：l 只有当第 64 个人完成任务后，第 63 个人才能完成任务；只有第 264 个人完成任务后，第 1 个人才能完成任务！典型的递归

18、问题！思考：思考：思考：思考：递归的结束条件是什么？21321ABC32ABC13ABC213ABC21ABC231ABC213ABC213ABC213进一步分析：v 欲将 A 上 3 个盘子移到 C 上，用递归思想可以分解为以下 3 步：1)将 A 上 2 个盘子移到 B 上（借助 C）2)将 A 上 1 个盘子移到 C 上3)将 B 上 2 个盘子移到 C 上（借助 A）（其中，第 2 步可以直接实现。）l 第 1 步又可以用递归方法分解为：u 将 A 上 1 个盘子从 A 移到 C u 将 A 上 1 个盘子从 A 移到 B u 将 C 上 1 个盘子从 C 移到 Bl 第 3 步又可以

19、用递归方法分解为：u 将 B 上 1 个盘子从 B 移到 A u 将 B 上 1 个盘子从 B 移到 C u 将 A 上 1 个盘子从 A 移到 C22l 综上，便可得到移动 3 个盘子的步骤为u AC u ABu CBu ACu BAu BCu AC23结论v将 n 个盘子从 A 移到 C 可以分解为以下 3 个步骤：1)1)将将将将 A A 上上上上 n-1 n-1 个盘子借助个盘子借助个盘子借助个盘子借助 C C 先移到先移到先移到先移到 B B 上上上上；2)2)把把把把 A A 上剩下的上剩下的上剩下的上剩下的 1 1 个盘移到个盘移到个盘移到个盘移到 C C 上上上上；3)3)将将

20、将将 n-1 n-1 个盘从个盘从个盘从个盘从 B B 借助借助借助借助 A A 移到移到移到移到 C C 上上上上。v上面第 1 步和第 3 步，都是把 n-1 个盘子从 1 个座移到另 1 个座上，采用的办法是相同的，只是座的名字不同而已。为使之一般化，可以将第 1 步和第 3 步表示为：l将 one 座上 n-1 个盘子移到 two 座（借助 three 座）。l只是在第 1 步和第 3 步中，one、two、three 和 A、B、C 的对应关系不同。l对第 1 步，对应关系是：oneA，twoB，threeC。l对第 3 步，对应关系是：oneB，twoC，threeA。24v 因此

21、，将上面 3 个步骤分为 2 类操作：l 将 n-1 个盘子从 1 个座移到另 1 个座上（当 n1 时）；l 将最后 1 个盘子从 1 个座上移到另 1 个座上。设计程序v 分别用 2 个函数实现以上 2 类操作：l 设计 hanoi 函数实现第 1 类操作；u 函数 hanoi(n,one,two,three)将实现把 n 个盘子从 one 座借助 two 座移到 three 座的过程；l 设计 move 函数实现第 2 类操作；u 函数 move(x,y)将实现把 1 个盘子从 x 座移到 y 座的过程。x 和 y 是代表 A、B、C 座之一，根据每次不同情况分别以 A、B、C 代入。#

22、include using namespace std;int main()void hanoi(int n,char one,char two,char three);int m;printf(input the number of diskes:);scanf(%d,&m);printf(The steps of moving%d disks:n,m);hanoihanoi(m,A,B,C);(m,A,B,C);return 0;void move(char x,char y)printf(%c-%cn,x,y);/将将n个盘从个盘从one座借助座借助two座，移到座，移到three座座v

23、oid hanoi(int n,char one,char two,char three)void move(char x,char y);/声明声明 if(n=1)move(one,three);move(one,three);else hanoi(n-1,one,three,two);move(one,three);move(one,three);hanoi(n-1,two,one,three);函数调用 move(x,y)表示将 1 个盘子从 x 座移到 y 座的过程。x 和 y 是代表 A、B、C 座之一，根据每次不同情况分别以 A、B、C 代入。函数调用 hanoi(n-1,two,

24、one,three)表示将 n-1 个盘子从 two 座借助 one 座移到 three 座的过程；26Hanoi(3,A,B,C)的执行过程问题：问题：问题：问题：分析m=3时7个步骤是怎么输出来的，依次输出哪个步骤？/n=3void hanoi(n,A,B,C)if(n=1)elsehanoi(2,A,C,B);move(A,C);hanoi(2,B,A,C);/m=3int main()hanoi(m,A,B,C);/n=2void hanoi(n,A,C,B)if(n=1)elsehanoi(1,A,B,C);move(A,B);hanoi(1,C,A,B);/n=1void hano

25、i(n,A,B,C)if(n=1)move(A,C);else/n=2void hanoi(n,B,A,C)if(n=1)elsehanoi(1,B,C,A);move(B,C);hanoi(1,A,B,C);/n=1void hanoi(n,C,A,B)if(n=1)move(C,B);else/n=1void hanoi(n,B,C,A)if(n=1)move(B,A);else/n=1void hanoi(n,A,B,C)if(n=1)move(A,C);else27运行情况如下：运行情况如下：input the number of disks:4The steps of moving

26、4 disks:ABACBCABCACBABACBCBACABCABACBC288.1.3 递归存在的问题递归思想虽然很好理解，特别是对于一些可以用递推式子表示的问题。然而，使用递归的代价使用递归的代价使用递归的代价使用递归的代价是十分巨大的：它会消耗大量的内存！函数调用时需要用到堆栈，而堆栈的资源是十分有限的。在例8.3中，使用递归思想求Fibonacci数列的第n项。单独求FibonacciFibonacci(20)(20)，递归调用Fibonacci()函数就达到2189121891次！这一点可以用下面的代码验证。#include int count=0;/Fibonacci函数递归调用

27、次数int Fibonacci(int n)count+;if(n=0|n=1)return 1;else return(Fibonacci(n-1)+Fibonacci(n-2);void main()Fibonacci(20);printf(count=%dn,count);298.2 递归思想在竞赛试题中的应用 例例例例8.6 8.6 另一个另一个另一个另一个FibonacciFibonacci数列数列数列数列(FibonacciFibonacci Again)Again)例例例例8.7 8.7 分形分形分形分形(Fractal)Fractal)30例例例例8.6 8.6 另一个另一个另

28、一个另一个FibonacciFibonacci数列数列数列数列(FibonacciFibonacci Again)Again)题目来源：ZOJ Monthly,December 2003题号：ZOJ2060题目描述：题目描述：题目描述：题目描述：定义另外一个Fibonacci数列：F(0)=7，F(1)=11，F(n)=F(n-1)+F(n-2)，(n=2)。输入描述：输入描述：输入描述：输入描述：输入文件包含多行，每行为一个整数n，n 1,000,000。第三种输入方式!输出描述：输出描述：输出描述：输出描述：对输入文件中的每个整数n，如果F(n)能被3整除，输出yes，否则输出no。样例输

29、出：样例输出：样例输出：样例输出：nonoyesno样例输入：样例输入：样例输入：样例输入：012331分析：分析：分析：分析：本章例8.3讲解了用递归思想求Fibonacci数列各项，但在本题中如果如果如果如果直接求出第直接求出第直接求出第直接求出第n n项，再判断是否能被项，再判断是否能被项，再判断是否能被项，再判断是否能被3 3整数，则会超时！整数，则会超时！整数，则会超时！整数，则会超时！因为n的值最大可以取到1,000,000。我们先用下面的程序输出前30项对3取余的结果：#include int f(int n)if(n=0)return 1;else if(n=1)return

30、2;else return(f(n-1)+f(n-2)%3;int main()for(int i=0;i30;i+)printf(%d,f(i);前30项对3取余得到的余数分别为：1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1。分析这些余数我们发现该该该该FibonacciFibonacci数列各项数列各项数列各项数列各项对对对对3 3取余得到的余数每取余得到的余数每取余得到的余数每取余得到的余数每8 8项构成循环：项构成循环：项构成循环：项构成循环：1 2 0 2 2 1 0 11 2 0 2 2 1 0 1。如果我们

31、把这8个余数存放到一个数组f0，对输入的任意整数n，则f(n)%3=f0n%8f(n)%3=f0n%8。按照这种方法可以很快判断f(n)是否能被3整除。32#include int f(int n)/求第n项对3取余得到的余数if(n=0)return 1;else if(n=1)return 2;else return(f(n-1)+f(n-2)%3;int main()int f08;for(int i=0;i8;i+)/把前8项的余数保存下来f0i=f(i);int n;while(scanf(%d,&n)!=EOF)if(f0n%8=0)printf(yesn);else printf

32、(non);return 0;33例例例例8.7 8.7 分形分形分形分形(Fractal)Fractal)题目来源：Asia 2004,Shanghai(Mainland China),Preliminary题号：ZOJ2423，POJ2083题目描述：题目描述：题目描述：题目描述：分形分形分形分形是存在“自相似”的一个物体或一种量，从某种技术角度来说，这种“自相似”是全方位的。盒形分形盒形分形盒形分形盒形分形定义如下：度数为1的分形很简单，为：X度数为2的分形为：X X XX X如果用B(n-1)B(n-1)代表度数为n-1n-1的盒形分形，则度数为n n的盒形分形可以递归递归递归递归地定

33、义为：B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)你的任务是输出度数为输出度数为输出度数为输出度数为n n的盒形分形的盒形分形的盒形分形的盒形分形。34输入描述：输入描述：输入描述：输入描述：输入文件包含多个测试数据，每个测试数据占一行，包含一个正整数n，n7。输入文件的最后一行为输入文件的最后一行为输入文件的最后一行为输入文件的最后一行为-1-1，代表输入结束，代表输入结束，代表输入结束，代表输入结束。第二种输入方式!输出描述：输出描述：输出描述：输出描述：对每个测试数据，用符号“X”输出盒形分形。在每个测试数据对应

34、的输出之后输出一个短划线符号“-”，在每行的末尾不要在每行的末尾不要在每行的末尾不要在每行的末尾不要输出任何多余的空格输出任何多余的空格输出任何多余的空格输出任何多余的空格，否则得到的是“格式错误”的结果。注意：注意：注意：注意：这道题目在ZOJ和POJ上对输出的要求不一样；在ZOJ上要求在每行的末尾不要输出多余的空格，而在POJ上要求每行的宽度一样，这样某些行末尾有若干个空格。35样例输出：样例输出：样例输出：样例输出：X-X X XX X-X X X X X XX X X X X X X X XX X X X X XX X X X-样例输入：样例输入：样例输入：样例输入：123-136分析

35、：分析：分析：分析：首先注意到度数为n的盒形分形，其大小是3 3n-1n-133n-1n-1。可以用字符数组来存储盒形分形中各字符。因为n7，而36=729，因此可以定义一字符数组定义一字符数组定义一字符数组定义一字符数组Fractal730730Fractal730730来存储度数不超过来存储度数不超过来存储度数不超过来存储度数不超过7 7的盒形分形的盒形分形的盒形分形的盒形分形。其次，度数为n的盒形分形可以由以下递推式子递推式子表示：B(n-1)B(n-1)B(n)=B(n-1)B(n-1)B(n-1)37 B(n-1)B(n-1)B(n)=B(n-1)B(n-1)B(n-1)因此，可以用

36、一个递归函数递归函数递归函数递归函数来设置度数为n的盒形分形。假设需需需需要在要在要在要在(startXstartX,startYstartY)位置开始设置度数为位置开始设置度数为位置开始设置度数为位置开始设置度数为n n的盒形分形的盒形分形的盒形分形的盒形分形，它由5个度数为n-1的盒形分形组成，其起始位置分别为：(startXstartX+0,+0,startYstartY+0)+0)、(startXstartX+2*L0,+2*L0,startYstartY+0)+0)、(startXstartX+L0,+L0,startYstartY+L0)+L0)、(startXstartX+0,+

37、0,startYstartY+2*L0)+2*L0)和(startXstartX+2*L0,+2*L0,startYstartY+2*L0)+2*L0)，其中L0=3L0=3n-2n-2。该递归函数的结束条件结束条件结束条件结束条件是：当当当当n=1n=1时，即度数为时，即度数为时，即度数为时，即度数为1 1的盒形分形，的盒形分形，的盒形分形，的盒形分形，只需在只需在只需在只需在(startXstartX,startYstartY)位置设置一个位置设置一个位置设置一个位置设置一个“X”X”字符字符字符字符。另外，题目中提到“在每行的末尾不要输出任何多余的空格在每行的末尾不要输出任何多余的空格在

38、每行的末尾不要输出任何多余的空格在每行的末尾不要输出任何多余的空格”，因此在字符数组Fractal每行最后一个“X”字符之后，应该设置串结束符标志0。38#include#include#define MAXSCALE 730/n为最大值7时，分形的大小是3636，而36=729/函数功能：从(startX,startY)位置开始设置度数为n的盒形分形，/即对盒形分形中的每个X，在字符数组Frac的相应位置设置字符X/其中第1个形参为二维数组名，其第2维不能省略void SetFractal(char Frac 730,int startX,int startY,int n)if(n=1)Fr

39、acstartXstartY=X;elseint L0=(int)pow(3,n-2);SetFractal(Frac,startX+0,startY+0,n-1);SetFractal(Frac,startX+2*L0,startY+0,n-1);SetFractal(Frac,startX+L0,startY+L0,n-1);SetFractal(Frac,startX+0,startY+2*L0,n-1);SetFractal(Frac,startX+2*L0,startY+2*L0,n-1);39int main()int n;/分形的大小int i,j;/循环变量char Fract

40、alMAXSCALEMAXSCALE;while(scanf(%d,&n)if(n=-1)break;int measure=(int)pow(3,n-1);/盒形分形大小SetFractal(Fractal,0,0,n);for(i=0;imeasure;i+)/保证每行最后的X后是0int max=0;for(j=0;jmeasure;j+)/找到每行最后的Xif(Fractalij=X)max=j;for(j=0;jmax;j+)/非X的位置上为空格if(Fractalij!=X)Fractalij=;Fractalimax+1=0;/在每行最后的X后添上0for(i=0;imeasure;i+)printf(%sn,Fractali);printf(-n);return 0;