Рубрики

Заполните два экземпляра всех чисел от 1 до n определенным образом

Учитывая число n, создайте массив размером 2n так, чтобы массив содержал 2 экземпляра каждого числа от 1 до n, а количество элементов между двумя экземплярами числа i равно i. Если такая конфигурация невозможна, распечатайте тоже самое.

Примеры:

Input: n = 3
Output: res[] = {3, 1, 2, 1, 3, 2}

Input: n = 2
Output: Not Possible

Input: n = 4
Output: res[] = {4, 1, 3, 1, 2, 4, 3, 2}

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Одним из решений является возврат. Идея проста, мы помещаем два экземпляра n в одном месте, а затем повторяем для n-1. Если повторение прошло успешно, мы возвращаем true, иначе мы возвращаемся назад и пытаемся поместить n в другое место. Ниже приводится реализация идеи.

C ++

// Программа на C ++ для возврата
// два экземпляра всех чисел от 1 до n
// определенным образом
#include <bits/stdc++.h>

using namespace std;

  
// Рекурсивная вспомогательная функция для заполнения
// два экземпляра чисел от 1 до n
// в разрешении [0..2n-1]. 'curr' - текущее значение n.

bool fillUtil(int res[], int curr, int n) 

    // Если текущее число становится 0,

    // тогда все числа заполнены

    if (curr == 0) 

    return true

  

    // Попробуем поместить два экземпляра curr в

    // все возможные местоположения, пока решение не найдено

    int i; 

    for (i = 0; i < 2 * n - curr - 1; i++) 

    

        // Два 'curr' должны быть помещены в

        // расстояние curr + 1

        if (res[i] == 0 && res[i + curr + 1] == 0) 

        

              

            // Добавьте два экземпляра curr

            res[i] = res[i + curr + 1] = curr; 

      

            // Повторим, чтобы проверить, если вышеуказанное размещение

            // приводит к решению

            if (fillUtil(res, curr - 1, n)) 

                return true

      

            // Если решение невозможно,

            // затем возвращаемся

            res[i] = res[i + curr + 1] = 0; 

        

    

    return false

  
// Эта функция печатает результат для
// вводим число 'n', используя fillUtil ()

void fill(int n) 

    // Создаем массив размером 2n и

    // инициализируем все элементы в нем как 0

    int res[2 * n], i; 

    for (i = 0; i < 2 * n; i++) 

    res[i] = 0; 

  

    // Если решение возможно,

    // затем распечатать его.

    if (fillUtil(res, n, n)) 

    

        for (i = 0; i < 2 * n; i++) 

        cout << res[i] << " "

    

    else

        cout << "Not Possible"

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

int main() 

    fill(7); 

    return 0; 

  
// Этот код добавлен
// от SHUBHAMSINGH8410

С

// Программа C на основе обратного отслеживания для заполнения двух экземпляров всех чисел
// от 1 до n определенным образом
#include <stdio.h>
#include <stdbool.h>

  
// Рекурсивная служебная функция для заполнения двух экземпляров чисел из
// от 1 до n в res [0..2n-1]. 'curr' - текущее значение n.

bool fillUtil(int res[], int curr, int n)

{

     // Если текущее число становится 0, тогда все числа заполнены

     if (curr == 0) return true;

  

     // Попробуйте разместить два экземпляра curr во всех возможных местах

     // пока не найдено решение

     int i;

     for (i=0; i<2*n-curr-1; i++)

     {

        // Два 'curr' должны быть расположены на расстоянии 'curr + 1'

        if (res[i] == 0 && res[i + curr + 1] == 0)

        {

           // Добавьте два экземпляра curr

           res[i] = res[i + curr + 1] = curr;

  

           // Повторяем, чтобы проверить, приводит ли приведенное выше размещение к решению

           if (fillUtil(res, curr-1, n))

               return true;

  

           // Если решение не возможно, тогда возвращаемся

           res[i] = res[i + curr + 1] = 0;

        }

     }

     return false;

}

  
// Эта функция печатает результат для входного номера 'n', используя fillUtil ()

void fill(int n)

{

    // Создать массив размером 2n и инициализировать все элементы в нем как 0

    int res[2*n], i;

    for (i=0; i<2*n; i++)

       res[i] = 0;

  

    // Если решение возможно, выведите его.

    if (fillUtil(res, n, n))

    {

        for (i=0; i<2*n; i++)

           printf("%d ", res[i]);

    }

    else

        puts("Not Possible");

}

  
// Драйвер программы

int main()

{

  fill(7);

  return 0;

}

Джава

// Программа на C ++ для возврата
// два экземпляра всех чисел от 1 до n
// определенным образом

import java.io.*;

  

class GFG 

{

      
// Рекурсивная вспомогательная функция для заполнения
// два экземпляра чисел от 1 до n
// в разрешении [0..2n-1]. 'curr' - текущее значение n.

static boolean fillUtil(int res[], int curr, int n) 

    // Если текущее число становится 0,

    // тогда все числа заполнены

    if (curr == 0

    return true

  

    // Попробуем поместить два экземпляра curr в

    // все возможные местоположения, пока решение не найдено

    int i; 

    for (i = 0; i < 2 * n - curr - 1; i++) 

    

        // Два 'curr' должны быть помещены в

        // расстояние curr + 1

        if (res[i] == 0 && res[i + curr + 1] == 0

        

              

            // Добавьте два экземпляра curr

            res[i] = res[i + curr + 1] = curr; 

      

            // Повторим, чтобы проверить, если вышеуказанное размещение

            // приводит к решению

            if (fillUtil(res, curr - 1, n)) 

                return true

      

            // Если решение невозможно,

            // затем возвращаемся

            res[i] = res[i + curr + 1] = 0

        

    

    return false

  
// Эта функция печатает результат для
// вводим число 'n', используя fillUtil ()

static void fill(int n) 

    // Создаем массив размером 2n и

    // инициализируем все элементы в нем как 0

    int res[] = new int[2 * n];

    int i; 

    for (i = 0; i < 2 * n; i++) 

    res[i] = 0

  

    // Если решение возможно,

    // затем распечатать его.

    if (fillUtil(res, n, n)) 

    

        for (i = 0; i < 2 * n; i++) 

            System.out.print(res[i] + " "); 

    

    else

        System.out.print("Not Possible"); 

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

public static void main (String[] args)

{

    fill(7); 


}

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

python3

# Программа Python3, основанная на возврате
# заполнить два экземпляра всех чисел
# от 1 до n определенным образом

def fillUtil(res, curr, n):

      

    # Рекурсивная вспомогательная функция для заполнения

    # два экземпляра чисел от 1 до n

    # в разрешении [0..2n-1]. 'curr' - текущее значение n.

  

    # Если текущий номер становится 0,

    # тогда все числа заполнены

    if curr == 0:

        return True

  

    # Попробуйте поместить два экземпляра curr на всех

    # возможные местоположения, пока решение не найдено

    for i in range(2 * n - curr - 1):

  

        # Два 'curr' должны быть размещены

        # на расстоянии 'curr + 1'

        if res[i] == 0 and res[i + curr + 1] == 0:

  

            # Поместите два экземпляра 'curr'

            res[i] = res[i + curr + 1] = curr

  

            # Повторить, чтобы проверить, если выше

            # размещение приводит к решению

            if fillUtil(res, curr - 1, n):

                return True

  

            # Если решение невозможно,

            # затем возвращаемся

            res[i] = 0

            res[i + curr + 1] = 0

  

    return False

  

def fill(n):

      

    # Эта функция печатает результат

    # для ввода номера 'n' с использованием fillUtil ()

  

    # Создайте массив размером 2n и

    # инициализировать все элементы в нем как 0

    res = [0] * (2 * n)

  

    # Если решение возможно, распечатайте его.

    if fillUtil(res, n, n):

        for i in range(2 * n):

            print(res[i], end = ' ')

        print()

    else:

        print("Not Possible")

  
Код водителя

if __name__ == '__main__':

    fill(7)

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

C #

// Программа на C # для возврата
// два экземпляра всех чисел от 1 до n
// определенным образом

using System;

  

class GFG

{

      
// Рекурсивная вспомогательная функция для заполнения
// два экземпляра чисел от 1 до n
// в разрешении [0..2n-1]. 'curr' - текущее значение n.

static bool fillUtil(int []res, int curr, int n) 

    // Если текущее число становится 0,

    // тогда все числа заполнены

    if (curr == 0) 

    return true

  

    // Попробуем поместить два экземпляра curr в

    // все возможные местоположения, пока решение не найдено

    int i; 

    for (i = 0; i < 2 * n - curr - 1; i++) 

    

        // Два 'curr' должны быть помещены в

        // расстояние curr + 1

        if (res[i] == 0 && res[i + curr + 1] == 0) 

        

              

            // Добавьте два экземпляра curr

            res[i] = res[i + curr + 1] = curr; 

      

            // Повторим, чтобы проверить, если вышеуказанное размещение

            // приводит к решению

            if (fillUtil(res, curr - 1, n)) 

                return true

      

            // Если решение невозможно,

            // затем возвращаемся

            res[i] = res[i + curr + 1] = 0; 

        

    

    return false

  
// Эта функция печатает результат для
// вводим число 'n', используя fillUtil ()

static void fill(int n) 

    // Создаем массив размером 2n и

    // инициализируем все элементы в нем как 0

    int []res=new int[2 * n];

    int i; 

    for (i = 0; i < (2 * n); i++) 

    res[i] = 0; 

  

    // Если решение возможно,

    // затем распечатать его.

    if (fillUtil(res, n, n)) 

    

        for (i = 0; i < 2 * n; i++) 

        Console.Write (res[i] + " "); 

    

    else

        Console.Write ("Not Possible"); 

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

static public void Main ()

{

    fill(7);


}

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


Выход:

7 3 6 2 5 3 2 4 7 6 5 1 4 1

Приведенное выше решение может быть не самым лучшим решением. Кажется, что на выходе есть закономерность. Я ищу лучшее решение от других гиков.

Эта статья пополняемая Асифа. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Заполните два экземпляра всех чисел от 1 до n определенным образом

0.00 (0%) 0 votes