1

次のコードは、lとの間の合計数を検索することを目的としていますr(複数のテスト ケースの場合t)。このコードは完全に実行されrますが、100000 を超えると非常に遅くなります。より良い代替案を提案できる人はいますか?

#include <iostream>
#include <algorithm>
using namespace std;
long long int nd(long long int x, int n) //return the digit at a particular index    staring with zero as index for unit place
{
while (n--) {
    x /= 10;
}
return (x % 10);
}
int ng(long long int number) //returns total number of digits in an integer
{
int digits = 0;
if (number < 0) digits = 1;
while (number) {
    number /= 10;
    digits++;
}
return digits;
}

int main()
{
int t;
cin>>t;
long long int l[t], r[t], c;
for(long long int j=0;j<t;j++)
{
    cin>>l[j]>>r[j];
}
for(long long int k=0;k<t;k++)
{    
  long long int sum=0;
  long long int t=0;

  for(long long int i=l[k];i<=r[k];i++)
  {
   while(t<ng(i))
   {
       c=nd(i,t);
       if((c%2)==0)
       {
           ++sum;
           break;
       }
       ++t;
    }
   t=0;    
  }
 cout<<sum<<endl;
}    
cin.ignore();
cin.get();
return 0;
}
4

7 に答える 7

2

基本的な考え方は、数値の各桁をループして偶数かどうかを確認することです。そうであれば、積全体は偶数であり、残りの桁を確認する必要はありません。

あなたのコードの問題は、数値を何度も実行して index の数字を探していることですi。途中で均等性をチェックしたら、数値の桁を単純に実行する必要があります。

アルゴリズムを実装するわかりやすい Go コードを次に示します。

package main

func iseven(num int) bool {
    for num > 0 {
        digit := num % 10
        if digit&1 == 0 {  # same as digit%2 == 0, only simpler
            return true
        }
        num /= 10
    }
    return false
}

func main() {
    sum := 0
    for n := 1; n < 1000000; n++ {
        if iseven(n) {
            sum++
        }
    }
    println(sum)
}

私のマシンでのパフォーマンス:

λ time go run main.go
980469
go run main.go  0.05s user 0.01s system 81% cpu 0.073 total

アップデート

膨大な数を処理する必要がある場合は、より効率的な方法を使用できます。

それらの桁の積を持つ数字を奇数ドッズ数と呼びましょう。だから、135ドッド数です、そうで134はありません。同様に、数字の積が偶数になる数字はdevenと呼ばれます。偶数134も同様です。

前に述べたように、奇数桁で構成される数字のみがドッドです。1したがって、数字を列挙する代わりに、数字、3、5、7、およびで構成される数字を数えることができます9。integerN > 1の場合、正確に10^N - 10^(N-1)数字を持つN数字があります。そして、それらの数のうち、5 ^ Ndodd は dodd であり、したがって10^N - 10^(N-1) - 5^Ndeven です。

leftこのアプローチは、との境界の間にいくつの dodd 数があるかを数え、とrightの間の数の合計数からその数を減算することです。十数だけを数えることもできますが、それは少しトリッキーです。leftright

事実上、このアプローチでは、数字ではなく数字をループします。Python での私の実装1では、とint("1" * 100000)( 10000桁の数字) の間の十数の数を 1 秒未満で計算できます。

于 2013-05-20T10:56:30.647 に答える
0

以下に基づく最適化が機能します。

2つの数を掛け合わせると、ルールに従って奇数/偶数が得られます

even * even = even
odd * even = even * odd = even
odd * odd = odd

したがって、番号番号の最後の桁のみを追跡する必要があります。

私はこれをコーディングするには年を取りすぎていますが、0 から 9 までの数字だけを考慮する必要があるため、非常に迅速に処理できると思います。

于 2013-05-20T10:30:50.573 に答える
0

あなたのコードが何をしているのかわかりませんが、基本原則は単純です:

  • value % 10は下位桁です
  • value /= 10下位桁を削除します
  • いずれかの数字が偶数の場合、積は偶数になります。

これにより、値ごとに非常に単純なループが発生するはずです。(特殊なケースが必要な場合があり0ます。)

さらなる最適化が可能です: すべての偶数は偶数の桁の積を持つため、2 のステップで反復し、後で偶数の数 (範囲の半分) を追加できます。これにより、速度が 2 倍になるはずです。

もう 1 つの最適化: 下位桁が偶数の場合、数値自体も偶数であるため、下位桁を抽出してテストする必要はありません。

于 2013-05-20T10:38:16.027 に答える
0

たとえば、10…、12…、14…、…、2…、30… で始まるすべての数字は、数字の偶数積を持つことがすでに知られています。したがって、左 (より有効な桁) から開始し、ブロック単位でカウントします。桁の積が奇数になる数はわずかしかなく (1111111111 など)、ここだけはさらに深く掘り下げる必要があります。

ここにいくつかの擬似コードがあります:

int count(String prefix, int digits) {
  int result = 0;
  if (digits == 0)
    return 0;
  for (int d = 0; d < 10; d++) {
    if (d%2 == 0)
      result += 10**(digits-1);
    else
      result += count(prefix . toString(d), digits-1);
  }
  return result;
}

count("2", 8)これは、200000000 から 299999999 までの間隔のカウントを取得するように呼び出されます。

ブロック全体 (つまり、すべてd桁の数字)の Haskell 実装を次に示します。

blockcount :: Integer -> Integer
blockcount 0 = 0
blockcount d = 5 * 10^(d-1) + 5 * blockcount (d-1)

例えば、blockcount 1000と計算されます999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999906673638149678112100991045527618283038290855362829197537828566020403308902422436554555967290211889764040501006967575737578451247864596760515847918279606924376558933386167484972600492401409816848889950920373488688175948748520406620919482172887458489618930162114557351888053018577133904077798233708955720154383055111285253347199367163154735257073817013783479720680471050639288214933633125893456019446928186367940015517395804589878677037013049780548539009578539133163875520704796517313538234207308395257993406361095826210417788163492195444337155572607461248287214520321844365359628512231823310014460793073456057599128802632529825013737330925270323746419607062376616601895307212544139457835秒以下

範囲を適切なブロックに分割するコードを追加する必要があります。

于 2013-05-20T10:58:46.243 に答える
0

あなたができるもう一つのことは、変更することです

  while(t<ng(i))

に

int d = ng(i);
while (t < d)

したがって、 ng はループごとに 1 回だけ呼び出されます。

また、ng は単に log(number)+1 (log base 10) です。

それが速くなるかどうかはわかりませんが。

于 2013-05-20T11:08:58.983 に答える
0

確認する必要があるのは、数値の数字の 1 つが偶数かどうかだけです。もしそうなら、それは因子として 2 を持つので、偶数です。

また、自分がどこにいるのかを数字で覚えていないようです-ループでインクリメントtしてから を呼び出すたびに、それから でゼロまでカウントダウンします。これは、最悪の場合、桁数が 2 次になります。単純に数字を最初の構成桁に分割する方がよいでしょう。fornd(i,t)tnd

于 2013-05-20T10:38:36.360 に答える