zadacha

Boyov · 07.11.2002, 08:51

Zdarova lyudi,

Goda 2 nazad na olimpiade po informatike mne popalas' sleduyuschaya zadacha:

Dano chislo N (N<=200) nujno nayti skol'kimi sposobami eto chislo mojno predstavit' v vide summi nepovtoryayushixsya natural'nix chisel.

Naprimer dlya N=10 eto chishlo budet 10.

1.10=10+0
2.10=1+9
3.10=8+2
4.10=7+3
5.10=6+4
6.10=1+2+7
7.10=1+3+6
8.10=1+4+5
9.10=2+3+5
10.10=1+2+3+4

po moemu vse.

Koroche eta zadacha 'legko

' reshaetsya esil delaesh sami naitupeishi perebor (tipa 26(!!!) vlojennix ciklov), no estestvenno eto reshenie nel'zya schitat' "xelqin motik".

Kakie u vas budut idei ?

Spasibo

Boyov

di0phantus · 07.11.2002, 16:40

xorsho bi utochnit' odnu vazhuyu detal'...
predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`?

Griffon2-7 · 07.11.2002, 17:01

Если учитывается вариант 10+0=10, то почему не учитываются остальныер варианты, где фигурирует 0?

Например: 0+1+2+3+4=10

Может 0 вообще не надо учитывать? Число вариантов уменьшится в 2 раза

Boyov · 07.11.2002, 17:14

Quote:

Originally posted by di0phantus:
xorsho bi utochnit' odnu vazhuyu detal'...
predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`?

nujno prosto vichislit' kolichestvo

Boyov

di0phantus · 07.11.2002, 17:37

Code:

int getCount (int number){
  return getIt(number, number);
}

int getIt(int number, int pieces){
  if (pieces == number)
    return 1;
  return getForEveryPieces(number, pieces) + getIt(number, pieces-1);
}

a eto funkciaya vozvrashyaet reshenie zadachi s myachami, po kombinatorike
formulu ne pomnyu nado vivesti. zadacha takaya.

Code:

SUM(x[i]) = N, i = 1, ..., k.
x[i] >= a; pri lyubom i.
(a=1 eto nash sluchay)

no eto reshenie vklyuchaet takzhe povtori, tipa

Code:

primer N=5, k=3, a=1 
1+2+2
2+1+2
2+2+1

tak chto nado otvet razdelit na

Code:

k!. 
int getForEveryPieces (int number, int pieces){
}

naverno tak.

Grigor · 07.11.2002, 20:28

Можно так.
Здесь counts[i][j] - количество вариантов разложений числа i, в которых числа меньше j.
Используется следующее рекуррентное соотношение counts[i][j] = counts[i][j-1] + counts[i - j + 1][j-1]

Code:

 
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> intVec;

int main()
{
	int n;
	cin >> n;
	
	vector <intVec> counts;
	counts.resize(n+1);
	for (int i = 0; i < n + 1; i++)
		counts[i].resize(n + 2);

	for (int i = 1; i < n + 1; i++)
		counts[i][1] = 0;
	for (int i = 2; i < n + 2; i++)
		counts[1][i] = 1;
	
	for (int i = 2; i <= n; i++)
		for (int j = 2; j <= n+1; j++)
			if (j > i) 
				counts[i][j] = counts[i][i] + 1;
			else
				counts[i][j] = counts[i][j-1] + counts[i-j+1][j-1];

	cout << counts[n][n+1] << endl;

	return 0;
}

Временная сложность этого алгоритма O(N²), что при N <= 200 приемлимо.