为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
程序设计入门
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
程序并不只是一个计算机科学中专用的词汇，可以表示做任何一件事情的顺序和安排。例如，做一道菜的程序、打开电脑的程序、维基百科上进行投票选举的程序，等等。比如打开电脑的程序，传统的教育中的方法一般是先开显示器，再开主机，就是这么简单。但事实上并不一定是先打开显示器的。而如果有每次关机后断开电源的习惯，那么在这之前需要先接上电源。另外解一道数学题，或者写一篇文章，有时候都需要按一定的顺序来完成，这就是程序。
目录 |
[编辑] 基础知识
提示：这些内容仅介绍思想，并不详细介绍一种语言及其标准库函数的使用。这些内容可以参见编程语言、Basic、Pascal、C++。
如果你已经了解编程语言的基本思想、程序结构模型等内容，可以跳过相应的章节。
[编辑] 编程语言
程序本身是一个无形的东西，但是必须表达出来才能让别人或者电脑理解这是什么样的。现实中的程序，可以直接说出来，例如“先插电源，再按一下电源按钮”。这就是程序的具体表达。也可以用一些不同语言表达出来，比如还有“Plug in the power supply and press the power button”，但是表达的都是一个意思。我们把这些语言的内容理解了之后，会以另外一种形式储存在大脑中，做这些事的时候可以直接想这些内容而不是用中文或者英文怎么说，这也可以当成另外一种语言。
当然，目前电脑还不能完全理解这些人说的自然语言。所以就有了更容易让电脑理解的专用的语言，例如：
其中机器码通常就是电脑执行程序的时候实际用的语言。电脑本身并不能理解其它的语言，要让其他语言发挥作用还要有解释器或者编译器，可以在执行的时候向电脑解释其他的语言的内容的含义，或者把其他语言的内容一次性的编译成机器码。
当你开始学习一门语言的时候，你可能希望进行一些测试，写个程序让电脑输出Hello World。如果你能自己写出，并理解这个程序每一部分的意思，就说明你已经能基本理解程序的思想了。
注意写一个有用的软件或者库的时候，不要默认任何输入的参数是正确的、合法的。在输入有问题的时候可以不返回正确的结果，但是要小心不要造成对内存程序或者数据文件的破坏。比如产生溢出错误，极有可能成为黑客利用的漏洞。同理，在数据文件很重要的情况下也不能默认程序会以正常方式退出。
[编辑] 程序结构
程序也是可以是有选择性的执行的，比如，如果用的是笔记本电脑，而且自己在户外没有电源的地方，那么直接按电源按钮打开电源，否则按刚才说的，先插电源再按电源按钮。。换一种说法就是，（如果用的电脑没有电池，或者现在可以用交流电源，那么接上电源），然后按一下电源按钮。很多刚开始没有打算用来表示程序的比较低级的脚本语言中，这个功能往往是最先出现的。
另外还可以循环，比如如果你刚重装完Windows并且正在更新系统，你可能执行这样操作：重复：装更新，重启，直到没有新的更新的时候结束。这就是相对复杂一点的程序。
可能你也会想把这两个可以综合起来，比如，重复：（如果装的更新里面有侵犯用户权利的Windows正版验证程序，那么把这个去掉）；然后安装剩下的更新，重启系统，直到除此之外的更新全部装完。你可能会把一些别的事也加入到这里面，比如先开机，重新安装系统，或者更新完之后关机，去睡觉甚至开始安装系统，然后出去玩，回来之后完成系统的安装。这些都可以算是一个程序。
有的时候，一些简单的过程可以组合在一起作为一个整体。比如一般人说到开机，就会直接把这理解成先插电源再按开关或者更复杂的类似的内容。这时候如果有个更复杂的程序中要用到开机，只要说开机就可以了。另外比如用计算器算一下123432*5483291，直接就可以包括找出并打开计算器这一个动作。这类简单过程的集合可以叫做函数或者过程。函数可以有参数，比如123432*5483291。另外还可以有返回值，比如123432*5483291的结果676813574712。通过这类东西，我们可以不用把做一件事的整个过程的每一个详细的步骤都写出来，比如做数学题的时候也经常用“同理”这个词表示对相同过程的省略。函数和过程还可以包括其它的函数和过程，这样可以让过程的表达和记忆、储存更容易。另外如果要做的事的整个程序比较复杂，分成若干个名字很清楚的过程也会让人更容易理解。
有的比较原始的语言只提供“跳转”而不提供循环和函数的功能。这时候可以通过判断和跳转完成这些功能。而较高级的语言中往往不再鼓励使用跳转功能——这些都可以用上面说的更清晰的结构完成。而有一些抽象的程序设计语言也不直接提供循环等功能，这些可能要用更抽象的方法完成。
你可能希望看一下你所使用的编程语言（例如C、C++、Pascal）中这些有关程序结构的内容的写法。
[编辑] 程序优化
另外也可能有好多种方法可以实现同一个功能，例如把电源接在一个插座上，再把插座接到墙上，然后再按开关，或者向旁边的一个会按你说的做的人喊一句：给我接上电源开机。这些和最开始的开机方法的结果是一样的，不过有的时候可能有速度、麻烦程度等的区别。试想一个人在家想要远程连接工作单位的电脑，那比较快的方法当然是打电话或者用QQ/MSN之类的软件让同事来完成这项工作。但是要是这个人还想打开自己家的电脑，显然不能让那个同事跑来帮忙。
一般地说，程序先要考虑时间快慢的问题，参见时间复杂度，,另外程序运行所需要的空间也经常是需要考虑的问题之一。一个运行100h的程序或许比一个需要100G内存的程序更让人接受。
软件工程学是另外一个重要问题。比如程序的'可读性'可维护性也是个问题，例如Windows以前的很多错误提示就不告诉人应该具体怎么办，只是说“请查询帮助文档”或者“请联系系统管理员”之类的，虽然有可能的确是能解决问题的方法，用户很不容易知道到底应该怎么办。而对于自动运行的程序，如果出了点问题，可读性差的话别人也根本无法知道是在哪出错了。所以要写可读性强的程序，让人知道这到底是干什么，比如用适当的缩进、换行还有一些注释。当然对于一部分语言，缩进和换行也有编译器可以理解的特殊的意义，例如Python的缩进、Basic的换行，Whitespace中甚至只有这些空白字符有意义。
在实践中，可读性强，易于维护的程序要远比程序执行的速度与空间重要，Java,动态语言如Python的流行就是一个例子，面向对象或是LISP也会影响程序的效率，但他们都很流行，因为实践上，硬件的增速比软件快得多。当然，既快又好的程序更好。但应该明确，除非有特殊的需求，不要轻易牺牲程序的可读性,哪怕是在OI当中。往往清晰的，易于维护的程序并不一定很慢。dd_engi的coding就是一个很好的例子。所有的人都应该在适当的时候阅读Code Complete
一般除非是专门比不可读的程序的竞赛，程序都要有适当的缩进、空格以及注释。缩进和空格可以让人清楚的看出哪一部分程序是属于哪一部分的，而注释可以直接告诉自己(或是维护你程序的人)关于程序的信息，例如一个函数的使用方法、数据的存储格式、要达到某种目的需要使用的函数等等。记住，几个月之后，你很可能对你自己写出的代码不知所措。
[编辑] 标准库
一门编程语言通常会自带一些函数和过程的集合，通常叫做标准库（或是标准单元、标准模块等）。这些库一般给出了很多常用的功能所需要的函数，例如在文件中读入一个数字。不同于编程语法，很多时候标准库的内容是可以重新定义的。就像自然语言一样，自然语言中可以用牛表示一种反刍的哺乳动物，在特定的环境下，例如OIer人群中，也可以表示特别厉害的人，或是OI界特别厉害的人。而一般使用这种语言，能理解这种语言自带的“牛”的意思的人可能根本不知道OIer是什么。
很多时候标准库中的函数的效率是很高的，尤其解释执行语言（即使用解释器执行的语言）。但是也不一定，比如Pascal中的字符串匹配函数。这种情况下，应该在尽量理解函数的具体实现方法的情况下使用这些函数。通常标准库中速度比较快的函数都是可以尽量直接使用的。
这些就是一般的语言的基本思想，关于编程语言以及如何使用编程语言的更多的内容可以参见编程语言、Basic、Pascal、C++。
你可能需要了解一下标准库中关于数学计算、输入输出的内容以及常用类型、系统常量和变量等。
[编辑] 算法
算法就是程序解决问题所用的数学方法和过程，也就是就是输入和输出的中间步骤。一个很简单的程序，也经常会用到算法。很多问题都有一个显然的简单算法，而好的算法会非常显著的提高程序的运行效率。在优化的问题上，好的算法也会很大程度的提高解的质量。
[编辑] 基本算法
有一些问题只要按照给出的步骤一步一步的进行即可。这叫做“模拟”算法。
而也有很多问题并不能像这样直接算出来。一个最容易想到的方法是枚举算法：枚举所有的可能的情况，逐个求解。
例如，解方程的题目的枚举算法就是：枚举每一个可能的解，判断等式是否成立。求最小值的算法也一样：枚举其中未知数的每一个可能的值，求出其结果，最后取一个最小的。当然以上这些算法可能不适用于可能有任何实数解的情况。再比如我们在修理电脑的时候，往往会进行很多测试，以便把无关的软硬件排除，这就是在进行枚举。
这是一种比较原始的方法。对于大部分的问题，这种算法都适用。但是其中有很多情况虽然可以用，但是情况数特别多，以至于不可能在可以忍受的时间之内出解。我们知道2的64次方是一个很大的数字，以至于一个国家乃至全世界的米粒数加起来也不够这么多，甚至有人预言在经过了这么长时间，64个盘的汉诺塔搬完之后就是世界末日的来临。即使对现在运算速度非常快的计算机来说，这个数字还是很大——所以不要指望需要枚举这么多情况的程序能够在有限的时间之内出解。而对于很多问题，其可能的状态数往往会远远超过这么多——加密算法的安全性也都是依赖于这不可能枚举出来的情况数的。
注意不要为了写程序而写程序。可以直接手算出来的内容，往往是不需要程序解决的，直接引用或者输出结果即可。相反的，如果在计算过程中碰到了手算比较困难的问题，则也可以用程序帮助解决。
[编辑] 递归
递归是一种常见的思想。我们想象一下为什么汉诺塔需要那么多的步数——对于n个盘的汉诺塔，都需要进行两次(n-1)个盘的汉诺塔的移动。这种引用自己更小规模的情况的自身的算法，而求出最终结果的方法，就叫做递归。
例如，要输出1到n的所有全排列的话，有一种简单的方法是，先枚举一下第一个数，然后再求后面n-1个数的所有全排列。这就是递归。
很多时候递归都会调用两个或者更多的其本身，也就造成了很低的速度，一般只能在n不超过大约20的时候解决问题。但是也不是所有的时候递归都意味着低效率。比如经过优化的递归平均调用其本身的数量还不到两个，而下面要说的分治，递归时调用两个其本身的规模都是n/2，所以不会成倍的扩大总体规模，也就不会造成低效率，相反分治的算法往往很快。
而枚举算法往往就需要递归，规模成倍扩大的递归就是上面说的速度很慢所以大数据无法出解的情况。
一般的编程语言中可以使用递归函数，即引用自己的函数。这是递归的一种实现方法。这种方法需要一个由系统分配的栈来保存之前所在的函数。然而系统的栈的大小是有限制的。如果递归的层数太多（往往是调用其本身平均不足两次的情况），则需要一个自己的栈来保存现在计算到的位置，而不能直接使用递归函数。这种方法枚举情况的过程有点类似于手工计算“加一”的操作，如果最后一位加满了，那就处理前一位，要是也加满了就处理再前面那一位……然后再把后面的情况依次都重置成可能的第一种。
[编辑] 动态规划
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
分类：动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
线性动规：拦截导弹，合唱队形，挖地雷等
区域动规：石子合并， 加分二叉树，统计单词个数等
树形动规：贪吃的九头龙，二分查找树等
背包问题：装箱问题，挤牛奶（同济ACM第1132题）等
[编辑] 分治
分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等等。 在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。这种方法，就是所谓的分治法。 适用于： 采用分治法解决的问题一般具有的特征如下：
1. 问题的规模缩小到一定的规模就可以较容易地解决。
2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。
3. 合并问题分解出的子问题的解可以得到问题的解。
4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。
设计步骤：
1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。 2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。 3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。 分治法的关键是算法的组合步。究竟应该怎样合并，目前没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。
[编辑] 算法分析
[编辑] 时间、空间复杂度
[编辑] 概率
[编辑] 均摊分析
[编辑] 其他算法分析
[编辑] 算法的扩展与组合
[编辑] 数学知识
[编辑] 数据结构
[编辑] 基本数据结构
[编辑] 数据结构操作
[编辑] 结构化数据结构
[编辑] 数据结构的设计与扩展
[编辑] 封装
[编辑] 记录、类
[编辑] 命名空间
[编辑] 库、引用
[编辑] 开发套件、依赖性
[编辑] 程序结构与规划
[编辑] 代码整理
xcvfsfasdasd
[编辑] 模块
[编辑] 程序规划
[编辑] 软件工程
[编辑] 参见
[编辑] 习题
- Hello World（80%）
- Your Ride Is Here（10%）
