在不计算值的情况下对 String 中提供的大数字列表进行排序

Question

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

Answer 1

来自：

I need somehow to check, which is greater without having these values because there is a certain time limit for the program to complete.

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

例如计算值的对数：

对于“power”，很简单：log(x^y) = y * log(x)
对于“阶乘”，可以使用log(x!) = Ramanujan's approximation to factorial

或者，如 :

There is no need of approximation. Use log(x!) = log(x)+log(x-1) + ... + log(1). Since x is at most 1000, precompute the cumulative sum till log(1000).

Answer 2

这是上述问题的 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;
}

在不计算值的情况下对 String 中提供的大数字列表进行排序

Sorting list of big numbers provided in String without calculating their values

java

sorting

math

factorial

exponential