Рубрики

Вывести все возрастающие последовательности длины k из первых n натуральных чисел

Если даны два натуральных числа n и k, выведите все возрастающие последовательности длины k, чтобы элементы в каждой последовательности были из первых n натуральных чисел.

Примеры:

Input: k = 2, n = 3
Output: 1 2
        1 3
        2 3 

Input: k = 5, n = 5
Output: 1 2 3 4 5

Input: k = 3, n = 5
Output: 1 2 3
        1 2 4
        1 2 5
        1 3 4
        1 3 5
        1 4 5
        2 3 4
        2 3 5
        2 4 5
        3 4 5

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

Это хороший вопрос рекурсии. Идея состоит в том, чтобы создать массив длиной k. Массив хранит текущую последовательность. Для каждой позиции в массиве мы проверяем предыдущий элемент, и один за другим помещаем все элементы больше, чем предыдущий элемент. Если предыдущего элемента (первой позиции) нет, мы ставим все числа от 1 до n.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для печати всех возрастающих последовательностей
// длина 'k' такая, что элементы в каждой последовательности
// взяты из первых «n» натуральных чисел.
#include<iostream>

using namespace std;

  
// Утилита для печати содержимого arr [0..k-1]

void printArr(int arr[], int k)

{

    for (int i=0; i<k; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  
// Рекурсивная функция для печати всех возрастающих последовательностей
// первых n натуральных чисел. Каждая последовательность должна быть
// длина k. Массив arr [] используется для хранения текущего
// последовательность

void printSeqUtil(int n, int k, int &len, int arr[])

{

    // Если длина текущей увеличивающейся последовательности становится k,

    // распечатать

    if (len == k)

    {

        printArr(arr, k);

        return;

    }

  

    // Определить начальный номер для размещения в текущей позиции:

    // Если длина равна 0, то предыдущих элементов нет

    // в обр []. Так что начните ставить новые цифры с 1.

    // Если длина не равна 0, то начинать со значения

    // предыдущий элемент плюс 1.

    int i = (len == 0)? 1 : arr[len-1] + 1;

  

    // Увеличить длину

    len++;

  

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

    // элемент) на новой позиции.

    while (i<=n)

    {

        arr[len-1] = i;

        printSeqUtil(n, k, len, arr);

        i++;

    }

  

    // Это важно. Переменная 'len' распределяется между

    // все вызовы функций в дереве рекурсии. Его значение должно быть

    // возвращаем перед следующей итерацией цикла while

    len--;

}

  
// Эта функция печатает все возрастающие последовательности
// первые n натуральных чисел. Длина каждой последовательности
// должно быть k. Эта функция в основном использует printSeqUtil ()

void printSeq(int n, int k)

{

    int arr[k];  // Массив для хранения отдельных последовательностей

    int len = 0; // Начальная длина текущей последовательности

    printSeqUtil(n, k, len, arr);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int k = 3, n = 7;

    printSeq(n, k);

    return 0;

}

Джава

// Java программа для печати всех
// увеличивающиеся последовательности
// длина 'k' такая, что
// элементы в каждой последовательности
// являются первыми 'n'
// натуральные числа.

  

class GFG {

      

    // Утилита для печати

    // содержимое arr [0..k-1]

    static void printArr(int[] arr, int k)

    {

        for (int i = 0; i < k; i++)

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

        System.out.print("\n");

    }

      

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

    // все возрастающие последовательности

    // первых n натуральных чисел.

    // Каждая последовательность должна быть

    // длина k. Массив arr [] является

    // используется для хранения текущей последовательности

    static void printSeqUtil(int n, int k, 

                             int len, int[] arr)

    {

          

        // Если длина тока увеличивается

        // последовательность становится k, выведите ее

        if (len == k)

        {

            printArr(arr, k);

            return;

        }

      

        // Определяем начальный номер

        // поставить на текущую позицию:

        // Если длина равна 0, тогда

        // нет предыдущих элементов

        // в обр []. Так что начните ставить

        // новые номера с 1.

        // Если длина не равна 0,

        // затем начинаем со значения

        // предыдущий элемент плюс 1.

        int i = (len == 0) ? 1 : arr[len - 1] + 1;

      

        // Увеличить длину

        len++;

      

        // Поместить все числа (которые

        // больше предыдущего

        // элемент) на новой позиции.

        while (i <= n)

        {

            arr[len - 1] = i;

            printSeqUtil(n, k, len, arr);

            i++;

        }

      

        // Это важно.

        // переменная 'len' используется совместно

        // все вызовы функций в рекурсии

        // дерево. Его значение должно быть

        // возвращено до следующего

        // итерация цикла while

        len--;

    }

      

    // Эта функция печатает все

    // увеличивающиеся последовательности

    // первые n натуральных чисел.

    // Длина каждой последовательности

    // должно быть k. Эта функция

    // в основном использует printSeqUtil ()

    static void printSeq(int n, int k)

    {

          

        // массив для хранения

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

        int[] arr = new int[k];

          

        // Начальная длина

        // текущая последовательность

        int len = 0

        printSeqUtil(n, k, len, arr);

    }

  

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

    static public void main (String[] args)

    {

        int k = 3, n = 7;

        printSeq(n, k);

    }

}

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

python3

# Python3 программа для печати всех
# увеличение последовательности длины
# 'k' такое, что элементы в
# каждая последовательность от первого
# 'n' натуральные числа.

  
# Полезная функция для
# печатать содержимое arr [0..k-1]

def printArr(arr, k):

    for i in range(k):

        print(arr[i], end = " ");

    print();

  
# Рекурсивная функция для печати
# все возрастающие последовательности
# первые n натуральных чисел. каждый
# последовательность должна быть длиной k.
# Массив arr [] используется для
# сохранить текущую последовательность.

def printSeqUtil(n, k,len1, arr):

      

    # Если длина тока

    # увеличивающаяся последовательность

    # становится k, распечатай

    if (len1 == k):

        printArr(arr, k);

        return;

  

    # Определить начальный номер

    # поставить на текущую позицию:

    # Если длина равна 0, то есть

    # нет предыдущих элементов

    # в обр []. Так что начните ставить

    # новые номера с 1. Если длина

    # не равно 0, затем начните со значения

    # предыдущего элемента плюс 1.

    i = 1 if(len1 == 0) else (arr[len1 - 1] + 1);

  

    # Увеличить длину

    len1 += 1;

  

    # Положите все числа (которые больше

    # чем предыдущий элемент) в

    # Новая позиция.

    while (i <= n):

        arr[len1 - 1] = i;

        printSeqUtil(n, k, len1, arr);

        i += 1;

  

    # Это важно. Переменная

    # 'len' распределяется между всеми функциями

    # вызовы в дереве рекурсии. Его ценность

    # должен быть возвращен до следующего

    # итерация цикла while

    len1 -= 1;

  
# Эта функция печатает все увеличивающиеся
# последовательности первых n натуральных чисел.
# Длина каждой последовательности должна быть
# к. Эта функция в основном использует printSeqUtil ()

def printSeq(n, k):

        arr = [0] * k; # Массив для хранения

                       # отдельные последовательности

        len1 = 0; # Начальная длина

                  # текущая последовательность

        printSeqUtil(n, k, len1, arr);

  
Код водителя

k = 3

n = 7;

printSeq(n, k);

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

C #

// C # программа для печати всех
// увеличивающиеся последовательности
// длина 'k' такая, что
// элементы в каждой последовательности
// являются первыми 'n'
// натуральные числа.

using System;

  

class GFG {

      

    // Утилита для печати

    // содержимое arr [0..k-1]

    static void printArr(int[] arr, int k)

    {

        for (int i = 0; i < k; i++)

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

        Console.WriteLine();

    }

      

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

    // все возрастающие последовательности

    // первых n натуральных чисел.

    // Каждая последовательность должна быть

    // длина k. Массив arr [] является

    // используется для хранения текущей последовательности

    static void printSeqUtil(int n, int k, 

                             int len, int[] arr)

    {

          

        // Если длина тока увеличивается

        // последовательность становится k, выведите ее

        if (len == k)

        {

            printArr(arr, k);

            return;

        }

      

        // Определяем начальный номер

        // поставить на текущую позицию:

        // Если длина равна 0, тогда

        // нет предыдущих элементов

        // в обр []. Так что начните ставить

        // новые номера с 1.

        // Если длина не равна 0,

        // затем начинаем со значения

        // предыдущий элемент плюс 1.

        int i = (len == 0) ? 1 : arr[len - 1] + 1;

      

        // Увеличить длину

        len++;

      

        // Поместить все числа (которые

        // больше предыдущего

        // элемент) на новой позиции.

        while (i <= n)

        {

            arr[len - 1] = i;

            printSeqUtil(n, k, len, arr);

            i++;

        }

      

        // Это важно.

        // переменная 'len' используется совместно

        // все вызовы функций в рекурсии

        // дерево. Его значение должно быть

        // возвращено до следующего

        // итерация цикла while

        len--;

    }

      

    // Эта функция печатает все

    // увеличивающиеся последовательности

    // первые n натуральных чисел.

    // Длина каждой последовательности

    // должно быть k. Эта функция

    // в основном использует printSeqUtil ()

    static void printSeq(int n, int k)

    {

          

        // массив для хранения

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

        int[] arr = new int[k];

          

        // Начальная длина

        // текущая последовательность

        int len = 0; 

        printSeqUtil(n, k, len, arr);

    }

  

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

    static public void Main ()

    {

        int k = 3, n = 7;

        printSeq(n, k);

    }

}

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

PHP

<?php
// PHP программа для печати всего
// увеличивающиеся последовательности
// длина 'k' такая, что
// элементы в каждой последовательности
// являются первыми 'n' натуральными
// числа.

  
// Функция полезности для
// выводим содержимое arr [0..k-1]

function printArr($arr, $k)

{

    for ($i = 0; $i < $k; $i++)

        echo $arr[$i], " ";

        echo "\n";

}

  
// Рекурсивная функция для
// печатаем все по возрастанию
// последовательности первых n
// натуральные числа. каждый
// последовательность должна быть длиной
// к. Используется массив arr []
// сохранить текущую последовательность.

function printSeqUtil($n, $k

                      $len, $arr)

{

    // Если длина тока

    // увеличивающаяся последовательность

    // становится k, распечатай

    if ($len == $k)

    {

        printArr($arr, $k);

        return;

    }

  

    // Определяем начальный номер

    // поставить на текущую позицию:

    // Если длина равна 0, тогда

    // нет предыдущих элементов

    // в обр []. Так что начните ставить

    // новые числа с 1. Если длина

    // не равно 0, тогда начнем со значения

    // предыдущего элемента плюс 1.

    $i = ($len == 0)? 1 : 

          $arr[$len - 1] + 1;

  

    // Увеличить длину

    $len++;

  

    // Поместить все числа (которые

    // больше предыдущего

    // элемент) на новой позиции.

    while ($i <= $n)

    {

        $arr[$len-1] = $i;

        printSeqUtil($n, $k

                     $len, $arr);

        $i++;

    }

  

    // Это важно.

    // переменная 'len' является общей

    // среди всех вызовов функций

    // в дереве рекурсии. это

    // значение должно быть возвращено

    // до следующей итерации

    // цикл while

      

    $len--;

}

  
// Эта функция печатает все
// увеличивающиеся последовательности
// первые n натуральных чисел.
// Длина каждой последовательности
// должно быть k. Эта функция
// в основном использует printSeqUtil ()

function printSeq($n, $k)

{

        $arr = array(); // массив для хранения

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

        $len = 0; // Начальная длина

                  // текущая последовательность

        printSeqUtil($n, $k

                     $len, $arr);

}

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

$k = 3; 

$n = 7;

printSeq($n, $k);

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


Выход:

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

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

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

Вывести все возрастающие последовательности длины k из первых n натуральных чисел

0.00 (0%) 0 votes