在网上看到的一个算法题,据说是某个大公司的面试题。题目如下:给出一个数n,求1到n这些数中1出现的次数
这个题是典型的用递归算法来解决的,代码如下:
java 代码
- import
java.math.BigInteger;
- import
java.util.*;
-
-
-
-
- public
class
CountOne{
-
private
static
HashMap result =
new
HashMap();
-
-
-
private
static
BigInteger computeX(String num){
- BigInteger r =result.get(num.length());
-
if
(r==
null
){
- r =countOne(num);
- result.put(num.length(),r);
- }
-
return
r;
- }
-
-
private
static
BigInteger getInteger(
int
n){
- StringBuilder sb =
new
StringBuilder(n+
1
);
- sb.append('
1
');
-
for
(
int
i=
0
;i0
');
-
return
new
BigInteger(sb.toString());
- }
-
-
-
-
private
static
String getString(
int
n){
- StringBuilder sb =
new
StringBuilder(n);
-
for
(
int
i=
0
;i9
');
-
return
sb.toString();
- }
-
-
-
-
-
public
static
BigInteger countOne(String num){
-
if
(num.length()==
1
){
-
if
(num.equals(
"0"
))
return
BigInteger.ZERO;
-
else
return
BigInteger.ONE;
- }
-
- BigInteger high,lower,remainder;
-
-
if
(num.charAt(
0
)=='
0
') high =BigInteger.ZERO;
-
else
if
(num.charAt(
0
)=='
1
') high =
new
BigInteger(num.substring(
1
)).add(BigInteger.ONE);
-
else
high =getInteger(num.length()-
1
);
-
- lower =computeX(getString(num.length()-
1
)).multiply(
new
BigInteger(num.substring(
0
,
1
)));
- remainder =countOne(num.substring(
1
));
-
return
high.add(lower).add(remainder);
- }
-
-
public
static
void
main(String[] args){
-
long
currentTime =System.currentTimeMillis();
- BigInteger bi =
new
BigInteger(
"453454583828382932382932342342342423"
);
-
for
(
int
n=
0
;n<
10
;n++){
- System.out.println(bi +
" :"
+countOne(bi.toString()));
- bi =bi.add(BigInteger.ONE);
- }
-
long
det =System.currentTimeMillis() -currentTime;
- System.out.println(det);
- }
- }
注意代码里面用到了一个HashMap来保存10^n-1那些数的对应值,这段代码比较重要,如果不要的话,算法的时间复杂度将达到 O(N^(1/3)) (精确的说:其中n的指数是ln2/ln10
)
;而加上后,算法的时间复杂度降低到O(logN).
分享到:
- 2007-03-14 17:02
- 浏览 4168
- 评论(5)
- 论坛回复 / 浏览 (5 / 5542)
- 查看更多
相关推荐
### 递归算法在程序设计中的应用 #### 一、递归的概念与本质 递归是一种重要的编程思想,在计算机科学和数学领域都有广泛的应用。它指的是一个过程或函数直接或间接地调用自身来解决问题的方法。递归的核心在于将...
1. **确定基本情况**:这是递归算法中最小的子问题,可以直接给出答案。 2. **定义递归规则**:如何将大问题分解为小问题,并通过这些小问题的解决方案组合成大问题的解决方案。 3. **分析递归深度**:递归调用的...
对于n个圆盘的情况,非递归算法的核心在于通过交替执行两个步骤来移动圆盘: 1. **步骤1**:根据圆盘数量的奇偶性,按顺时针方向将圆盘1从当前柱子移动到下一柱子。如果圆盘1在A,移到B;如果在B,移到C;如果在C,...
在递归算法中,时间复杂度不仅取决于单次调用的操作数,还与递归调用的深度和次数有关。 #### 阶乘算法的时间复杂度 考虑一个计算阶乘n!的递归算法,其基本形式如下: ``` int fac(int n) { if (n == 0) return...
汉诺塔问题是一个经典的递归算法问题,它涉及到三个柱子(塔)和若干个大小不一的圆盘。在初始状态下,所有圆盘按照大小顺序堆叠在第一个柱子(1号塔)上,大的在下,小的在上。目标是将所有的圆盘从1号塔移动到2号...
递归算法是一种非常强大的编程技术,在C++语言中尤为重要。递归通过函数或者过程调用自身来解决问题,使得很多复杂的问题得以简化。 **递归的特点:** - **直接递归**:函数直接调用自身。 - **间接递归**:函数A...
在编程领域,递归函数是一种强大的工具...总的来说,理解和计算递归函数调用次数是编程中的重要技能,它涉及到算法分析、性能优化和问题解决策略等多个方面。通过熟练掌握递归,程序员能更好地应对各种复杂的编程挑战。
递归算法设计方法是解决问题的有效手段,特别是在实际编程中遇到的许多定义或者问题本身具有递归性质的情况下。递归算法可以使代码简洁,结构清晰,但设计递归算法需要考虑到递归关系和边界条件。 递归算法的特点是...
- 考虑文章中提到的递归题目,即计算一个正整数 n 变为 1 的最少操作次数。 - 此递归算法的时间复杂度可以通过递归树来分析。 - 由于算法中存在三种操作(除以 2、加 1 和减 1),因此递归树的分支数量不固定。 - ...
数据结构 C 语言的 N 皇后算法是数据结构和 C 语言应用中的一种经典算法。该算法解决了 N 皇后问题,即在 N×N 格的国际象棋上摆放 N 个皇后,使其不能互相攻击的摆法问题。该算法的优化设计是通过对 C 语言的知识...
这意味着通过某种方式减少了计算过程中的递归调用次数。具体来说,这种方法通过避免重复计算相同的子问题来减少递归次数,从而提高了效率。 ### 3. **自定义数据结构的应用** 文件中的`EstateTool`类包含了一个内部...
其中,`C(n)`表示处理大小为`n`的问题实例所需的比较次数。该方程体现了分治策略的核心思想:将问题分解为两个相等大小的子问题,递归解决这两个子问题,并在合并结果时进行额外的比较。 #### 递归方程的求解方法 ...
`Pow`函数是一个简单的幂运算函数,用于计算`x`的`y`次方,这里用于计算移动圆盘的总次数,即`2^n - 1`。 在`main`函数中,用户输入圆盘的数量,程序创建相应的结构数组并初始化,然后调用`Hannuota`函数开始移动...
在设计递归算法时,我们需要确保满足三个基本条件:一是问题可以通过解决规模更小的子问题来解决,二是递归调用的次数是有限的,三是存在一个终止条件以结束递归。 以“上楼梯”问题为例,假设有N阶台阶,每次可以...
在设计递归算法时,我们需要注意递归调用的次数,以及递归停止的条件,以避免造成无限递归的情况。 2.1.1 递归算法特性 递归算法的特性主要表现在它的重复性,即算法会在解决问题的过程中不断调用自身来达到分解...
推论1:设某一递归算法时间复杂度函数为t(n),如果其k阶常系数递推关系式所对应的特征多项式C(x)有k个不同的根β1, β2, ..., βk,则t(n)的解为t(n) = A1β1n + A2β2n ... + Akβkn,其中A1, A2, ..., Ak为k个待定...
本主题涵盖了5个使用C语言编写的递归法经典例题,包括找到数组中的最大值、模拟母牛繁殖、计算x的n次幂、求一个整数各数字的和以及输出整数的各位数字。下面将详细解释这些知识点: 1. **最大值**:在"最大值.c...
通过上述分析,我们可以看到递归算法是如何被应用于具体的C语言程序中的。这种方法不仅能够简化问题的求解过程,还能够在很多情况下提供简洁优雅的解决方案。对于希望深入学习递归算法和组合问题的读者来说,本文...
递归算法是一种重要的编程技术,它在计算机科学中占有举足轻重的地位。递归算法的概念最早由约翰·麦卡锡(John McCarthy)教授提出,他曾在麻省理工学院任教,并后移至斯坦福大学继续其研究工作。1970年左右,递归...
1. **确定最大数**:在待排序的数组中找出最大的数,确定其位数,作为循环的次数。这一步骤确保了所有的数字都能被正确排序。 2. **分配**:从最低位开始,对每一位进行排序。首先创建与位数相同数量的桶,每个桶...