-1

我下面的程序在蛮力任务中抛出了 bad_alloc。我相信它是由我的功能中的某些东西引起的，但我无法找出是什么原因造成的。有人可以帮我找出导致此错误的原因吗？问题陈述在下面，然后我的代码在下面。

问题陈述 编写一个程序，读取两个数（以 10 为基数）： N (1 <= N <= 15) S (0 < S < 10000) 然后找到并打印（以 10 为基数）前 N 个严格大于的数比 S 写成两个或多个数字基数（2 <= base <= 10）时是回文的。此问题的解决方案不需要处理大于标准 32 位的整数。

代码 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <fstream>

using namespace std;

string convert(int num, int base)
{
    int quo = 100000;
    int rem = 0;
    string to_reverse;
    while (quo > 0)
    {
        quo = num / base;
        rem = num % base;
        to_reverse += to_string(rem);
        num /= base;
    }
    reverse(to_reverse.begin(), to_reverse.end());
    return to_reverse;
}

bool is_pal(string conv_num)
{
    string reversed_conv_num = conv_num;
    reverse(reversed_conv_num.begin(), reversed_conv_num.end());
    if (reversed_conv_num == conv_num)
    {
        return true;
    }

    return false;
}

int main()
{
    ofstream fout("dualpal.out");
    ifstream fin("dualpal.in");
    int n, start;
    cin >> n >> start;
    vector<int> finals;
    int times = 0;
    for (int i = start + 1; i <= 10000; i++)
    {
        if (times == n)
        {
            for (auto x : finals)
            {
                cout << x << "\n";
            }
            break;
        }
        else
        {
            for (int j = 2; j <= 10; j++)
            {
                if(is_pal(convert(i, j)) == true)
                {
                    times++;
                    finals.push_back(i);
                }
            }
        }
    }
    return 0;
}
4

1 回答 1

0

问题是以下行：

while (quo >= 0)

x/y如果的结果是什么x < y？特别是，结果是0/x什么？猜猜，结果始终为 0，因此==您的条件中的部分将始终为真，从而导致无限循环'0'一次又一次地添加，直到没有更多的内存剩余......所以只需检查即可 > 0。

旁注：quo无论如何您都不需要该变量：

while(num)
{
    int rem = num % base;

    // OK, this won't do the trick; you try to append an integer,
    // but need a character instead!
    //to_reverse += rem;

    // if base always is smaller than or equal to 10 anyway,
    // you can just do:
    to_reverse += char('0' + rem);

    // if you want to support arbitrary bases even greater, you can do instead:
    to_reverse += "0123456789abcdefghijklmnopqrstuvwxyz"[rem];
    // (or capital letters, if you prefer)

    num /= base;
}
// and now don't reverse here - you are just interested in if the
// string is palindrome, not in correct number representation...

顺便说一句：检查是否是回文可以更有效地完成（避免复制）：

if(!s.empty())
{
    auto l = s.begin();
    auto r = std::prev(s.end());
    while(l < r)
    {
        if(*l != *r)
        {
            return false;
        }
        ++l;
        --r;
    }
}
return true;

针对问题进行编辑：

我把它改成了 quo > 0 而不是 quo >= 0，你知道为什么我的程序会输出一个巨大的整数列表吗？

for (int j = n + 1; j <= 10000; j++)
    for (int i = 0; i < n; i++)
        for (int k = 2; k <= 10; k++)

您已经创建了大量的迭代： (10000 - n) * n * 9 并且您可能会从...中得到相当多的回文数。

你可能更想要这样的东西：

while(n && start < 10000)
{
    for(int base = 2; base <= 10; ++base)
    {
        if(palindrome(start, base))
        {
            --n;
        }
    }
    ++start;
}

好的，以上不准确，您可以从内部循环中获得一些超出要求的值，留给您修复...

于 2018-07-11T15:58:58.860 回答