子序列问题
#include <stdlib.h>
#include <stdio.h>
/*
* === FUNCTION ======================================================================
* Name: maxsubsum
* Description: 用分治法找出数组中的最长公共子序列
* =====================================================================================
*/
int max3(int a, int b, int c)
{
int max;
if (a > b) {
max = a;
} else {
max = b;
}
return max > c ? max : c;
}
int maxsubsum(const int a[], int left, int right)
{
int maxleft, maxright; /* 左右最大子序列和 */
int maxleftborder = 0, maxrightborder = 0; /* 包含中间元素的左右两部份的和 */
int leftbordersum = 0;
int rightbordersum = 0;
int mid, i;
if (left == right) {
if (a[left] > 0) {
return left;
} else {
return 0;
}
}
mid = (left + right) / 2;
maxleft = maxsubsum(a, left, mid);
maxright = maxsubsum(a, mid + 1 , right);
for ( i = mid; i >= left; i--) {
leftbordersum += a[i];
if (leftbordersum > maxleftborder) {
maxleftborder = leftbordersum;
}
}
for ( i = mid + 1; i <= right; i++) {
rightbordersum += a[i];
if (rightbordersum > maxrightborder) {
maxrightborder = rightbordersum;
}
}
return max3(maxleft, maxright, maxleftborder + maxrightborder);
}
int main(void)
{
int a[] = {4, -3, 5, -2, -1, 2, 6, -2};
printf("%d\n", maxsubsum(a, 0, 7));
return 0;
}
/*
* === FUNCTION ======================================================================
* Name: maxsubmulti
* Description: 采用分治法求解最大子序列乘积。
* 因为负负得正，所以设置了 minleftborder,minrightborder
* =====================================================================================
*/
#include <stdio.h>
double max4(double, double, double, double);
double maxone(const double [], int); /* 如果maxsubmulti返回结果为1.0，则可能是都为小于1的小数且至多有一个负元素 */
double maxsubmulti(const double [], int, int);
double maxsub(const double a[], int n)
{
double maxsubm = maxsubmulti(a, 0, n-1);
if (maxsubm == 1.0)
return (maxone(a, n));
else
return maxsubm;
}
double maxsubmulti(const double a[], int left, int right)
{
double maxleft, maxright;
double maxleftborder = 1, maxrightborder = 1;
double minleftborder = 1, minrightborder = 1;
double leftborder = 1, rightborder =1;
int mid, i;
if (left == right) {
if (a[left] > 0)
return a[left];
else
return 0;
}
mid = (left + right) / 2;
maxleft = maxsubmulti(a, left, mid);
maxright = maxsubmulti(a, mid + 1, right);
for (i = mid; i >= left; i--) {
leftborder *= a[i];
if (leftborder > maxleftborder)
maxleftborder = leftborder;
if (leftborder < minleftborder)
minleftborder = leftborder;
}
for (i = mid + 1; i <= right; i++) {
rightborder *= a[i];
if (rightborder > maxrightborder)
maxrightborder = rightborder;
if (rightborder < minrightborder)
minrightborder = rightborder;
}
return max4(maxleft, maxright, maxleftborder * maxrightborder, minleftborder * minrightborder);
}
int main(void)
{
double arr[6] = {-1.0, 1000.0, 0.001, 1.5, -80, 10};
printf("%f\n",maxsub(arr, 6));
double arb[6] = {-3, 0.02, 0.001, 0.3, 0.11, 0.210};
printf("%f\n",maxsub(arb, 6));
return 0;
}
double max4(double a, double b, double c, double d)
{
double max = a;
if (max < b)
max = b;
if (max < c)
max = c;
if (max < d)
max = d;
return max;
}
double maxone(const double a[], int n)
{
double maxd = a[0];
int i;
for (i = 1; i < n; i++)
if (a[i] > maxd)
maxd = a[i];
return maxd;
}
#include <stdio.h>
#include <stdlib.h>
// max1num返回数组中最大值
int max1num(int a[], int n)
{
int i,max;
max = a[0];
for (i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
//求数组a的最大子序列和
int maxsub(int a[], int n)
{
int i,maxsum,linesum;
maxsum = max1num(a, n);
if (maxsum <= 0)
return maxsum;
linesum = 0;
for (i = 0; i < n; i++) {
linesum += a[i];
if (linesum < 0)
linesum = 0;
if (linesum > maxsum)
maxsum = linesum;
}
return maxsum;
}
// min1num返回数组中最小值
int min1num(int a[], int n)
{
int i, min;
min = a[0];
for (i = 1; i < n; i++)
if (a[i] < min)
min = a[i];
return min;
}
//求数组a的最小子序列和
int minsub(int a[], int n)
{
int i;
int minsum, linesum;
minsum = min1num(a,n);
if (minsum >= 0) //如果minsum >= 0的话，数组中没有负数，minsum即是最小子序列（只有一个元素minsum）
return minsum;
linesum = 0;
for (i = 0; i < n; i++) {
linesum += a[i];
if (linesum > 0 && linesum > minsum)
linesum = 0;
if (linesum < minsum)
minsum = linesum;
}
return minsum;
}
int main(void)
{
int a[]={-324,23,23,111,23232,222,1111,555,-222,22,-88888};
printf("%d\n",minsub(a,11));
int b[]={324,23,-300,111,-121,2,-456,555,222,22,88888};
printf("%d\n",minsub(b,11));
int c[]={-324,23,23,111,23232,222,1111,555,-222,22,-88888};
printf("%d\n",maxsub(c,11));
int d[]={324,23,-300,111,-121,2,-456,555,222,22,88888};
printf("%d\n",maxsub(d,11));
return 0;
}
sasf
数据结构与算法分析数学和文本部份
一，归纳法证明：
1，证明基准情形(base case)。就是确定定理对于某个小的（通常是退化的）值的正确性。
2，归纳假设(inductive hypothesis)。假设定理对直到某个有限数k的所有情况都是成立的，然后使用这个假设证明定理对下一个值(k + 1)也是成立的。
二，递归：
1，基准情形(base case)。
2，不断推进(make progress)。对于需要递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进。
3，设计法则(design rule)。假设所有的递归调用都能运行。
4，合成效益法则(compound interest rule）。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
三，
O(N)的一些排序算法：
基数排序(radix sort)，也称卡式排序(card sort)
桶式排序(bucket sort)，该排序运行时间为O(P(N+B))，P是排序趟数，N是元素个数，B是桶数。
C素数筛法（更新中）
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <time.h>
unsigned int prime(unsigned int max)
{
unsigned int count = 0; /* 返回count: 素数个数 */
unsigned int i, j, k;
// 申请内存
bool *sieve = (bool *) malloc(sizeof(bool) * (max));
if (sieve == NULL) {
fprintf(stderr, "\ndynamic memory allocation failed\n");
exit(EXIT_FAILURE);
}
sieve[0] = false;
sieve[1] = false;
sieve[2] = true;
//除2之外，所有偶数都是合数
for (i = 3; i < max; i++)
if (i % 2)
sieve[i] = true;
else
sieve[i] = false;
k = (int)sqrt(max);
for (i = 2; i < k; i++) {
if (sieve[i])
for (j = i + i; j < max; j += i) {
sieve[j] = false;
}
}
for (i = 0; i < max; i++)
if (sieve[i])
count++;
free(sieve);
sieve = NULL;
return count;
}
int main(void)
{
unsigned int count;
unsigned int N = 100000000;
clock_t start, end;
start = clock();
count = prime(N);
end = clock();
printf("[%u]以内素数个数%u 计算用时：%g 秒\n", N, count,
(double)(end - start) / (double)CLOCKS_PER_SEC);
}
[100000000]以内素数个数5761455 计算用时：5.86 秒
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <time.h>
/*
* === FUNCTION ======================================================================
* Name: prime
* Description: 只存奇数的bool型数组，素数筛法。[0]表示自然数3
* =====================================================================================
*/
unsigned int prime(unsigned int max)
{
unsigned int count = 1; /* 返回count: 素数个数，已经包括2，所以count为1 */
unsigned int limit = max / 2 - 1; /* max以内的素数用到的数组需要空间 max/2-1 */
unsigned int i, k;
unsigned int multiprime;
// 申请内存,
bool *sieve = (bool *) malloc(sizeof(bool) * (limit));
if (sieve == NULL) {
fprintf(stderr, "\ndynamic memory allocation failed\n");
exit(EXIT_FAILURE);
}
for (i = 0; i < limit; i++)
sieve[i] = true;
// 2*i+3 为数组下标内容所代表的数值
k = (unsigned int)sqrt(max);
for (i = 0; 2 * i + 3 < k; i++) {
if (sieve[i]) {
int temp = 2 * i + 3; /* temp代表数组下标所代表的真实数值 */
/* 索引i所代表数值的奇数倍索引，3倍时为3*temp */
for (multiprime = temp * 3; multiprime < max;
multiprime += 2 * temp)
sieve[(multiprime - 3) / 2] = false;
}
}
for (i = 0; i < limit; i++)
if (sieve[i])
count++;
free(sieve);
sieve = NULL;
return count;
}
int main(void)
{
unsigned int count;
unsigned int N = 100000000;
clock_t start, end;
start = clock();
count = prime(N);
end = clock();
printf("[%u]以内素数个数%u 计算用时：%g 秒\n", N, count,
(double)(end - start) / (double)CLOCKS_PER_SEC);
}
[100000000]以内素数个数5761455 计算用时：2.85 秒
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <time.h>
unsigned int prime(unsigned int max)
{
unsigned int count = 0; /* 返回count: 素数个数 */
unsigned int i, j, k;
// 申请内存
bool *sieve = (bool *) malloc(sizeof(bool) * (max));
if (sieve == NULL) {
fprintf(stderr, "\ndynamic memory allocation failed\n");
exit(EXIT_FAILURE);
}
sieve[0] = false;
sieve[1] = false;
sieve[2] = true;
//除2之外，所有偶数都是合数
for (i = 3; i < max; i++)
if (i % 2)
sieve[i] = true;
else
sieve[i] = false;
k = (int)sqrt(max);
/*------------------------------------------------------------------
* 台湾ACMTino同学的算法：i是素数，则下一个起点是i*i，把后面所有的i*i+2*x*i筛掉
* 我的实现还不完备
*----------------------------------------------------------------*/
for (i = 2; i < k; i++) {
if (sieve[i])
for (j = i * i; j < max; j += 2 * i) {
sieve[j] = false;
}
}
for (i = 0; i < max; i++)
if (sieve[i])
count++;
free(sieve);
sieve = NULL;
return count;
}
int main(void)
{
unsigned int count;
unsigned int N = 100000000;
clock_t start, end;
start = clock();
count = prime(N);
end = clock();
printf("[%u]以内素数个数%u 计算用时：%g 秒\n", N, count,
(double)(end - start) / (double)CLOCKS_PER_SEC);
}
[100000000]以内素数个数5761455 计算用时：3.53 秒
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>
/*
* === FUNCTION ======================================================================
* Description: 只计算奇数数组里的奇数是否为素数，[0]为3
* prime(n)中的n为n以内的素数，不包括n本身。
* =====================================================================================
*/
int prime(unsigned int n)
{
unsigned int i, j, k;
unsigned int limit = n / 2 - 1;
unsigned int count = 1; /* 数组中不包含的2也为素数 */
bool *sieve = (bool *) malloc(sizeof(bool) * limit);
if (sieve == NULL) {
fprintf(stderr, "\ndynamic memory allocation failed\n");
exit(EXIT_FAILURE);
}
for (i = 0; i < limit; i++)
sieve[i] = true;
j = (unsigned int)sqrt(n);
for (i = 0; 2 * i + 3 <= j; i++)
if (sieve[i]) {
int temp = 2 * i + 3; /* 2*i+3为数组下标实际代表的数值 */
for (k = temp * temp; k <= n; k += 2 * temp) /* x是素数，则下一个起点是x*x，并把后面所有的x*x+2*x*i筛掉 */
sieve[(k - 3) / 2] = false;
}
for (i = 0; i < limit; i++)
if (sieve[i])
count++;
free(sieve);
sieve = NULL;
return count;
}
int main(int argc, char *argv[])
{
unsigned int count;
unsigned int N = 100000001;
clock_t start, end;
start = clock();
count = prime(N);
end = clock();
printf("[%u]以内素数个数%u 计算用时：%g 秒\n", N, count,
(double)(end - start) / (double)CLOCKS_PER_SEC);
return 0;
}
[100000000]以内素数个数5761455 计算用时：2.56 秒
/*-----------------------------------------------------------------------------
* 可参考论文COMPUTING π(x): THE MEISSEL-LEHMER METHOD
* 以下函数为百度C语言贴吧 5230所做 （我完全不懂撒 -__-）
*-----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int *primarr, *v;
int q = 1, p = 1;
//π(n)
int pi(int n, int primarr[], int len)
{
int i = 0, mark = 0;
for (i = len - 1; i > 0; i--) {
if (primarr[i] < n) {
mark = 1;
break;
}
}
if (mark)
return i + 1;
return 0;
}
//Φ(x,a)
int phi(int x, int a, int m)
{
if (a == m)
return (x / q) * p + v[x % q];
if (x < primarr[a - 1])
return 1;
return phi(x, a - 1, m) - phi(x / primarr[a - 1], a - 1, m);
}
int prime(int n)
{
char *mark;
int mark_len;
int count = 0;
int i, j, m = 7;
int sum = 0, s = 0;
int len, len2, len3;
mark_len = (n < 10000) ? 10002 : ((int)exp(2.0 / 3 * log(n)) + 1);
//筛选n^(2/3)或n内的素数
mark = (char *)malloc(sizeof(char) * mark_len);
memset(mark, 0, sizeof(char) * mark_len);
for (i = 2; i < (int)sqrt(mark_len); i++) {
if (mark[i])
continue;
for (j = i + i; j < mark_len; j += i)
mark[j] = 1;
}
mark[0] = mark[1] = 1;
//统计素数数目
for (i = 0; i < mark_len; i++)
if (!mark[i])
count++;
//保存素数
primarr = (int *)malloc(sizeof(int) * count);
j = 0;
for (i = 0; i < mark_len; i++)
if (!mark[i])
primarr[j++] = i;
if (n < 10000)
return pi(n, primarr, count);
//n^(1/3)内的素数数目
len = pi((int)exp(1.0 / 3 * log(n)), primarr, count);
//n^(1/2)内的素数数目
len2 = pi((int)sqrt(n), primarr, count);
//n^（2/3)内的素数数目
len3 = pi(mark_len - 1, primarr, count);
//乘积个数
j = mark_len - 2;
for (i = (int)exp(1.0 / 3 * log(n)); i <= (int)sqrt(n); i++) {
if (!mark[i]) {
while (i * j > n) {
if (!mark[j])
s++;
j--;
}
sum += s;
}
}
free(mark);
sum = (len2 - len) * len3 - sum;
sum += (len * (len - 1) - len2 * (len2 - 1)) / 2;
//欧拉函数
if (m > len)
m = len;
for (i = 0; i < m; i++) {
q *= primarr[i];
p *= primarr[i] - 1;
}
v = (int *)malloc(sizeof(int) * q);
for (i = 0; i < q; i++)
v[i] = i;
for (i = 0; i < m; i++)
for (j = q - 1; j >= 0; j--)
v[j] -= v[j / primarr[i]];
sum = phi(n, len, m) - sum + len - 1;
free(primarr);
free(v);
return sum;
}
int main()
{
int n;
int count;
clock_t start, end;
scanf("%d", &n);
start = clock();
count = prime(n);
end = clock() - start;
printf
("[%d]内的素数个数为%d，计算用时：%d毫秒\n",
n, count, (int)end / 1000);
getchar();
return 0;
}
入门排序算法（逐步更新）
/*交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。*/
/* 冒泡排序
* */
#include <stdio.h>
void bubble_sort(int *x, int n)
{
int i, j, exchange, temp; //用exchange保存交换标志
for (i = n - 1; i > 0; i--) { //冒泡算法最多做n-1趟排序
exchange = 0; //本趟排序开始前，交换标志应为假
for (j = 0; j < i; j++) //预置k=0,循环扫描后更新
if (*(x + j) > *(x + j + 1)) {
temp = *(x + j);
*(x + j) = *(x + j + 1);
*(x + j + 1) = temp;
exchange = 1; //发生交换，置标志为1
}
if (!exchange) //如果未发生交换，退出
return;
}
}
int main(void)
{
int i;
int a[5] = { 5, 3, 2, -5, 1 };
bubble_sort(a, 5);
for (i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
#include <stdio.h>
void select_sort(int a[], int n)
{
int i, j, temp, iMin;
for (i = 0; i < n - 1; ++i) {
iMin = i;
for (j = i + 1; j < n; ++j)
if (a[j] < a[iMin])
iMin = j;
if (iMin != i)
temp = a[i], a[i] = a[iMin], a[iMin] = temp;
}
}
static void merge(int array[], int low, int mid, int high)
{
int i, k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
if(array[begin1]<=array[begin2])
temp[k] = array[begin1++];
else
temp[k] = array[begin2++];
if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
free(temp);
}
void merge_sort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
mid = (first+last)/2;
merge_sort(array, first, mid);
merge_sort(array, mid+1,last);
merge(array,first,mid,last);
}
}
/*
* === FUNCTION ======================================================================
* Name: SHELLSORT
* Description: Donald Shell 最初建议步长选择为n/2并且对步长取半直到步长达到1。虽然这样取可以比O(n2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。 可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
步长序列 最坏情况下复杂度
n / 2i \mathcal{O}(n2)
2k − 1 \mathcal{O}(n3 / 2)
2i3i \mathcal{O}(nlog2n)
已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…） 这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）[2]
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
void shellsort(int data[], int n)
{
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && data[j] > data[j + gap];
j -= gap) {
temp = data[j];
data[j] = data[j + gap];
data[j + gap] = temp;
}
}
int main(void)
{
int a[] = { 53, 325, 456, 24352, 2345, 32, 234, 23, 21, 2, 3, 4325 };
shellsort(a, 12);
for (int i = 0; i < 12; i++)
printf("%d\t", a[i]);
return EXIT_SUCCESS;
}
#include <stdio.h>
#include <stdlib.h>
void swap(int v[], int i, int j)
{
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
void qsort1(int v[], int left, int right)
{
int i, last;
if (left >= right)
return;
swap(v, left, (left + right) / 2);
last = left;
for (i = left + 1; i <= right; i++)
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last);
qsort1(v, left, last - 1);
qsort1(v, last + 1, right);
}
void InsertSort(char array[], unsigned int n)
{
int i, j;
int temp;
for (i = 1; i < n; i++) {
temp = array[i]; //store the original sorted array in temp
for (j = i; j > 0 && temp < array[j - 1]; j--) //compare the new array with temp(maybe -1?)
{
array[j] = array[j - 1]; //all larger elements are moved one pot to the right
array[j - 1] = temp;
}
}
}
算法相关的网址