java 阶乘从偶数开始

k2fxgqgv  于 2022-11-20  发布在  Java
关注(0)|答案(5)|浏览(168)

我想收集[a,b]范围内所有阶乘以偶数开头的数字。

例如:

a = 1, b = 10

答案:

2 3 4 8

说明:

2! = 2 = starts with even
3! = 6 = starts with even
4! = 24 = starts with even
8! = 40320 = starts with even

限制式:

1 ≤ a,B ≤ 100
下面是我的代码:

List<Integer> process(int a, int b) {
    long base = i;
    for(int i=1; i<=a; i++) base *= i;
    
    if(even(base)) list.add(a);
    
    for(int i=a+1; i<=b; i++) {
        base *= i;
        if(even(base)) list.add(i);
    }
    return list;
}

boolean even(long k) {
    int z = ("" + k).charAt(0) - '0';
    return z % 2 == 0;
}

这是几天前在一个编码挑战中问到的,当我实现这个的时候,15个测试用例中有6个隐藏的测试用例失败了。我不能找到这个代码中的bug是什么。

00jrzges

00jrzges1#

我使用BigInteger来解决这个问题。为了加速这个过程,我将随后的阶乘计算记下来,作为未来计算的起点。我还建立了一个记录来保存相关数据,以便于这个过程。
也许有一种数学方法可以预测第一个数字的奇偶性,但就目前而言,这似乎是可行的。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class FactorialStartsWithEven {

    public static void main(String[] args) {
       
        List<Integer> list = getForRange(1, 20);
        System.out.println(list);
    }

印刷品
第一次
声明为保存数据的记录

record Fact(BigInteger fact, int n, boolean parity) {}

初始化计算阶乘的备忘录

static List<Fact> computed = new ArrayList<>(List.of(
            new Fact(BigInteger.ONE, 0, false),
            new Fact(BigInteger.ONE, 1, false),
            new Fact(BigInteger.TWO, 2, true)));
  • 如果该值已经存在,只需查找它并返回布尔值。
  • 否则,获取最后计算的值并开始计算直到n,在计算时将每个阶乘添加到列表中。
public static boolean factorialStartsWithEven(int n) {
        if (n < computed.size()) {
            return computed.get(n).parity;
        }
        Fact f = computed.get(computed.size()-1);
        BigInteger b = f.fact;
        Fact result = null;
        for (int k = f.n+1; k <= n; k++) {
            b = b.multiply(BigInteger.valueOf(k));
            result = new Fact(b, k, Character.digit(b.toString().charAt(0),10) % 2 == 0);
            computed.add(result);
        }
        return result.parity;
    }
vlf7wbxs

vlf7wbxs2#

这是一个肮脏的解决方案-我不是真的推荐它,只是在这里发布它的兴趣-但较低值的数字将有相对较小的影响,第一位数字。

import java.math.BigInteger;
public class Main {  
  public static void main(String args[]) {
    long acc = 1;
    int limit = (int)Math.log10(Long.MAX_VALUE);
    for (int i = 1; i <= 100; i++){
      int accLength = (int)Math.log10(acc) + 1;
      int iLength = (int)Math.log10(i) + 1;
      //System.out.printf("Acc :%s, accLength : %s, i : %s, iLength : %s \n", acc, accLength, i, iLength);
      if (accLength + iLength >= limit){
        //System.out.printf("Adjusting %s by %s", acc, iLength);
        acc = acc / (long)(Math.pow(10, iLength));
        //System.out.println(" becomes: " + acc);
      }
      acc = acc * i;
      System.out.printf("acc is %s\n", acc);
    }
  }
}

原谅我的草率,我已经很久没有在Java工作了。
不管怎样,这个解决方案是基于这样一个事实,即尾随数字对前导数字的贡献不大,所以--不要告诉任何人我说这样做是可以的--我只是丢弃它们,除以10的某个幂,并且只保留long中我能容纳的数量。
实际上,我并不确定这个公式的准确性能维持多久,我很好奇是否有人想对此发表意见,但我怀疑这个公式会一直保持到i(我们要取其阶乘的东西)的数字相对于long的长度变得显著为止。

nbysray5

nbysray53#

下面的Ruby代码可以为您的参数解决这个问题。我不懂Java,但它很容易翻译。当您的输入参数太小(特别是b〈= 100)时,解决这个困难的泛型问题没有任何意义。我的数组在87处停止,因为88!到100!都有奇数的前导数字。

def get_list(a, b)
  arr = [2, 3, 4, 8, 12, 13, 14, 16, 18, 20, 23, 24, 26, 29, 30, 31, 32, 33, 34, 39, 40, 43, 44, 47, 49, 52, 53, 54, 57, 58, 60, 65, 68, 71, 72, 73, 75, 79, 82, 85, 86, 87]
  
  list = []
  
  arr.each do |val|
    list.append(val) if a <= val && val <= b
  end
  
  return list
end

> get_list(10, 20)
=> [12, 13, 14, 16, 18, 20]
whhtz7ly

whhtz7ly4#

不能用Java测试,所以我用Python。下面是代码。递归公式基于被除数(y)除以除数(d)的商(q)和余数(r)的计算。除数(d)是10的递增幂。对应的Python指令:q,r=divmod(y,d)。
当然我不得不使用浮点数!它在Java中最多工作n=34!下面是Java代码的改进版本。

static void getFirstEvenDigits(int n) {
    int q = 1;
    float r = 0;
    float d = 1, y;
    for (int i = 1; i <= n; i++) {
        y = (q * d + r) * i;
        q = (int) (y / d);
        while (q >= 10) {
            d = d * 10;
            q = (int) (y / d);
        }
        r = y % d;
        if (q % 2 == 0) {
            print("i:"+i+", q:"+(int)q+", y:"+y);
        }
    }
}

结果是:

i:2, q:2, y:2.0
i:3, q:6, y:6.0
i:4, q:2, y:24.0
i:8, q:4, y:40320.0
i:12, q:4, y:4.790016E8
i:13, q:6, y:6.2270208E9
i:14, q:8, y:8.7178289E10
i:16, q:2, y:2.09227885E13
i:18, q:6, y:6.4023735E15
i:20, q:2, y:2.43290202E18
i:23, q:2, y:2.5852017E22
i:24, q:6, y:6.2044845E23
i:26, q:4, y:4.032915E26
i:29, q:8, y:8.841763E30
i:30, q:2, y:2.6525289E32
i:31, q:8, y:8.2228397E33
i:32, q:2, y:2.6313087E35
i:33, q:8, y:8.6833185E36
i:34, q:2, y:2.9523282E38
i:35, q:0, y:Infinity

这是Python的结果,注意到在i=34之前,有一个完美的对应关系。

2 2 2.0
3 6 6.0
4 2 24.0
8 4 40320.0
12 4 479001600.0
13 6 6227020800.0
14 8 87178291200.0
16 2 20922789888000.0
18 6 6402373705728000.0
20 2 2.43290200817664e+18
23 2 2.585201673888498e+22
24 6 6.204484017332394e+23
26 4 4.0329146112660565e+26
29 8 8.841761993739702e+30
30 2 2.6525285981219107e+32
31 8 8.222838654177922e+33
32 2 2.631308369336935e+35
33 8 8.683317618811886e+36
34 2 2.9523279903960416e+38
39 2 2.0397882081197444e+46
40 8 8.159152832478977e+47
43 6 6.041526306337383e+52
44 2 2.658271574788449e+54
47 2 2.5862324151116818e+59
49 6 6.082818640342675e+62
52 8 8.065817517094388e+67
53 4 4.2748832840600255e+69
54 2 2.308436973392414e+71
57 4 4.0526919504877214e+76
58 2 2.3505613312828785e+78
60 8 8.32098711274139e+81
65 8 8.247650592082472e+90
68 2 2.4800355424368305e+96
71 8 8.504785885678623e+101
72 6 6.1234458376886085e+103
73 4 4.4701154615126844e+105
75 2 2.48091408113954e+109
79 8 8.946182130782976e+116
82 4 4.753643337012842e+122
85 2 2.81710411438055e+128
86 2 2.4227095383672734e+130
87 2 2.107757298379528e+132
bqujaahr

bqujaahr5#

比你想的要简单。
1.从a循环到B
1.计算循环索引的阶乘
1.检查生成的索引的第一个字符是否为偶数,并将其添加到列表中
1.打印清单

private static List<Integer> process(int a, int b)
{
    List<Integer> list = new ArrayList<>();
    for (int i = a; i <= b; i++)
    {
        final int factorial = calcFactorial(i);
        if (factorialStartsWithEven(factorial))
            list.add(i);
    }
    return list;
}

private static boolean factorialStartsWithEven(int factorial)
{
    final String strVal = String.valueOf(factorial);
    final int intVal = Integer.valueOf(strVal.charAt(0));
    return intVal % 2 == 0;
}

private static int calcFactorial(int n)
{
    if (n == 0)
        return 1;
    return (n * calcFactorial(n - 1));
}

相关问题