0

OEISで興味のあるシーケンスを見つけました。現在取り組んでいるプログラミング コンテストのソリューション用に、同じシーケンスを C++ で生成したいと考えています。

しかし、シーケンスページで指定されたプログラムがどのように機能するかを理解するのに障害がありました。

これがページに記載されているプログラムです-

(PARI) test(n)= {m=n; forprime(p=2, 5, while(m%p==0, m=m/p));                                         
return(m==1)} for(n=1, 500, if(test(n), print1(n", ")))
(PARI) a(n)=local(m); if(n<1, 0, n=a(n-1); 
            until(if(m=n, forprime(p=2, 5, while(m%p==0, m/=p)); m==1), n++); n)
(PARI) list(lim)={
lim\=1;
my(v=List(), s, t);
for(i=0, log(lim+.5)\log(5),
    t=5^i;
    for(j=0, log(lim\t+.5)\log(3),
        s=t*3^j;
        while(s <= lim,
            listput(v, s);
            s <<= 1;
        )
    )
);
vecsort(Vec(v))
};

PARI とは何かはわかりましたが、このプログラムを C++ に変換できません。C ++で同じシーケンスを生成するのに役立つ提案があれば、大歓迎です。

次のコード スニペットを使用して、C++ でシーケンスを生成しようとしました。しかし、オンライン IDE でいくつかのテストに失敗したため、その間に特定の数値が欠落していると思います。

for(int i = 0; i < 16; i++)
{
    for(int j = 0; j < 15; j++)
    {
        for(int k = 0; k < 12; k++)
        {
            std::cout<<pow(2,i)*pow(3,j)*pow(5,k)<<std::endl;
        }
    }
}

制限として 16、15、および 12 を選択しました。

4

1 に答える 1

1

ここには 3 つのプログラムがあり、それぞれが異なる目的を果たします。

1 つ目は、数値が 5-smooth かどうかをチェックします。2、3、5 で割り切れなくなるまで単純に割り、残りが 1 かどうかをテストします。

2 番目は ''n'' 番目の 5-smooth 数を生成します。最初と同じ考え方を使用して、範囲内の各数値をテストします。これは非常に非効率的です！

3 番目は、指定された境界までのすべての 5-smooth 数値を生成します。

3 番目は、あなたの状況に最も当てはまる可能性が高いと思われるため、あなたが望むものであると仮定します。(私がそのプログラムの作成者であることも役に立ちます。)

#include <iostream>
#include <vector>
#include <algorithm>

int main(void);
std::vector<long> smooth(long lim);

int main(void) {
    long lim = 1000;
    std::vector<long> v = smooth(lim);
    std::cout << "5-smooth numbers up to " << lim << ": ";
    for (std::vector<long>::iterator it = v.begin(); it != v.end(); it++) {
        std::cout << *it << ", ";
    }
    std::cout << "\n";
    return 0;
}

std::vector<long> smooth(long lim) {
    std::vector<long> v = {};
    for (long t = 1; t <= lim; t*=5) {
        for (long s = t; s <= lim; s*=3) {
            for (long n = s; n <= lim; n*=2) {
                v.push_back(n);
            }
        }
    }
    std::sort(v.begin(), v.end());
    return v;
}

もちろん、これは行ごとの変換ではありません。たとえば、PARI のように正確な対数は C++ に組み込まれていないため、対数は使用しませんでした。これは非常に高速で、1,844,674,407,370,955,161 (64 ビット マシンで実行できる最高値) までのすべての 5-smooth 数値をほんの一瞬で見つけます。

于 2016-12-17T04:30:58.330 に答える