Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 07.11.2002, 08:51   #1
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Post zadacha

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
__________________
Free your mind and your OS will follow
Reply With Quote
Old 07.11.2002, 16:40   #2
Младенец
 
di0phantus's Avatar
 
Join Date: 05 2002
Location: Yerevan, RA
Posts: 58
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Exclamation

xorsho bi utochnit' odnu vazhuyu detal'...
predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`?
Reply With Quote
Old 07.11.2002, 17:01   #3
hex god
 
Griffon2-7's Avatar
 
Join Date: 03 2002
Location: Yerevan, AM
Age: 39
Posts: 3,172
Downloads: 1
Uploads: 0
Reputation: 9 | 0
Post

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

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

Может 0 вообще не надо учитывать? Число вариантов уменьшится в 2 раза
Reply With Quote
Old 07.11.2002, 17:14   #4
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Post

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
Reply With Quote
Old 07.11.2002, 17:37   #5
Младенец
 
di0phantus's Avatar
 
Join Date: 05 2002
Location: Yerevan, RA
Posts: 58
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

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.
Reply With Quote
Old 07.11.2002, 20:28   #6
Младенец
 
Join Date: 05 2002
Location: Yerevan
Posts: 5
Downloads: 1
Uploads: 0
Reputation: 0 | 0
Post

Можно так.
Здесь 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 приемлимо.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 09:02.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.