黑马程序员技术交流社区

标题: 一个递归的小问题,求解决------急 [打印本页]
作者: 丁桂松    时间: 2012-5-29 23:19
标题: 一个递归的小问题,求解决------急
本帖最后由 丁桂松 于 2012-5-30 04:46 编辑

对于一个整数n，有一个函数f（n） 可以计算到0到n之间的出现“1“的个数。例如：f（1） = 1，f（13） = 6，
因为 1,2,3,4,5,6,7,8,9,10,11,12,13 数数1的个数正好是6。实现这个函数 int f（int n）  只能用递归解答！
作者: 贾旭    时间: 2012-5-29 23:21
先占座。一会儿给答案
作者: 秦冲    时间: 2012-5-30 00:03
我的方法有点取巧，呵呵，简单，把大于10的数字变成string得到每位有1就加1，看代码非常好理解。
  1. public class Test {
  2.         public static void main(String[] args) {
  3.                 Test t = new Test();
  4.                 System.out.println(t.f(13));
  5.         }
  6.         public int num = 0;// 计算1出现的个数
  7.         public int f(int n) {
  8.                 if (n < 10) {
  9.                         if (n == 1) {
  10.                                 return ++num;
  11.                         } else {
  12.                                 f(n-1);
  13.                         }
  14.                 } else {
  15.                         if (n >= 10) {
  16.                                 String s = new String(n + "");
  17.                                 char[] cs = s.toCharArray();
  18.                                 for (char c : cs) {
  19.                                         if (c == 49) {
  20.                                                 num++;
  21.                                         }
  22.                                 }
  23.                                 f(n-1);
  24.                         }
  25.                 }
  26.                 return num;
  27.         }
  28. }
复制代码
作者: 丁桂松    时间: 2012-5-30 01:17
秦冲 发表于 2012-5-30 00:03
我的方法有点取巧，呵呵，简单，把大于10的数字变成string得到每位有1就加1，看代码非常好理解。 ...

谢谢,一直在忙,没来得及回
作者: 胡团乐    时间: 2012-5-30 03:47
本帖最后由 胡团乐 于 2012-5-30 03:54 编辑

我觉得我这个也蛮好理解的 把n（比如13）以下的数字逐一加到一个Stringbuilder中 然后转换成字符串数组，逐一取出和'1'比较，如果相等就count++
  1. public class Test01 {

  3.         public static void main(String[] args) {
  4.                 Test01 t = new Test01();
  5.                 t.f(13);
  6.         }

  8.         int count = 0;
  9.         StringBuilder sb = new StringBuilder();

  11.         public void f(int n) {
  12.                 sb.append(n);
  13.                 if (n >= 1)
  14.                         f(n - 1);
  15.                 String str = sb.toString();
  16.                 if (!(n >= 1)) {
  17.                         char[] chs = str.toCharArray();
  18.                         for (int i = 0; i < chs.length; i++) {
  19.                                 if (chs[i] == '1')
  20.                                         count++;
  21.                         }
  22.                         System.out.println(str);
  23.                         System.out.println("count=" + count);
  24.                 }

  26.         }

  28. }
复制代码
作者: 张亭    时间: 2012-5-30 09:21
咱也写个玩玩,供参考
  1. int f(int n){
  2.      if (n==1)
  3.            return 1;
  4.      int num = 0;
  5.      char[] chs = Integer.toString(n).toCharArray();
  6.      for (char ch : chs)
  7.           if (ch == '1')
  8.                num++;
  9.      return f(--n)+num;
  10. }
复制代码
作者: 杨天皓    时间: 2012-5-30 10:33
可能我写的比较复杂了
  1. class  RecursionDemo

  3. {
  4.         public static void main(String[] args)
  5.         {
  6.                 System.out.println(count(0));
  7.         }

  9.         public static int count(int a)
  10.         {
  11.                 int temp = 0;
  12.                 for (int i = a;i>0;)
  13.                 {
  14.                         //System.out.println("a::"+a+"   a%10::"+a%10+"  a%100/10::"+a%100/10);
  15.                         if(a%10==1)//求各位上的数
  16.                         {
  17.                                 ++temp;
  18.                                 //在这里多判断一次十位上的数是因为，
  19.                                 //如果个位上是1就在继续判断十位上是否是1.
  20.                        
  21.                                 if(a%100/10==1)//求十位上的数。
  22.                                 {
  23.                                         return ++temp+count(--a);
  24.                                 }
  25.                                 return temp+count(--a);
  26.                         }
  27.                         //如果个位上不是1，再继续判断判断十位是否是1
  28.                         if(a%100/10==1)
  29.                         {
  30.                                 return ++temp+count(--a);
  31.                         }
  32.                         a--;
  33.                 }
  34.                 return temp;
  35.         }
  36. }
复制代码
作者: 杨天皓    时间: 2012-5-30 10:41
如果不用递归的话。那就简单多了。
class  RecursionDemo

{
        public static void main(String[] args)
        {
                System.out.println(count(14));
        }

        public static int count(int a)
        {
                int temp = 0;
                for (int i = a;i>0;i--)
                {
                       
                        if(i%10==1)
                        {
                                temp++;
                        }
                        if(i%100/10==1)
                        {
                                temp++;
                        }
                }
                return temp;
        }
}
作者: 唐辉辉    时间: 2012-5-30 12:20
我也写个玩玩！！

class DiGuiDemo{
       
        public static int count=0;
        public static String str;
        public static int point=0;
       
        public static void fun(int num){
               
                str = String.valueOf(point);
                char[] ch = str.toCharArray();
               
                for(int i=0;i<ch.length;i++){
                       
                        if(ch[i]=='1'){
                                count++;
                                break;
                               
                        }
                }
               
                System.out.println(point);
                if(point<num){
                       
                        point++;
                        fun(num);
                }else{
                       
                        System.out.println(count);
                }               
        }
       
       
        public static void main(String[] args){
               
                fun(30);
        }
}



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2