R elementlərinin mümkün olan bütün birləşmələrini N ölçülü verilmiş bir massivdə çap edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Boz Portağal Oxigen cüzdanı
RiyaziyyatBaxılıb 1038

Problem bəyanat

"Verilən R Elementlərinin Bütün Mümkün Kombinasiyalarını Çap et Geyim ölçüsü N ”problemi ilə n ölçülü bir sıra verdik. Massivdə r ölçüsündə bütün birləşmələri tapın.

Giriş Formatı

Birincisi və N tam ədədi olan yalnız bir sətir.

Boşluqla ayrılmış n tam ədədi ehtiva edən ikinci sətir.

Bir R tam ədədi olan üçüncü sətir.

Çıxış formatı

Verilən bir sıra R elementlərinin bütün mümkün birləşmələrini elə çap edin ki, hər sətir tam bir kombinasiyadır.

Məhdudiyyətlər

  • 1 <= N <= 10
  • 1 <= a [i] <= 10 ^ 9

misal

4 
1 2 3 4
2
1 2
1 3
1 4
2 3
2 4
3 4

Alqoritm

Bu metodda əsas fikir R ölçüsündə müvəqqəti bir ans [] massivi yaratmaq və nəticəni orada saxlamaqdır.

Bütün çıxışı bir-bir saxlayan müvəqqəti bir 'məlumat []' düzəldirik. Fikir, məlumatdakı ilk indeksdən (indeks = 0) başlayaraq [bu indeksdə bir-bir düzəltmə elementləri və qalan indekslər üçün təkrarlanmalıdır. Giriş massivi {1, 2, 3, 4, 5} və r 3 olsun. Əvvəlcə məlumatlarda [] indeksində 1-i düzəldirik, sonra qalan indekslər üçün təkrarlanır, sonra 0-da 2-ni düzəldirik və təkrarlayırıq. Nəhayət, 0-ü düzəldirik və qalan indekslər üçün təkrar edirik. Verilərdəki elementlərin sayı [] r-a (birləşmə ölçüsü) bərabər olduqda, məlumatları [] yazdırırıq.

1. Ans [] içindəki ilk indeksdən başlayın, bu indeksdə bir-bir düzəltmə elementləri və qalan indekslər üçün təkrarlayın.

2. Ans [] massivi dolduqda ans [] dizisini çap edin.

Həyata keçirilməsi

Verilən N ölçülü massivdə R Elementlərinin mümkün olan bütün birləşmələrini çap etmək üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 

void combination(int arr[], int data[], int start, int end, int index, int r) 
{ 
  if(index == r) 
  { 
    for (int j = 0; j < r; j++) 
      cout << data[j] << " "; 
    cout << endl; 
    return; 
  } 
  for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
  { 
    data[index] = arr[i]; 
    combination(arr, data, i+1, end, index+1, r); 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int r;
  cin>>r;
  int data[r]; 
  combination(a,data,0,n-1,0,r);
} 

N ölçüsündə müəyyən bir massivdə R Elementlərinin Mümkün Bütün Kombinasiyalarını Çıxartmaq üçün Java Proqramı

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void combination(int arr[], int data[], int start, int end, int index, int r) 
    { 
            if(index == r) 
            { 
                    for(int j = 0; j < r; j++) 
                           System.out.print(data[j]+" "); 
                    System.out.println();
                    return; 
            } 
            for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
            { 
                    data[index] = arr[i]; 
                    combination(arr, data, i+1, end, index+1, r); 
            } 
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int r = sr.nextInt();
        int data [] = new int[r];
        combination(a,data,0,n-1,0,r);
    }
}
5
105 21 35 10 183
3
105 21 35 
105 21 10 
105 21 183 
105 35 10 
105 35 183 
105 10 183 
21 35 10 
21 35 183 
21 10 183 
35 10 183

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (nCr) burada n - verilən massivin ölçüsü və r - birləşmə üçün götürdüyümüz elementlərin sayı.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Translate »