Determinar pares amistosos dentro de los límites de θ (n) -- ++ campo con time-limit-exceeded campo con mathematics camp codereview Relacionados El problema

Determine amicable pairs within confines of Θ(n)


1
vote

problema

Español

Tuve que implementar un programa que lleva un número 9988776655544336 del usuario y encuentra todos los números y pares perfectos de números amigables dentro del rango $ lbrace 2, ldots, texttt {usernum } rbrace $ y envíalos al usuario.

Requisitos

  1. Función de implementación void AnalyzeDivisors(int num, int& outCountDivs, int& outSumDivs)
  2. implementar bool IsPerfect(int num) usando analizedivisors
  3. Uso Funciones para escribir un programa que lea del usuario un entero positivo e imprime todos los números perfectos entre 2 y M y todos los pares de números amistosos que están entre 2 y M (ambos números deben estar en rango).
  4. Las llamadas a los analizados deben mantenerse a $ theTa (M) $ Times todos juntos.

No he podido satisfacer el requisito 4: Actualmente, mi algoritmo es muy ineficiente y no estoy seguro de cómo hacerlo lo contrario. Cualquier recomendación sobre cómo permanecer dentro de $ THETA (M) $ en referencia a AnalyzeDivisors sería muy apreciado.

Código a continuación:

principal:

  /**  * Generate an array of random & unique values in the interval [0,desiredSize*3]  * To use only for small arrays with size in [1,50k]  * for an array of 1k time: 0.01s  * for an array of 10k time: 0.3s  * for an array of 50k time: 8s   * @param desiredSize  * @return  */ public int[] generateRandAndUniq(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Random rand = new Random();     arrayResult[0]= rand.nextInt(desiredSize);     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         int[] tempArray= new int[counter+2];         System.arraycopy(arrayResult, 0, tempArray,0, counter);         tempArray[counter+1]=randValue;         if(!checkDuplicate(tempArray)){             arrayResult[counter]=randValue;             counter++;         }     }     return arrayResult; }  public boolean checkDuplicate(int[] arr) {     boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */     for (int v : arr) {         if (!bitmap[v]) {             bitmap[v] = true;         } else {             return true;         }     }     return false; }   public int maxValueInArray(int[] arr){     int max=-1;     for(int v:arr){         if(v>max)             max=v;     }     return max; } 0  

analizar dividors

  /**  * Generate an array of random & unique values in the interval [0,desiredSize*3]  * To use only for small arrays with size in [1,50k]  * for an array of 1k time: 0.01s  * for an array of 10k time: 0.3s  * for an array of 50k time: 8s   * @param desiredSize  * @return  */ public int[] generateRandAndUniq(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Random rand = new Random();     arrayResult[0]= rand.nextInt(desiredSize);     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         int[] tempArray= new int[counter+2];         System.arraycopy(arrayResult, 0, tempArray,0, counter);         tempArray[counter+1]=randValue;         if(!checkDuplicate(tempArray)){             arrayResult[counter]=randValue;             counter++;         }     }     return arrayResult; }  public boolean checkDuplicate(int[] arr) {     boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */     for (int v : arr) {         if (!bitmap[v]) {             bitmap[v] = true;         } else {             return true;         }     }     return false; }   public int maxValueInArray(int[] arr){     int max=-1;     for(int v:arr){         if(v>max)             max=v;     }     return max; } 1  

isperfect

  /**  * Generate an array of random & unique values in the interval [0,desiredSize*3]  * To use only for small arrays with size in [1,50k]  * for an array of 1k time: 0.01s  * for an array of 10k time: 0.3s  * for an array of 50k time: 8s   * @param desiredSize  * @return  */ public int[] generateRandAndUniq(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Random rand = new Random();     arrayResult[0]= rand.nextInt(desiredSize);     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         int[] tempArray= new int[counter+2];         System.arraycopy(arrayResult, 0, tempArray,0, counter);         tempArray[counter+1]=randValue;         if(!checkDuplicate(tempArray)){             arrayResult[counter]=randValue;             counter++;         }     }     return arrayResult; }  public boolean checkDuplicate(int[] arr) {     boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */     for (int v : arr) {         if (!bitmap[v]) {             bitmap[v] = true;         } else {             return true;         }     }     return false; }   public int maxValueInArray(int[] arr){     int max=-1;     for(int v:arr){         if(v>max)             max=v;     }     return max; } 2  
Original en ingles

I had to implement a program that takes a number userNum from the user and finds all perfect numbers and pairs of amicable numbers within the range \$\lbrace 2, \ldots, \texttt{userNum} \rbrace\$ and output them to the user.

Requirements

  1. Implement function void AnalyzeDivisors(int num, int& outCountDivs, int& outSumDivs)
  2. implement bool IsPerfect(int num) using AnalyzeDivisors
  3. Use functions to write a program that reads from the user a positive integer and prints all perfect numbers between 2 and M and All pairs of amicable numbers that are between 2 and M (both numbers must be in range).
  4. Calls to AnalyzeDivisors must be kept to \$\Theta(m)\$ times all together.

I have not been able to satisfy requirement 4 xe2x80xa6 Currently my algorithm is very inefficient and I'm unsure how to do it otherwise. Any recommendations on how to remain within \$\Theta(m)\$ in reference to AnalyzeDivisors would be greatly appreciated.

Code below:

main:

const string IS_PERFECT_NUM = " is a perfect number.";  void AnalyzeDividors(int num, int& outCountDivs, int& outSumDivs); bool IsPerfect(int userNum, int outSumDivs);  int main() {     int userNum;      //Request number input from the user     cout << "Please input a positive integer num (>= 2): " << endl;     cin >> userNum;      for (int counter = 2; counter <= userNum; counter++)     {         //Set variables          int outCountDivs = 0, outSumDivs = 0;         bool perfectNum = false, isAmicablePair = false;          //Analyze dividors         AnalyzeDividors(counter, outCountDivs, outSumDivs);          //determine perfect num         perfectNum = IsPerfect(counter, outSumDivs);          if (perfectNum)             cout << endl << counter << IS_PERFECT_NUM;          //Smallest pair of amicable numbers (220,284)...No need to check if not above range         if (userNum >= 284)         {              for (int amicablePairCounter = counter + 1; amicablePairCounter <= userNum; amicablePairCounter++)             {                 //Determine if amicable pairs exist by checking against outCountDivs and outSumDivs from prior counter number                 int otherAmicablePairSum = 0, otherOutCountDivs = 0;                  AnalyzeDividors(amicablePairCounter, otherOutCountDivs, otherAmicablePairSum);                  if (otherAmicablePairSum == counter && outSumDivs == amicablePairCounter)                     cout << endl << amicablePairCounter << " and " << counter << " are an amicable pair.";             }         }       }      return 0; } 

Analyze Dividors

void AnalyzeDividors(int num, int& outCountDivs, int& outSumDivs) {     int divisorCounter;      for (divisorCounter = 1; divisorCounter <= sqrt(num); divisorCounter++)     {         if (num % divisorCounter == 0 && num / divisorCounter != divisorCounter && num / divisorCounter != num)         {             //both counter and num/divisorCounter             outSumDivs += divisorCounter + (num / divisorCounter);             outCountDivs += 2;         }          else if ((num % divisorCounter == 0 && num / divisorCounter == divisorCounter) || num/divisorCounter == num)         {             //Just divisorCounter             outSumDivs += divisorCounter;             outCountDivs += 1;         }     } } 

IsPerfect

bool IsPerfect(int userNum, int outSumDivs) {      if (userNum == outSumDivs)         return true;     else         return false;  } 
        
 
 

Lista de respuestas


Relacionados problema

3  Análisis de simetría para arreglos atómicos en un cristal  ( Symmetry analysis for atom arrangements in a crystal ) 
Por un tiempo ahora he tenido la intención de publicar un poco de mi código Haskell aquí para que alguien pueda decirme qué partes de la biblioteca de idiomas...

11  Números de colmena - usando goto en C ++  ( Beehive numbers using goto in c ) 
Entiendo que el uso de orca_array.hpp4 en el código C ++ está estrictamente no aconsejado, pero a veces, realmente reduce la cantidad de líneas de código co...

13  Plantilla de expresión para calcular la distancia euclidiana  ( Expression template to compute the euclidean distance ) 
Estaba escribiendo un código relacionado con el geometría nuevamente y tuvo un vistazo más de cerca a mi función que se supone que calcula la distancia euclid...

4  Algoritmo más rápido para adaptar la expresión matemática dada  ( Faster algorithm to tailor given mathematical expression ) 
¿Hay una solución más optimizada para resolver el problema declarado? Dada una matriz 'Arr' de 'n' elementos y un número 'M', encuentra el menor índice 'Z' ...

3  Código C ++ para encontrar la distancia entre la línea y el punto  ( C code to find distance between line and point ) 
Así que hice este simple programa que permite a los usuarios construir puntos y líneas y luego devolver la distancia más pequeña entre un punto dado y una lín...

2  Optimización del código para la secuencia A064604  ( Optimizing code for sequence a064604 ) 
Estoy implementando a064604 - oeis para enteros positivos de hasta 10 mil millones. Estoy encontrando a los divisores en $ o ( sqrt n) $. Por lo tanto, ...

15  Función de sine en C / C ++  ( Sine function in c c ) 
Debido a las restricciones de software, No puedo usar las bibliotecas estándar, cmath , 9988776655544334 , plantillas, en línea o impulso . También estoy u...

4  Verificación computacional de la conjetura de Collatz utilizando OpenCl  ( Computational verification of collatz conjecture using opencl ) 
Esta solicitud de revisión de código sigue mi solicitud anterior Verificación computacional de Collatz Conyecture . A diferencia del programa anterior (que ...

6  Determinar si f (n) = n ^ 2 + 3n + 5 es divisible por 121  ( Determining if fn n2 3n 5 is ever divisible by 121 ) 
Dado el siguiente problema: Se conjeture eso para cualquier $ N & GT; 0 $, $ N ^ 2 + 3n + 5 $ nunca es divisible por 121. Pruebe esta conjetura por ...

13  Numérica para un cálculo de teoría de juegos usando la utilidad esperada  ( Numerics for a game theory calculation using expected utility ) 
Estoy tratando de replicar los resultados de Bruce B. de Mesquita (BDM) en la teoría del juego político para la predicción. Sobre la base de dónde se encuentr...




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