-4

以下のコードを高速化したい。実行に時間がかかり、次のエラーが発生しました。

警告: FOR ループ インデックスが大きすぎます。2147483647 に切り捨てます。

3^100以上の計算をしなければならないので・・・無理ですか？

function sodiv = divisorSum(n)
    sodiv = 0;
    for i=1:n
        if (mod(n,i) == 0)
            sodiv = sodiv + i;
        end
    end
end

function finalSum1 = formular1(N,n)
    finalSum1 = 0;
    for k = 1:N
       finalSum1 = finalSum1 + (divisorSum(k) * divisorSum(3^n*(N-k)));
    end
end

Nv=100;
nv=[1:20];

for i=1:length(nv)
    tic;
    nfunc1(i)=formular1(Nv,nv(i));
    nt1(i)=toc;
    sprintf('nt1 : %d finished, %f', i,nt1(i))
end

このコードの目的は、アルゴリズムの計算時間をチェックすることです。

4

2 に答える 2

4

アルゴリズムは一般的すぎて、この特定の問題には非効率的です。

3^100 の約数を合計したいのですね。しかし、これらの約数は簡単に決定されます。

S = 1 + 3 + 3^2 + 3^3 + ... + 3^100、等比級数。

3*S = 3 + 3^2 + ... + 3^101

減算

2*S = 3^101 - 1

S = (3^101 - 1)/2

于 2012-08-06T06:32:56.603 に答える
3

このコードは非常に非効率的であるため、決して終了しません。

たとえば、すべての約数の数を数え、1 から N までのすべての数を調べてカウントする関数があります。しかし、効率的な式を使用すると、それははるかにマスターになります。

素数a^bである数の約数を合計する必要があるとしましょう。aa^b を計算して form に行く代わりに、これらの数だけが約数であるため、 go の1 to a^b方が良いことがわかります 。a^1, a^2, a^3, ..., a^nしかし、さらに進んで、これらの数の合計が等比数列の合計であることを観察することができるので、約数は次のようになります。

総除数、 a^b = (a^(b+1)-1) / (a-1)

于 2012-08-06T06:40:26.937 に答える