大整数问题

  1. 云栖社区>
  2. 博客>
  3. 正文

大整数问题

嗯哼9925 2018-01-08 12:53:13 浏览559
展开阅读全文
题目描述:有一个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,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
嗯哼9925
+ 关注