Dados dos números enteros A, B que son dos términos cualesquiera de una serie de Progresión aritmética, y un número entero N , la tarea es construir una serie de Progresión aritmética de tamaño N tal que debe incluir tanto a A como a B y el N -ésimo término de el AP debe ser mínimo.
Ejemplos:
Entrada: N = 5, A = 20, B = 50
Salida: 10 20 30 40 50
Explicación:
Una de las posibles secuencias AP es {10, 20, 30, 40, 50} con 50 como el 5º valor , que es el mínimo posible.Entrada: N = 2, A = 1, B = 49
Salida: 1 49
Enfoque: El término N de un PA viene dado por X N = X + (N – 1)*d , donde X es el primer término y d es una diferencia común. Para hacer que el elemento más grande sea mínimo, minimice tanto x como d . Se puede observar que el valor de X no puede ser mayor que min(A, B) y el valor de d no puede ser mayor que abs(A – B) .
- Ahora, use la misma fórmula para construir el AP para cada valor posible de x ( desde 1 hasta min(A, B) ) y d (desde 1 hasta abs(A – B) ).
- Ahora, construya la array arr[] como {x, x + d, x + 2d, …, x + d*(N – 1)} .
- Compruebe si A y B están presentes en él o no y el N -ésimo elementoes mínimo posible o no. Si se encuentra que es cierto, entonces actualice ans[] por la array construida arr[] .
- De lo contrario, itere más y busque otros valores de x y d .
- Finalmente, imprima ans[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if both a and
// b are present in the AP series or not
bool check_both_present(int arr[], int N,
int a, int b)
{
bool f1 = false, f2 = false;
// Iterate over the array arr[]
for (int i = 0; i < N; i++) {
// If a is present
if (arr[i] == a) {
f1 = true;
}
// If b is present
if (arr[i] == b) {
f2 = true;
}
}
// If both are present
if (f1 && f2) {
return true;
}
// Otherwise
else {
return false;
}
}
// Function to print all the elements
// of the Arithmetic Progression
void print_array(int ans[], int N)
{
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
}
// Function to construct AP series
// consisting of A and B with
// minimum Nth term
void build_AP(int N, int a, int b)
{
// Stores the resultant series
int arr[N], ans[N];
// Initialise ans[i] as INT_MAX
for (int i = 0; i < N; i++)
ans[i] = INT_MAX;
int flag = 0;
// Maintain a smaller than b
if (a > b) {
swap(a, b);
}
// Difference between a and b
int diff = b - a;
// Check for all possible combination
// of start and common difference d
for (int start = 1;
start <= a; start++) {
for (int d = 1;
d <= diff; d++) {
// Initialise arr[0] as start
arr[0] = start;
for (int i = 1; i < N; i++) {
arr[i] = arr[i - 1] + d;
}
// Check if both a and b are
// present or not and the Nth
// term is the minimum or not
if (check_both_present(arr, N, a, b)
&& arr[N - 1] < ans[N - 1]) {
// Update the answer
for (int i = 0; i < N; i++) {
ans[i] = arr[i];
}
}
}
}
// Print the resultant array
print_array(ans, N);
}
// Driver Code
int main()
{
int N = 5, A = 20, B = 50;
// Function Call
build_AP(N, A, B);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to check if both a and
// b are present in the AP series or not
public static boolean check_both_present(int[] arr,
int N, int a,
int b)
{
boolean f1 = false, f2 = false;
// Iterate over the array arr[]
for(int i = 0; i < N; i++)
{
// If a is present
if (arr[i] == a)
{
f1 = true;
}
// If b is present
if (arr[i] == b)
{
f2 = true;
}
}
// If both are present
if (f1 && f2)
{
return true;
}
// Otherwise
else
{
return false;
}
}
// Function to print all the elements
// of the Arithmetic Progression
public static void print_array(int[] ans, int N)
{
for(int i = 0; i < N; i++)
{
System.out.print(ans[i] + " ");
}
}
// Function to construct AP series
// consisting of A and B with
// minimum Nth term
public static void build_AP(int N, int a, int b)
{
// Stores the resultant series
int[] arr = new int[N];
int[] ans = new int[N];
// Initialise ans[i] as INT_MAX
for(int i = 0; i < N; i++)
ans[i] = Integer.MAX_VALUE;
int flag = 0;
// Maintain a smaller than b
if (a > b)
{
// swap(a and b)
a += (b - (b = a));
}
// Difference between a and b
int diff = b - a;
// Check for all possible combination
// of start and common difference d
for(int start = 1; start <= a; start++)
{
for(int d = 1; d <= diff; d++)
{
// Initialise arr[0] as start
arr[0] = start;
for(int i = 1; i < N; i++)
{
arr[i] = arr[i - 1] + d;
}
// Check if both a and b are
// present or not and the Nth
// term is the minimum or not
if (check_both_present(arr, N, a, b) &&
arr[N - 1] < ans[N - 1])
{
// Update the answer
for(int i = 0; i < N; i++)
{
ans[i] = arr[i];
}
}
}
}
// Print the resultant array
print_array(ans, N);
}
// Driver Code
public static void main(String[] args)
{
int N = 5, A = 20, B = 50;
// Function call
build_AP(N, A, B);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach import sys # Function to check if both a and # b are present in the AP series or not def check_both_present(arr, N, a, b): f1 = False f2 = False # Iterate over the array arr[] for i in range(0, N): # If a is present if arr[i] == a: f1 = True # If b is present if arr[i] == b: f2 = True # If both are present if f1 and f2: return True # Otherwise else: return False # Function to print all the elements # of the Arithmetic Progression def print_array(ans, N): for i in range(0, N): print(ans[i], end = " ") # Function to construct AP series # consisting of A and B with # minimum Nth term def build_AP(N, a, b): INT_MAX = sys.maxsize # Stores the resultant series arr = [None for i in range(N)] # Initialise ans[i] as INT_MAX ans = [INT_MAX for i in range(N)] flag = 0 # Maintain a smaller than b if a > b: # Swap a and b a, b = b, a # Difference between a and b diff = b - a # Check for all possible combination # of start and common difference d for start in range(1, a + 1): for d in range(1, diff + 1): # Initialise arr[0] as start arr[0] = start for i in range(1, N): arr[i] = arr[i - 1] + d # Check if both a and b are # present or not and the Nth # term is the minimum or not if ((check_both_present(arr, N, a, b) and arr[N - 1] < ans[N - 1])): # Update the answer for i in range(0, N): ans[i] = arr[i] # Print the resultant array print_array(ans, N) # Driver Code if __name__ == "__main__": N = 5 A = 20 B = 50 # Function call build_AP(N, A, B) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if both a and
// b are present in the AP series or not
static bool check_both_present(int[] arr, int N,
int a, int b)
{
bool f1 = false, f2 = false;
// Iterate over the array arr[]
for(int i = 0; i < N; i++)
{
// If a is present
if (arr[i] == a)
{
f1 = true;
}
// If b is present
if (arr[i] == b)
{
f2 = true;
}
}
// If both are present
if (f1 && f2)
{
return true;
}
// Otherwise
else
{
return false;
}
}
// Function to print all the elements
// of the Arithmetic Progression
static void print_array(int[] ans, int N)
{
for(int i = 0; i < N; i++)
{
Console.Write(ans[i] + " ");
}
}
// Function to construct AP series
// consisting of A and B with
// minimum Nth term
static void build_AP(int N, int a, int b)
{
// Stores the resultant series
int[] arr = new int[N];
int[] ans = new int[N];
// Initialise ans[i] as INT_MAX
for(int i = 0; i < N; i++)
ans[i] = int.MaxValue;
// Maintain a smaller than b
if (a > b)
{
// Swap a and b
a += (b - (b = a));
}
// Difference between a and b
int diff = b - a;
// Check for all possible combination
// of start and common difference d
for(int start = 1; start <= a; start++)
{
for(int d = 1; d <= diff; d++)
{
// Initialise arr[0] as start
arr[0] = start;
for(int i = 1; i < N; i++)
{
arr[i] = arr[i - 1] + d;
}
// Check if both a and b are
// present or not and the Nth
// term is the minimum or not
if (check_both_present(arr, N, a, b) &&
arr[N - 1] < ans[N - 1])
{
// Update the answer
for(int i = 0; i < N; i++)
{
ans[i] = arr[i];
}
}
}
}
// Print the resultant array
print_array(ans, N);
}
// Driver Code
static public void Main()
{
int N = 5, A = 20, B = 50;
// Function call
build_AP(N, A, B);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program for the
// above approach
// Function to check if both a and
// b are present in the AP series or not
function check_both_present(arr, N, a, b)
{
let f1 = false, f2 = false;
// Iterate over the array arr[]
for(let i = 0; i < N; i++)
{
// If a is present
if (arr[i] == a)
{
f1 = true;
}
// If b is present
if (arr[i] == b)
{
f2 = true;
}
}
// If both are present
if (f1 && f2)
{
return true;
}
// Otherwise
else
{
return false;
}
}
// Function to print all the elements
// of the Arithmetic Progression
function print_array(ans, N)
{
for(let i = 0; i < N; i++)
{
document.write(ans[i] + " ");
}
}
// Function to construct AP series
// consisting of A and B with
// minimum Nth term
function build_AP(N, a, b)
{
// Stores the resultant series
let arr = Array(N).fill(0);
let ans = Array(N).fill(0);
// Initialise ans[i] as let_MAX
for(let i = 0; i < N; i++)
ans[i] = Number.MAX_VALUE;
let flag = 0;
// Maintain a smaller than b
if (a > b)
{
// swap(a and b)
a += (b - (b = a));
}
// Difference between a and b
let diff = b - a;
// Check for all possible combination
// of start and common difference d
for(let start = 1; start <= a; start++)
{
for(let d = 1; d <= diff; d++)
{
// Initialise arr[0] as start
arr[0] = start;
for(let i = 1; i < N; i++)
{
arr[i] = arr[i - 1] + d;
}
// Check if both a and b are
// present or not and the Nth
// term is the minimum or not
if (check_both_present(arr, N, a, b) &&
arr[N - 1] < ans[N - 1])
{
// Update the answer
for(let i = 0; i < N; i++)
{
ans[i] = arr[i];
}
}
}
}
// Print the resultant array
print_array(ans, N);
}
// Driver Code
let N = 5, A = 20, B = 50;
// Function call
build_AP(N, A, B);
// This code is contributed by avijitmondal1998.
</script>
Producción:
10 20 30 40 50
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rishabhtyagi2306 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA