Construya una serie AP que consista en A y B que tenga el mínimo N-ésimo término posible

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) .

  1. 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) ).
  2. Ahora, construya la array arr[] como {x, x + d, x + 2d, …, x + d*(N – 1)} .
  3. 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[] .
  4. De lo contrario, itere más y busque otros valores de x y d .
  5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *