|
|
back to boardSolution of the program Posted by aybek 11 Dec 2013 00:44 I decided to write post my solution and comment it, may be it will be useful for someone. So, you have recursively defined sequence. Of course first idea is to write recursive function. But, we need to find max element from 1 to n and if you will call function for every n in order to find maximum element, such algorithm will cost O(n^2). Another way is to store results gotten before in special array and compare gotten result with max of them. I hope I helped you at least as it. And here is accepted solution in C++: #include <iostream> #define max(a, b) ((a) < (b) ? (b): (a)) int last = 1; int mem[100000]; int max[100000]; int F(int n) { for (int i = last+1; i <= n; ++i) { if (i%2) mem[i] = mem[i/2]+mem[i/2+1]; else mem[i] = mem[i/2]; max[i] = max(mem[i], max[i-1]); } return max[n]; } int main() { mem[0] = 0; mem[1] = 1; max[0] = 0; max[1] = 1; int n; while (1) { std::cin >> n; if (!n) break;
std::cout << F(n) << std::endl; } return 0; } Re: Solution of the program well done, bro.... :) here's another way... >> -------------------------------------------------------------------------------------- #include <iostream> using namespace std; int arr[100000]; int find_max(int n) { int maximum = 0; for(int i = 0; i <= n; i++) if(maximum < arr[i]) maximum = arr[i]; return maximum; } int main() { int n[11], i, idx; arr[0] = 0; arr[1] = 1; for(idx = 2; idx < 100000; idx++) { if(idx & 1) { // when idx is odd. i = (idx-1) / 2; arr[idx] = arr[i] + arr[i+1]; } else { // when idx is even. i = idx / 2; arr[idx] = arr[i]; } } i = 0; while(cin >> n[i], n[i++] != 0); i--; idx = i; for(i = 0; i < idx; i++) { cout << find_max(n[i]) << '\n'; } return 0; } ------------------------------------------------------------------------------------- Edited by author 07.06.2015 08:42 |
|
|