Рубрики

Построить массив из GCD последовательных элементов в данном массиве

Дан массив a [] из n элементов. Задача состоит в том, чтобы найти массив (скажем, b []) из n + 1, такой, что Величайший общий делитель b [i] и b [i + 1] равен a [i]. Если существует несколько решений, выведите решение, сумма массива которого минимальна.

Примеры:

Input : a[] = { 1, 2, 3 }
Output : 1 2 6 3
GCD(1, 2) = 1
GCD(2, 6) = 2
GCD(6, 3) = 3
Also, 1 + 2 + 6 + 3 = 12 which is smallest among all
possible value of array that can be constructed.

Input : a[] = { 5, 10, 5 }
Output : 5 10 10 5

Предположим, что в данном массиве есть только одно число a []. Пусть это будет K, тогда оба числа в построенном массиве (скажем, b []) будут K и K.

Таким образом, значение b [0] будет только [0]. Теперь рассмотрим, что мы закончили до индекса i, т.е. мы уже обработали до индекса i и вычислили b [i + 1].

Теперь gcd (b [i + 1], b [i + 2]) = a [i + 1] и gcd (b [i + 2], b [i + 3]) = a [i + 2]. Итак, b [i + 2]> = lcm (a [i + 1], a [i + 2]). Или b [i + 2] будет кратно lcm (a [i + 1], a [i + 2]). Как нам нужна минимальная сумма, так и минимальному значению b [i + 2]. Итак, b [i + 2] = lcm (a [i + 2], a [i + 3]).

Ниже приведена реализация этого подхода:

C ++

// Программа CPP для построения массива, GCD которого
// каждый последующий элемент является заданным массивом
#include <bits/stdc++.h>

using namespace std;

  
// Возвращаем LCM двух чисел.

int lcm(int a, int b)

{

    return (a * b) / __gcd(a, b);

}

  
// Распечатать требуемый построенный массив

void printArray(int a[], int n)

{

    // печать первого элемента.

    cout << a[0] << " ";

  

    // нахождение и печать LCM последовательных

    // элемент данного массива.

    for (int i = 0; i < n - 1; i++)

        cout << lcm(a[i], a[i + 1]) << " ";

  

    // печать последнего элемента данного массива.

    cout << a[n - 1] << endl;

}

  
// Управляемая программа

int main()

{

    int a[] = { 1, 2, 3 };

    int n = sizeof(a) / sizeof(a[0]);

    printArray(a, n);

    return 0;

}

Джава

// Java-программа для построения массива которого
// GCD каждого последовательного элемента является
// данный массив

  

import java.io.*;

  

class GFG {

      

    // Рекурсивная функция для возврата gcd из

    // а и б

    static int __gcd(int a, int b)

    {

          

        // Все делит 0

        if (a == 0 || b == 0)

        return 0;

      

        // базовый вариант

        if (a == b)

            return a;

      

        // а больше

        if (a > b)

            return __gcd(a - b, b);

              

        return __gcd(a, b - a);

    }

  

    // Возвращаем LCM двух чисел.

    static int lcm(int a, int b)

    {

        return (a * b) / __gcd(a, b);

    }

      

    // Распечатать требуемый построенный массив

    static void printArray(int a[], int n)

    {

          

        // печать первого элемента.

        System.out.print( a[0] + " ");

      

        // найти и распечатать LCM

        // последовательный элемент данного массива.

        for (int i = 0; i < n - 1; i++)

            System.out.print(lcm(a[i],

                            a[i + 1]) + " ");

      

        // печать последнего элемента

        // данный массив.

        System.out.print(a[n - 1]);

    }

      

    // Управляемая программа

    public static void main (String[] args)

    {

        int a[] = { 1, 2, 3 };

        int n = a.length;

        printArray(a, n);

    }

}

  
// Этот код предоставлен anuj_67.

python3

# Программа Python для построения массива которого
# GCD каждого последовательного элемента является
# заданный массив

  
# Рекурсивная функция для возврата gcd из
№ а и б

def __gcd( a, b):

          

    # Все делит 0

    if (a == 0 or b == 0):

        return 0

          

    # базовый вариант

    if (a == b):

        return

          

    # больше

    if (a > b):

        return __gcd(a - b, b)         

    return __gcd(a, b - a)

      
# Вернуть LCM двух чисел.

def lcm(a, b):

    return (a * b) / __gcd(a, b)

  
# Распечатать требуемый построенный массив

def printArray(a, n):

          

    # печать первого элемента.

    print ( str(a[0]) + " ")

          

    # найти и распечатать LCM

    # последовательный элемент данного массива.

    for i in range(0,n-1):

        print (str(lcm(a[i],a[i + 1])) + " ")

          

    # печать последнего элемента

    # заданный массив.

    print (a[n - 1])

  
# Код драйвера

a = [1, 2, 3 ]

n = len(a)

printArray(a, n)

  
# Этот код предоставлен Prateek Bajaj

C #

// C # Программа для создания массива которого
// GCD каждого последовательного элемента является
// данный массив

using System;

class GFG {

      

    // Рекурсивная функция для возврата

    // gcd of a и b

    static int __gcd(int a, int b)

    {

        // Все делит 0

        if (a == 0 || b == 0)

        return 0;

      

        // базовый вариант

        if (a == b)

            return a;

      

        // а больше

        if (a > b)

            return __gcd(a - b, b);

              

        return __gcd(a, b - a);

    }

  

    // Возвращаем LCM двух чисел.

    static int lcm(int a, int b)

    {

        return (a * b) / __gcd(a, b);

    }

      

    // Распечатать требуемый построенный массив

    static void printArray(int []a, int n)

    {

          

        // печать первого элемента.

        Console.Write( a[0] + " ");

      

        // найти и распечатать LCM

        // последовательный элемент данного массива.

        for (int i = 0; i < n - 1; i++)

            Console.Write(lcm(a[i],

                  a[i + 1]) + " ");

      

        // печать последнего элемента

        // данного массива.

        Console.Write(a[n - 1]);

    }

      

    // Код драйвера

    public static void Main ()

    {

        int []a = {1, 2, 3};

        int n = a.Length;

        printArray(a, n);

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для построения
// массив, GCD которого
// каждый последующий элемент
// это заданный массив

  
// Рекурсивная функция для
// вернуть gcd из a и b

function __gcd($a, $b)

{

      

    // Все делит 0

    if($a == 0 or $b == 0)

        return 0 ;

  

    // базовый вариант

    if($a == $b)

        return $a ;

      

    // а больше

    if($a > $b)

        return __gcd( $a - $b , $b ) ;

  

    return __gcd( $a , $b - $a ) ;

}

  
// Возвращаем LCM двух чисел.

function lcm($a, $b)

{

    return ($a * $b) / __gcd($a, $b);

}

  
// Распечатать требуемый построенный массив

function printArray( $a, $n)

{

      

    // печать первого элемента.

    echo $a[0] , " ";

  

    // поиск и печать

    // LCM последовательных

    // элемент данного массива.

    for ( $i = 0; $i < $n - 1; $i++)

        echo lcm($a[$i], $a[$i + 1]) , " ";

  

    // печать последнего элемента

    // данного массива.

    echo $a[$n - 1] ,"\n";

}

  

    // Код драйвера

    $a = array(1, 2, 3);

    $n = count($a);

    printArray($a, $n);

  
// Этот код предоставлен anuj_67.
?>


Выход

1 2 6 3

Рекомендуемые посты:

Построить массив из GCD последовательных элементов в данном массиве

0.00 (0%) 0 votes