分类目录归档:CS106A

斯坦福大学公开课 CS106A – 编程方法学(Programming Methodology)学习笔记

CS106A 学习笔记(9):Assignment #2-1

cs106a-assignment-2-1

主要思路:

  • 从下往上,最底层(第0行),有14块砖;第1行,有13块砖;第2行,有12块砖…
  • 以此类推,每一行的砖块数量等于底层数(14)减去行数
  • 获取砖块放置的坐标:
    • 横坐标:窗口宽度/2 – 每行砖块总宽度/2 + 相应砖块的数量的宽度
    • 纵坐标:窗口高度 – 相应行数砖块的高度

参考代码:

/*
 * File:    Pyramid.java
 * -------------------------
 * Draws a pyramid consisting of bricks arranged in horizontal rows.
 */

import acm.program.*;
import acm.graphics.*;

public class Pyramid extends GraphicsProgram {

    private static final int BRICK_WIDTH = 30; // brick 宽度:30px
    private static final int BRICK_HEIGHT = 12; // brick 高度:12px
    private static final int BRICK_IN_BASE =14; // 底层 brick 数量:14

    public void run() {

        /*
         * 从下往上,第0行,14个 bricks;第1行,13个 bricks;第2行,12个 bricks;
         * 所以,每一行的 bricks 数量为 BRICK_IN_BASE - 行数;
         * 总共 14 行;
         */

        // 主循环,定义行数
        for (int row = 0; row < BRICK_IN_BASE; row++) {
            int bricksInRow = BRICK_IN_BASE - row; // 每一行brick的数量等于底层数量减去行数

            // 定位每行中bricks的位置
            for (int brickNum = 0; brickNum < bricksInRow; brickNum++) {

                // brick 横坐标
                int x = getWidth() / 2 - ( BRICK_WIDTH * bricksInRow ) /2 + brickNum * BRICK_WIDTH;
                // brick 纵坐标
                int y = getHeight() - BRICK_HEIGHT * ( row + 1 );
                // 添加bricks
                GRect brick = new GRect ( x, y, BRICK_WIDTH, BRICK_HEIGHT );
                add(brick);
            }
        }
    }

}

CS106A 学习笔记(9):阶乘

第七课视频中讲的阶乘的例子:

/*
 * File:    Factorial.java
 * -----------------------------
 */

import acm.program.*;

public class Factorial extends ConsoleProgram {

    private static final int MAX_NUM = 10;

    public void run() {

        for (int i = 0; i < MAX_NUM; i++) {
            println(i + "! = " + factorial(i));
        }

    }

    private int factorial(int n) {
        int resault = 1;
        for (int i = 1; i <= n; i++) {
            resault *= i;
        }

        return resault;
    }

}

CS106A 学习笔记(8):方法

方法(Methods)

Java 方法是语句的集合,它们在一起执行一个功能。

  • 方法是解决一类问题的步骤的有序组合
  • 方法包含于类或对象中
  • 方法在程序中被创建,在其他地方被引用

方法调用

reveiver name (arguments)

创建方法

visibility type name (parameters) {
    ...
    body
    ...
}
  • visibility:private 或者 public
  • type:返回值的类型。void 为特殊类型,意为不返回任何值
  • name:方法的名字
  • parameter:方法的参数。多个参数使用逗号(,)隔开,参数类型与参数名之间空格。

define-a-method

CS106A 学习笔记(7):运算符、常量及语句

运算符

Java 运算:

  • 加(+)
  • 减(-)
  • 乘(*)
  • 除(/)
  • 取余(%)

加(+)、减(-)、乘(*)这三种运算符使用起来和数学的一般用法基本相同。

在Java中,如果两个运算数都是整数,那么除法运算符的运算结果也是整数,并且会省略一切小数点后的值(或者说是两个整数相除得到的商)。而取余运算符(%),则对应的是两个整数相除得到的余数。

运算符的简写

Long Form Shorthand Form
x = x + 1 x++
x = x – 1 x——
x = x + y x + = y
x = x – y x – = y
x = x * y x * = y
x = x / y x / = y

常量(Constant)

虽然常量名也可以用小写,但为了便于识别,通常使用大写字母表示常量。

常量声明方式:

private static final type NAME = value;

布尔变量(Boolean)

Boolean expression is just a test for a condition.

true被显示为”true”,false被显示为”false”

比较运算符

  • ==:等于
  • !=:不等于
  • >:大于
  • <:小于
  • >=:大于等于
  • <=:小于等于

逻辑运算符

  • !:非
  • &&:与
  • ||:或

阅读全文

CS106A 学习笔记(6):变量

变量(variable)

在程序设计中,变量是一种存储数据的载体。计算机中的变量是实际存在的数据,与数学方程中抽象的“变量”存在本质区别。变量的数值可以被读取和修改,是所有计算的基础。

变量一般具有三个要素:

  • 名称: name
  • 数据类型: type
  • 值: value

Java 中变量的命名规范:

  • 必须以字母、下划线或美元符号开头
  • 只能出现字母、下划线、数字和美元符号,不得出现任何其他符号或空格
  • 不能使用保留字作为名字
  • 在同一使用范围内,所有变量、函数、类、对象等的名称不得重复

数据类型

数据类型是程序设计语言描述事物、对象的方法。

Java数据类型分为内置类型扩展类型两大类。

内置类型就是Java语言本身提供的基本数据类型,比如,整型数,浮点数,字符,布尔值等等。而扩展类型则是Java语言根据基本类型扩展出的其他类型,Java要求所有的扩展类型都必须包括在类定义里面,这就是Java为什么是面向对象编程语言的原因。

常用的内置类型:

  • int:整数
  • double:双精度浮点数
  • boolean:布尔值
  • char(car):字符值

变量声明语法:

type name = value;

GObject 类

  • GLabel
  • GRect
  • GOval
  • Gline

GObject 类可进行的运算:

  • 设置对象颜色

    object.setColor(color)
    

java.awt.* 中定义了标准的颜色名称:

Color.BLACK
Color.RED
Color.BLUE
Color.DARK_GRAY
Color.YELLOW
Color.MAGENTA
Color.GRAY
Color.GREEN
Color.ORANGE
Color.LIGHT_GRAY
Color.CYAN
Color.PINK
Color.WHITE
  • 设置对象位置

    object.setLocation(x, y)
    
  • 移动对象

    object.move(dx, dy)
    

GLabel 类可进行的运算:

  • 在(x, y)点创建一个新的标签(Label)

    new GLabel (text, x, y)
    
  • 设置Label中文字的字体

    label.setFont(font)
    

    字体参数的格式:

    family-style-size
    

绘制图形对象

  • 在(x, y)点创建一个指定长和宽的矩形

    new GRect (x, y, width, height)
    
  • 在(x, y)点创建一个指定长和宽的椭圆形

    new GOval (x, y, width, height)
    
  • 画一条从点(x1, y1)到点(x2, y2)的直线

    new GLine (x1, y1, x2, y2)
    
  • 如果 filltrue 则填充对象,false 则只显示轮廓

    object.setFilled(fill)
    
  • 设置对象填充颜色

    object.setFillColor(color)
    

获取图象窗口大小

// Returns the width of the graphics window
getWidth()

//Returns the height of the graphics window
getHeight()

上述两个命令只能在 GraphicsProgram 中调用。

CS106A 学习笔记(5):Hello, Java!

程序编译

将用某种编程语言写成的源代码(Source Code),转换成另一种编程语言——目标语言(Object Code)。

编译的主要目的是将便于人编写、阅读、维护的高级编程语言写作的源代码程序,翻译为计算机能够解读、运行的低阶机器语言的程序,也就是可执行文件。

源代码一般为高阶语言(High-level language),如C、C++、C# 、Java等,而目标语言则是汇编语言或目标机器的目标代码(Object code),有时也称作机器代码(Machine code)。

一个现代编译器的主要工作流程如下: 源代码(source code)→ 预处理器(preprocessor)→ 编译器(compiler)→ 汇编程序(assembler)→ 目标代码(object code)→ 链接器(Linker)→ 可执行文件(executables)

Java 通过虚拟机(Java Virtual Machine,JVM)进行编译。源代码通过编译器翻译成class文件,即中间语言,中间语言通过虚拟机(JVM)编译为计算机能够理解的目标语言。

javavirtualmachine

Java 特性:

  • 跨平台
  • 面向对象
  • 泛型编程

面向对象的程序设计(Object-oriented programming,OOP)

对象指的是类的实例。它将对象作为程序的基本单元,将程序和数据封装其中,以提高软件的重用性、灵活性和扩展性。

类(Class)定义了一件事物的抽象特点。通常来说,类定义了事物的属性和它可以做到的(它的行为)。一个类的方法和属性被称为“成员”。

对象(Object)是类的实例。一个具体对象属性的值被称作它的“状态”。

类是抽象的,对象是具体的。

ACM Program Hierarchy

ProgramHierarchy

第一个Java程序

/*
 * File:    HelloJava.java
 * -----------------------------
 * This is my first Java program.
 * It displays 'Hello, Java!' on the screen.
 */

import acm.graphics.*;
import acm.program.*;

public class HelloJava extends GraphicsProgram {
    public void run() {
        add( new GLabel( "Hello, Java!", 100, 75 ) );
    }
}

阅读全文

CS106A 学习笔记(4):课堂练习

Problem 1:Doubling the number of beepers

doubling-the-number-of-beepers

使 Karel 前面的 Beepers 数量加倍,然后回到起始位置、方向。

动作分解

DoubleBeepers

祥细代码

/*
 * File:    DoubleBeepers.java
 * -------------------------------
 * Karel doubles the number of beepers on the corner directly in front of him in the world.
 * He then returns to his original position/orientation.
 */

import stanford.karel.*;

public class DoubleBeepers extends SuperKarel {

    public void run() {
        move();
        doubleTheBeepers();
        moveBackward();
    }

    /*
     * For every beeper on the current corner, karel puts two beepers on the corner ahead of him.
     */
    private void doubleTheBeepers() {
        while (beepersPresent()) {
            pickBeeper();
            putTwoBeepersNextDoor();
        }
        moveAllBeepersBack();
    }

    /*
     * Put two beepers on the corner in 3rd avenue, and then move back to the starting position/orientation.
     */
    private void putTwoBeepersNextDoor() {
        move();
        for (int i=0; i<2; i++) {
            putBeeper();
        }
        moveBackward();
    }

    /*
     * Move all the beepers on the corner in front of Karel to the corner Karel is currently on.
     */
    private void moveAllBeepersBack() {
        move();
        while (beepersPresent()) {
            moveOneBeeperBack();
        }
        moveBackward();
    }

    /*
     * Move one beeper from the current corner back 1st avenue and return to the original position/orientation.
     */
    private void moveOneBeeperBack() {
        pickBeeper();
        moveBackward();
        putBeeper();
        move();
    }

    /*
     * Karel move back to the 1st avenue, and has the same final orientation. 
     */
    private void moveBackward() {
        turnAround();
        move();
        turnAround();
    }
}

阅读全文

CS106A 学习笔记(3):Karel & Java

常见错误(common errors)

  • 无限循环(infinite loop)
  • 差一错误(OBOB:Off By One Bug):还差一件需要做的事情,尽管按逻辑来讲不需要做

注释(comment)

块注释:

/*
 * the block comment
 */

行注释

// the one-liner comment

逐步求解法(stepwise refinement)

从最高阶向下逐步分解,直到分解成计算机能够理解的语言。

  • 自顶向下设计:Top-Down Design
  • 自底向上设计:Bottom-Up Design

算法(algorithm)

算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

以下是Donald Knuth在他的著作The Art of Computer Programming里对算法的特征归纳:

  • 输入:一个算法必须有零个或以上输入量。
  • 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
  • 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际运行结果是确定的。
  • 有限性:依据图灵的定义,一个算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
  • 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

函数名书写规范

驼峰式写法(camel case):全部首字母大写或者除第一个单词外首字母大写

函数分解原则

  • 每个程序/方法解决一个问题
  • 每个方法(method)最好在1-15行之间
  • 定义一个“好”的名字(Good name):名字可以是函数的用途,或是解决了什么问题

虽然程序是由计算机运行的,但归根结底是写给人看的。

CS106A 学习笔记:Assignment (1)

Problem 1

CollectNewspaperKarel

  1. Move to the newspaper,
  2. Pick it up, and
  3. Return to its starting point.
  4. include a private method for each of the steps shown in the outline.

思路

问题1比较简单,练习各种指令的使用。代码如下:

import stanford.karel.*;

public class CollectNewspaperKarel extends SuperKarel {

    public void run() {
        moveToWall();
        turnLeft();//facing east
        move();
        pickBeeper();
        turnAround();//facing west
        moveToWall();
        turnRight();// facing east
    }

    /*
     * Pre-condition:   none
     * Postcondition:   move to first wall in whichever direction
     * then turn right and move one step
     */
    private void moveToWall() {
        while (frontIsClear()) {
            move();
        }
        turnRight();
        move();
    }

}

Problem 2:

StoneMasonKarel

  • Karel starts at 1st Avenue and 1st Street, facing east, with an infinite number of beepers.
  • The columns are exactly four units apart, on 1st, 5th, 9th Avenue, and so forth.
  • The end of the columns is marked by a wall immediately after the final column. This wall section appears after 13th Avenue in the example, but your program should work for any number of columns.
  • The top of the column is marked by a wall, but Karel cannot assume that columns are always five units high, or even that all columns are the same height.
  • Some of the corners in the column may already contain beepers representing stones that are still in place. Your program should not put a second beeper on these corners.

思路

类似于障碍跑那个例子,修复一行完成行原路返回,如此循环即可。代码如下:

阅读全文

CS106A学习笔记:Karel

Karel 指令

move

turnLeft

pickBeeper

putBeeper

第一个小程序

MyFirstKarel

import stanford.karel.*;

public class MyFirstKarel extends Karel {
    public void run() {
        move();
        pickBeeper();
        move();
        turnLeft();
        move();
        turnLeft();
        turnLeft();
        turnLeft();
        move();
        putBeeper();
        move();
    }
}

添加右转(turnRight)指令:

import stanford.karel.*;

public class MyFirstKarel extends Karel {
    public void run() {
        move();
        pickBeeper();
        move();
        turnLeft();
        move();
        turnRight();
        move();
        putBeeper();
        move();
    }

    // Define turnRight
    private void turnRight() {
        turnLeft();
        turnLeft();
        turnLeft();
    }

}

For 循环

基本语法:

for (int i = 0; i < N; i++) {
    // statements to be repeated
}

利用 For 循环定义 turnRight 指令:

private void turnRight() {
    for (int i=0; i<3; i++) {
        turnLeft();
    }
}

While 循环

基本语法:

while ( true ) {
    // the body of the while-loop
}

用法举例:

private void walkToWall() {
    while ( frontIsClear() )
    move();
}

If 条件语句

基本语法:

if ( // condition ) {
    // the body
}

用法举例:

if ( beeperPresent() ) {
    pickBeeper();
}

if-else 语句

基本语法:

if ( // condition ) {
    // the body
} else {
    // the body
}

用法举例:

if ( beeperPresent() ) {
    pickBeeper();
} else {
    putBeeper();
}

if 语句嵌套用法举例:

if (beeperPresent()) {
    if (frontIsClear()) {
        move();
    }
} else {
    putBeeper();
}

Karel 条件汇总

Test Opposite
frontIsClear() frontIsBlocked()
leftIsClear() leftIsBlocked()
rightIsClear() rightIsBlocked()
beepersPresent() noBeepersPresent()
beepersInBag() noBeepersInBag()
facingNorth() notFacingNorth()
facingSouth() notFacingSouth()
facingEast() notFacingEast()
facingWest() notFacingWest()

综合练习:Karel 障碍跑

SteepleChase

import stanford.karel.*;
public class SteepleChase extends SuperKarel {
    public void run() {
        for (int i=0; i<8; i++) {
            if (frontIsClear()) {
                move();
            } else {
                jumpHurdle();
            }
        }
    }

    private void jumpHurdle() {
        ascendHurdle();
        move();
        descendHurdle();
    }

    private void ascendHurdle() {
        turnLeft();
        while (rightIsBlocked()) {
            move();
        }
        turnRight();
    }

    private void descendHurdle() {
        turnRight();
        while (frontIsClear()) {
            move();
        }
        turnLeft();
    }

}