1

有一个以字符串格式 x^y 或 z! 编写的数字列表。例如 1000^1000、954！525^419, 89!, 427!, 428^727... x,y,z 是区间 <0,1000> 内的随机值。该列表最多可包含 200 个这些公式。我需要根据这些公式的值以某种方式对这个给定的字符串列表进行升序排序，而不计算这些值。如何在不计算其值的情况下检查某个阶乘是否大于某个幂数？

4

2 回答 2

0

这是上述问题的 C++ 代码。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int i, n;
    vector<string> arr = {"1000^1000", "954!", "525^419", "89!", "427!", "428^727"};
    n = (int)arr.size();
    vector<pair<double, int> > ans;
    vector<double> calc(1001);

    // Since the maximum number is 1000, Pre-calculating the cumulative log sum
    for(i=2;i<=1000;i++){
        calc[i] = log10(i) + calc[i-1];
    }

    for(i=0;i<n;i++){
        string temp = arr[i];
        int x = (int)temp.size();
        if(temp[x-1]=='!'){
            int k = stoi(temp.substr(0, x-1));
            ans.push_back({calc[k], i});
        }else{
            int f = temp.find('^');
            int a = stoi(temp.substr(0, f));
            int b = stoi(temp.substr(f+1));
            ans.push_back({b*log10(a), i});
        }
    }
    sort(ans.begin(), ans.end());
    for(i=0;i<n;i++){
        cout<<arr[ans[i].second]<<" ";
    }cout<<endl;
    return 0;
}

void solve(){
    int i, n;
    vector<string> arr = {"1000^1000", "954!", "525^419", "89!", "427!", "428^727"};
    n = (int)arr.size();
    vector<pair<double, int> > ans;
    vector<double> calc(1001);

    // Since the maximum number is 1000, Pre-calculating the cumulative log sum
    for(i=2;i<=1000;i++){
        calc[i] = log10(i) + calc[i-1];
    }
    for(i=0;i<n;i++){
        string temp = arr[i];
        int x = (int)temp.size();
        if(temp[x-1]=='!'){
            int k = stoi(temp.substr(0, x-1));
            ans.push_back({calc[k], i});
        }else{
            int f = temp.find('^');
            int a = stoi(temp.substr(0, f));
            int b = stoi(temp.substr(f+1));
            ans.push_back({b*log10(a), i});
        }
    }
    sort(ans.begin(), ans.end());
    for(i=0;i<n;i++){
        cout<<arr[ans[i].second]<<" ";
    }cout<<endl;
}
于 2021-05-04T15:42:54.453 回答
0

来自评论：

我需要以某种方式检查，没有这些值会更大，因为程序完成有一定的时间限制。

要进行排序，您确实需要某种值。由于性能是问题，您可能必须计算近似值。

例如计算值的对数：

  • 对于“权力”，这很简单：log(x^y)=y * log(x)

  • 对于“阶乘”，您可以使用log(x!)= Ramanujan 对阶乘的近似

    或者，正如risingStark 所建议的那样：

    不需要近似。使用log(x!)= log(x)+log(x-1) + ... + log(1)。由于x最多为 1000，因此预先计算累积和直到log(1000)。

于 2021-05-04T15:41:28.537 回答