fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. // Рекурсивно генерируем все допустимые строки и считаем их.
  8. // Сложность O(3^N)
  9. size_t recursive_helper(vector<char>& acc, size_t pos, size_t limit)
  10. {
  11.     size_t result = 0;
  12.  
  13.     if (pos <= limit) {
  14.         acc.push_back(1);
  15.         result += recursive_helper(acc, pos + 1, limit);
  16.         acc.push_back(3);
  17.         result += recursive_helper(acc, pos + 1, limit);
  18.         if (acc.empty() || acc.back() != 1) {
  19.             acc.push_back(2);
  20.             result += recursive_helper(acc, pos + 1, limit);
  21.         };
  22.     } else {
  23.         result = 1;
  24.     }
  25.  
  26.     acc.pop_back();
  27.  
  28.     return result;
  29. }
  30.  
  31. size_t task126_recursive(size_t N)
  32. {
  33.     vector<char> acc;
  34.     acc.reserve(N);
  35.     return recursive_helper(acc, 1, N);
  36. }
  37.  
  38.  
  39. // Динамика по длине строки. Для определения какой символ мы можем сейчас поставить
  40. // нужно знать только предыдущий символ. Чем и пользуемся.
  41. // Сложность O(N)
  42. size_t task126(size_t N)
  43. {
  44.     enum
  45.     {
  46.         END_1,
  47.         END_2,
  48.         END_3
  49.     };
  50.  
  51.     size_t a[] = {1, 1, 1};
  52.     size_t b[] = {0, 0, 0};
  53.  
  54.     size_t* prev = a;
  55.     size_t* cur = b;
  56.  
  57.     for (int i = 2; i < N+1; ++i) {
  58.         cur[END_1] = prev[END_1] + prev[END_2] + prev[END_3];
  59.         cur[END_2] = prev[END_2] + prev[END_3];
  60.         cur[END_3] = prev[END_1] + prev[END_2] + prev[END_3];
  61.         std::swap(cur,prev);
  62.     }
  63.  
  64.     return prev[END_1] + prev[END_2] + prev[END_3];
  65. }
  66.  
  67. // Можно заметить что в предыдущем алгоритме вычисления для
  68. // cur[END_1] и cur[END_3] одинаковы. Поэтому можно их обьединить
  69. // и за счет этого немного сьэкономить памяти
  70. size_t task126_tricky(size_t N)
  71. {
  72.     enum
  73.     {
  74.         END_OTHER,
  75.         END_2,
  76.     };
  77.  
  78.     size_t a[] = {2, 1};
  79.     size_t b[] = {0, 0};
  80.  
  81.     size_t* prev = a;
  82.     size_t* cur = b;
  83.  
  84.     for (int i = 2; i < N+1; ++i) {
  85.         cur[END_OTHER] = 2 * (prev[END_OTHER] + prev[END_2]);
  86.         cur[END_2] = prev[END_OTHER] / 2 + prev[END_2];
  87.         std::swap(cur,prev);
  88.     }
  89.  
  90.     return prev[END_OTHER] + prev[END_2];
  91. }
  92.  
  93.  
  94. int main() {
  95.  
  96.     for (size_t i = 1; i < 31; ++i) {
  97.         auto a = task126(i);
  98.         auto b = task126_tricky(i);
  99.         auto c = a; //task126_recursive(i); //можно раскоментировать но считать будет долго
  100.         std::cout << a << " == " << b << " == " << c <<  " is " << ((a == b && c == b) ? "true" : "false")  << std::endl;
  101.     }
  102.     return 0;
  103. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 == 3 == 3 is true
8 == 8 == 8 is true
21 == 21 == 21 is true
55 == 55 == 55 is true
144 == 144 == 144 is true
377 == 377 == 377 is true
987 == 987 == 987 is true
2584 == 2584 == 2584 is true
6765 == 6765 == 6765 is true
17711 == 17711 == 17711 is true
46368 == 46368 == 46368 is true
121393 == 121393 == 121393 is true
317811 == 317811 == 317811 is true
832040 == 832040 == 832040 is true
2178309 == 2178309 == 2178309 is true
5702887 == 5702887 == 5702887 is true
14930352 == 14930352 == 14930352 is true
39088169 == 39088169 == 39088169 is true
102334155 == 102334155 == 102334155 is true
267914296 == 267914296 == 267914296 is true
701408733 == 701408733 == 701408733 is true
1836311903 == 1836311903 == 1836311903 is true
4807526976 == 4807526976 == 4807526976 is true
12586269025 == 12586269025 == 12586269025 is true
32951280099 == 32951280099 == 32951280099 is true
86267571272 == 86267571272 == 86267571272 is true
225851433717 == 225851433717 == 225851433717 is true
591286729879 == 591286729879 == 591286729879 is true
1548008755920 == 1548008755920 == 1548008755920 is true
4052739537881 == 4052739537881 == 4052739537881 is true
https://ideone.com/VI8dD1
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!