fork(1) download
copy 
  1. /*
  2.  
  3. U ovom problemu potrebno je prebrojati ukupni broj rekurzivnih palindromskih (RP) particija
  4. za dani broj n u oznaci f(n)
  5.  
  6. Jedna od ideja jest koristiti podijeli-pa-vladaj pristup koji se temelji na sljedecem:
  7.   a) Podijeli: dani broj n particioniraj s obzirom na parnost: 
  8.   								n = 2k =   w+2j+w, za neki k>0 cijeli broj i j>=0  cijeli broj
  9.   								n = 2k+1 = w+(2j+1)+w za neki k>0 i j>=0 cijeli broj
  10.   	gdje w = k-j.
  11.   	Pretpostavimo da je n=2k, dakle paran. 
  12.   	Tada je za sve j>=0 cijele brojeve, f(k-j) RP particija zajedno s 2j čine podskup od RP particija za n.
  13.   	Ukupno, sumirajući po j=0,1,2,...,k dobivamo 
  14.   				f(n) = \sum^k_{j=0}  f(k-j) (*)
  15.   	što kad se oduzme s f(n-2) dobivamo rekurziju
  16.   				f(n) = f(n-2)+f(n/2), za n = 2k (R1)
  17.   	
  18.   	Ukoliko je n=2k+1, dakle neparan, f(k-j) RP particija zajedno s (2j+1) čine isto tako podskup od RP particija
  19.   	za n, pa vrijedi f(n) = \sum^k_{j=0}  f(k-j) što iz (*) zaključujemo 
  20.   				f(n) = f(n-1), za n = 2k+1 (R2)
  21.   b) Vladaj: racunaj f(n-1), f(n-2), f(n/2)
  22.   c) Spoji: spoji rjesenja prema (R1) i (R2)
  23.   
  24.   **komentar: programski kod upravo implemntira ovo razmatranje. Dodatno, omogućuje memoizaciju: spremanje
  25.   vrijednosti jednom pozvanih rekurzivnih funkcija. 
  26.   
  27.  
  28.  
  29. */
  30.  
  31. #include <iostream>
  32. #include <fstream>
  33. #include <cstring>
  34. #include <cstdlib>
  35. using namespace std;
  36.  
  37. #define None 0
  38.  
  39. long *RP;
  40.  
  41. // ukoliko zelimo smanjiti broj poziva rekurzija spremamo rezultate jednom izracunatih rekurzija
  42. #define NO_MEMO
  43.  
  44. // ukoliko zelimo smanjiti broj poziva rekurzija spremamo rezultate jednom izracunatih rekurzija
  45. // odkomentirajte sljedeci redak
  46. #define MEMO
  47.  
  48. #ifdef MEMO
  49. #undef NO_MEMO
  50. #endif
  51.  
  52. int PalindromePartition(int n)
  53. {
  54.      if (n ==0 || n == 1) 
  55.      {
  56.        # ifdef MEMO 
  57.        RP[0] = RP[1] = 1;
  58.        #endif
  59.        return 1;
  60.      }
  61.      // else
  62.       #ifdef NO_MEMO
  63.       if ((n % 2) == 0) return PalindromePartition(n-2)+PalindromePartition(n/2);
  64.       else return PalindromePartition(n-1);
  65.       #endif
  66.       #ifdef MEMO
  67.       if((n%2)==0)
  68.       {
  69.         RP[n-2] = (RP[n-2] == None) ? PalindromePartition(n-2) : RP[n-2];
  70.         RP[n/2] = (RP[n/2] == None) ? PalindromePartition(n/2) : RP[n/2];
  71.         return (RP[n-2]+RP[n/2]);
  72.       }
  73.       else
  74.       {
  75.         RP[n-1]  = (RP[n-1] == None) ? PalindromePartition(n-1) : RP[n-1];
  76.         return RP[n-1];
  77.       }
  78.       #endif
  79. }
  80.  
  81.  
  82. int main()
  83. {
  84.  
  85.     // ucitaj broj testova
  86.     int N;
  87.     cin >> N;
  88.  
  89.  
  90.     int num_of_Tests = 0;
  91.  
  92.     // vrijednost
  93.     int n;
  94.  
  95.     while(++num_of_Tests <= N)
  96.     {
  97.       cin >> n;
  98.       #ifdef MEMO
  99.       RP = new long[n];
  100.       memset(RP, None, sizeof(RP[0]) * n);
  101.       #endif 
  102.       int sol = PalindromePartition(n);
  103.       cout << sol << endl;
  104.       #ifdef MEMO
  105.       delete [] RP;
  106.       #endif
  107.     }
  108.     return 0;
  109. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
3
4
7
20
stdout
copy 
4
6
60
https://ideone.com/OwU7FC
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!