Рубрики

Распечатать все комбинации точек, которые могут составить данное число

Вы можете выиграть три вида баскетбольных очков: 1, 2 и 3. Учитывая общую оценку n, распечатайте все комбинации, чтобы составить n.

Примеры:

For n = 1, the program should print following:
1

For n = 2, the program should print following:
1 1
2

For n = 3, the program should print following:
1 1 1
1 2
2 1 
3

For n = 4, the program should print following:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

and so on ...

Алгоритм:

  1. На первой позиции у нас может быть три числа 1 или 2 или 3.
  2. Сначала поставьте 1 на первую позицию и рекурсивно вызовите n-1.
  3. Затем поставьте 2 на первую позицию и рекурсивно вызовите n-2.
  4. Затем поставьте 3 на первую позицию и рекурсивно вызовите n-3.
  5. Если n становится 0, то мы сформировали комбинацию, которая составляет n, поэтому выведите текущую комбинацию.

Ниже приведена обобщенная реализация. В приведенной ниже реализации мы можем изменить MAX_POINT, если в баскетбольном матче есть более высокие баллы (более 3).

C ++

// C ++ программа для печати всего
// комбинации точек, которые
// можем составить данное число
#define MAX_POINT 3 
#define ARR_SIZE 100 
#include <bits/stdc++.h>

using namespace std;

  
/ * Утилита для печати массива arr [] * /

void printArray(int arr[], int arr_size); 

  
/ * Функция печатает все комбинации чисел 1, 2, ... MAX_POINT
эта сумма до п.
я используется в рекурсии отслеживать индекс в arr [], где следующий
элемент должен быть добавлен. Начальное значение i должно быть передано как 0 * /

void printCompositions(int n, int i) 

  

    / * массив должен быть статическим, так как мы хотим отслеживать

    значений, хранящихся в arr [] с использованием текущих вызовов

    printCompositions () в стеке вызовов функций * /

    static int arr[ARR_SIZE]; 

      

    if (n == 0) 

    

        printArray(arr, i); 

    

    else if(n > 0) 

    

        int k; 

        for (k = 1; k <= MAX_POINT; k++) 

        

            arr[i]= k; 

            printCompositions(n-k, i+1); 

        

    

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Утилита для печати массива arr [] * /

void printArray(int arr[], int arr_size) 

    int i; 

    for (i = 0; i < arr_size; i++) 

        cout<<arr[i]<<" "

    cout<<endl;

  
/ * Код водителя * /

int main() 

    int n = 5; 

      

    cout<<"Different compositions formed by 1, 2 and 3 of "<<n<<" are\n"

    printCompositions(n, 0); 

    return 0; 

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

С

// C программа для печати всех
// комбинации точек, которые
// можем составить данное число
#define MAX_POINT 3
#define ARR_SIZE 100
#include<stdio.h>

  
/ * Утилита для печати массива arr [] * /

void printArray(int arr[], int arr_size);

  
/ * Функция печатает все комбинации чисел 1, 2, ... MAX_POINT
эта сумма до п.
я используется в рекурсии отслеживать индекс в arr [], где следующий
элемент должен быть добавлен. Начальное значение i должно быть передано как 0 * /

void printCompositions(int n, int i)

{

  

    / * массив должен быть статическим, так как мы хотим отслеживать

    значений, хранящихся в arr [] с использованием текущих вызовов

    printCompositions () в стеке вызовов функций * /

    static int arr[ARR_SIZE];

      

    if (n == 0)

    {

        printArray(arr, i);

    }

    else if(n > 0)

    {

        int k; 

        for (k = 1; k <= MAX_POINT; k++)

        {

        arr[i]= k;

        printCompositions(n-k, i+1);

        }

    }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Утилита для печати массива arr [] * /

void printArray(int arr[], int arr_size)

{

    int i;

    for (i = 0; i < arr_size; i++)

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

    printf("\n");

}

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

int main()

{

    int n = 5;

      

    printf("Different compositions formed by 1, 2 and 3 of %d are\n", n);

    printCompositions(n, 0);

      

    getchar();

    return 0;

}

Джава

// Java-программа для печати всех
// комбинации точек, которые
// можем составить данное число

import java.io.*;

  

class GFG 

{

    // Функция печатает все комбинации чисел 1, 2, ... MAX_POINT

    // это сумма до n.

    // i используется в рекурсии, отслеживает индекс в arr [], где next

    // элемент должен быть добавлен. Начальное значение i должно быть передано как 0

    static void printCompositions(int arr[], int n, int i)

    {

        int MAX_POINT = 3;

        if (n == 0)

        {

            printArray(arr, i);

        }

        else if(n > 0)

        {

            for (int k = 1; k <= MAX_POINT; k++)

            {

                arr[i]= k;

                printCompositions(arr, n-k, i+1);

            }

        }

    }

      

    // Утилита для печати массива arr []

    static void printArray(int arr[], int m)

    {

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

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

        System.out.println();

    }

      

      

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

    public static void main (String[] args) 

    {

        int n = 5;

        int size = 100;

        int[] arr = new int[size];

        System.out.println("Different compositions formed by 1, 2 and 3 of "+ n + " are");

        printCompositions(arr, n, 0);

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python3 программа для печати всех комбинаций
Количество точек, которые могут составить данное число

MAX_POINT = 3;

ARR_SIZE = 100;

  

arr = [0] * ARR_SIZE;

  
# Функция печатает все комбинации
Количество чисел 1, 2, ... MAX_POINT этой суммы
# до п. меня используют в рекурсии
# трек индекса в arr [] где следующий
Элемент # должен быть добавлен. Начальная стоимость
№ из меня должен быть передан как 0

def printCompositions(n, i):

      

    # массив должен быть статическим, как мы

    # хочу отслеживать значения

    # хранится в arr [] используя current

    # вызовы printCompositions () в

    # стек вызовов функций * /

    if (n == 0):

        printArray(arr, i);

    elif(n > 0):

        for k in range(1,MAX_POINT + 1):

            arr[i] = k;

            printCompositions(n - k, i + 1);

  
# ПОЛЕЗНЫЕ ФУНКЦИИ * /
# Утилита для печати массива arr [] * /

def printArray(arr, arr_size):

    for i in range(arr_size):

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

    print();

  
Код водителя

n = 5;

print("Different compositions formed " + 

         "by 1, 2 and 3 of", n, " are");

printCompositions(n, 0);

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

C #

// C # программа для печати всех
// комбинации точек, которые
// можем составить данное число

using System;

  

class GFG {

      

    // Функция печатает все комбинации чисел

    // 1, 2, ... MAX_POINT с суммой до n. я есть

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

    // arr [] где следующий элемент должен быть добавлен.

    // Начальное значение i должно быть передано как 0

    static void printCompositions(int[] arr, int n, int i)

    {

        int MAX_POINT = 3;

        if (n == 0) {

            printArray(arr, i);

        }

        else if (n > 0) {

            for (int k = 1; k <= MAX_POINT; k++) {

                arr[i] = k;

                printCompositions(arr, n - k, i + 1);

            }

        }

    }

  

    // Утилита для печати массива arr []

    static void printArray(int[] arr, int m)

    {

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

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

        Console.WriteLine();

    }

  

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

    public static void Main()

    {

        int n = 5;

        int size = 100;

        int[] arr = new int[size];

          

        Console.WriteLine("Different compositions formed"

                    + " by 1, 2 and 3 of " + n + " are");

        printCompositions(arr, n, 0);

    }

}

  
// Предоставлено Sam007

PHP

<?php
// PHP программа для печати всего
// комбинации точек, которые
// можем составить данное число

$MAX_POINT = 3;

$ARR_SIZE = 100;

  

$arr = array($ARR_SIZE);

  
/ * Функция печатает все комбинации
чисел 1, 2, ... MAX_POINT этой суммы
до п. меня используют в рекурсии
трек индекса в arr [], где следующий
элемент должен быть добавлен. Начальная стоимость
из я должен быть передан как 0 * /

function printCompositions($n, $i)

{

    global $arr, $MAX_POINT, $ARR_SIZE;

      

    / * массив должен быть статическим, как мы

    хочу отслеживать значения

    хранится в arr [] используя current

    вызовы printCompositions () в

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

    if ($n == 0)

    {

        printArray($arr, $i);

    }

    else if($n > 0)

    {

        for ($k = 1; $k <= $MAX_POINT; $k++)

        {

            $arr[$i] = $k;

            printCompositions($n - $k, $i + 1);

        }

    }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Утилита для печати массива arr [] * /

function printArray($arr, $arr_size)

{

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

        echo $arr[$i]." ";

    echo "\n";

}

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

$n = 5;

  

echo "Different compositions formed" .

     " by 1, 2 and 3 of ".$n." are\n";

printCompositions($n, 0);

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


Выход:

Different compositions formed by 1, 2 and 3 of 5 are
1 1 1 1 1 
1 1 1 2 
1 1 2 1 
1 1 3 
1 2 1 1 
1 2 2 
1 3 1 
2 1 1 1 
2 1 2 
2 2 1 
2 3 
3 1 1 
3 2 

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы

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

Распечатать все комбинации точек, которые могут составить данное число

0.00 (0%) 0 votes