Java编程入门(3.2):代码块、循环和分支

3.2 算法开发


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

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

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


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所在的位置。

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


原文链接: math.hws.edu 翻译: ImportNew.com - 唐尤华
译文链接: http://www.importnew.com/17341.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 唐尤华

我喜欢程序员,他们单纯、固执、容易体会到成就感;面对压力,能够挑灯夜战不眠不休;面对困难,能够迎难而上挑战自我。他们也会感到困惑与傍徨,但每个程序员的心中都有一个比尔盖茨或是乔布斯的梦想“用智慧开创属于自己的事业”。我想说的是,其实我是一个程序员。(新浪微博:@唐尤华

查看唐尤华的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

1 条评论

  1. wqe 说道:

    啥时候更新下面的章节啊

    Thumb up 0 Thumb down 0

跳到底部
返回顶部