站长网 大数据 poj 1001 Exponentiation 模拟大数(hdu 1063)

poj 1001 Exponentiation 模拟大数(hdu 1063)

poj 1001 Exponentiation ?模拟大数 链接: http://poj.org/problem?id=1001 题意: 题意很简单,给你2个数(前面的是小数,后面是不超过25的整数),求得前一个数的幂(后一个数作指数部分)。 思路: 要求小数的幂,用一般的double,float完全满足不了解

poj 1001 Exponentiation ?模拟大数

链接:
http://poj.org/problem?id=1001

题意:

题意很简单,给你2个数(前面的是小数,后面是不超过25的整数),求得前一个数的幂(后一个数作指数部分)。

思路:

要求小数的幂,用一般的double,float完全满足不了解的需求。而且看到案例就知道肯定用大数解决。

大数解决最简单的看来是用JAVA直接可以求,不过我还没有学习JAVA,只能悲催的用字符串来解决。

由于第2个数(指数项)并不大,完全可以以相乘来解决乘方。

又由于小数点可以自行推算,所以可以把小数做整数来求,最后再插入小数点。

所以,我们总结起来要解决的问题,无非下面几点:

1.如何做整数乘法,并记录大数?

大数乘法,本来需要俩个乘数都化为字符串形式,逐位相乘,再进位记录。但这一题乘数只有5位酱紫,可以用整数记录。

那么只需要一个用数组记录结果,另一个用整数记录。

2.如何找到小数点位置?

小数就为原来查找到小数距最后一位的距离乘上指数就是最后小数点距最后一位的距离。

3.如何做最后输出(舍去前导0和后导0)

寻找到有用的开始下标数,和结束下标数。

ac代码:

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
#define ll long long
#define PI acos(-1.0)
const int INF=99999999;
const int MAXN=3000;
const int mod=100;

int result[130];  //记录结果数组
int multiplier;   //作乘数

void multiply()
{
    int temp[130]; //过程数组
    memset(temp,sizeof(temp));

    for(int i = 0; i < 130; i++)
    {
        int t = result[i] * multiplier;
        int carry = (t + temp[i]) / 10; //需要进位的数
        temp[i] = (t + temp[i]) % 10;   //不需要进位的数
        //进位处理
        int g = 1;
        while(carry)
        {
            int t = temp[i+g] + carry;
            carry = t / 10;
            temp[i+g] = t % 10;
            g++;
        }
    }
    //传回数组数值
    for(int i = 0; i < 130; i++)
        result[i] = temp[i];
}
void output(int point)
{
    int began=0,aim=129;
    for(int i = 0; i < 130 ;i++)
    {
        began = i;
        if(i == point)
            break;
        if(result[i] != 0)
            break;
    }
    for(int i = 129; i >= 0; i--)
    {
        aim = i;
        if(result[i] != 0)
            break;
        if(i == point-1)
            break;
    }
    for(int i = aim; i >= began; i--)
    {
        if(i == point-1)
            cout << '.';
        cout << result[i];
    }
    cout << endl;
}
int main()
{
    char a[15];
    int n;
    while(~scanf("%s%d",a,&n))
    {
        memset(result,sizeof(result)); //初始化
        int point; //记录小数点位置
        int index=4; //记录下标
        multiplier = 0;
        //处理乘数的值,点的位置,结果数组的初始值
        for(int i=0;i<6;i++)
        {
            if(a[i] == '.')
                point = i;
            else
            {
                multiplier = multiplier*10+(a[i]-'0');
                result[index--] = a[i]-'0';
            }
        }
        //处理最终点的位置
        point = 5 - point;
        point = point * n;
        //连乘
        for(int i = 1; i < n; i++)
            multiply();
        //for(int i=0;i<= 50;i++)
            //cout << result [i];
        //cout << endl;
        output(point);
    }
    return 0;
}

发现以上代码在HDU1063并过不了。

现在重新编写了一份代码,已AC:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int N = 130;

int result[N];
char real[N];
char s[10];
int main()
{
    int n;
    while(~scanf("%s",s))
    {
        memset(result,sizeof(result));
        scanf("%d",&n);
        int temp[N];
        int len = strlen(s);
        int point_id = -1;      //小数点后面数字的数量
        int k = 0;
        int a = 0,b = 1;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != '.')
            {
                result[k++] = s[i]-'0';
                a += (s[i]-'0')*b;
                b *= 10;
            }
            else
                point_id = k;
        }
        if(point_id != -1)
            point_id = point_id*n;
        printf("%d\n",point_id);
        n--;
        while(n--)
        {
            memset(temp,sizeof(temp));
            int add = 0;
            for(int i = 0; i < N; i++)
            {
                int x = a*result[i];
                printf("%d x\n",x);
                int g = 0;
                while(x)
                {
                    int f = temp[i+g]+x;
                    x = f/10;
                    temp[i+g] = f%10;
                    g++;
                }
            }
            for(int i = 0; i < N; i++)
                result[i] = temp[i];
        }
        k = 0;
        int flag = 0;
        for(int i = 0; i < N; i++)
        {
            if(i == point_id)
            {
                real[k++] = '.';
                point_id = -1;
                flag = 1;
            }
            if(result[i] == 0 && point_id != -1 && !flag)
                continue;
            real[k++] = result[i]+'0';
            flag = 1;
        }
        real[k] = '\0';
        puts(real);
        flag = 0;
        for(int i = k-1; i >= 0; i--)
        {
            if(i == 0 && real[i] == '.')
                continue;
            if(real[i] != '0')
            {
                printf("%c",real[i]);
                if(flag == 0)
                    flag = 1;
            }
            else if(flag == 1 && real[i] == '0')
                printf("%c",real[i]);
        }
        puts("");
    }
    return 0;
}

本文来自网络,不代表站长网立场,转载请注明出处:https://www.tzzz.com.cn/html/shuju/2021/0525/6416.html

作者: dawei

【声明】:站长网内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。
联系我们

联系我们

0577-28828765

在线咨询: QQ交谈

邮箱: xwei067@foxmail.com

工作时间:周一至周五,9:00-17:30,节假日休息

返回顶部