程序员的数学

0的关于故事

1. N进制计数法
   一般来说，N进制计数法有如下特征：

• 使用的数字有0，1，......，N-1，共N种
• 从右往左分别是N的0次方位，N的1次方位，N的2次方位......（基数是N）

2. 指数法则
   N不等于0时，N的a次方乘以N的b次方等于N的a加b之和的次方。

逻辑

1. 命题
   能够判断对错的陈述句叫做命题。
   在考虑规则时确认没有“遗漏”和“重复”是相当重要的：
   没有“遗漏”，即具备完整性，由此明确该规则无论在什么情况下都能适用。
   没有“重复”，即具备排他性，由此明确该规则不存在矛盾。
2. 复杂命题
   2.1. 逻辑非
   假定某命题A，则A的逻辑非表达式为：
   ¬A（not A）
   2.2. 逻辑与
   A并且B的命题称作逻辑与，写作：
   A∧B（A and B）
   2.3. 逻辑或
   A或者B的命题称为逻辑或，写作：
   A∨B
   2.4. 逻辑异或
   A或者B，但不能同时满足的命题称为逻辑异或，写作：
   A⊕B
   2.5. 相等
   A和B相等的命题，逻辑表达式写作：
   A=B
   2.6. 蕴涵
   命题若A满足则B必然满足称为蕴涵，写作：
   A⇒B
3. 德摩根定律
4. 余数--周期性和分组
5. 数学归纳法
   数学归纳法是证明有关整数的断言对于0以上的所有整数是否成立所用的方法。
   假设要用数学归纳法证明：
   断言P(n)对于0以上的所有整数n都成立。
   则需要通过一下两步进行证明：

1. 证明P(0)成立(基底)
2. 证明不论k为0以上的哪个整数，若P(k)成立，则P(k+1)也成立

例1.高斯求和
证明G(k)：
0+1+2+...+k = (k * (k+1))/2

步骤1：基底证明
证明G(0)成立。
G(0)就是0到0的整数之和与(0*(0+1))/2相等。
通过直接计算即可得出。
步骤2:归纳的证明
证明当k为任意整数时,若G(k)成立，则G(k+1)也成立。
现假设G(k)成立，即假设：
0+1+2+...+k = (k * (k+1) ) /2成立
下面就是证明G(k+1)成立，即：
0+1+2+3+...+k+(k+1) = ( (k+1) * ( (k+1) +1)) /2
假设G(k)成立，左边可进行如下计算：
G(k+1)=0+1+2+3+...+k+(k+1)
            =G(k) + ( k + 1 )
            =( ( k * ( k + 1) ) /2 ) + ( k + 1 )
            =( ( k * ( k + 1 ) ) /2 ) + ( (2 * (k + 1) ) /2 )
            =( ( k * ( k + 1 ) ) + ( 2 * ( k + 1 ) ) ) /2
            =((k*k) + (3*k) + 2)/2
 右边可进行如下计算：
G(k+1)=((k+1) * ((k+1)+1))/2
            =((k+1) * (k+2))/2
            =((k*k) + 3k + 2)/2

例2.奇数求和
证明Q(n)：
1 + 3 + 5 + 7 + ... + (2n-1) = nn

步骤1：证明基底
1 = 1*1
步骤2.归纳证明
假设Q(n)=n*n，证明Q(n+1)：
1+3+5+...+(2*n-1)+(2*(n+1)-1) = (n+1)*(n+1)
假设Q(n)成立，则左边可进行如下计算：
Q(n+1)=n*n + (2*(n+1)-1)
            =n*n + 2*n + 1
右边可进行如下计算
Q(n+1)=n*n + 2*n + 1

排列与组合

1. 加法法则
   加法法则是指将无重复的两个集合相加；
   加法法则的容斥原理：
   集合A，B元素的总数=A的元素数+B的元素数-A和B共同的元素数
2. 乘法法则
   有A，B两个集合，要将A和B的所有元素组合起来，这时组合起来的总数就是两个集合元素数相乘所得出的结果。
3. 置换
   将n个事物按顺序进行排列称为置换。
   阶乘
4. 排列
   假设从n个元素中取k的元素进行排列，排列的总数就是
   n（n-1）...*（n-（k-1））
5. 组合
   与置换和排列不同，组合不考虑顺序。

递归

1. 汉诺塔
   汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 --引用*
   现有x，y，z3个柱子，A柱子上套这n个圆盘，这些圆盘大小各异，按从大到小的顺序自下而上排列，现将所有圆盘从x移动到y，且移动时遵循下述规则：

• 一次只能移动柱子最上端的一个圆盘
• 小圆盘上不能放大圆盘
  解法：
  将n个圆盘从x柱子，经由z柱子中转，移到y柱子时：
  当n=0时，
  不做任何操作。
  当n>0时，
  首先，将n-1个圆盘从x柱子，经由y柱子中转，移到z柱子。
  然后，将1个圆盘从x柱子移动到y柱子。
  最后，将n-1个圆盘从z柱子，经x柱子中转，移到y柱子。
  我们将移动n个圆盘的最少次数记为H(n),那么有：
  n=0时，H(n)=0;
  n>0时，H(n)=H(n-1)+1+H(n-1);
  我们将H(n)和H(n-1)的关系称为递推公式。
  由上可以的出一下数列：
  0，1，3，7，15，31，63...
  即H(n)=2^n -1；
  通过数学归纳法可以证明该等式成立,我们将只使用n表示H(n)的式子叫做解析式；
  C语言实现汉诺塔解法：

#include <stdio.h>
#include <stdlib.h>

static unsigned short const  Line  = 35;
static unsigned short uLen = 0;
static unsigned long uCount = 0;

void Hanoi(unsigned int const n, char const& x, char const& y, char const& z){
    if(0 == n){
        return;
    }else{
        Hanoi(n-1, x, z, y);
        if(Line == uLen){
            printf("\n");
            uLen = 0;
        }
        printf("%c->%c, ", x, y);
        ++uLen;
        ++uCount;
        Hanoi(n-1, z, y, x);
    }
}

int main(int argc, const char** argv){
    int uN = 8;
    if(1 < argc){
        uN = atoi(argv[1]);
    }
    Hanoi(uN, 'x','y','z');
    printf("\n[%d]个盘子需要移动[%lu]次\n", uN, uCount);
    return 0;
}

2. 再谈阶乘

3. 斐波那契数列

4.帕斯卡三角形(杨辉三角形，贾宪三角形)

5. 递归图形

6. 谢尔平斯基三角形

指数爆炸

不可解问题

什么是程序员的数学