Count and Say，统计并输出，利用递归，和斐波那契数列原理一样。

问题描述：n=1，返回“1”；n=2，返回“11”；n=3，返回“21”；n=4，返回1211，。。。。

算法分析：和斐波那契数列道理差不多，都是后一个要依赖前一个元素。因此可以使用递归，也可以使用迭代。

递归算法：

 public String countAndSay(int n)

     {

         StringBuffer sb = new StringBuffer();

         if(n <= 0)

             return null;

         if(n == 1)

         {

             return "1";

         }

         if(n >= 2)

         {

             String s = countAndSay(n-1);

             int count = 1;

             for(int i = 1; i < s.length(); i ++)

             {

                 if(s.charAt(i) == s.charAt(i-1))

                 {

                     count ++;

                 }

                 else

                 {

                     sb.append(count);

                     sb.append(s.charAt(i-1));

                     count = 1;

                 }

             }

             sb.append(count);

             sb.append(s.charAt(s.length()-1));

         }

         return sb.toString();

     }

迭代算法：

 public String countAndSay(int n)

     {

         if(n <= 0)

         {

             return null;

         }

         String result = "1";

         for(int i = 1; i < n; i ++)

         {

             StringBuffer sb = new StringBuffer();

             int count = 1;

             for(int j = 1; j < result.length(); j ++)

             {

                 if(result.charAt(j) == result.charAt(j - 1))

                 {

                     count ++;

                 }

                 else

                 {

                     sb.append(count);

                     sb.append(result.charAt(j-1));

                     count = 1;

                 }

             }

             sb.append(count);

             sb.append(result.charAt(result.length()-1));

             result = sb.toString();

         }

         return result;

     }

巴特西

Count and Say，统计并输出，利用递归，和斐波那契数列原理一样。

最新文章

热门文章