This is an old revision of the document!


Поставка задатка

На улазу се задају природни бројеви N и K који означавају број елемената скупа чије комбинације са понављањем тражимо, односно класу тих комбинација. Након задавања тих параметара, корисник уноси елементе скупа. Програм треба да ради за скупове објеката било којег типа.

Поступак решавања

Сажетак алгоритма

Алгоритам конструкције комбинација са понављањем произвољног скупа заснива се на генерисању комбинација са понављањем скупа природних бројева од 0 до N-1. Нека је А коначан скуп чије комбинације тражимо(|A|=N). Тада можемо успоставити бијективно пресликавање f:A→{0,…,N-1}. Нека је b1b2…bk произвољна k-комбинација са понављањем скупа {0,…,N-1}. Одговарајућа комбинација са понављањем скупа А је f-1(b1b2…bk).

Комбинације са понављањем скупа {0,...,N-1}

Пример

Нека важи да је N=3 и K=3. Комбинације са понављањем скупа {0,1,2} су:

  1. 000
  2. 001
  3. 002
  4. 011
  5. 012
  6. 022
  7. 111
  8. 112
  9. 122
  10. 222

Функција која налази наредну комбинацију са понављањем на основу задате

int sledeca(int *komb, int k, int n){
	int i,s;
	s=k-1;
	while(s>=0 && !(komb[s]<n-1)) s--;
	if(s<0) return 0;
	komb[s]=komb[s]+1;
	for(i=s;i<k-1;i++) komb[i+1]=komb[i];
	return 1;
}

idi na sazetak Сажетак алгоритма

 
smor3.1358989114.txt.gz · Last modified: 2013/01/24 01:58 by aleksandar.mladenovic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki