dado un entero nortela tarea es generar una matriz A[] de longitud norte de modo que cumpla las siguientes condiciones para todos: 1 yo ≤ N−1:
- Ai es múltiplo de AI-1 cuando i es extraño
- Ai no es múltiplo de AI-1 cuando i incluso
- todo uni son diferentes por pares
- 1 Ai ≤ 2⋅N
Observación: Si hay varias respuestas, imprima una.
Ejemplos:
Aporte: norte = 4
Salida: 3 6 4 8
Explicación: [3, 6, 4, 8] es una matriz válida porque:
A1 = 3 es múltiplo de A2 = 6
A2 = 6 no es múltiplo de A3 = 4
A3 = 4 es múltiplo de A4 = 8.Aporte: norte = 6
Salida: 4 8 5 10 6 12
Acercarse: El problema se puede resolver con base en la siguiente observación:
observaciones:
Sea x = N − ⌈N / 2⌉ + 1. Entonces la siguiente secuencia es válida: [x, 2⋅x, x + 1, 2⋅(x + 1), x + 2, …]
- Es fácil ver que los elementos con índices impares están en orden ascendente de x→N. Del mismo modo, los elementos de los índices pares están en orden ascendente de 2⋅x→2⋅N (desde 2⋅x→2⋅(N − 1) cuando N es impar).
- Entonces 2⋅x = 2⋅(N − ⌈N / 2⌉ + 1) > N implica los conjuntos {x, x + 1, …, N} y {2⋅x, 2⋅(x + 1), … , 2⋅N} son incoherentes. Por lo tanto, todos los elementos de la serie anterior son únicos.
- Ai es múltiplo de AI-1 se puede verificar trivialmente que es cierto para todos los impares
Ai no es múltiplo de AI-1 se aplica a todos, incluso a mí.Por lo tanto, la orden dada cumple con todos los requisitos del problema y, por lo tanto, ¡es válida!
Siga los pasos a continuación para resolver el problema:
- Inicializar una variable elemento impar = (N / 2) + 1 para elementos impares indexados.
- Inicializar una variable elemento par = elemento impar * 2 incluso para elementos indexados.
- Bucle a través de un bucle de 1 a N en i:
- Si soy una huella extraña elemento impar.
- Asignar a elemento par = elemento impar * 2.
- Aumenta el elemento par.
- De lo contrario imprima el elemento par.
- Si soy una huella extraña elemento impar.
A continuación encontrará la implementación del enfoque anterior.
Java
|
Complejidad del tiempo: A)
cuarto auxiliar: O(1)