![]() |
![]() | #1 |
4294967296 Join Date: 03 2002 Location: /proc/1 Age: 36
Posts: 379
Downloads: 4 Uploads: 0
Reputation: 0 | 0 | ![]()
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 ![]() Kakie u vas budut idei ? Spasibo Boyov
__________________ Free your mind and your OS will follow |
![]() |
![]() | #2 |
Младенец Join Date: 05 2002 Location: Yerevan, RA
Posts: 58
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
xorsho bi utochnit' odnu vazhuyu detal'... predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`? |
![]() |
![]() | #3 |
hex god Join Date: 03 2002 Location: Yerevan, AM Age: 43
Posts: 3,172
Downloads: 1 Uploads: 0
Reputation: 9 | 0 | ![]()
Если учитывается вариант 10+0=10, то почему не учитываются остальныер варианты, где фигурирует 0? Например: 0+1+2+3+4=10 Может 0 вообще не надо учитывать? Число вариантов уменьшится в 2 раза ![]() |
![]() |
![]() | #4 | |
4294967296 Join Date: 03 2002 Location: /proc/1 Age: 36
Posts: 379
Downloads: 4 Uploads: 0
Reputation: 0 | 0 | ![]() Quote:
Boyov | |
![]() |
![]() | #5 |
Младенец Join Date: 05 2002 Location: Yerevan, RA
Posts: 58
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() 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); } 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) Code: primer N=5, k=3, a=1 1+2+2 2+1+2 2+2+1 Code: k!. int getForEveryPieces (int number, int pieces){ } |
![]() |
![]() | #6 |
Младенец Join Date: 05 2002 Location: Yerevan
Posts: 5
Downloads: 1 Uploads: 0
Reputation: 0 | 0 | ![]()
Можно так. Здесь 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; } |
![]() |
Sponsored Links |