Cálculo del número de números primos para resolver el rompecabezas -- java campo con optimization campo con algorithm campo con programming-challenge campo con dynamic-programming camp codereview Relacionados El problema

Calculating the number of prime numbers to solve the puzzle


2
vote

problema

Español

¿Cómo puede mejorar el siguiente tiempo de ejecución del programa? He usado la programación dinámica en la función "recursiva", así como la función "Prime", pero no recibo el tiempo de ejecución eficiente.

Hay una pared de tamaño 4xn en la casa de la víctima donde. La víctima También tiene un suministro infinito de ladrillos de tamaño 4x1 y 1x4 en ella. casa. En cada configuración, la pared tiene que estar completamente cubierta. utilizando los ladrillos. Gale Bertram quiere saber el número total de formas en el que se pueden organizar los ladrillos en la pared para que un nuevo La configuración surge cada vez.

Deje el número de configuración = $ M $.

Entonces, quiere que Patrick calcule el número de números primos (Diga $ P $) Hasta $ M $ (i.e. $ & lt; = m $). Usted está obligado a ayudar a Patrick correctamente resolver el rompecabezas.

Entrada de muestra

La primera línea de entrada contendrá un entero $ t $ seguido de $ t $ líneas que contiene un entero $ n $.

Salida de muestra

Imprima exactamente una línea de salida para cada caso de prueba. El La salida debe contener el número $ P $.

restricciones

$ 1 & lt; = t & lt; = 20 $
$ 1 & lt; = n & lt; = 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]; //array initialized before because the value remains same.         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;         }     } }   

Tengo un tiempo de espera (más de 4s) para la siguiente entrada:

  20 35 23 25 38 4 35 19 8 23 35 3 36 12 10 30 13 18 31 40 37   
Original en ingles

How can the following program execution time improved? I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time.

There is a wall of size 4xN in the victim's house where. The victim also has an infinite supply of bricks of size 4x1 and 1x4 in her house. In every configuration, the wall has to be completely covered using the bricks. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time.

Let the number of Configuration = \$M\$.

So, he wants Patrick to calculate the number of prime numbers (say \$P\$) up to \$M\$ (i.e. \$<= M\$). You are required to help Patrick correctly solve the puzzle.

Sample Input

The first line of input will contain an integer \$T\$ followed by \$T\$ lines each containing an integer \$N\$.

Sample Output

Print exactly one line of output for each test case. The output should contain the number \$P\$.

Constraints

\$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]; //array initialized before because the value remains same.         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;         }     } } 

I got a timeout (more than 4s) for the following input:

20 35 23 25 38 4 35 19 8 23 35 3 36 12 10 30 13 18 31 40 37 
              
     
     

Lista de respuestas

4
 
vote
  import java.io.*; import java.util.*; import java.text.*; import java.math.*;   

Limpia esas importaciones. Importarlo Todo en un paquete es una mala idea, ya que podría conducir fácilmente a los conflictos entre las mismas clases nombradas. También es difícil ver lo que realmente se usa.


No tiene un paquete definido, defina uno.


  class Solution{   

Eso es un nombre de clase no muy bueno. Las clases deben ser nombradas después de qué propósito sirven, o qué propósito los métodos contenidos dentro de la clase sirven.


  public static int[] b = new int[217287];   

Aquí está la regla definitiva para denominación variable:

Solo tiene derecho a usar los nombres de una variable de carácter si está tratando con dimensiones (x, y, z). El segundo mejor es que se le permite usar un carácter de variable de caracteres en el simple for Loops (i, j, k) ... pero el último punto está en proceso de debate y no debe ser el caso.

y aquí hay una guía simple para nombrar variables:

Variables de nombre después de lo que contienen. No se le permite usar variables de carácter, excepto cuando se trata de dimensiones.

¿Por qué es tan importante nombrar variables después de lo que hacen? Bueno, rápido, dime que hace este código: if (b[n] != 0) .


  for(int x=0;x<t;x++){   

Esto es aún peor. x65544336 solo se usa para la dimensión, por lo que a menos que esté en bucle sobre la x dimensión de algo aquí, esta variable debe llamarse diferente y de acuerdo con lo que hace.


  for(int i=0;i<=n;i++){     a[i] = -1;         //initialise all value in the array as -1. }   

Solo comenta cosas que no son obvias del código. En este caso, puedo ver que la matriz se inicializa a -1 ... o podría verla si las variables tendrían nombres de ajuste:

  for (int index = 0; index < a.length; index++) {     a[index] = -1; }   

NOTA QUE a sigue siendo un buen nombre. Además, lo que no veo en este punto en este punto es por qué se inicializa a ese valor. Entonces, si para comentar algo, entonces el por qué es interesante.


  class Solution{ 0  

No debe omitir los llaves de class Solution{ 1 S y class Solution{ 2 s, incluso una línea una vez. Puede ser muy confuso a largo plazo.


  class Solution{ 3  

¿Por qué su 99887766655443314 sucursales no sangradas?


  class Solution{ 5  

Ese es otro no muy buen nombre. Las funciones deben ser verbos, no adjetivos. Tienen una función, no un estado, y el nombre debe reflejar esa función.


No tiene javadoc allí, arreglar eso.


Considere el uso de un formato de código, y luego considere usar más líneas en blanco y más espacio en blanco para facilitar el código legible.

 
import java.io.*; import java.util.*; import java.text.*; import java.math.*; 

Clean up those imports. Importing everything in a package is a bad idea, as it might easily lead to conflicts between same named classes. Also it is hard to see what is actually used.


You ain't got a package defined, define one.


class Solution{ 

That's a not very good class name. Classes should be named after what purpose they serve, or what purpose the methods contained within the class serve.


public static int[] b = new int[217287]; 

Here is the ultimate rule for variable naming:

You're only entitled to use one character variable names if you're dealing with dimensions (x, y, z). Second best is you're allowed to use one character variable names in simple for loops (i, j, k)...but the last point is up for debate and it should not be the case.

And here is a simple guide for naming variables:

Name variables after what they contain. You're not allowed to use one character variables except when dealing with dimensions.

Why is it so important to name variables after what they do? Well, quick, tell me what this code does: if (b[n] != 0).


for(int x=0;x<t;x++){ 

This is even worse. x is normally only used for the dimension, so unless you're looping over the x dimension of something here, this variable should be called different and according to what it does.


for(int i=0;i<=n;i++){     a[i] = -1;         //initialise all value in the array as -1. } 

Only comment things that are not obvious from the code. In this case I can see that the array is initialized to -1...or I could see it if the variables would have fitting names:

for (int index = 0; index < a.length; index++) {     a[index] = -1; } 

Note that a is still not a good name. Also what I do not see from the code at this point is why it is initialized to that value. So if to comment something, then the why is interesting.


if(n<4)     System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0. else{ 

You should not omit braces from ifs and fors, even one line once. It can be very confusing in the long run.


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

Why are your else branches not indented?


public static int recursive(int[] a, int n){ 

That's another not very good name. Functions should be verbs, not adjectives. They have a function, not a state, and the name should mirror that function.


You have no JavaDoc in there, fix that.


Consider using a code formatter, and then consider using more blank lines and more whitespace to make the code easier readable.

 
 
1
 
vote

primero, arregla su sangría cerca de una línea única si las declaraciones que tienen declaraciones más . Están haciendo que su código sea difícil de leer y , cuando durante la fijación del formato, descubrí que realmente funcionó de manera diferente).

y hay class Solution{ 6 atascado allí ... Supongo que no pertenece allí.

quieto. Echemos un vistazo a su parte superior más para el bucle:

  class Solution{ 7  

Dado que es un problema de rendimiento, una mejora que tendría es reorganizar el orden de las operaciones.

lo que haces es ...

  class Solution{ 8  

Eso es solo un desperdicio. Hagamos esto en lugar:

  class Solution{ 9  

ahora, veamos lo que definí como "cosas".

  public static int[] b = new int[217287]; 0  

lo hace ...

  public static int[] b = new int[217287]; 1  

Podrías eliminar las tiendas locales aquí. No necesitas esos. Sin embargo, más importante, cuando combinamos los dos ...

  public static int[] b = new int[217287]; 2  

Estamos escribiendo DOBLE! Vamos a no.

  public static int[] b = new int[217287]; 3  

o, en código ...

  public static int[] b = new int[217287]; 4  

Tenga en cuenta que esto es solo yo mirando el rendimiento y no la legibilidad, ni siquiera la lógica. Incluso podría ser el caso de que el JVM sea tan inteligente como yo y hace todo esto para usted. Además, puede obtener más de una velocidad al mirar los bucles más internos.

 

First off, fix your indentation near single line if statements that have else statements. They're making your code hard to read and I even made a mistake interpretting the bottom most function (I thought it would return after a single iteration, went to go to great lengths to explain that's not how things would work and that it was broken, when during fixing the formatting, I found out it actually worked differently.)

And there's enter code here stuck in there... I assume it doesn't belong there.

Still. Let's take a look at your top most for loop:

        int n = stdin.nextInt();         int[] a = new int[n+1];`enter code here`         for(int i=0;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(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 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);         } 

Since it's a performance issue, one improvement I would have is to reshuffle the order of operations.

What you do is...

read int declare array set values in array if(n<4){     print 0 } else {     stuff } 

That's just a waste. Let's do this instead:

read int if(n<4){     print 0     continue } declare array set values in array stuff 

Now, lets look at what I defined as "stuff".

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

It does...

set array index 0-3 to 1 set array index 4 to 2 calculate recursive calculate prime print prime 

You could remove the local stores here. You don't need those. More importantly though, when we combine the two...

read int if(n<4){     print 0     continue } declare array set values in array set array index 0-3 to 1 set array index 4 to 2 calculate recursive calculate prime print prime 

We're writing double! Let's not.

read int if(n<4){     print 0     continue } declare array set array index 0-3 to 1 set array index 4 to 2 set values in array, from index 5 to and including index n to -1 calculate recursive calculate prime print prime 

Or, in code...

        int n = stdin.nextInt();         if(n < 4){             System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.             continue;         }         int[] a = new int[n+1];         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 i=5;i<=n;i++){             a[i] = -1;         //initialise all remaining value in the array as -1.         }         System.out.println(prime(recursive(a,n))); 

Note that this is just me looking at performance, and not readability, or even logic. It might even be the case that the JVM is just as smart as me and does all of this for you. Additionally, you might get more of a speed up by looking at the more inner loops.

 
 
 
 

Relacionados problema

3  Problema de Knapsack01, escrito en C #  ( Knapsack01 problem written in c ) 
¿Este código está escrito en un estilo decente? Aprecie algunos comentarios :) ShopItemCategory4 ...

11  Substitution Cipher Algorithm Rendimiento Boost  ( Substitution cipher algorithm performance boost ) 
Este algoritmo está destinado a leer una cadena de números en una entrada, un código de cifrado de sustitución ingenuo (A = 1, B = 2, ..., z = 26) y salga de ...

6  UVA 100: "El problema 3n + 1"  ( Uva 100 the 3n 1 problem ) 
He resuelto el problema de la UVA 100: el problema 3n + 1 . En resumen, la tarea era escribir un programa que calcula un máximo de longitudes de secuencia de...

8  (Codewars kata) Memoised Log Cutting  ( Codewars kata memoised log cutting ) 
(No estoy seguro del nombre oficial de CS para el problema en cuestión, por lo que simplemente le di el nombre del kata). Problema Clear Cutter's necesi...

11  Desafío de optimización para colorear por casa  ( House coloring optimization challenge ) 
Tengo una entrevista en las próximas semanas, y estoy eligiendo ser entrevistado en Python. Comencé a programar en Python (fue hace unos cuatro años), por lo ...

56  Solución de mochila de programación dinámica  ( Dynamic programming knapsack solution ) 
Escribí una solución a la problema de mochila en Python, utilizando un algoritmo de programación dinámico de abajo hacia arriba. Calcula correctamente el va...

4  Calculando la suma de elementos de matriz a la izquierda y derecha  ( Calculating the sum of array elements to the left and right ) 
Estoy usando C ++ para codificar la siguiente lógica: Se da una matriz. Tenemos que atravesar la matriz de tal manera que la suma de elementos de matriz a ...

8  Manejo del estado compartido entre muchos elementos en angular  ( Handling shared state among a lot of elements in angular ) 
Estoy trabajando en un proyecto en angular donde tengo un número de objetos de datos similares. Cuando hace clic en alguien de ellos, su estado y la cantidad ...

7  LEETCODE: BURCO BALLOONS C #  ( Leetcode burst balloons c ) 
https://leetcode.com/problems/burst-balloons/ Dado n globos, indexados de 0 a 9988777665544332 , cada globo está pintado con Un número en él repre...

2  Tiempo de alta ejecución en el programa de partición numérico en Python 2.7  ( High execution time on number partitioning program in python 2 7 ) 
Estoy escribiendo un programa para contar solo las particiones de un número con distinta partes . Estoy usando un enfoque de abajo hacia arriba para la progr...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos