大数记录之，大数乘整型数nyoj832

想到了一个题目：对决二http://acm.nyist.net/JudgeOnline/problem.php?pid=832

但是发现有一道题目是相似的：http://acm.nyist.net/JudgeOnline/problem.php?pid=541

但是答案是不一样的、我的代码交到战斗力题目上会wa....终于找到答案了，是求大数的代码有漏洞。

求大数的代码：刚开始没有加k=0,找好久错误。

int cheng(int x,int p)

{

    int k;

    int t=p;

    for(int i=0,k=0;i<t;i++)

    {

        s[i]=s[i]*x+k;k=0;

        //printf("%d\n",s[i]);

        if(s[i]>=10)

        {

            if(i==p-1)

                t++;

            int h=s[i];

            s[i]=s[i]%10;

            k=h/10;

        }

    }

    return t;

}

别人的：

int cheng(int x,int p)//大数乘小数

{

    int i,j,k,t;

    int temp = 0;

    int c = 0;t=p;

    for(i=0; i<t; i++)

    {

        temp = s[i]*x+c;

        if(i==p-1&&temp>=10)

            t++;

        s[i] = temp%10;

        c = temp/10;

    }

    return t;

}

不加字符长度的：

int multiply(int x)//大数乘小数

{

    int i,j,k;

    int temp = 0;

    int c = 0;

    for(i=0; i<200; i++)

    {

        temp = ans[i]*x+c;

        ans[i] = temp%10;

        c = temp/10;

    }

}

题意都是吧一个数n分成多个数的和，让多个数的和的乘积最大！

后来发现我的思路跟那道题目不一样，我的思路是，判断能分成3尽量分成3，分不了3的分成2。比如6分成2的话为2+2+2，乘积为2^3=8，而分成3的话为3+3，乘积为3*3=9；

所以我先判断是不是奇数，是奇数的话先分成一个3，即n-3，变成偶数，然后在判断大于6的话，ans*=9；n-=6;不大于6的话是否大于4，大于四的话ans*=4;n-=4;然后大于2的情况也一样，直到为0.

果然思路是对的，是乘法搞错了。在好好看看、代码：

#include <stdio.h>

#include <string.h>

int s[100000];

int cheng(int x,int p)//大数乘小数

{

    int i,j,k,t;

    int temp = 0;

    int c = 0;t=p;

    for(i=0; i<t; i++)

    {

        temp = s[i]*x+c;

        if(i==p-1&&temp>=10)

            t++;

        s[i] = temp%10;

        c = temp/10;

    }

    return t;

}

/*int cheng(int x,int p)

{

    int k;

    int t=p;

    for(int i=0,k=0;i<t;i++)

    {

        s[i]=s[i]*x+k;

        //printf("%d\n",s[i]);

        if(s[i]>=10)

        {

            if(i==p-1)

                t++;

            int h=s[i];

            s[i]=s[i]%10;

            k=h/10;

        }

    }

    return t;

}*/

int main()

{

	int n,T;

	scanf("%d",&T);

	while(T--)

    {   scanf("%d",&n);

        memset(s,0,sizeof(s));

        int p=1;s[0]=1;

        if(n<4)

        {

            printf("%d\n",n);continue;

        }

        else

        {

            if(n%2)

            {

                p=cheng(3,p);n-=3;

            }

            while(n>0)

            {

                if(n>=6)

                {

                    p=cheng(9,p);

                    n-=6;

                }

                else if(n>=4)

                {

                    p=cheng(4,p);

                    n-=4;

                }

                else

                {

                    p=cheng(2,p);

                    n-=2;

                }

            }

        }

        for(int i=p-1;i>=0;i--)

            printf("%d",s[i]);

        printf("\n");

    }

    return 0;

}

巴特西

大数记录之，大数乘整型数nyoj832

最新文章

热门文章