4年前 (2020-10-05)  Java系列 |   抢沙发  719 
文章评分 0 次,平均分 0.0

二进制数系统

你可能知道计算机只能存储1和0,这是因为处理器和内存是由数十亿个微小的开关组成的。

值1表示开关打开;值0表示开关关闭。所有类型的数据,无论是整数、浮点、文本、音频、视频或其他数据,都用1和0表示。

幸运的是,我们可以将任何整数表示为二进制数。下表显示了前8个二进制和十进制数字。

Binary Decimal
0 0
1 1
10 2
11 3
100 4
101 5
110 6
111 7

十进制有10位数字,数字的书面表示是以10的幂为基础的。例如,456在100位有4位,10位有5位,1位有6位。所以值是400+50+6

4 5 6
102 101 100

二进制中有两个数字,数字的书面表示是基于2的幂。例如,10111在16位有1,8位有0,4位有1,2位有1,1在1位。所以这个值是16+0+4+2+1,十进制数是23。

1 0 1 1 1
24 23 22 21 20

为了得到十进制数的位数,我们可以使用重复除法。例如,如果我们用456除以10,那么余数为6得到45。余数是456的最右边的数字。

如果我们再除以结果,我们得到4和余数5。余数是456的第二个最右边的数字。如果我们再除以一次,余数为4得到0。余数是456的第三个最右边的数字,结果是0,告诉我们完成了。

如果我们除以2,在二进制中也可以做同样的事情。除以2时,余数是最右边的数字,可以是0或1。如果你再除以结果,你得到第二个最右边的数字。如果你继续写下余数,你就会得到二进制数:

23 / 2 is 11 remainder 1
11 / 2 is  5 remainder 1
 5 / 2 is  2 remainder 1
 2 / 2 is  1 remainder 0
 1 / 2 is  0 remainder 1

从下至上读这些余数,二进制中的23等于10111。

递归二进制法

现在,为了以二进制形式显示一个数字,我们可以结合上一节的算法和这一篇中的的“向上计数”模式:https://javakk.com/517.html

以下是一个递归方法,它以二进制形式显示任何正整数:

public static void displayBinary(int value) {
    if (value > 0) {
        displayBinary(value / 2);
        System.out.print(value % 2);
    }
}

如果value为0,displayBinary不执行任何操作(这是基本情况)。如果参数为正,则该方法将其除以2并递归调用displayBinary。当递归调用返回时,该方法显示结果的一位数并返回(再次)。下图说明了这一过程。

Java递归方法Recursive详解二

最左边的数字在堆栈的底部附近,所以它首先显示出来。最右边的数字,靠近栈顶,最后显示。在调用displayBinary之后,我们使用println来完成输出:

displayBinary(23);      // output is 10111
System.out.println();

CodingBat问题

在过去的几章中,您已经看到了方法、条件、循环、字符串、数组和递归。实践所有这些概念的一个很好的资源是:http://codingbat.com/

斯坦福大学的一个免费编程网站是由尼克·兰特开发的。当您处理这些问题时,CodingBat会保存您的进度(如果您创建了一个帐户)。

为了结束这一章,我们考虑了CodingBat的递归-1部分中的两个问题。其中一个处理字符串,另一个处理数组。它们都有相同的递归思想:检查基本情况,查看当前索引,然后递归地处理其余的内容。

第一个问题在 http://codingbat.com/prob/p118230 :

递归-1 noX

给定一个字符串,递归地计算一个新字符串,其中所有的“x”字符都已删除。

noX("xaxb") → "ab"

noX("abc") → "abc"

noX("xx") → ""

在解决递归问题时,首先考虑基本情况是有帮助的。基本情况是问题的最简单版本;对于noX,它是空字符串。如果参数是空字符串,则没有要删除的x:

if (str.length() == 0) {
    return "";
}

接下来是更困难的部分。要递归地解决问题,您需要考虑同一问题的一个更简单的实例。对于noX,它是从一个较短的字符串中去掉所有的x

所以让我们把字符串分成两部分,第一个字母和其余的字母:

char first = str.charAt(0);
String rest = str.substring(1);

现在我们可以通过递归调用从rest中删除x

String recurse = noX(rest);

如果第一个正好是x,我们就完成了;我们只需要返回recurse。否则,我们必须首先连接并递归。下面是我们需要的if语句:

if (first == 'x') {
    return recurse;
} else {
    return first + recurse;
}

通过将这些代码片段粘贴到提供的方法定义中,可以在CodingBat上运行此解决方案。

递归-1数组11

给定一个整数数组,递归计算值11在数组中出现的次数。

array11([1, 2, 11], 0) → 1
array11([11, 11], 0) → 2
array11([1, 2, 3, 4], 0) → 0

这个问题使用传递索引作为参数的约定。所以基本情况是当我们到达数组的末尾时。在那一点上,我们知道没有更多的11:

if (index >= nums.length) {
    return 0;
}

接下来我们查看当前的数字(基于给定的索引),并检查它是否是11。之后,我们可以递归地检查数组的其余部分。与noX问题类似,每个方法调用只查看一个整数:

int recurse = array11(nums, index + 1);
if (nums[index] == 11) {
    return recurse + 1;
} else {
    return recurse;
}

同样,通过将代码片段粘贴到方法定义中,可以在CodingBat上运行此解决方案。

学习递归思维是学习像计算机科学家一样思考的一个重要部分。许多算法可以用递归方法简洁地编写,递归方法在向下、向上或同时执行计算。

递归练习题

使用堆栈图来理解以下递归方法的执行:

public static void main(String[] args) {
    System.out.println(prod(1, 4));
}

public static int prod(int m, int n) {
    if (m == n) {
        return n;
    } else {
        int recurse = prod(m, n - 1);
        int result = n * recurse;
        return result;
    }
}
  1. 绘制一个堆栈图,显示最后一次prod调用完成之前程序的状态。
  2. 这个程序的输出是什么?(请先在纸上回答这个问题;然后运行代码检查您的答案。)
  3. 用几句话解释一下prod是做什么的(没有详细说明它是如何工作的)。
  4. 重写prod而不使用递归和结果临时变量。提示:else分支只需要一行。

本练习的目标是将递归定义转换为Java方法。Ackermann函数为非负整数定义如下:

Java递归方法Recursive详解二

编写一个名为ack的递归方法,它以两个int作为参数,计算并返回Ackermann函数的值。

测试Ackermann的实现,方法是从main调用它并显示返回值。注意,返回值很快就会变得非常大。您应该只对m和n的较小值(不大于3)进行尝试。

创建一个名为递归.java并键入以下方法:

/**
 * Returns the first character of the given String.
 */
public static char first(String s) {
    return s.charAt(0);
}
/**
 * Returns all but the first letter of the given String.
 */
public static String rest(String s) {
    return s.substring(1);
}
/**
 * Returns all but the first and last letter of the String.
 */
public static String middle(String s) {
    return s.substring(1, s.length() - 1);
}
/**
 * Returns the length of the given String.
 */
public static int length(String s) {
    return s.length();
}
  1. main中编写一些测试这些方法的代码。确保它们能起作用,你也能理解它们的作用。
  2. 使用这些方法,在不使用任何其他字符串方法的情况下,编写一个名为printString的方法,该方法以字符串为参数并显示字符串的字母,每行一个。它应该是一个无效的方法。
  3. 同样,只使用这些方法,编写一个名为printback的方法,它执行与printString相同的操作,但是向后显示字符串(同样,每行一个字符)。
  4. 现在编写一个名为reverseString的方法,它将字符串作为参数,并返回一个新字符串作为返回值。新字符串应包含与参数相同的字母,但顺序相反:
String backwards = reverseString("coffee");
System.out.println(backwards);

此示例代码的输出应如下所示:

eeffoc
 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/527.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册