java - 缩短执行时间

Question

下面的程序执行时间如何改进。 我在“递归”和“基本”函数中都使用了动态编程。 但是没有得到有效的执行时间。

问题:受害人家中有一堵 4xN 大小的墙。受害者也有无限的 在她的房子里供应尺寸为 4x1 和 1x4 的砖 block 。在每一个 配置，墙壁必须用砖 block 完全覆盖。 Gale Bertram 想知道砖 block 在墙上的排列方式总数，以便每次都能产生新的配置。 让Configuration的个数=M。

因此，他希望 Patrick 计算最多 M(即 <= M)的素数(例如 P)的个数。 您需要帮助帕特里克正确解决难题。

示例输入 输入的第一行将包含一个整数 T，然后是 T 行，每行包含一个 整数N。

示例输出 为每个测试用例打印一行输出。输出应包含 数P。 约束条件 1<=T<=20 1<=N<=40

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Solution{
    public static int[] b = new int[217287];
    public static void main(String[] args){
        Scanner stdin = new Scanner(System.in);
    int t = stdin.nextInt();
    int[] a = new int[41];
    for(int j=0;j<4;j++){
            a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
        }
        a[4] = 2;
    for(int x=0;x<t;x++){
        int n = stdin.nextInt();
        for(int i=5;i<=n;i++){
            a[i] = -1;         //initialise all value in the array as -1.
        }
        if(n<4)
            System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
        else{
                     //for n=4, possibilities = 2. This is a base case.
        int num1 = recursive(a,n);          // storing number of possibilities in num1.
        int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
        System.out.println(num2);
        }
    }
}
public static int recursive(int[] a, int n){
    if(a[n]!=-1)                             // retrieving a[n] value if already calculated.
        return a[n];
    else{
        a[n] = recursive(a,n-1) + recursive(a,n-4); // calling recursively.If we fill with a 4*1 first tile then number 
                                                    //tiles left is n-1(try visualising).If we fill 1*4 tile first
                                                    // we have n-4 tile left.
        return a[n];
    }
}
public static int prime(int n){
    int count = 0;
    if(b[n]!=0)
        return b[n];
    else{
    for(int i=2;i<=n;i++){
        if(b[i]!=0){
            count = b[i];
        }
        else{
        int flag = 0;           
        for(int j=2;j<=i/2;j++){
            if(i%j==0){
                flag = 1;
                break;
                }
            }
    if(flag==0){
        count++;
        b[i]=count;
    }
    }
    }
    return count;
    }
}

我收到以下输入的超时(超过 4 秒)。 20 35 23 25 38 4个 35 19 8个 23 35 3个 36 12 10 30 13 18 31 40 37

Answer 1

你在这里犯了 2 个主要错误(或者更确切地说，允许 2 个低效率):

1. 你在每次循环中重新初始化和计算你的 a 数组。这些不会改变，只是通过最初分配一个大小为 40 的数组来重用上次的结果(您可能还需要考虑更好的命名约定...)
2. 您没有在任务的“首要”部分使用动态规划。动态规划是关于保存中间结果以供将来使用，您只是保存答案，希望它能被再次使用(它不会被再次使用，因为 n 对于唯一的 来说是唯一的>N - 又是命名约定)

第 1 部分不太可能会增加很多时间，因为计算很简单并且 N <= 40。
第 2 部分是您搞砸的地方。除了只保存 b[n]，您还可以执行以下操作:从 1 循环到 n，用小于的素数填充 b或等于 i 其中 i 是索引。这是在单个素数检查中完成的 - 如果 i 是素数，则放入 b[i-1] 否则 b[i-1] + 1。这将意味着您只检查一个数字是否为质数每个数字一次(在您当前的实现中，您检查它 20 次)。您可以像评论中那样添加一个筛子以进一步提高性能，但上面的内容可能会提供足够的加速，在具有给定约束的普通机器上有 0.1 秒的运行时间。