WallHero

TP01 Punto Uno

Sep 17th, 2020 (edited)
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class PuntoUno {
  6.    
  7.    
  8.     static int maxN = (int) 1e7;
  9.     static boolean cribe[] = new boolean[maxN+1];
  10.     static Scanner scanner = new Scanner(System.in);
  11.     static ArrayList<Integer> primesToGenerate = new ArrayList<Integer>();
  12.     static Float actualAvg = 0.0f;
  13.    
  14.     static long fastExp(long b, long e)
  15.     {
  16.         int s = 63;
  17.         long r = b;
  18.        
  19.         while(((e >> s--) & 1) == 0);
  20.         while(s >= 0)
  21.         {
  22.             r *=r;
  23.             if(((e >> s--)&1) == 1) r = r*b;
  24.         }
  25.         return r;
  26.     }
  27.    
  28.     static long fastExp(long b, long e, long m) {
  29.         int s =63;
  30.         long r = b;
  31.        
  32.         while(((e >> s--) & 1) == 0);
  33.         while(s >= 0)
  34.         {
  35.             r = (r*r)% m;
  36.             if(((e >> s--)&1) == 1) r = (r*b)%m;
  37.         }
  38.         return r;
  39.     }
  40.    
  41.     static boolean isPrimeProb(long n, int a)
  42.     {
  43.         if(n == a) return true;
  44.         long s = 0, d = n-1;
  45.         while((d%2) == 0)
  46.         {
  47.             s++;
  48.             d/=2;
  49.         }
  50.         long x = fastExp(a, d, n);
  51.         if((x== 1) || (x+1 == n)) return true;
  52.         for(int i = 0; i < s-1; i++)
  53.         {
  54.             x = fastExp(x, 2, n);
  55.             if(x == 1) return false;
  56.             if(x+1 == n) return true;
  57.         }
  58.         return false;
  59.     }
  60.    
  61.     static boolean rabin(long n)
  62.     {
  63.         if(n == 1) return false;
  64.         int tests[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
  65.         for(int t : tests)
  66.         {
  67.             if ( t == n ) return true;
  68.             if(!isPrimeProb(n, t)) return false;
  69.         }
  70.         return true;
  71.     }
  72.    
  73.    
  74.    
  75.     static long forceReadPositiveLong(String message, int op)
  76.     {
  77.         long n = 0;
  78.         while(true)
  79.         {
  80.             try
  81.             {
  82.                 System.out.println(message);
  83.                 n = Long.parseLong(scanner.next());
  84.                 if(op == 0) // Se carga el array de múltiplos de mil
  85.                 {
  86.                     if(n!= 0 && n%1000 == 0) return n;
  87.                     System.out.println("N debe ser múltiplo de 1000");
  88.                     continue;
  89.                 }
  90.                 else if(op == 1) // Se carga el array de  primos.
  91.                 {
  92.                     if(n > 1 &&  ((n<= maxN && cribe[(int) n]) || (n> maxN && rabin(n)))) return n;
  93.                     System.out.println("El número debe ser un número primo.");
  94.                     continue;
  95.                 }
  96.                 else if(op == 2)
  97.                 {
  98.                     if(n > 0 ) return n;
  99.                     System.out.println("El tamaño de los arreglos a cargar debe ser positivo.");
  100.                     continue;
  101.                 }
  102.                 else
  103.                 {
  104.                     if(n > 0 && n < 3) return n;
  105.                     System.out.println("Opción incorrecta");
  106.                     continue;
  107.                 }
  108.             }
  109.             catch(Exception ex)
  110.             {
  111.                 System.out.println("Se introdujo un número inválido, reintente.");
  112.             }  
  113.         }
  114.     }  
  115.    
  116.     /* Para números menores a maxN = 10^7 O(n log n)*/
  117.     static void initCribe()
  118.     {
  119.         Arrays.fill(cribe, true);
  120.         cribe[0] = (cribe[1] = false);
  121.         for(int i = 2; i*i <= maxN; i++)
  122.         {
  123.             if(cribe[i])
  124.             {
  125.                 primesToGenerate.add(i);
  126.                 for(int j = i*i; j < maxN; j+=i)
  127.                 {
  128.                     cribe[j] = false;
  129.                 }
  130.             }
  131.         }
  132.     }
  133.    
  134.     static ArrayList<Long> sumArrays(ArrayList<Long> a, ArrayList<Long> b)
  135.     {
  136.         ArrayList<Long> ret = new ArrayList<Long>();
  137.         int n = a.size();
  138.         for(int i = 0; i < n ; i++)
  139.         {
  140.             ret.add(a.get(i)+b.get(i));
  141.         }
  142.         return ret;
  143.     }
  144.     static int getRandomIntBetweenRange(double min, double max){
  145.         int x = (int) ((int)(Math.random()*((max-min)+1))+min);
  146.         return x;
  147.     }
  148.    
  149.     static long generateRandomValues(int op)
  150.     {
  151.         if(op == 0) return getRandomIntBetweenRange(1, 100)*1000;
  152.         return primesToGenerate.get(getRandomIntBetweenRange(0, primesToGenerate.size()-1));
  153.     }
  154.    
  155.     static ArrayList<Long> chargeArray(int op, int max, int tipo)
  156.     {  
  157.         ArrayList<Long> retArray = new ArrayList<Long>();
  158.         String msg = (op == 0) ? "Introduzca un número múltiplo de 1000:" : "Introduzca un numero primo:";
  159.         Float sum = (float) 0;
  160.         while(max-- > 0 )
  161.         {
  162.             retArray.add((tipo == 1) ? forceReadPositiveLong(msg, op) : generateRandomValues(op));
  163.             sum+=retArray.get(retArray.size()-1);
  164.         }
  165.         sum/= retArray.size();
  166.         actualAvg = sum;
  167.         return retArray;
  168.     }
  169.    
  170.     static void showArrayList(ArrayList<Long> a, float avg, float avgPrime)
  171.     {
  172.         ArrayList<Long> arraySumLess = new ArrayList<Long>();
  173.         ArrayList<Long> arraySumHigher = new ArrayList<Long>();
  174.        
  175.         System.out.print("Vector suma:[");
  176.         for(int i = 0; i < a.size(); i++)
  177.         {
  178.             System.out.print(a.get(i) + ((i == a.size()-1) ? "]\n":", "));
  179.             if(a.get(i) < avg) arraySumLess.add(a.get(i));
  180.             if(a.get(i) > avgPrime) arraySumHigher.add(a.get(i));
  181.         }
  182.         System.out.println("Media del primer arreglo: " + avg);
  183.         System.out.println("Media del segundo arreglo: " + avgPrime);
  184.        
  185.        
  186.         System.out.print("Valores menores de la media del primer arreglo: [" + (arraySumLess.size() == 0? "]" : "") );
  187.         for(int i = 0; i < arraySumLess.size(); i++)
  188.         {
  189.             System.out.print(arraySumLess.get(i) + ((i == arraySumLess.size()-1) ? "]":", "));
  190.         }
  191.        
  192.        
  193.         System.out.print("\nValores mayores de la media del segundo arreglo: [");
  194.         for(int i = 0; i < arraySumHigher.size(); i++)
  195.         {
  196.             System.out.print(arraySumHigher.get(i) + ((i == arraySumHigher.size()-1) ? "]":", "));
  197.         }
  198.  
  199.     }
  200.    
  201.     public static void main(String[] args) {
  202.         initCribe();
  203.         int max = (int) forceReadPositiveLong("Introduzca el tamaño del arreglo:",2);
  204.         int tipo = (int) forceReadPositiveLong("¿Cómo cargará los arreglos? \n1-Introducir valores por consola.\n2-Generar valores aleatorios.",3);
  205.         ArrayList<Long> divs1000Array = chargeArray(0, max, tipo);
  206.         Float avg1000 = actualAvg;
  207.         ArrayList<Long> primeArray = chargeArray(1, max, tipo);
  208.         Float avgPrime = actualAvg;
  209.         showArrayList(sumArrays(divs1000Array, primeArray), avg1000, avgPrime);
  210.     }
  211.  
  212. }
  213.  
RAW Paste Data