`
Eastsun
  • 浏览: 308233 次
  • 性别: Icon_minigender_1
  • 来自: 天津
社区版块
存档分类
最新评论

求1~N中1出现的次数的递归算法

阅读更多

        在网上看到的一个算法题,据说是某个大公司的面试题。题目如下:给出一个数n,求1到n这些数中1出现的次数

       这个题是典型的用递归算法来解决的,代码如下:

java 代码
  1. import  java.math.BigInteger;   
  2. import  java.util.*;   
  3. /**  
  4. *求1到N这些数中1出现的次数  
  5. *@author Eastsun  
  6. */   
  7. public   class  CountOne{   
  8.      private   static  HashMap result = new  HashMap();   
  9.        
  10.      //计算countOne(10^n-1)   
  11.      private   static  BigInteger computeX(String num){   
  12.         BigInteger r =result.get(num.length());   
  13.          if (r== null ){   
  14.             r =countOne(num);   
  15.             result.put(num.length(),r);   
  16.         }   
  17.          return  r;   
  18.     }   
  19.      //得到一个表示10^n的BigInteger   
  20.      private   static  BigInteger getInteger( int  n){   
  21.         StringBuilder sb = new  StringBuilder(n+ 1 );   
  22.         sb.append(' 1 ');   
  23.          for ( int  i= 0 ;i0 ');   
  24.          return   new  BigInteger(sb.toString());   
  25.     }   
  26.        
  27.   
  28.      //生成一个代表10^n-1的字符串,即n个9   
  29.      private   static  String getString( int  n){   
  30.         StringBuilder sb = new  StringBuilder(n);   
  31.          for ( int  i= 0 ;i9 ');   
  32.          return  sb.toString();   
  33.     }   
  34.      /**  
  35.     *计算从1到num这些数中1出现的次数  
  36.     *@param num 一个表示整数的字符串  
  37.     */   
  38.      public   static  BigInteger countOne(String num){   
  39.          if (num.length()== 1 ){   
  40.              if (num.equals( "0" ))  return  BigInteger.ZERO;   
  41.              else                  return  BigInteger.ONE;   
  42.         }   
  43.            
  44.         BigInteger high,lower,remainder;   
  45.            
  46.          if (num.charAt( 0 )==' 0 ') high =BigInteger.ZERO;   
  47.          else   if (num.charAt( 0 )==' 1 ') high = new  BigInteger(num.substring( 1 )).add(BigInteger.ONE);   
  48.          else   high =getInteger(num.length()- 1 );   
  49.            
  50.         lower =computeX(getString(num.length()- 1 )).multiply( new  BigInteger(num.substring( 0 , 1 )));   
  51.         remainder =countOne(num.substring( 1 ));   
  52.          return  high.add(lower).add(remainder);   
  53.     }   
  54.        
  55.      public   static   void  main(String[] args){   
  56.          long  currentTime =System.currentTimeMillis();   
  57.         BigInteger bi = new  BigInteger( "453454583828382932382932342342342423" );   
  58.          for ( int  n= 0 ;n< 10 ;n++){   
  59.             System.out.println(bi + " :" +countOne(bi.toString()));   
  60.             bi =bi.add(BigInteger.ONE);   
  61.         }   
  62.          long  det =System.currentTimeMillis() -currentTime;   
  63.         System.out.println(det);   
  64.     }   
  65. }  

          注意代码里面用到了一个HashMap来保存10^n-1那些数的对应值,这段代码比较重要,如果不要的话,算法的时间复杂度将达到 O(N^(1/3)) (精确的说:其中n的指数是ln2/ln10 ) ;而加上后,算法的时间复杂度降低到O(logN).

  • CountOne.rar (889 Bytes)
  • 描述: 本文中的代码,贴上的代码有走样。
  • 下载次数: 62
分享到:
评论
5 楼 crackerwang 2007-08-17  
想起PKU  3286和2282
当时要是看了你这篇肯定能瞬间AC
4 楼 Godlikeme 2007-03-15  
暂且叫查表吧,呵呵。
粗略想到一种不需要查表的logN 复杂度算法,还没有验证,待抽时间写出来。
3 楼 simohayha 2007-03-14  
很老的帖子了,看这个
http://www.iteye.com/post/98905
2 楼 Eastsun 2007-03-14  
不叫速查表吧,只是把那些会多次用到的数据保存下来,避免重复递归(与动态规划有点像)。
1 楼 Godlikeme 2007-03-14  
抽时间看一下,使用了 速查表,速查表的生成没看太明白。

相关推荐

    程序设计中递归算法

    ### 递归算法在程序设计中的应用 #### 一、递归的概念与本质 递归是一种重要的编程思想,在计算机科学和数学领域都有广泛的应用。它指的是一个过程或函数直接或间接地调用自身来解决问题的方法。递归的核心在于将...

    递归算法专题ppt

    1. **确定基本情况**:这是递归算法中最小的子问题,可以直接给出答案。 2. **定义递归规则**:如何将大问题分解为小问题,并通过这些小问题的解决方案组合成大问题的解决方案。 3. **分析递归深度**:递归调用的...

    汉诺塔问题的非递归算法

    对于n个圆盘的情况,非递归算法的核心在于通过交替执行两个步骤来移动圆盘: 1. **步骤1**:根据圆盘数量的奇偶性,按顺时针方向将圆盘1从当前柱子移动到下一柱子。如果圆盘1在A,移到B;如果在B,移到C;如果在C,...

    关于递归算法时间复杂度分析的探讨.pdf

    在递归算法中,时间复杂度不仅取决于单次调用的操作数,还与递归调用的深度和次数有关。 #### 阶乘算法的时间复杂度 考虑一个计算阶乘n!的递归算法,其基本形式如下: ``` int fac(int n) { if (n == 0) return...

    汉诺塔递归算法--C语言

    汉诺塔问题是一个经典的递归算法问题,它涉及到三个柱子(塔)和若干个大小不一的圆盘。在初始状态下,所有圆盘按照大小顺序堆叠在第一个柱子(1号塔)上,大的在下,小的在上。目标是将所有的圆盘从1号塔移动到2号...

    基础算法 第4章 递归算法(C++版)-2020.12.22.pdf

    递归算法是一种非常强大的编程技术,在C++语言中尤为重要。递归通过函数或者过程调用自身来解决问题,使得很多复杂的问题得以简化。 **递归的特点:** - **直接递归**:函数直接调用自身。 - **间接递归**:函数A...

    计算递归函数调用次数

    在编程领域,递归函数是一种强大的工具...总的来说,理解和计算递归函数调用次数是编程中的重要技能,它涉及到算法分析、性能优化和问题解决策略等多个方面。通过熟练掌握递归,程序员能更好地应对各种复杂的编程挑战。

    递归算法设计方法(免费资源,超级实惠)

    递归算法设计方法是解决问题的有效手段,特别是在实际编程中遇到的许多定义或者问题本身具有递归性质的情况下。递归算法可以使代码简洁,结构清晰,但设计递归算法需要考虑到递归关系和边界条件。 递归算法的特点是...

    Java 数组递归算法的复杂度

    - 考虑文章中提到的递归题目,即计算一个正整数 n 变为 1 的最少操作次数。 - 此递归算法的时间复杂度可以通过递归树来分析。 - 由于算法中存在三种操作(除以 2、加 1 和减 1),因此递归树的分支数量不固定。 - ...

    数据结构C语言的n皇后算法

    数据结构 C 语言的 N 皇后算法是数据结构和 C 语言应用中的一种经典算法。该算法解决了 N 皇后问题,即在 N×N 格的国际象棋上摆放 N 个皇后,使其不能互相攻击的摆法问题。该算法的优化设计是通过对 C 语言的知识...

    可以节省(n-1)!次递归的排列生成工具类(java)

    这意味着通过某种方式减少了计算过程中的递归调用次数。具体来说,这种方法通过避免重复计算相同的子问题来减少递归次数,从而提高了效率。 ### 3. **自定义数据结构的应用** 文件中的`EstateTool`类包含了一个内部...

    算法时间复杂度分析中递归方程求解方法综述

    其中,`C(n)`表示处理大小为`n`的问题实例所需的比较次数。该方程体现了分治策略的核心思想:将问题分解为两个相等大小的子问题,递归解决这两个子问题,并在合并结果时进行额外的比较。 #### 递归方程的求解方法 ...

    汉诺塔的算法,有递归算法

    `Pow`函数是一个简单的幂运算函数,用于计算`x`的`y`次方,这里用于计算移动圆盘的总次数,即`2^n - 1`。 在`main`函数中,用户输入圆盘的数量,程序创建相应的结构数组并初始化,然后调用`Hannuota`函数开始移动...

    pascal递归算法.doc

    在设计递归算法时,我们需要确保满足三个基本条件:一是问题可以通过解决规模更小的子问题来解决,二是递归调用的次数是有限的,三是存在一个终止条件以结束递归。 以“上楼梯”问题为例,假设有N阶台阶,每次可以...

    算法设计与分析:第2章 递归法.pdf

    在设计递归算法时,我们需要注意递归调用的次数,以及递归停止的条件,以避免造成无限递归的情况。 2.1.1 递归算法特性 递归算法的特性主要表现在它的重复性,即算法会在解决问题的过程中不断调用自身来达到分解...

    用递推关系理论分析递归算法的时间复杂度.doc

    推论1:设某一递归算法时间复杂度函数为t(n),如果其k阶常系数递推关系式所对应的特征多项式C(x)有k个不同的根β1, β2, ..., βk,则t(n)的解为t(n) = A1β1n + A2β2n ... + Akβkn,其中A1, A2, ..., Ak为k个待定...

    算法设计与优化第六章递归法经典例题(如最大值,母牛繁殖,x的n次幂等共5个)

    本主题涵盖了5个使用C语言编写的递归法经典例题,包括找到数组中的最大值、模拟母牛繁殖、计算x的n次幂、求一个整数各数字的和以及输出整数的各位数字。下面将详细解释这些知识点: 1. **最大值**:在"最大值.c...

    递归算法实现组合(c语言实现,平台:Automation Studio@AR system)

    通过上述分析,我们可以看到递归算法是如何被应用于具体的C语言程序中的。这种方法不仅能够简化问题的求解过程,还能够在很多情况下提供简洁优雅的解决方案。对于希望深入学习递归算法和组合问题的读者来说,本文...

    算法与数据结构 算法分析课程 递归算法及归纳法 共56页.pptx

    递归算法是一种重要的编程技术,它在计算机科学中占有举足轻重的地位。递归算法的概念最早由约翰·麦卡锡(John McCarthy)教授提出,他曾在麻省理工学院任教,并后移至斯坦福大学继续其研究工作。1970年左右,递归...

    利用递归算法实现的基数排序算法

    1. **确定最大数**:在待排序的数组中找出最大的数,确定其位数,作为循环的次数。这一步骤确保了所有的数字都能被正确排序。 2. **分配**:从最低位开始,对每一位进行排序。首先创建与位数相同数量的桶,每个桶...

Global site tag (gtag.js) - Google Analytics