1）求最大公约数：int Gcd( int a, int b )
int Gcd( int a, int b ){ //a, b为两个输入的数，返回最大公约数
while( b!= 0 ){
int r= b;
b= a % b;
a= r;
}
return a;
}
2）二分查找
int BSearch( int *t, int k, int l, int h ){ //参数分别表示：数组，要查找的元素，上界，下界
int mid;
while( l<= h ){
mid= ( l+ h )/ 2;
if( k== t[mid] ) return mid;
else if( k< t[mid] ) h= mid- 1;
else l= mid+ 1;
}
return -1;
}
3）求不大于size的质数并保存在prime中，返回质数的个数
int Primes( int *prime, int size ){
int i, j, n= 0;
bool get[size]; //这一步是简写，根据实际情况申请
memset(get,true,sizeof(get));
get[0]= get[1]= false;
for( i= 2; i<= size; i++ )
if( get[i] ){
prime[n++]= i;
j= i+i;
while( j<= size ){ get[j]= false; j+= i; }
}
return n;
}
4）快速排序，l和r为要排序数组的上下界，b为要排序的数组
void QSort( int l, int r, int b[] ){
int i= l, j= r, x= b[i];
if( l>= r ) return;
while( i!= j ){
while( b[j]>x && j>i ) j--;
if( i< j ) b[i++]= b[j];
while( b[i]<x && j>i ) i++;
if( i< j ) b[j--]=b[i];
}
b[i]= x;
QSort(l,j-1,b);
QSort(i+1,r,b);
}
5)计算n个数的m组合，并返回总的个数，Print()根据b数组的序号打印a数组的内容
void Print( int m, int a[], int b[] ){
for( int i= 0; i< m-1; i++ )
printf("%d ",a[b[i]]);
printf("%d\n",a[b[m-1]]);
}
int N_combination( int n, int m, int a[], int b[]){
int i, j, temp, cnt= 1;
bool change;
for( i= 0; i< m; i++ ) b[i]= i;
Print(m,a,b);
while( b[0]!= n-m ){
for( i= m-1; i>= 0; i-- ){
change= true;
if( b[i]+1< n ){
for( j= 0; j< m; j++ )
if( b[j]== b[i]+1 ){
change= false;
break;
}
if( change ){
temp= b[i];
for( j= i; j< m; j++ )
b[j]= temp+ j-i+1;
Print(m,a,b);
cnt++;
break;
}
}
}
}
return cnt;
}
6）任意进制间的转换（大于9的数字用'A'~'Z'表示）
//s[]保存原进制数，d1为原进制，s2[]保存转换后的数，d2为目标进制
void Conversion( char s[], char s2[], long d1, long d2 ){
long i, j, t, num= 0;
char c;
for( i= 0; s[i]!='\0'; i++ ){
if( s[i]<='9' && s[i]>='0' ) t= s[i]-'0';
else t= s[i]-55;
num= num*d1+ t;
}
for( i= 0; num; i++ ){
t= num% d2;
if( t<=9 ) s2[i]= t+'0';
else s2[i]= t+55;
num/= d2;
}
for( j= 0, i--; j<= i/2; j++ ){
c= s2[j];
s2[j]= s2[i-j];
s2[i-j]= c;
}
s2[i+1]='\0';
}
7）求a^b%m的值，a、b、m为int型
__int64 pow( int a, int b, int m ){ //返回a^b%m
bool pw[32];
int l;
__int64 res= 1;
for( l= 0; b; l++, b>>=1 )
pw[l]= (b&1);
for( int i= l-1; i>= 0; i-- ){
res= (res*res)%m;
if( pw[i]&1 ) res= (res*a)%m;
}
return res;
}
posted on 2009-03-13 13:02
古月残辉 阅读(204)
评论(0) 编辑 收藏 引用 所属分类:
Template