posts - 77, comments - 54, trackbacks - 0, articles - 0
  IT博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

关于递归(recursion)的理解实例。

Posted on 2006-06-07 10:25 东人EP 阅读(219) 评论(0)  编辑 收藏 引用 所属分类: .NET
 1 /*
 2     递归(recursion)
 3     递归是常用的一种解决问题的方法,即把问题逐渐简化。
 4     递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将直接或间接地调用自身的方法。
 5     利用递归可以用简单程序解决复杂的问题。
 6     我们先来看看一个用递归求阶乘的例子,如下所示。
 7 */

 8 public   class   recursion
 9 {
10      static   long  function( int  n)
11      {
12          if  (n  ==   1 )
13          {
14              return   1 ;
15         }

16          else
17          {
18              return  n  *  function(n - 1 );
19         }

20     }

21
22      public   static   void  main(String[] args) 
23      {
24          int  n  =   10 ;
25         System.out.println(n  +   " !=  "   +  function(n));
26     }

27 }

28 /*
29     程序的输出结果为:
30     10!=3628800
31     递归的结构主要包括两部分:
32     1.定义递归头:任何一个递归方法都必须有一个递归头,也就是递归终止的条件。
33        即要解决的问题被简化到足够简单时,将可以直接获得问题的答案,而不必再调用自身。
34        例如上例中求1!可以直接得到1,就是递归头。
35     2.定义如何从同性质的简化问题求得当前问题。
36        问题的解答依赖于一个同性质问题的解答,而解答这个同性质的问题就是用不同的参数来调用递归方法自身。
37        例如上例中求n!这个问题,被划分为求(n-1)!和(n-1)!*n两个步骤。
38        依次类推求(b-1)!可以继续划分。。。。。
39 */

40 /*
41     下面我们利用递归来求解8个皇后问题。
42     8个皇后问题说得是:在国际象棋的棋盘上,放置8个皇后,如何放才能使得这8个皇后无论横着看,竖着看,斜着看都不在同一条直线上。
43     如图所示是一种可能的摆放情况:其中放置皇后的地方标记Q。
44 */

45 //  Queen.Java
46 import  javax.swing. * ;
47 public   class  Queens
48 {
49      int [] a  =   new   int [ 8 ];
50      int [] b  =   new   int [ 15 ];
51      int [][] c  =   new   int [ 8 ][ 8 ];
52
53      void  next( int  i)
54      {
55          for ( int  j = 0 ; j  <   8 ; j ++ )
56          {
57              if (a[j]  ==   0   &&  b[i + j}
  ==   0   &&  c[i - j + 7 ==   0 )
58              {
59                 a[j]  =  b[i + j]  =  c[i - j + 7 =   1 ;
60                 Queen[i][j]  =   1 ;
61                  if (i < 7 )
62                  {
63                     next(i + 1 );
64                 }

65                  else
66                  {
67                     String output  =   new  String();
68                      for ( int  m = 0 ; m  <   8 ; m ++ )
69                      {
70                          for ( int  n = 0 ; n  <   8 ; n ++ )
71                             output  +=   "      "   +  d[m][n]  +   "       " ;
72                         output  +=   " \n " ;
73                     }

74                      // 每种可能的情况以0、1表示(1表示皇后)输出
75                     JTextArea outputArea  =   new  JTextArea();
76                     outputArea.setText(output);
77                     JOptionPane.showMessageDialog( null , outputArea,  " One Possible distribution " , JOptionPane.INFORMATION_MESSAGE);
78                 }

79                 a[j]  =  b[i + j]  =  c[i - j + 7 =  Queen[i][j]  =   0 ;
80             }

81         }

82     }

83
84      public   static   void  main(String args[])
85      {
86         Queens one  =   new  Queens();
87         one.next( 0 );
88         System.exit( 0 );
89     }

90 };
只有注册用户登录后才能发表评论。