初步解读与实现大数运算Exponentiation

Exponentiation

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2475 Accepted Submission(s): 669

Problem Description
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.

This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.

感觉这种大数处理的题目越来越多了，但是也是越来越喜欢这种进位的算法了，还有数组，字符等的处理，感觉以后也会越来越熟练的。下面是我根据网上的代码做出了相应的详解，也是越来越了解该类的编程思维了吧。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int num[10], result[200], len, flag = 0, cnt1;

int char_to_int( char *s )              /*将字符型数组s中的数据复制到整型数组num中，且返回小数位数*/
{
    int i, dian = 0, j, jihao;
    memset(num,0,10*sizeof(int));       //将数组num内的各个数据设为0
    len = strlen(s);                    //len为字符数组s的长度
    //printf( "%s\n", s );
    //printf( "%d\n", len );
    cnt1 = 0;                           //cnt为0
    for( j = len - 1; j >= 0; j-- )
         if( s[j] == '.' )              //找到字符数组s中‘.’的地址，即为jihao
             jihao = j;

        for( j = len - 1; j > jihao; j-- )
             if( s[j] != '0' )          //将j指向数组s中数据的起始位置，既有s【0~j】内存放的为有效数据
                 break;
        //printf( "%d\n", j )
        
    
    for( i = j; i >= 0; i--)
         if( s[i] != '.' )
             num[cnt1++] = s[i] - '0';  //将字符型数据转化为整型并放入num中，忽略小数点，并且从高位到低位的顺序为j-1~0；
                                    
         else
             dian = j  - i;
    /*for( i = 0; i < cnt1; i++ )
         printf( "%d", num[i] );
    printf( "\n%d\n", dian );*/
    return dian;                        //返回有几位小数
}
int bignummulti(  )                                     //将result数组乘上上num数组，调整好位数状态，将结果存入result数组
{
    int i, j, temp[200];
    memset(temp, 0 ,200*sizeof(int));                   //初始化temp数组为零数组
    for( i = 0; i < len; i++ )                          //按乘法竖式来思考的到的是result数组与怒骂数组的乘积
         for( j = 0; j < 200; j++ )
             temp[i+j] += result[j] * num[i];
    
    for( i = 0; i < 200; i++ )                          //temp数组的进位操作
         if( temp[i] >= 10 )
         {
             temp[i+1] += temp[i] / 10; 
             temp[i] = temp[i] % 10;
         }
    for( i = 0; i < 200; i++ )                          //temp数组内的数据全部复制给result数组。
        result[i] =  temp[i];
    return 0;
}

int main(int argc, char *argv[])
{
    int n, dian, i, cnt, j;
    char s[10];
    memset(s,0,sizeof(s));
    while( scanf( "%s %d", &s, &n )!=EOF )
    {
           dian = char_to_int( s ) * n;
           memset(result,0,200 * sizeof(int));
           result[0] = 1;
           for( i = 1; i <= n; i++  )                   //进行n次自乘，达到指数方程的解。
                bignummulti();
           
          for( i = 199; i >= 0; i-- )                   //i和j分别指向高位的有效数字和低位的有效数字，为了防止多余的0输出
                if( result[i] != 0 )
                    break;
           for( j = 0; j < dian; j++ )
                if( result[j] != 0 )
                    break;
           if( dian > i )                               //如果得到的结果是纯小数，需要在dian的前面补一个零，
           {                                            //输出小数点，之后再补零，直到补到i之后再依次输出数字。
               if( i == -1 )
                   printf( "0" );
               else
                   printf( "." );
               cnt = dian - (i + 1);
               while( cnt-- )
                      printf( "0" );
               for( ; i >= j; i-- )
                    printf( "%d", result[i] );
           }
           else                                         //如果不是纯小数，依次输出每位i到j数字，
               for( ; i >= j; i-- )
               {                                        //如果遇到dian，输出小数点，如果没有遇到，则说明是整数。
                    if( i == dian-1 )
                        printf( "." );
                    printf( "%d", result[i] );
               }
           printf( "\n" );     
    }
  
  //system("PAUSE");    
  return 0;
}