#include<stdio.h>
#include<stdlib.h>
#define random(x) (rand()%x)
//以下写成 a^=b^=a^=b 在gcc version 4.4.1上将不能实现两数交换，必须分开写（在swap()函数内如此连写一样不能正确执行）,如果不加if(a!=b)则会出现在调用swap(a,a)后，a=0。
#define swap(a, b) if( a!=b ) {a ^= b; b ^=a ; a ^= b; }
/*
void swap(int * a, int * b)
{
(*a) ^= (*b);
(*b) ^= (*a);
(*a) ^= (*b);
}
*/
//获取随机数数组
int * getArray(int len)
{
int i = 0;
int* arr = NULL;
if(len > 0)
{
arr = (int *)malloc(sizeof(int)*len);
for(i = 0; i < len; i ++)
arr[i] = random(len/3);
}
return arr;
}
//打印数组内容
void printArray(int* arr,int len)
{
printf("\n -------------- \n");
int i = 0;
for( i =0; i < len ; i++)
printf("%d ",arr[i]);
printf("\n -------------- \n");
}
//求最大公约数(Greatest Common Divisor)，辗除法
int gcd(int m, int n){
int r=1;
if(m < n)
swap(m,n);
while(r=m%n){
m = n;
n = r;
}
//printf("gcd=%d",n);
return n;
}
//求最小公倍数(leatest Common Mutiple),两数之积除最大公约数
int lcm(int m, int n){
return m / gcd(m,n) * n;
}
//堆排序算法，调整堆
void heapAdjust(int a[],int n, int i){
int index = i, child = 2*index + 1;
while(child < n){
if(child + 1 < n)
child = (a[child + 1] > a[child])?child + 1:child ;
if(a[child] > a[index])
{
swap(a[child],a[index]);
index = child;
child = 2*child +1;
}
else break;
//printArray(a,n);
}
}
//堆排序
void heapSort(int a[],int n){
int i =0;
//建堆
for(i =(n-2)/2; i >= 0; i --){
heapAdjust(a,n,i);
}
//printArray(a, n);
//依次调堆。将堆顶与最后元素交换，然后调整堆
for(i = n-1; i > 0; i --){
swap(a[i],a[0]);
heapAdjust(a,i,0);
}
printArray(a, n);
}
//经典的快速排序算法，总共不过十几行，抄自《编程之美》
void quickSort(int a[], int left, int right)
{
int m = left,i = 0;
if(left >= right)
return ;
for(i = left + 1; i <= right; i ++)
if(a[i] < a[left])
{ m++;
swap(a[m],a[i]);
}
swap(a[m],a[left]);
//printArray(a,right);
quickSort(a,left,m-1);
quickSort(a,m + 1,right);
}
//从n个数的序列中选取和最大的子序列。注：原序列中元素值有正有负
int maxSub(int a[], int n){
//max最大子序列的和，tempSum子序列临时和
//end最大子序列的结尾下标，length最大子序列长度。
int max = a[0], tempSum = 0;
int end = 0,length = 1, tempLen = 0,i = 0;
for( i = 0; i < n; i ++){
//计算当前段之和
tempSum += a[i];
if(tempSum > max){
max = tempSum;
end = i;
length = tempLen + 1;
}
//如果当前段之和小于0,则说明a[i]一定小于0导致tempSum小于0，当前段重新计算
if(tempSum < 0){
tempSum = 0;
tempLen = 0;
}
else{
tempLen ++;
}
}
printf("\n start=%d,length=%d,maxSum=%d \n",end-length+1,length,max);
return max;
}
//百度2011非质量部校招题目
//最大子序列变种，有一串首位相连的珠子，总共有m颗，珠子涂有不同的颜色，全部颜色共有n种,现在要在里面截取一段，要求包含所有不同的颜色，并且长度越短越好，求如何截取。
//a[]存的是珠子，m是珠子个数，n是颜色种数
int maxSub2(int a[], int m, int n){
//start最终截取段的起始下标，end最终端的结尾下标，minLen最终段的长度，sumColor统计当前段中已经存在多少种颜色，colorCount[]统计最终段中每种颜色的珠子各有多少个
//注：由于m个珠子首尾相连,则要遍历珠子2m次(2m? 3*m/2+1 ?),可能会出现end < start 的情况
int start = 0, end =0, sumColor = 0, minLen = m,i = 0;
int colorCount[n];
for(i=0; i < n; i ++)
colorCount[i] = 0;
for(i = 0, end = 0; i < 2*m; i++, end= (end+1)%m){
//如果end珠子的颜色在当前段中是新颜色，则将统计颜色值的sumColor++
if(!colorCount[a[end]])
sumColor ++;
//将对应颜色的珠子数++
colorCount[a[end]]++;
//删除当前段头部重复颜色的珠子
while(colorCount[a[start]]>1)
{
colorCount[a[start]]--;
start =(start + 1) % m;
}
//包含所有颜色值的段，如果当前长度小于最小值则更新最小值
if((sumColor == n) && ((end + m - start)%m + 1) < minLen)
minLen = (end + m - start)%m + 1;
//printArray(colorCount,n);
}
printf("\n start=%d,end=%d,minlength=%d \n",start,end,sumColor,minLen);
return minLen;
}
//2011百度质量部校园招聘题目
//一个数列中只包含能被2,3,5等质因数整除的数，数列递增。给定一个N，输出不大于N的这样一个数列。
//例如：N= 15 时，2 3 4 5 6 8 9 10 12 14 15
//先算出给定数的最小公倍数，然后找出所有小于最小公倍数的数列，然后以最小公倍数循环即可。
void getNumSeq(int a[], int n, int N){
int *arr = NULL;
int _lcm = a[0],_len = 0, arrLen = 0, i = 0, j = 0, m = 0;
printArray(a,n);
//求所有数的最小公倍数
for(i = 1; i < n; i ++)
{
_lcm = lcm(_lcm,a[i]);
}
arrLen = (_lcm < N)?_lcm:N;
//arr = new int[arrLen];
arr = (int*)malloc(sizeof(int)*arrLen);
//计算出小于min(_gcd,N)的数列并存到 arr[0 .. _len]中
for(i=1; i <= arrLen; i ++)
{
for(j=0; j < n ; j++)
if(!(i % a[j]))
{
arr[_len++] = i;
break;
}
}
//以最小公倍数为周期，打印出数列。
for(m = 0, i = 0; i < _len && m+arr[i] <= N ; i = (i+1)%_len, m +=(i)?0:_lcm)
{
printf("%d ",m+arr[i]);
}
//delete [] arr;
free(arr);
}
int main()
{
int len = 11;
int c =6, d = 6;
int* arr = getArray(len),a[]={3,4,5};
getNumSeq(a,3,60);
printArray(arr,len);
/*
maxSub(arr,len);
maxSub2(arr,len,4);
*/
//heapSort(arr,len);
quickSort(arr,0,len-1);
printArray(arr,len);
swap(c,c);
printArray(&c,1);
free(arr);
return 0;
}