大整数问题-阿里云开发者社区

开发者社区> 开发与运维> 正文

大整数问题

简介:
题目描述:有一个k(1≤k≤80)位的十进制正整数n,设计一个程序,找到满足条件:P3+ P2+3P≤n的P的最大值。

测试用例:

输入:

1000000000000001000000000000003000000000000001

输出:

100000000000000

复制代码
#include <iostream>
#include <string>
using namespace std;
#include "decnum.h"

decnum n,p;
int k;
char succ(char num)
{//后继数字
    if (num=='9')
    {
        num = '0';
    }
    else
        ++num;
    return num;
}
char pred(char num)
{//前一个数字
    return --num;
}
bool IsOk(const char* temp,int size)
{//判断是否当前值符合条件
    decnum num(temp,size);
    decnum sum = pow(num, 3)+pow(num,2)+(num*3);
    if (sum>n)
    {//太大了
        return false;
    }
    return true;
}

void search()
{
    char* temp = new char[k];
    int i;
    //初始化都是0
    for (i=0;i<k;++i)
    {
        temp[i] = '0';
    }
    temp[i] = '\0';
    for (i=0;i<k;++i)
    {
        do
        {
            //尝试这一位
            temp[i] = succ(temp[i]);
            if (temp[i]=='0')
            {//此位置从0到9都尝试过了
                break;
            }
        }
        while(IsOk(temp,k));
        //回退到前一位合法值
        temp[i] = pred(temp[i]);
    }
    //输出结果
    p = decnum(temp,k);
    cout<<p<<endl;
}
int main()
{
    string line;
    getline(cin,line);
    n = decnum(line.c_str(), line.length());
    k = line.length();//位数
    search();
    cout<<n<<endl;
    return 0;
}
复制代码


本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2008/11/17/1335239.html,如需转载请自行联系原作者

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章