随笔-20  评论-16  文章-36  trackbacks-0

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++ )
        
ifget[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]>&& j>i )    j--;
        
if( i< j )    b[i++]= b[j];
        
while( b[i]<&& 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[] ){
    
forint 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);
    
forint 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 古月残辉 阅读(220) 评论(0)  编辑 收藏 引用 所属分类: Template

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理