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。对于 integer N > 1，恰好有数字10^N - 10^(N-1)具有N数字。在这些数字中，5 ^ N是多奇的，因此10^N - 10^(N-1) - 5^N是奇偶的。

left方法是计算和边界之间有多少个多德数，然后从和right之间的数字总数中减去该数。您也可以只计算偶数，但这有点棘手。leftright

实际上，您将使用这种方法循环数字，而不是数字。我在 Python 中的实现1能够在一秒钟内计算出和之间的偶数个数int("1" * 100000)（一个10000位的数字）。

于 2013-05-20T10:56:30.647 回答
0

首先，请修正你的缩进

您的代码使用了太多的除法和循环，这会导致很多延迟

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);
}

这可以通过表查找轻松修复

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
{
    long long int pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
                             100000000, 1000000000, 10000000000, 100000000000,
                             1000000000000, 10000000000000, 100000000000000,
                             1000000000000000, 10000000000000000,
                             100000000000000000, 1000000000000000000};

    return ((x / pow10[n]) % 10);
}

同样，获取整数位数的 ng 函数可以更改为快速log10，无需重复除法和计数。当然，它需要一个小改动来适应 64 位数字

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;
}
于 2013-08-27T02:10:35.470 回答
0

我不知道你的代码在做什么，但基本原则很简单：

  • value % 10是低位数字
  • value /= 10删除低位数字
  • 如果任何数字是偶数，那么产品将是偶数。

这应该导致每个值的一个非常简单的循环。（您可能需要特殊情况0。）

进一步的优化是可能的：所有偶数的数字乘积都是偶数，因此您可以以 2 的步长进行迭代，然后添加偶数（范围的一半）。这应该使速度加倍。

进一步优化：如果低位是偶数，则数字本身是偶数，因此您不必提取低位来测试它。

于 2013-05-20T10:38:16.027 回答
0

您唯一需要检查的是数字中的一个数字是否是偶数。如果是，它将以 2 作为因子，因此是偶数。

你似乎也不记得你的数字在哪里——每次你t在for循环中增加，然后调用nd(i,t)，你从那个倒数t到零nd。在最坏的情况下，这是位数的二次方。最好在开始时简单地将数字分解为其组成数字。

于 2013-05-20T10:38:36.360 回答
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 的间隔的计数。

这是整个块的 Haskell 实现（即所有d位数字）：

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

例如，blockcount 1000计算为99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990667363814967811210099104552761828303829085536282919753782856602040330890242243655455596729021188976404050100696757573757845124786459676051584791827960692437655893338616748497260049240140981684888995092037348868817594874852040662091948217288745848961893016211455735188805301857713390407779823370895572015438305511128525334719936716315473525707381701378347972068047105063928821493363312589345601944692818636794001551739580458987867703701304978054853900957853913316387552070479651731353823420730839525799340636109582621041778816349219544433715557260746124828721452032184436535962851223182331001446079307345605759912880263252982501373733092527032374641960706237661660189530721255413946936秒不到35413947636

您仍然需要添加将您的范围分成合适的块的代码。

于 2013-05-20T10:58:46.243 回答
0

基于以下内容的优化将起作用：

根据规则，将两个数字相乘得到奇数/偶数

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

因此，您只需要跟踪您的号码的最后一位数字。

我太老了，无法编写这个代码，但我敢打赌它会非常快，因为你只需要考虑 0 到 9 之间的数字。

于 2013-05-20T10:30:50.573 回答
0

你可以做的另一件事是改变

  while(t<ng(i))

至

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

所以 ng 每个循环只调用一次。

ng 也只是 log(number)+1 （即以 10 为基数）

我不知道那会更快。

于 2013-05-20T11:08:58.983 回答