高中数学拓展

补充章节 — 素数和模算术 — 逻辑

矩阵 — 进一步模算术 — 数学编程 — 马尔可夫链

在我们开始之前

本章不会尝试严格地教你如何编程。因此，强烈建议您具备 C 语言的基本工作知识。建议您在学习本章内容之前尽可能多地了解 C 语言。

如果您不熟悉编程或 C 语言，请阅读 About.com 上的 "C 语言教程" 的前 7 课。

随着您获得编程经验，您会更欣赏更具体的解释，例如 C 语言维基教科书。

编程简介

编程有很多用途。编程和计算机科学在人工智能和统计学等领域非常重要。编程允许您灵活地使用计算机，并非常快地处理数据。

编写程序时，程序被写入人类可以理解的文本形式。但是，计算机不直接理解人类写的程序。它需要被转换成计算机可以理解的方式。

例如，计算机就像一个阅读和说德语的人。你用英语写和说。您写给计算机的信件需要被翻译，以便计算机能理解。负责这项工作的程序被称为编译器。

你需要编译你的类似英语的指令，以便计算机能理解。一旦程序被编译，它就很难“反编译”，或者将其转换回英语。程序员编写程序（用我们的比喻，用英语），称为源代码，它是程序的人类可读定义，然后编译器将其翻译成“机器代码”。我们建议使用广泛可用的 gcc 编译器。

当我们在这里研究数学编程时，我们将看看如何编写程序来解决一些困难的数学问题，这些问题通常需要花费我们很多时间才能解决。例如，如果我们要找到多项式x⁵+x+1 的根的近似值 - 这对人类来说非常难。但计算机可以轻松解决这个问题 - 如何？

编程语言基础

在本章中，我们将使用 C 语言，请通过阅读 About.com 上的 "C 语言教程" 的前 7 课来了解 C 的基础知识。

C语言示例程序

C语言示例程序

数据类型

大小限制：头文件 limits.h 和 float.h

计算机是基于布尔逻辑的机器。这意味着计算机基于某种区分状态为真或假，或设置和未设置的方法。抽象地说，我们认为计算机使用 1 代表真或设置，使用 0 代表假或未设置。我们将这些 1 和 0 称为位。在计算机中，我们不将信息作为位来跟踪。相反，计算机中的信息存储在称为字节的可寻址块中。字节是计算机中可以访问的最小内存片段，它不是位。当我们在 C 程序中声明一个 [标量] 变量时，该内存具有一个地址和一个长度。地址表示内存从哪里开始，长度表示表示变量使用多少个字节。

包含文件 <limits.h> 用于定义可寻址整数类型的尺寸，包含文件 <float.h> 用于定义可寻址浮点类型的尺寸。这些文件中的值依赖于编译器和计算机。这意味着如果您更改编译器或在不同类型的计算机上编译程序，它可能会以不同的方式执行。

以下是在这两个文件中定义的一些值

练习

用整数编程

离散编程处理整数以及如何在计算机中操作它们。

整数运算

理解整数除法

在 C 中，命令

int number;

number = 3 / 2;

将在计算机内存中预留一些空间，我们可以通过变量名称number来引用该空间。在计算机看来，number是一个整数，仅此而已。之后

number = 3 / 2;

numbers 等于 1，而不是 1.5，这是因为当/应用于两个整数时，只会给出结果的整数部分。例如在 C 中

5 / 2 等于 2

353 / 3 等于 117

-5 / 2 等于 -2

353 / -3 等于 -117

-5 / - 2 等于 2

如果您正在测试的数字介于 1 和 -1 之间 - 例如 2 / 5 或 -2 / 5，则结果未定义，尽管大多数编译器返回 0。

模运算符, %，返回整数除法产生的余数。例如在 C 中

5 % 2 等于 2

353 % 3 等于 2

-5 % 2 等于 -2

353 % - 3 等于 2

-5 % -2 等于 -1

结果的符号与您预期的被除数的符号相同。对于介于 1 和 -1 之间的分数，结果与分子相同。

练习

练习 1

写下您对探索除法和模运算的程序应该做什么的想法。

需要进行哪些处理？
您有哪些类型的输入？
您的输出是什么样的？

以下示例将引导您完成此练习。

C 程序示例，用于练习 1

探索整数除法和整数模运算的程序

递归定义函数的建模

阶乘函数 n! 递归定义为

0! = 1

n! = n×(n-1)! if n ≥ 1

在 C 中，如果 fact(n) 是如上所述的函数，我们希望

fact(0)=1;

fact(n)=n*fact(n-1)

; if

n\geq 1

我们应该注意到所有递归定义的函数都有一个终止条件，在这种情况下，函数可以直接给出答案，例如 fact(0) = 1。

我们可以使用以下代码轻松地对阶乘函数进行建模，然后执行它

int fact (int n)

{

if (n == 0)

return 1;

if (n >= 1)

return n * fact(n - 1);

}

上面的 C 函数非常自然地对阶乘函数进行了建模。为了测试结果，我们可以编译以下代码

#include <stdio.h> /* 标准输入输出头文件 */

int fact (int n)

{

if (n == 0)

return 1;

if (n >= 1)

return n * fact(n - 1);

}

int main(void)

{

int n = 5;

printf("%d", fact(n)); /* printf 在 stdio.h 中定义 */

}

我们也可以对斐波那契数函数进行建模。设 fib(n) 返回第 (n + 1) 个斐波那契数，以下内容应该清楚

fib(0) 应该返回 1

fib(1) 应该返回 1

fib(n) 应该返回 fib(n - 1) + fib(n - 2); 对于 n ≥ 2

我们可以使用 C 对上述内容进行建模

int fib (int n)

{

if (n == 0 || n == 1) /* 如果 n = 0 或如果 n = 1 */

return 1;

if (n >= 2)

return fib(n - 1) + fib(n - 2);

}

同样，您将看到对递归函数进行建模并不难，因为它只涉及将数学翻译成 C 代码。

对非递归函数进行建模

有一些函数只涉及整数，并且可以使用 C 中的函数很好地对它们进行建模。阶乘函数

f(n) = n! = n(n - 1)(n - 2) ... 3×2×1

可以使用以下代码简单地建模

int n = 10;  //get factorial for 10
int f = 1;   //start f at 1
while(n > 0) //keep looping if n bigger then 0
{
   f = n * f; //f is now product of f and n
   n = n - 1; //n is one less (repeat loop)
}

浮点编程

程序不仅可以使用整数值编写，还可以使用各种形式的浮点值编写。您通常应该使用double关键字来定义浮点数；这样做的原因是，在许多情况下，用浮点算术编写表达式的直观方法是次优的。浮点算术是非结合性的 - 在以 10 为基数的系统中，具有 2 位精度的系统具有 (1.0 + 0.02) + 0.04 = 1.0（向下舍入，因为 1.02 舍入为 1.0，然后 1.04 向下舍入为 1.0），但 1.0 + (0.02 + 0.04) = 1.0 + 0.06 = 1.1。还存在一个float类型，它使用 4 个字节而不是 8 个字节，但除非您知道自己在做什么，否则不应该使用它，因为只有 24 位精度，或者大约 9 个以 10 为基数的有效数字。

注意：如果您使用 2 个整数操作数，它仍然执行整数运算，因此它打印 1，而不是您预期的 1.5

double number;

number = 3/2;

printf("%f\n",number);

定义浮点数然后计算 3/2 的示例

double number = 3;

number /= 2;

printf("%f\n",number);

需要注意的是：浮点数不能完美地表示所有十进制数。显然，由于变量占用的内存是有限的，它不能表示无限数量，而只能表示它的近似值。此外，某些数字无法在浮点中完美表示。在这段代码中

double number;

number = 1/10;

number 的值不是 0.1，而是实际上是 0.10000000000000001。

这种限制的一个类比是 1/3 的值。在十进制系统中，此值不能用有限数量的 3 来精确表示，如 0.333... 由于 2 和 5 是 10（十进制系统的基数）的唯一质因数，因此只有分母包含 2 和 5 的乘积的分数，例如 5/8 $\left({\tfrac {5}{2^{3}}}\right)$ 或 231/250 $\left({\tfrac {231}{2\times 5^{3}}}\right)$ （但不是 1/3 或 5/14）可以通过十进制数（分别是 0.625 和 0.924）精确表示。

计算机使用以 2 为基数的算术，因此只有分母包含 2 的乘积（2 的幂）的分数，例如 5/8 $\left({\tfrac {5}{2^{3}}}\right)$ 或 231/256 $\left({\tfrac {231}{2^{8}}}\right)$ （但不是 231/250、1/3 或 1/10，如上所述）可以通过浮点数精确表示。

反馈

您怎么看？ 太容易还是太难？信息太多还是不够？我们怎样才能改进？请通过在讨论标签中发表评论来告知我们。更好的是，自己编辑它并使其更好。