Java编程技巧入门：算法开发

3.2 算法开发

本次的Java编程技巧告诉我们，编程是困难的（像大部分有用且有价值的活动一样，你可以从编程中获得回报和乐趣）。编写程序时，你需要告诉计算机如何处理每个细节。并且，由于计算机只会根据你写的内容执行，你还需要确保一切都执行正确。然而，人们只会编写最简单的程序吗？实际上，这其中没有什么秘密。重要的是学习如何正确思考。希望对大家学习Java编程技巧有所帮助。

程序就是一种思想的表达。一开始程序员对如何让计算机执行任务有一个总的想法。情况大概是这样，首先程序员会思考如何手工执行这个任务，至少会有一个总体的轮廓。问题在于如何将轮廓充实成没有歧义、逐步执行的过程，可以在有限的步骤之后终止。这个过程就称为“算法”。（从技术上讲，算法是一个没有歧义、逐步执行并在有限步后终止的过程。我们不想要这个过程无限执行下去。）算法与程序不同。程序是用某种特定的编程语言写成的。而算法更像是程序背后的思想，这个思想指的是完成指定的任务的步骤，而不是任务本身。在描述算法时，算法的步骤不需要提供完整的细节，只要没有歧义而且通过这些步骤可以完整指定的任务即可。算法可以用任何语言描述，包括英语。当然，在填充细节时算法只能表示为实际的编程。

那么，算法究竟从何而来？通常，开发算法需要大量的思考和艰苦的工作。虽然算法开发技巧是从练习中获得的，但还是有一些技巧和指导可以帮助开发算法。我会介绍一些与“微观编程”相关的算法开发技巧和指导。在后面的章节里，我还会回到这个主题继续讨论。

3.2.1  伪代码和逐步优化

在微观编程时，你需要处理一些基本概念：变量、赋值语句和输入输出例程。你可能还会有子函数、对象、已经编写的其他构建模块等等（与这个类有关的输入输出例程）。你可以构建这些基础指令序列，并且将它们加入像 while 循环和 if 语句这样更复杂的控制结构中。

假设你需要让计算机执行脑中的某个任务。一种方法，可以编写任务描述，写出需要开发的算法大纲。然后，你可以继续优化并完善描述，逐步添加执行步骤和细节，直至得到一个完整的算法，可以直接翻译成编程语言。这种方法叫做逐步优化，一种自顶向下的设计。随着优化的不同阶段，你能够将算法描述写成伪代码——这是一种非正式的指令，它模仿了编程语言的结构，但在细节上没有实际程序代码那么完整并且在语法上也不完善。作为示例，让我们看看如何开发前面章节中的程序，这个程序会计算5年的投资。程序要执行的任务是：“用户会输入初始投资额及利率，要求计算并显示未来5年中每一年的投资结果。”你可能会这么写或者这么思考，描述出来像下面这样：

Get the user's input
Compute the value of the investment after 1 year
Display the value
Compute the value after 2 years
Display the value
Compute the value after 3 years
Display the value
Compute the value after 4 years
Display the value
Compute the value after 5 years
Display the value

获取用户输入

计算1年后的投资结果

显示

计算2年后的投资结果

显示

计算3年后的投资结果

显示

计算4年后的投资结果

显示

计算5年后的投资结果

显示

虽然正确，但略显重复。当你看到重复的步骤，可能会想到这里可以用循环。使用循环可以避免重复的描述。更重要的是，这样会变得更通用：基本上你可以用同一个循环计算任意年数。隐私，你可能会重写上面的步骤：

Get the user's input
while there are more years to process:
    Compute the value after the next year
    Display the value

获得用户输入

有需要处理的年粉：

   计算下一年的投资结果

   显示

用这个算法可以顺利地解决问题，但是计算机需要我们提供这样的信息，“如何获取用户输入？如何计算下一年的投资结果？有需要处理的年份是什么意思？”于是我们需要将步骤细化，“获取用户输入”就变为：

Ask the user for the initial investment
Read the user's response
Ask the user for the interest rate
Read the user's response

请求用户输入初始投资

读取用户输入

请求用户输入利率

读取用户输入

要细化“计算下一年的投资结果”这个步骤，你自己必须需要知道如何计算。（可能你需要请教你的老板或者向教授求助？）假设你知道的计算过程是把利息与前一年的收益相加。然后，我们可以优化这个循环：

while there are more years to process:
    Compute the interest
    Add the interest to the value
    Display the value

while 有待处理的年份：

    计算利率

    将利率与投资结果相加

    显示

作为测试“是否有待处理的年份”，我们可以做的是自己统计要计算的年数。这时一种常见的模式，你应当使用与大多数程序类似的模式：从年数为0开始，每天增加1年进行处理，直到我们完成任务中的年数。有时这种模式被称作记数循环。因此，while 循环会编程：

years = 0
while years < 5:
    years = years + 1
    Compute the interest
    Add the interest to the value
    Display the value
   
years = 0
while years < 5:
    years = years + 1
    计算利息
    将利息与投资结果相加
    显示

我们还需要知道如何计算利息。假设利息等于利率乘以当前的投资结果。将这个过程为获取用户输入算法的一部分，下面得到了完整的算法：

Ask the user for the initial investment
Read the user's response
Ask the user for the interest rate
Read the user's response
years = 0
while years < 5:
    years = years + 1
    Compute interest = value * interest rate
    Add the interest to the value
    Display the value

请求用户输入初始投资

读取用户输入

请求用户输入初始利率

读取用户输入

years = 0

while years < 5:

    years = years + 1

    计算利息 利息 = value * 利率

    将利息与 value 相加

    显示 value

最后，终于到了可以将这些直接翻译成编程语言语法的时候了。我们还需要为变量取名，确定向用户提示的信息。完成了这一步，我们的Java程序就是这样：

double principal, rate, interest;  // declare the variables 声明变量
int years;
System.out.print("Type initial investment: 请输入初始投资：");
principal = TextIO.getlnDouble();
System.out.print("Type interest rate: 输入利率：");
rate = TextIO.getlnDouble();
years = 0;
while (years < 5) {
   years = years + 1;
   interest = principal * rate;
   principal = principal + interest;
   System.out.println(principal);
}

这个算法还需要继续变成完整的程序，需要添加注释并且向用户输出的提示要更加友善。但是，这已经与前面章节中的程序基本上一样的。（注意：算法的伪代码中，使用缩进表示那些是循环内的语句。在Java中，计算机会完全忽略缩进，因此需要用一对括号让计算机知道哪些语句在循环内。如果漏掉了括号，那么循环内唯一的语句就会变成“years = years + 1;”。其它语句在循环结束后只会执行一次。最糟糕的是，计算机不会像“(years < 5)”漏掉圆括号那样，向你给出类似的提示。圆括号是 while 语句要求的语法。而花括号只具有语义上的意义。计算机可以识别语法错误，但是不能识别语义错误）。

这里还有一件事情需要注意，就是这个问题的原始需求尚未完成：“计算并显示未来5年中每一年的投资结果”。在你开始动手写程序之前，确保你已经有了完整的需求，清楚地知道程序应该完成的功能。尤其是，你需要知道程序的输入和输出是什么，需要执行怎样的计算。在这个例子中，合理的完整需求应该像下面这样：

“编写程序，计算并显示未来5年中每年的投资结果。需要把每一年的利息与投资结果相加。利率等于当前投资结果乘以固定的利率。在程序运行时，初始值和利率需要由用户输入。”

3.2.2  3N+1问题

让我们再做一个例子，这一次是之前没有看过的例子。这次的任务时一个抽象的数学问题，也是我最喜欢的编程练习题之一。这次，我们先从一个更完善的任务需求开始：

“给定一个正整数 N，定义‘3N+1’序列如下：如果N是偶数，N除以2；如果N是奇数，将N乘以3再加1。重复生成，直到N等于1。举例说明，从N=3开始，3是奇数，乘以3再加1，N = 3*3+1 = 10。接着，N是偶数，需要除以2，得到N = 10/2 = 5。重复这个过程，当N等于1时停止。完整的序列是：3、10、5、16、8、4、2、1。”“编写程序读取用户输入的一个正整数，打印出3N+1序列。要求程序能够记数并输出序列的个数。”

粗略的程序算法大纲如下：

Get a positive integer N from the user.

Compute, print, and count each number in the sequence.

Output the number of terms.

读取一个用户输入的正整数N。

计算、输出并对序列中的每个数字记数。

输出序列的个数。

程序的主题在第二个步骤。我们需要一个循环，因为想要记录计算数值直到结果为1。要把这个过程实现，需要知道什么时候继续循环，而非停止循环：只要得到的数字不是1就继续循环。因此，我们可以扩展算法的伪代码：

Get a positive integer N from the user;
while N is not 1:
    Compute N = next term;
    Output N;
    Count this term;
Output the number of terms;

读取一个用户输入的正整数N。

当 N 不等于 1

   计算 N = 下一个数字

   输出N

   记数

为了计算下一个数字，计算机必须根据N的奇偶性采取不同的行动。我们需要用 if 语句来区分这两种情况。

Get a positive integer N from the user;
while N is not 1:
    if N is even:
       Compute N = N/2;
    else
       Compute N = 3 * N + 1;
    Output N;
    Count this term;
Output the number of terms;

读取一个用户输入的正整数N。

当 N 不等于 1

   if N 是 偶数

      N = N/2;

   else

      N = 3*N+1;

   输出N

   记数

差不多快要完成了。剩下的问题是记数。记数意味着你需要从0开始，每次都为计数值加1。我们需要一个变量来记数。循环开始之前，要将变量置为0，在循环过程中进行增加。（再次注意，这是你会一直重复看到的模式。）加入记数变量后，结果如下：

Get a positive integer N from the user;
Let counter = 0;
while N is not 1:
    if N is even:
       Compute N = N/2;
    else
       Compute N = 3 * N + 1;
    Output N;
    Add 1 to counter;
Output the counter;

读取一个用户输入的正整数N。

counter置为0。

当 N 不等于 1

   if N 是 偶数

      N = N/2;

   else

      N = 3*N+1;

   输出N

   记数

   counter值加1

在程序的一开始，我们还有需要注意的地方。如何确保从用户那里得到的是正整数？如果只是读入一个数字，用户可能会输入负数或者0。如果真的出现这种情况，你会看到程序会一直循环下去，因为N永远不会等于1。这是非常糟糕的。虽然这种情况对题目本身不是什么大问题，但是通常你需要写出不会出错的程序。一种方法时不断读取，直到用户输入了一个正整数：

Ask user to input a positive number;
Let N be the user's response;
while N is not positive:
   Print an error message;
   Read another value for N;
Let counter = 0;
while N is not 1:
    if N is even:
       Compute N = N/2;
    else
       Compute N = 3 * N + 1;
    Output N;
    Add 1 to counter;
Output the counter;

读取一个用户输入一个正整数；

用户输入存入N；

while N 不是正整数

    输出错误信息;

    读取下一个输入值，存入N；

counter置为0；

当 N 不等于 1

   if N 是 偶数

      N = N/2;

   else

      N = 3*N+1;

   输出N；

   counter值加1；

输出counter值;

根据要求，第一个循环只有当N为正整数时才会结束。（初学者常见的一个错误，在这里使用 if 语句而不是 while 语句：“如果N是正整数，请求用户输入另一个值。”如果用户第二个输入还是非正整数，这里就会出现问题。if 语句只会执行一次，因此不会检测第二个输入，程序还是会进入无限循环。使用 while 循环时，在输入第二个数值后，计算机会跳转到循环开始的地方检查第二个输入值是否是正整数。如果不是，它会要求用户输入第三个数，直到输入的数值合法为止。当循环结束以后，我们可以完全肯定N就是一个正整数。）

下面是这个算法对应的Java实现。它使用 <= 操作符表示“小于或等于”和 != 表示“不等于。”用“N % 2 == 0”测试N是否是偶数。所有用到的操作符都在2.5节讨论过。

/** 
 * This program prints out a 3N+1 sequence starting from a positive
 * integer specified by the user.  It also counts the number of
 * terms in the sequence, and prints out that number.
 * 这个程序根据用户指定的正整数打印出一个3N+1序列。
 * 同时，还会输出序列的个数。
 */
 public class ThreeN1 {
 
      public static void main(String[] args) {               
 
         int N;       // for computing terms in the sequence 计算序列的初始值
         int counter; // for counting the terms 计数器
 
         System.out.print("Starting point for sequence: ");
         N = TextIO.getlnInt();
         while (N <= 0) {
            System.out.print(
                   "The starting point must be positive. Please try again: " );
            N = TextIO.getlnInt();
         }
         // At this point, we know that N > 0
         // 这里我们可以确认 N > 0
 
         counter = 0;
         while (N != 1) {
             if (N % 2 == 0)
                N = N / 2;
             else
                N = 3 * N + 1;
             System.out.println(N);
             counter = counter + 1;
         }
 
         System.out.println();
         System.out.print("There were ");
         System.out.print(counter);
         System.out.println(" terms in the sequence.");
 
     }  // end of main()
 
 }  // end of class ThreeN1

关于这个程序最后的注意事项：首先，你可能已经注意到序列的初始值——用户输入的N，并没有被程序输出。这时一个错误吗？很难确定。程序的需求是否详细地说明了这一点？这一类问题可能会让你回去找老板或教授澄清。（如果这是问题）这个问题可以很容易修复。只要将 while 前面的“counter = 0”这行改为：

System.out.println(N);   // print out initial term 输出初始值
counter = 1;       // and count it 计数器变为1

其次，还有一个问题，为什么这个程序会变得有趣？恩，之所以对数学家和计算机科学家变得有趣是因为，有一个他们都无法回答的简单问题：计算3N+1序列的过程对所有的起始值N都能在有限步以内完成？尽管单个序列计算起来很容易，但是没有人能给出所有正整数计算的结果。换句话说，没有人能知道计算3N+1序列的过程可以称为算法，因为算法的定义要求在有限步内计算完成！（注意：这里的讨论值针对整数integer，而非int类型！也就是说，假定N可以接受任意大的整数值，而非Java程序中的int类型变量。当整数大到无法用32位 int表示时，程序计算的结果在数学上就是错误的。所以，当N很大时，Java程序无法给出3N+1正确的计算结果。参见练习8.2）

3.2.3  编码、测试、调试

如果完成了算法、点击按钮就可以得到一个可以运行的程序，这是再好不过了。不幸的是，将算法转换为Java源代码的过程不会如此顺利。当你想要写出一个可工作的程序时，通常意味着程序会运行，但是结果可能不是你想要的。

从设计转入编码阶段：即把设计翻译为一个用Java或其他语言写成的程序。通常，无论你多么仔细，总会有一些语法错误混进某个地方。而Java编译器会报告一些错误信息。不幸的是，编译器通常只是检测语法错误，但是不会友好地告诉你确切的错误。有时候，对于出错的地方也不能很好地报告。在45行少写了一个花括号“{”可能会导致编译器卡在105行。要避免很多错误，你需要理解编程语言的语法规则并遵循一些基本的编程指南。例如，我从来不会只输入一个“{”却不写匹配的右括号“}”。写完这对括号，我才会返回去在括号之间添加语句。在大型程序中，多写或少写一个括号可能是最难发现的错误之一了。请一直确保将你的程序进行对齐。如果修改程序，需要相应地调整对齐。虽然麻烦但却非常值得。还有，要采用一致的命名规则，这样就不用去记变量名究竟是interstrate还是interestRate。通常，当编译器给出多个错误信息时，在改正第一个错误前不需要去看第二个错误。当编译器处理程序遇到错误时会被迷惑，因此后面报告的错误信息可能只是猜测。最佳的建议可能是：动手修复前，花时间去理解错误。编程不是一门试验科学。

当你的程序编译通过后，还没有完成。你需要测试程序确保可以正确工作。请记住，我们的目标不是像课堂上那样，为两个示例输入得到正确的结果。而是为所有合理的输入给出正确的结果。理想情况下，如果收到了一个非法输入，程序应当友善地提醒用户而不是直接崩溃。用更大范围的输入测试你的程序。试着找出一组能够测试程序所有功能的输入集合。当你开始编写更大的程序时，分阶段编写并且一直测试。你甚至可能需要编写代码来做测试——比如调用一个刚刚编写的子函数。如果可以避免，你肯定不希望看到刚写的500行代码报告某个地方出现了错误。

测试的目标就是发现bug——语义错误会表现为错误的行为，而不是编译错误。可悲的现实是，你将会在程序中发现这些错误。再一次地，你会小心设计、自己编程来减少bug，但是没有人找到可以完全避免bug的方法。一旦你发现了bug，就应该调试了。你需要在源代码中跟踪bug的源头并消除它。调试和编程的其它方面一样，需要练习来掌握。所以，不要害怕bug，要从解决bug中成长。调试的一个基本能力是代码阅读能力——排除各种先入为主的想象，按照计算机执行的方式，机械地、一步一步去查看究竟做了什么。这是非常困难的。我还清楚地记得，曾经花了很多时间查找一个bug，最后发现我读了10次的一行代码将“i”写成了“1”。还有我曾经写了一个WindowClosing子函数用来关闭窗口，结果计算机要调用的是windowClosing（开头字母是小写“w”）。有时候，找一个对你代码不了解的人会有助于找到问题。

通常，调试就是要定位出现问题的那个部分。大多数编程环境都带有一个调试器，它是一个能够帮助你找bug的程序。一般情况下，程序能够在调试器的控制下执行。你可以在调试器中为程序设置“断点”。当调试器执行到“断点”时会暂停程序，这样你可以查看程序的变量值。目标就是追踪程序执行过程中开始出错的地方。调试器会让你一次执行一条语句，这样就可以看到bug潜伏地点程序执行的细节。

我只是偶尔使用调试器，更常见的调试方法是在程序中插入调试语句，可以用输出语句打印出程序状态。典型的调试语句像下面这样：

System.out.println("At start of while loop, N = " + N);

你需要从输出信息中了解这个调试信息位于代码的什么地方，还有一些重要变量的值。有时候，你甚至会发现计算机不会执行到你认为应当执行的地方。请牢记调试目标，找到程序状态第一次与预期不符的地方。这就是bug所在的位置。

最后，请谨记调试黄金法则：如果你完全确信程序是正确的，但是仍然不能运行，那么一定是你的自信错了。

如有问题请加微信号：Iotek666，本微信号会不定期推送技术相关优质文章、热点资讯、视频资源及生活趣事，也很乐意与您一起交流IT知识，让我们在闲暇之余巩固一下自己的知识体系 ，扩充一下自己的知识面。快利用琐碎时间给自己充电吧！

希望这篇文章可以帮助到你，总之同学们，IT资讯尽在职坐标。