#include <stdio.h>
void reverseNum(int a[], int iLen)
{
int N = iLen;
for (int i = 0; i < N/2; i++)
{
int temp = a[i];
a[i] = a[N-1-i];
a[N-1-i] = temp;
}
}
int main()
{
int a[] = {1,2,3,4,5};
int iLen = sizeof(a) / sizeof(int);
reverseNum(a, iLen);
for (int i = 0; i < iLen; i++)
{
printf("%d ", a[i]);
}
printf("\n");
getchar();getchar();
return 0;
}
质数（prime number）又称素数，有无限个。除了1和它本身以外不再有其他的除数整除。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积，最小的质数是2。
所谓素数是指除了1和它本身以外，不能被任何整数整除的数。
例如17就是素数，因为它不能被2~16的任一整数整除。因此判断一个整数m是否是素数，只需把m被2~m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。
另外判断方法还可以简化。m不必被2~m-1之间的每一个整数去除，只需被2~sqrt(m)之间的每一个整数去除就可以了。如果m不能被2~sqrt(m)间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于sqrt(m)。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2~4之间有无因子即可）
#include <stdio.h>
bool bIsPrime(int N)
{
if(N < 2) return false;
for (int i = 2; i*i <= N; i++)
if(N % i == 0)
return false;
return true;
}
int main()
{
for (int i = 0; i < 20; i++)
{
if(bIsPrime(i))
{
printf("%d is prime\n", i);
}
else
{
printf("%d is not prime\n", i);
}
}
return 0;
}
欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：
假设质数只有有限的 n 个，从小到大依次排列为 p1，p2，……，pn，设 N=p1×p2×……×pn，那么，N+1 是素数或者不是素数。
如果 N+1 为合数，因为任何一个合数都可以分解为几个素数的积；而 N 和 N+1 的最大公约数是 1，所以 N+1 不可能被 p1，p2，……，pn 整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。
#include <stdio.h>
int gcd(int p, int q)
{
if(q == 0) return p;
int r = p % q;
return gcd(q, r);
}
int main()
{
printf("%d\n", gcd(30, 24)); //输出:6
printf("%d\n", gcd(30, 7)); //输出:1
printf("%d\n", gcd(28, 56)); //输出:28
getchar();getchar();
return 0;
}
辗转相除法
用（a,b）来表示a和b的最大公约数。
有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。 （证明过程请参考其它资料）
例1： 30 和 7
∵ 30 % 7 = 2 ∴ (30,7) = (7,2)
∵ 7 % 2 = 1 ∴ (7,2) = (2,1)
2 % 1 = 0
所以 30 和 7 的最大公约数是 1
例1： 30 和 24
30 % 24 = 6
24 % 6 = 0
所以 30 和 24 的最大公约数是 6
就是在一个有序的集合 a 里面，要查找一个数字 v。
我们通过和中间的那个数字 a[mid] 对比，
如果 a[mid] > v，说明 v 在集合的前半部分，即 a[0] ~ a[mid-1]。
如果 a[mid] < v，说明 v 在集合的后半部分，即 a[mid+1] ~ a[n-1]。
如果 a[mid] == v，则找到数字。
我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么？你每次猜的时候，我会告诉你猜的是太大了，还是太小了，直到你猜中为止。
假设我写的数字是 86。
用二次查找的思想猜数字的过程如下：
| 次数 | 猜测的范围 | 中间数字 | 对比大小 |
| 第 1 次 | 0 - 99 | 49 | 49 < 86 |
| 第 2 次 | 50 - 99 | 74 | 74 < 86 |
| 第 3 次 | 75 - 99 | 87 | 87 > 86 |
| 第 4 次 | 75 - 86 | 80 | 80 < 86 |
| 第 5 次 | 81 - 86 | 83 | 83 < 86 |
| 第 6 次 | 84 - 86 | 85 | 85 < 86 |
| 第 7 次 | 86 | 86 | 86 = 86 |
一共猜了 7 次，每次猜过之后，剩下的数字范围就少了一半。
第 1 次，猜的范围有 100 个数字。
第 2 次，猜的范围就只剩下 50 个数字了。
第 3 次，则只有 25 个数字了，这就是二分查找。
假设有 n 个元素，查找了 k 次才找到。
第 1 次查找: n/2
第 2 次查找: ( n/2 ) / 2 = n/4 = n/(2^2)
第 3 次查找: ( n/(2^2) ) / 2 = n/(2^3)
第 4 次查找: ( n/(2^3) ) / 2 = n/(2^4)
...
第 k 次查找: n/(2^k)
n/(2^k) 代表的是还剩下的元素的个数
n/(2^k) >= 1
当 n/(2^k) == 1 时，查找结束。
所以令 n/(2^k) = 1 ， 即
==> n = 2^k
==> k = log(n) //以2为基
所以时间复杂度为 O( log(n) )
https://github.com/MDGSF/algo/blob/master/go/binarysearch/binarysearch.go
https://github.com/MDGSF/algo/blob/master/c-cpp/binarysearch/binarysearch.cpp
// BinarySearch binary search
// 二分查找，非递归版本
func BinarySearch(a []int, v int) int {
if len(a) == 0 {
return -1
}
low := 0
high := len(a) - 1
for low <= high {
mid := low + (high-low)/2
if a[mid] == v {
return mid
} else if a[mid] > v {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
// BinarySearchRecursive binary search
// 二分查找，递归版本
func BinarySearchRecursive(a []int, v int) int {
if len(a) == 0 {
return -1
}
return BinarySearchRecursiveInner(a, v, 0, len(a)-1)
}
func BinarySearchRecursiveInner(a []int, v int, low int, high int) int {
if low > high {
return -1
}
mid := low + (high-low)/2
if a[mid] == v {
return mid
} else if a[mid] > v {
return BinarySearchRecursiveInner(a, v, low, mid-1)
} else {
return BinarySearchRecursiveInner(a, v, mid+1, high)
}
}
int iBinarySearch(int aiNum[], int iNumSize, int iVal)
{
if(NULL == aiNum || iNumSize <= 0)
{
return -1;
}
int iStart = 0;
int iEnd = iNumSize - 1;
while (iStart <= iEnd)
{
int iMid = iStart + ((iEnd - iStart) >> 1);
if(aiNum[iMid] < iVal)
{
iStart = iMid + 1;
}
else if(aiNum[iMid] > iVal)
{
iEnd = iMid - 1;
}
else
{
return iMid;
}
}
return -1;
}
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：
1+2+3+ … + n = n(n+1)/2
证明：
(1) 当 n = 1 时，
左边 = 1
右边 = 1(1+1)/2 = 1
所以：左边=右边，命题成立。
(2)假设当 n = m 时，命题成立，即
1+2+3+ ... + m = m(m+1)/2
两边同时加上 m+1， 如下：
1+2+3+ ... + m + (m+1) = m(m+1)/2 + (m+1)
右边 = m(m+1)/2 + (m+1)
= m(m+1)/2 + 2(m+1)/2
= (m+1)(m+2)/2
= (m+1)[(m+1)+1]/2
所以：对于任意自然数n，命题成立。