程序设计基础

1程序与程序设计

1.1 程序设计的一般步骤

1. 分析问题、确定需求：明确输入是什么、要输出什么、有哪些约束。
2. 设计算法：规划解题的方法和步骤（先想清楚再写代码！）。
3. 编写代码（编码）：用程序设计语言把算法表达出来。
4. 调试程序：发现并修正语法错误和逻辑错误，让程序跑通。
5. 测试与维护：用多组数据验证正确性与边界情况，后续按需修改完善。

1.2 著名的程序公式

瑞士计算机科学家沃斯（Niklaus Wirth）提出：

程序 = 数据结构 + 算法

数据结构描述数据如何组织，算法描述对数据如何操作，二者构成程序的核心。这也解释了为什么本课程后续要专门学习数据结构。

2算法基础

2.1 算法的五个基本特性

• 有穷性：必须在执行有限步骤之后结束，且每步都在有限时间内完成。
• 确定性：每条指令含义明确，不能有二义性；相同输入必有相同结果。
• 可行性（有效性）：每一个操作都可以由已经实现的基本运算执行有限次实现。
• 输入：有零个或多个输入（零输入时算法内部自带初始数据）。
• 输出：有一个或多个输出——没有输出的算法毫无意义。

2.2 算法的描述方法

以"求两个数的最大值"为例的伪代码：

算法 Max(a, b)
输入: 两个数 a, b
输出: 较大者
    if a > b then
        return a
    else
        return b

2.3 算法的评价

• 正确性：对合法输入能得到正确结果（最基本要求）。
• 可读性：易于理解，便于交流和维护。
• 健壮性（鲁棒性）：输入非法数据时能妥善处理而不崩溃。
• 高效率与低存储：运行时间短、占用内存少，用时间复杂度与空间复杂度量化。

时间复杂度表示算法运行时间随问题规模 n 的增长趋势，用大 O 记号表示，常见量级（从优到劣）： O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。 例如单层循环是 O(n)，两层嵌套循环通常是 O(n²)。

3程序的三种基本控制结构

1966 年 Bohm 和 Jacopini 证明：任何复杂的程序都可以由顺序、选择、循环三种基本结构组合嵌套而成。 它们都只有一个入口和一个出口，是结构化程序设计的基石。

3.1 顺序结构

最基本的结构：语句按书写顺序自上而下依次执行，每条语句只执行一次。

// 计算矩形面积
length = 5;          // 第 1 步：输入长
width  = 3;          // 第 2 步：输入宽
area = length * width; // 第 3 步：计算
print(area);         // 第 4 步：输出 15

3.2 选择结构（分支结构）

根据条件判断的真假选择执行不同语句。分为单分支、双分支和多分支：

if (score >= 60) {
    print("及格");
} else if (score >= 0) {
    print("不及格");
} else {
    print("成绩无效");
}

多分支还可用 switch / case 语句处理一个表达式取多个离散值的情况。注意条件判断中的相等比较是 ==（C/Java）或 =（Python），不要与赋值号混淆。

3.3 循环结构（重复结构）

在条件满足时反复执行某段语句（循环体），常见两种形式：

• 当型循环 while：先判断条件，真则执行循环体（可能一次也不执行）。
• 直到型循环 do-while：先执行循环体再判断（至少执行一次）。
• for 循环：适合循环次数已知的场景，把初始化、条件、增量写在一起。

// 求 1+2+...+100，结果应为 5050
sum = 0;
for (i = 1; i <= 100; i++) {
    sum = sum + i;
}
print(sum);

4数据类型、常量与变量

4.1 数据的表示

计算机内部所有数据都以二进制存储。数值型数据有原码、反码、补码等表示（计算机中有符号整数普遍采用补码，可化减法为加法）； 字符则通过编码标准映射为数字：

• ASCII 码：美国标准信息交换码，用 7 位表示 128 个英文字符；数字 '0' 是 48，大写 'A' 是 65，小写 'a' 是 97。
• 汉字编码：GB2312、GBK、GB18030；Unicode 致力于收录全球所有文字，UTF-8 是其最常用的变长编码实现。

4.2 基本数据类型

此外还有构造类型：数组、字符串、结构体/记录、枚举，以及指针、列表、字典等语言扩展类型。

4.3 常量与变量

• 常量：程序运行期间值不能改变，如圆周率 π、整数 100；用 const 修饰或全大写命名。
• 变量：内存中一块命名的存储单元，其值可以改变；变量具有名字、类型和值三要素，使用前通常要"先定义后使用"。

const PI = 3.14159;      // 常量
int age = 18;           // 整型变量
age = age + 1;            // 变量的值可以修改 → 19

5运算符与表达式

运算符规定对数据进行的操作，操作数通过运算符连接成表达式，表达式按优先级和结合性计算。

优先级大致顺序：括号最优先 → 算术（先乘除后加减）→ 关系 → 逻辑（与高于或）→ 赋值。 实际编程中建议用括号显式表达意图，避免死记优先级。

if ( (x > 0) && (x < 100) ) {
    print("x 是 1~99 之间的数");
}

6函数与模块化程序设计

// 定义：求两数之和
function add(a, b) {
    return a + b;
}
// 调用
result = add(3, 5);   // → 8

6.1 为什么需要函数

• 消除重复：同一段逻辑写一次、调用多次（DRY 原则：Don't Repeat Yourself）。
• 分解复杂问题：大程序拆成一个个高内聚、低耦合的小函数，便于分工与理解。
• 复用与共享：函数可放入库中供多个程序使用（如数学函数 sqrt()、print()）。
• 信息隐藏：调用者只需知道"传什么、返回什么"，不必关心内部实现。

6.2 参数传递与作用域

• 形参与实参：定义时括号中的是形式参数，调用时实际传入的是实际参数。
• 局部变量：函数内部定义，只在函数内有效；全局变量：函数外定义，整个文件可用。应尽量少用全局变量以减少相互影响。
• 递归：函数在定义中直接或间接调用自身。递归必须有明确的终止条件（出口）并不断向出口逼近，如阶乘 n! = n × (n-1)!。

6.3 结构化程序设计思想

20 世纪 60 年代为解决"软件危机"，Dijkstra 等人提出结构化程序设计：自顶向下、逐步求精、模块化， 只用三种基本结构、限制滥用 goto 语句，使程序层次清晰、易读易验证。

7面向对象程序设计

随着软件规模增大，面向对象程序设计（OOP）成为主流范式。它把现实世界中的事物抽象为对象， 用"对象 + 消息"来组织程序，比面向过程更贴近人的思维方式。代表语言有 C++、Java、C#、Python 等。

7.1 类与对象

• 类（Class）：对一类事物共同特征的抽象模板，包含属性（数据，描述状态）和方法（函数，描述行为）。
• 对象（Object）：类的具体实例。类与对象的关系如同"图纸与房子""学生类与张三同学"。

class Dog {
    String name;                 // 属性
    void bark() {             // 方法
        print(name + ": 汪汪!");
    }
}
Dog d = new Dog();       // 由类创建对象（实例化）
d.name = "旺财";
d.bark();

7.2 面向对象的三大特性

8程序的翻译、执行与开发环境

8.1 从源代码到运行

高级语言源程序不能被 CPU 直接执行，必须经过翻译：

• 编译方式（C/C++）：源代码 → 编译 → 目标文件 → 链接库 → 可执行文件（.exe），运行快、与平台相关。
• 解释方式（Python/JS）：解释器读取源代码边翻译边执行，开发调试方便、跨平台，速度较慢。
• 虚拟机方式（Java/C#）：先编译成字节码，再由虚拟机 JVM/CLR 在目标平台上执行。

8.2 集成开发环境（IDE）

IDE 把编辑器、编译器/解释器、调试器、项目管理等集成在一起，大幅提高开发效率。常见有： Visual Studio、IntelliJ IDEA（Java）、PyCharm（Python）、Dev-C++/CLion（C/C++）、VS Code（轻量通用、靠插件扩展）。

8.3 程序错误的类型

8.4 调试方法

常用手段：设置断点 → 单步执行 → 监视变量/表达式 → 查看调用栈；也可在关键位置打印中间结果。 调试的本质是"观察程序实际执行路径与预期的偏差"，先复现、再缩小范围、最后定位根因。

9主流编程语言与选择