Dado un número entero N . La tarea es encontrar el número en el rango de 1 a N-1 que tiene el número máximo de términos en su Secuencia de Collatz y el número de términos en la secuencia.
La secuencia collatz de un número N se define como:
- Si N es impar , cambie N a 3*N + 1 .
- Si N es par , cambie N a N/2 .
Por ejemplo, echemos un vistazo a la secuencia cuando N = 13 :
13 -> 40 -> 20 -> 10 -> 5 > 16 -> 8 -> 4 -> 2 -> 1
Ejemplos:
Entrada: 10
Salida: (9, 20)
9 tiene 20 términos en su secuencia de Collatz
Entrada: 50
Salida: (27, 112)
27 tiene 112 términos
Enfoque:
como en el ejemplo anterior discutido para N = 13 , la secuencia collatz para N = 13 y N = 40 tiene términos similares, excepto uno, que garantiza que puede haber una participación de la programación dinámica para almacenar la respuesta de los subproblemas y reutilizarla.
Pero aquí la memorización normal no funcionará porque en un paso estamos haciendo un número grande a partir de sí mismo (en el ejemplo anterior N = 13 depende de la solución de N = 40) o dividiendo por 2 (N = 40 la solución depende de la solución de N = 20).
Entonces, en lugar de usar una array dp, usaremos una estructura de datos de mapa/diccionario para almacenar la solución de los subproblemas y realizaremos la operación normal como se describe en la secuencia collatz.
A continuación se muestra la implementación del enfoque anterior:
C++
#include<bits/stdc++.h>
using namespace std;
int collatzLenUtil(int n, unordered_map<int,int>&collLenMap){
// If value already
// computed, return it
if(collLenMap.find(n) != collLenMap.end())
return collLenMap[n];
// Base case
if(n == 1)
collLenMap[n] = 1;
// Even case
else if(n % 2 == 0){
collLenMap[n] = 1 + collatzLenUtil(n/2 , collLenMap);
}
// Odd case
else{
collLenMap[n] = 1 + collatzLenUtil(3 * n + 1, collLenMap);
}
return collLenMap[n];
}
pair<int,int> collatzLen(int n){
// Declare empty Map / Dict
// to store collatz lengths
unordered_map<int,int>collLenMap;
collatzLenUtil(n, collLenMap);
// Initialise ans and
// its collatz length
int num = -1, l = 0;
for(int i=1;i<n;i++){
// If value not already computed,
// pass Dict to Helper function
// and calculate and store value
if(collLenMap.find(i)==collLenMap.end())
collatzLenUtil(i, collLenMap);
int cLen = collLenMap[i];
if(l < cLen){
l = cLen;
num = i;
}
}
// Return ans and
// its collatz length
return {num, l};
}
int main(){
cout<<"("<<collatzLen(10).first<<", "<<collatzLen(10).second<<")"<<endl;
}
// This code is contributed by shinjanpatra
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static int collatzLenUtil(int n, HashMap<Integer,Integer>collLenMap){
// If value already
// computed, return it
if(collLenMap.containsKey(n))
return collLenMap.get(n);
// Base case
if(n == 1)
collLenMap.put(n , 1);
// Even case
else if(n % 2 == 0){
collLenMap.put(n , 1 + collatzLenUtil(n/2 , collLenMap));
}
// Odd case
else{
collLenMap.put(n , 1 + collatzLenUtil(3 * n + 1, collLenMap));
}
return collLenMap.get(n);
}
static int[] collatzLen(int n){
// Declare empty Map / Dict
// to store collatz lengths
HashMap<Integer,Integer> collLenMap = new HashMap<>();
collatzLenUtil(n, collLenMap);
// Initialise ans and
// its collatz length
int num = -1, l = 0;
for(int i=1;i<n;i++){
// If value not already computed,
// pass Dict to Helper function
// and calculate and store value
if(collLenMap.containsKey(i)==false)
collatzLenUtil(i, collLenMap);
int cLen = collLenMap.get(i);
if(l < cLen){
l = cLen;
num = i;
}
}
// Return ans and
// its collatz length
int res[] = {num, l};
return res;
}
/* Driver program to test above function*/
public static void main(String args[])
{
System.out.println("(" + collatzLen(10)[0]+", "+collatzLen(10)[1] + ")");
}
}
// This code is contributed by shinjanpatra
Python3
def collatzLenUtil(n, collLenMap):
# If value already
# computed, return it
if n in collLenMap:
return collLenMap[n]
# Base case
if(n == 1):
collLenMap[n] = 1
# Even case
elif(n % 2 == 0):
collLenMap[n] \
= 1 \
+ collatzLenUtil(n//2, collLenMap)
# Odd case
else:
collLenMap[n] \
= 1 \
+ collatzLenUtil(3 * n + 1, collLenMap)
return collLenMap[n]
def collatzLen(n):
# Declare empty Map / Dict
# to store collatz lengths
collLenMap = {}
collatzLenUtil(n, collLenMap)
# Initialise ans and
# its collatz length
num, l =-1, 0
for i in range(1, n):
# If value not already computed,
# pass Dict to Helper function
# and calculate and store value
if i not in collLenMap:
collatzLenUtil(i, collLenMap)
cLen = collLenMap[i]
if l < cLen:
l = cLen
num = i
# Return ans and
# its collatz length
return (num, l)
print(collatzLen(10))
Javascript
<script>
function collatzLenUtil(n, collLenMap){
// If value already
// computed, return it
if(collLenMap.has(n))
return collLenMap.get(n)
// Base case
if(n == 1)
collLenMap.set(n, 1)
// Even case
else if(n % 2 == 0){
collLenMap.set(n , 1 + collatzLenUtil(Math.floor(n/2) , collLenMap))
}
// Odd case
else{
collLenMap.set(n , 1 + collatzLenUtil(3 * n + 1, collLenMap))
}
return collLenMap.get(n);
}
function collatzLen(n){
// Declare empty Map / Dict
// to store collatz lengths
let collLenMap = new Map()
collatzLenUtil(n, collLenMap)
// Initialise ans and
// its collatz length
let num = -1, l = 0
for(let i=1;i<n;i++){
// If value not already computed,
// pass Dict to Helper function
// and calculate and store value
if(collLenMap.has(i)==false)
collatzLenUtil(i, collLenMap)
let cLen = collLenMap.get(i)
if(l < cLen){
l = cLen
num = i
}
}
// Return ans and
// its collatz length
return [num, l]
}
document.write(collatzLen(10))
// This code is contributed by shinjanpatra
</script>
(9, 20)
Publicación traducida automáticamente
Artículo escrito por SayantanDas3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA