UVa 748 求幂

/*

* 解题思路:

* 题意不难理解、解题大概思想就是

* 第一步:记录小数点位置(即记录有多少位小数);

*      第二步:将小数点去掉、利用先前10106乘积那道题代码,连续成n次该数据

*      第三步:将小数点补回数据中去

*      p s: 题目有特殊说明前导0后缀0的问题,我在第一步前先将原输入数据去掉了前导0和后缀0!!

*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define A 500
char s[ 10 ],str[ A ];
char out[ A ];
int p;
int search( int len )
{
    int i;
    for(i=0;i<len;i++ )
        if( s[ i ] == ‘.‘ ) return i;
    return -1;
}
int delZeroPostFix( int pos , int len )
{
    int i;
    int total = 0,flag = 0;

    for( i=len-1;i>pos;i-- )
        if( !flag && s[ i ] == ‘0‘ ) total++;
        else break;
    return len-total;
}
void delZeroPreFix( int len )
{
    int i;
    int flag = 0,sum = 0;

    for( i=0;i<len;i++ )
        if( !flag && s[ i ] == ‘0‘ ) sum++;
        else break;

    for(i=0;i<len-sum;i++ )
        s[ i ] = s[ i+sum ];

    s[ len-sum ] = ‘\0‘;
}
void delPoint( int pos ,int len )
{
    int i;
    for( i=pos;i<len-1;i++ )
        s[ i ] = s[ i+1 ];
}
void Mutiply( char s1[] ,char s2[] , int len1 ,int len2 )
{
    int x,y,z,zz=0;
    int i,j,k;
    int tmp,flag;
    int len,in;
    char ss[ A ],stmp[ A ];

    if( len1 > len2 )
    {
        strcpy( stmp , s1 );
        strcpy( s1,s2 );
        strcpy( s2 , stmp );
        tmp = len1;
        len1 = len2;
        len2 = tmp;
    }
     memset( ss , ‘0‘ , sizeof( ss ) );
    for( i=len2-1;i>=0;i-- )
    {
        in = 0;
        memset(   stmp , ‘0‘,  sizeof( stmp ) );
        for( j=len1-1;j>=0;j-- )
        {
            x = s1[ j ] - ‘0‘;
            y = s2[ i ] - ‘0‘;

            if( ( x*y+in) >= 10 )
            {
                stmp[ i+j ] = ( char )(( (x*y+in)%10 )+‘0‘);
                    in = (x*y+in)/10;
            }
            else if( (x*y+in )<=9 && (x*y+in ) >=0 )
            {
                stmp[ i+j ] =(char) (x*y+in +‘0‘);
                in = 0;
            }
        }
        if( in != 0 && i!=0 )
            stmp[ i-1 ] = in+‘0‘;
        flag = 0;
        for( j=i+len2-1;j>=0;j-- )
        {
            if( ss[ j ]-‘0‘ + stmp[ j ] -‘0‘ + flag >=10 )
            {
                ss[ j ] = (ss[ j ]-‘0‘ + stmp[ j ] - ‘0‘ + flag )%10+‘0‘;
                flag = 1;
            }
            else
            {
                ss[ j ] += stmp[ j ] -‘0‘+ flag;
                flag = 0;
            }
        }
        if( i == 0 && in+flag )
        {
            zz = 0;
            memset( stmp ,‘\0‘, sizeof( stmp ) );
            z = in + flag;
            while( z!=0 )
            {
                stmp[ zz++ ] = z%10+‘0‘;
                z/=10;
            }

            ss[ len1+len2-1+zz ] = ‘\0‘;
            len = strlen( ss );
            for( k=len+zz;k>=zz;k-- )
                ss[ k ] = ss[ k-zz ];
            for( k=0;k<zz;k++ )
                ss[ zz-k-1 ] = stmp[ k ];
        }
    }
    ss[ len1+len2-1+zz ] = ‘\0‘;
    strcpy( str , ss );
}
void addPoint( int sum , int n)
{
    int i;
    int x = sum*n,y;
    int len = strlen( str );

    for( i=len-1,y=0;i>=0;i-- ,y++)
    {
        if( y == x ) out[ p++ ] = ‘.‘;
        out[ p++ ] = str[ i ];
    }

    if( y<x )
    {
        for( ;y<x;y++ )
           out[ p ++ ] = ‘0‘;
        out[ p++] = ‘.‘;
    }
}
void Paint( )
{
    int i;
    for( i = p-1;i>=0;i-- )
        printf("%c",out[ i ] );
    puts("");
}
int main( )
{
    int n;
    int pos,sum,len,y,tmp;
    int len1,len2;
    while( ~scanf("%s%d",s,&n ) )
    {
       len = strlen( s );
        pos = search( len );
        sum = len-pos-1;
        len = delZeroPostFix( pos , len );
        s[ len ] = ‘\0‘;
        delZeroPreFix( len );
        len = strlen( s );
        pos = search( len );
        sum = len-pos-1;
        delPoint( pos , len );
        s[ len-1 ] = ‘\0‘;
        strcpy( str , s);
        len1 = strlen( s );
        tmp = n;
        tmp--;
        while( tmp-- )
        {
            len2 = strlen( str );
            Mutiply( s , str , len1 , len2 );
        }
        p = 0;
        addPoint( sum , n );
        Paint( );
    }
    return 0;
}



UVa 748 求幂

上一篇:Linux忘记密码常用的几种解决方法


下一篇:简单理解mapreduce