Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 22.09.2017
Сообщений: 4
1

Напишите функцию, возвращающее ссылку на максимальное число в массиве, являющееся числом Фибонначи

08.02.2018, 11:22. Просмотров 1196. Ответов 8
Метки нет (Все метки)

Напишите функцию, возвращающую ссылку на максимальное число, встречающееся в заданном массиве произвольного размера (аргумент функции), являющееся числом Фиббоначчи. Если такого числа нет, то возвратить ссылку на любое из максимальных чисел массива. Замените значение этого элемента нулевым значением.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.02.2018, 11:22
Ответы с готовыми решениями:

Напишите функцию int CountMax (double A[], int n) которая подсчитывает, сколько раз в массиве встречается значение, являющееся максимальным
Напишите функцию int CountMax (double A, int n) которая подсчитывает, сколько раз в массиве...

Напишите функцию,возвращающее среднее арифметическое
Напишите функцию,возвращающее среднее арифметическое элементов в однородном целочисленном массиве с...

Дано целое число N (> 1), являющееся числом Фибоначчи: N = FK . Найти целое число K — порядковый номер числа Фибоначчи N
помогите пожалуйста на с написать, или хотя бы какой нить толчок сделать. Дано целое число N (> 1),...

Программа, находящая максимальное число, являющееся палиндромом в строке и заменяющая на него все слова, где есть цифры
Дана строка, написать программу, которая находит максимальное число, являющееся палиндромом (числа...

8
410 / 262 / 156
Регистрация: 30.04.2017
Сообщений: 516
08.02.2018, 13:30 2
Решил немного повеселится с индусским кодом.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <fstream>
 
using namespace std;
int main()
{
    ofstream fout;
    fout.open("out.cpp");
    fout<<"bool isFib(long long n)"<<"\n{";
    fout<<"\n\tif(n<0)\n\t\treturn false;";
    fout<<"\n\tswitch(n){";
    fout<<"\n\t\tcase 1:";
    long long a=1,b=1,tmp;
    while(true)
    {
        a=a+b;
        if(a<b)//переполнение
            break;
        fout<<"\n\t\tcase "<<a<<":";
        tmp=b;
        b=a;
        a=tmp;
    }
    fout<<"\n\t\t\t return true;";
    fout<<"\n\t}";
    fout<<"\n\treturn false;";
    fout<<"\n}";
    return 0;
}
Этот код генерирует в out.cpp длинный switch с числами Фибоначчи.
А вот использование такого кода.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <vector>
#include <exception>
using namespace std;
 
bool isFib(long long n)
{
    if(n<0)
        return false;
    switch(n){
        case 1:
        case 2:
        case 3:
        case 5:
        case 8:
        case 13:
        case 21:
        case 34:
        case 55:
        case 89:
        case 144:
        case 233:
        case 377:
        case 610:
        case 987:
        case 1597:
        case 2584:
        case 4181:
        case 6765:
        case 10946:
        case 17711:
        case 28657:
        case 46368:
        case 75025:
        case 121393:
        case 196418:
        case 317811:
        case 514229:
        case 832040:
        case 1346269:
        case 2178309:
        case 3524578:
        case 5702887:
        case 9227465:
        case 14930352:
        case 24157817:
        case 39088169:
        case 63245986:
        case 102334155:
        case 165580141:
        case 267914296:
        case 433494437:
        case 701408733:
        case 1134903170:
        case 1836311903:
        case 2971215073:
        case 4807526976:
        case 7778742049:
        case 12586269025:
        case 20365011074:
        case 32951280099:
        case 53316291173:
        case 86267571272:
        case 139583862445:
        case 225851433717:
        case 365435296162:
        case 591286729879:
        case 956722026041:
        case 1548008755920:
        case 2504730781961:
        case 4052739537881:
        case 6557470319842:
        case 10610209857723:
        case 17167680177565:
        case 27777890035288:
        case 44945570212853:
        case 72723460248141:
        case 117669030460994:
        case 190392490709135:
        case 308061521170129:
        case 498454011879264:
        case 806515533049393:
        case 1304969544928657:
        case 2111485077978050:
        case 3416454622906707:
        case 5527939700884757:
        case 8944394323791464:
        case 14472334024676221:
        case 23416728348467685:
        case 37889062373143906:
        case 61305790721611591:
        case 99194853094755497:
        case 160500643816367088:
        case 259695496911122585:
        case 420196140727489673:
        case 679891637638612258:
        case 1100087778366101931:
        case 1779979416004714189:
        case 2880067194370816120:
        case 4660046610375530309:
        case 7540113804746346429:
             return true;
    }
    return false;
}
long& func(vector<long> &vec)
{
    if(vec.size()==0)
        throw exception();//хз как обрабатывать такую ситуацию
    int m=-1;
    int i;
    for(i=0;i<vec.size();++i)
        if(isFib(vec[i]))
            m=i;
    if(m==-1)
    {
        m=0;
        for(i=1;i<vec.size();++i)
            if(vec[i]>vec[m])
                m=i;
    }
    else
        for(;i<vec.size();++i)
            if(isFib(vec[i]))
            if(vec[i]>vec[m])
                m=i;
    return vec[m];
}
int main()
{
    vector<long> v1={10,21,7,144,50,3000,203};
    vector<long> v2={0,17,-8,15,23,10000,58};
    vector<long> v3={-10,-21,-7,-144,-50,-3000,-203};
    cout<<func(v1)<<endl;
    cout<<func(v2)<<endl;
    cout<<func(v3)<<endl;
}
0
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,161
Записей в блоге: 5
08.02.2018, 14:45 3
Ovederax, проверте не сколько "быстрее" ваш switch работает за std::set<int>

Добавлено через 33 минуты
Ovederax, твои 162 строки против моих 43

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <set>
#include <vector>
 
template <typename Integer>
class Fibonachi
{
    std::set<Integer> s;
 
  public:
    Fibonachi()
    {
        for (Integer a{1}, b{1}; a + b < a + a + b;)
        {
            s.insert(b);
            std::swap(a, b);
            b += a;
        }
    }
    bool contains(const Integer value)
    {
        return s.find(value) != s.end();
    }
    Integer *max(std::vector<Integer> &v)
    {
        Integer *link = nullptr;
        for (auto &value : v)
            if (contains(value) && (link == nullptr || *link < value))
                link = &value;
        return link;
    }
};
 
int main()
{
    Fibonachi<int64_t> fib;
    std::vector<int64_t> v1{10, 21, 7, 144, 50, 3000, 203};
    std::vector<int64_t> v2{0, 17, -8, 15, 23, 10000, 58};
    std::vector<int64_t> v3{-10, -21, -7, -144, -50, -3000, -203};
    std::cout << fib.max(v1) << std::endl;
    std::cout << fib.max(v2) << std::endl;
    std::cout << fib.max(v3) << std::endl;
}
Добавлено через 21 минуту
Ovederax, ну да, поскорости реально проигрывает... раза в 3

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <set>
#include <vector>
#include <functional>
#include <ctime>
#include <random>
#include <limits>
 
template <typename Integer>
class Fibonachi
{
    std::set<Integer> s;
 
  public:
    Fibonachi()
    {
        for (Integer a{1}, b{1}; a + b < a + a + b;)
        {
            s.insert(b);
            std::swap(a, b);
            b += a;
        }
    }
    bool contains(const Integer value)
    {
        return s.find(value) != s.end();
    }
    Integer *max(std::vector<Integer> &v)
    {
        Integer *link = nullptr;
        for (auto &value : v)
            if (contains(value) && (link == nullptr || *link < value))
                link = &value;
        return link;
    }
};
 
bool isFib(int64_t);
 
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function)
{
    std::srand(1);
    const Integer MAX = std::numeric_limits<Integer>::max();
    clock_t start = clock();
    while (repeat--)
    {
        tested_function(Integer(std::rand() * MAX));
    }
    clock_t end = clock();
    return double(end - start) / CLOCKS_PER_SEC;
}
 
int main()
{
    Fibonachi<int64_t> fib;
    const size_t repeat = 1e7;
    auto search_with_set = [&fib](const int64_t &value) { return fib.contains(value); };
    auto search_with_switch = [&fib](const int64_t &value) { return isFib(value); };
    std::cout << speed_test<int64_t>(repeat, search_with_set) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_switch) << std::endl;
}
 
bool isFib(int64_t n)
{
    if(n<0)
        return false;
    switch(n){
        case 1:
        case 2:
        case 3:
        case 5:
        case 8:
        case 13:
        case 21:
        case 34:
        case 55:
        case 89:
        case 144:
        case 233:
        case 377:
        case 610:
        case 987:
        case 1597:
        case 2584:
        case 4181:
        case 6765:
        case 10946:
        case 17711:
        case 28657:
        case 46368:
        case 75025:
        case 121393:
        case 196418:
        case 317811:
        case 514229:
        case 832040:
        case 1346269:
        case 2178309:
        case 3524578:
        case 5702887:
        case 9227465:
        case 14930352:
        case 24157817:
        case 39088169:
        case 63245986:
        case 102334155:
        case 165580141:
        case 267914296:
        case 433494437:
        case 701408733:
        case 1134903170:
        case 1836311903:
        case 2971215073:
        case 4807526976:
        case 7778742049:
        case 12586269025:
        case 20365011074:
        case 32951280099:
        case 53316291173:
        case 86267571272:
        case 139583862445:
        case 225851433717:
        case 365435296162:
        case 591286729879:
        case 956722026041:
        case 1548008755920:
        case 2504730781961:
        case 4052739537881:
        case 6557470319842:
        case 10610209857723:
        case 17167680177565:
        case 27777890035288:
        case 44945570212853:
        case 72723460248141:
        case 117669030460994:
        case 190392490709135:
        case 308061521170129:
        case 498454011879264:
        case 806515533049393:
        case 1304969544928657:
        case 2111485077978050:
        case 3416454622906707:
        case 5527939700884757:
        case 8944394323791464:
        case 14472334024676221:
        case 23416728348467685:
        case 37889062373143906:
        case 61305790721611591:
        case 99194853094755497:
        case 160500643816367088:
        case 259695496911122585:
        case 420196140727489673:
        case 679891637638612258:
        case 1100087778366101931:
        case 1779979416004714189:
        case 2880067194370816120:
        case 4660046610375530309:
        case 7540113804746346429:
             return true;
    }
    return false;
}
Код
$ clang++ --std=c++11 -Wall -o run run.cpp
$ ./run 
3.34273
1.16395
0
5980 / 2106 / 737
Регистрация: 10.12.2010
Сообщений: 5,923
Записей в блоге: 3
08.02.2018, 15:03 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <iterator>
#include <algorithm>
#include <stdexcept>
#include <cmath>
 
bool IsPerfectSquare(const int n)
{
  if (n < 0) return false;
  else
  {
    int x = static_cast<int>(sqrt(n * 1.0) + 0.5);
    
    return (x * x == n);
  }
}
 
bool IsFibonacci(const int n)
{
  int pos = 5 * n * n + 4;
  int neg = 5 * n * n - 4;
  
  return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
}
 
int& MaxFibonacci(int* const array, const size_t n)
{
  if (array == nullptr) throw std::invalid_argument("array is null");
    
  int maxI = 0;
  
  bool isFibonacciNumberPresent = IsFibonacci(array[0]);
  
  for (size_t i = 1; i < n; i++)
  {
    if (IsFibonacci(array[i]))
    {
      if (!isFibonacciNumberPresent)
      {
        maxI = i;
        isFibonacciNumberPresent = true;
      }
      else if (array[maxI] < array[i]) maxI = i;
    }
    else if (!isFibonacciNumberPresent && (array[maxI] < array[i])) maxI = i;
  }
  
  return array[maxI];
}
 
int main()
{
  int a[] = {25, 15, 5, -5, -15, 144, 89, 21};
  
  size_t n = sizeof(a) / sizeof(*a);
  
  std::copy(&a[0], &a[n], std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  int& it = MaxFibonacci(a, n);
  
  it = 0;
  
  std::copy(&a[0], &a[n], std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  return 0;
}
1
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,161
Записей в блоге: 5
08.02.2018, 15:58 5
Цитата Сообщение от HighPredator Посмотреть сообщение
int x = static_cast<int>(sqrt(n * 1.0) + 0.5);
Чем static_cast лучше обычного приведения?

Добавлено через 51 секунду
Цитата Сообщение от HighPredator Посмотреть сообщение
&a[0], &a[n]
почему не

C++
1
std::begin(a), std::end(a)
?

Добавлено через 1 минуту
Цитата Сообщение от HighPredator Посмотреть сообщение
return (x * x == n);
Цитата Сообщение от HighPredator Посмотреть сообщение
return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
Это просто Ваш стиль или есть практическа причина оборачивать в скобки?
0
410 / 262 / 156
Регистрация: 30.04.2017
Сообщений: 516
08.02.2018, 16:51 6
outoftime,
Ваш код
для релиза:
0.452 и 0.312
-O2
mingw32-g++.exe -Wall -fexceptions -O2 -std=c++11 -c H:\proekts\C++\tt\main.cpp -o obj\Release\main.o
mingw32-g++.exe -o bin\Release\tt.exe obj\Release\main.o -s

-O
0.608 и 0.359
в 1.5-1.8 раза быстрее, а не в 3
хмм, оставим эти данные для холливара minGW лучше clang
0
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,161
Записей в блоге: 5
08.02.2018, 16:59 7
Цитата Сообщение от Ovederax Посмотреть сообщение
хмм, оставим эти данные для холливара minGW лучше clang
Код
$ clang++ --std=c++11 -O3 -Wall -o run run.cpp 
$ ./run 
0.354824
0.197177
clang умеет оптимизировать не хуже (:

Добавлено через 4 минуты
Я бы сравнил решение от HighPredator по скорости работы с нашими вариантами.
0
Падаван С++
443 / 257 / 88
Регистрация: 11.11.2014
Сообщений: 897
08.02.2018, 17:15 8
Цитата Сообщение от outoftime Посмотреть сообщение
Чем static_cast лучше обычного приведения
тем что это с++ все таки и обычное приведение это скорее сравненис с reinterpret_cast

Цитата Сообщение от outoftime Посмотреть сообщение
Это просто Ваш стиль или есть практическа причина оборачивать в скобки?
тут как по мне лучше читается, практического смысла нет
1
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,161
Записей в блоге: 5
08.02.2018, 17:47 9
Ovederax, собрал всё воедино

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <iostream>
#include <set>
#include <vector>
#include <functional>
#include <ctime>
#include <random>
#include <limits>
 
template <typename Integer>
class Fibonacci
{
    std::set<Integer> s;
 
  public:
    Fibonacci();
    bool contains(const Integer value) { return s.find(value) != s.end(); }
    Integer *max(std::vector<Integer> &v);
};
 
bool isFib(int64_t);
 
bool IsPerfectSquare(const int64_t n);
bool IsFibonacci(const int64_t n);
 
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function);
 
int main()
{
    Fibonacci<int64_t> fib;
    const size_t repeat = 1e7;
    auto search_with_set = [&fib](const int64_t &value) { return fib.contains(value); };
    auto search_with_switch = [&fib](const int64_t &value) { return isFib(value); };
    auto search_with_expression = [&fib](const int64_t &value) { return IsFibonacci(value); };
    std::cout << speed_test<int64_t>(repeat, search_with_set) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_switch) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_expression) << std::endl;
}
 
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function)
{
    std::srand(1);
    const Integer MAX = std::numeric_limits<Integer>::max();
    clock_t start = clock();
    while (repeat--)
        tested_function(Integer(std::rand() * MAX));
    clock_t end = clock();
    return double(end - start) / CLOCKS_PER_SEC;
}
 
template <typename Integer>
Fibonacci<Integer>::Fibonacci()
{
    for (Integer a{1}, b{1}; a + b < a + a + b;)
    {
        s.insert(b);
        std::swap(a, b);
        b += a;
    }
}
 
template <typename Integer>
Integer *Fibonacci<Integer>::max(std::vector<Integer> &v)
{
    Integer *link = nullptr;
    for (auto &value : v)
        if (contains(value) && (link == nullptr || *link < value))
            link = &value;
    return link;
}
 
bool IsPerfectSquare(const int64_t n)
{
    if (n < 0)
        return false;
 
    const int64_t x = static_cast<int64_t>(sqrt(n * 1.0) + 0.5);
    return (x * x == n);
}
 
bool IsFibonacci(const int64_t n)
{
    const int64_t pos = 5 * n * n + 4;
    const int64_t neg = 5 * n * n - 4;
 
    return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
}
 
bool isFib(int64_t n)
{
    if (n < 0)
        return false;
    switch (n)
    {
    case 1:
    case 2:
    case 3:
    case 5:
    case 8:
    case 13:
    case 21:
    case 34:
    case 55:
    case 89:
    case 144:
    case 233:
    case 377:
    case 610:
    case 987:
    case 1597:
    case 2584:
    case 4181:
    case 6765:
    case 10946:
    case 17711:
    case 28657:
    case 46368:
    case 75025:
    case 121393:
    case 196418:
    case 317811:
    case 514229:
    case 832040:
    case 1346269:
    case 2178309:
    case 3524578:
    case 5702887:
    case 9227465:
    case 14930352:
    case 24157817:
    case 39088169:
    case 63245986:
    case 102334155:
    case 165580141:
    case 267914296:
    case 433494437:
    case 701408733:
    case 1134903170:
    case 1836311903:
    case 2971215073:
    case 4807526976:
    case 7778742049:
    case 12586269025:
    case 20365011074:
    case 32951280099:
    case 53316291173:
    case 86267571272:
    case 139583862445:
    case 225851433717:
    case 365435296162:
    case 591286729879:
    case 956722026041:
    case 1548008755920:
    case 2504730781961:
    case 4052739537881:
    case 6557470319842:
    case 10610209857723:
    case 17167680177565:
    case 27777890035288:
    case 44945570212853:
    case 72723460248141:
    case 117669030460994:
    case 190392490709135:
    case 308061521170129:
    case 498454011879264:
    case 806515533049393:
    case 1304969544928657:
    case 2111485077978050:
    case 3416454622906707:
    case 5527939700884757:
    case 8944394323791464:
    case 14472334024676221:
    case 23416728348467685:
    case 37889062373143906:
    case 61305790721611591:
    case 99194853094755497:
    case 160500643816367088:
    case 259695496911122585:
    case 420196140727489673:
    case 679891637638612258:
    case 1100087778366101931:
    case 1779979416004714189:
    case 2880067194370816120:
    case 4660046610375530309:
    case 7540113804746346429:
        return true;
    }
    return false;
}
Код
$ clang++ -Wall -fexceptions -O3 -std=c++11 -o run run.cpp 
$ ./run 
0.352641
0.190936
0.359706


Мое решение оказалось по производительности такое же как и у HighPredator. Но получение корня, возможно, можно еще ускорить и формула дает чистое константное время, в отличии от switch который будет сравнивать весь список при больших значениях.

Кстати, а вот и еще одна идея для теста: проверка на большие и малые числа

Добавлено через 13 минут
Ovederax, доделал
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <iostream>
#include <set>
#include <vector>
#include <functional>
#include <ctime>
#include <random>
#include <limits>
 
template <typename Integer>
class Fibonacci
{
    std::set<Integer> s;
 
  public:
    Fibonacci();
    bool contains(const Integer value) { return s.find(value) != s.end(); }
    Integer *max(std::vector<Integer> &v);
};
 
bool isFib(int64_t);
 
bool IsPerfectSquare(const int64_t n);
bool IsFibonacci(const int64_t n);
 
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function, Integer *value = nullptr);
 
int main()
{
    Fibonacci<int64_t> fib;
    const size_t repeat = 1e7;
    auto search_with_set = [&fib](const int64_t &value) { return fib.contains(value); };
    auto search_with_switch = [&fib](const int64_t &value) { return isFib(value); };
    auto search_with_expression = [&fib](const int64_t &value) { return IsFibonacci(value); };
    std::cout << speed_test<int64_t>(repeat, search_with_set) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_switch) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_expression) << std::endl;
    int64_t value = 1;
    std::cout << "Fixed value: " << value << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_set, &value) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_switch, &value) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_expression, &value) << std::endl;
    value = 7540113804746346429;
    std::cout << "Fixed value: " << value << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_set, &value) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_switch, &value) << std::endl;
    std::cout << speed_test<int64_t>(repeat, search_with_expression, &value) << std::endl;
}
 
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function, Integer *value)
{
    std::srand(1);
    const Integer MAX = std::numeric_limits<Integer>::max();
    clock_t start = clock();
    if (value == nullptr)
        while (repeat--)
            tested_function(Integer(std::rand() * MAX));
    else
        while (repeat--)
            tested_function(*value);
    clock_t end = clock();
    return double(end - start) / CLOCKS_PER_SEC;
}
 
template <typename Integer>
Fibonacci<Integer>::Fibonacci()
{
    for (Integer a{1}, b{1}; a + b < a + a + b;)
    {
        s.insert(b);
        std::swap(a, b);
        b += a;
    }
}
 
template <typename Integer>
Integer *Fibonacci<Integer>::max(std::vector<Integer> &v)
{
    Integer *link = nullptr;
    for (auto &value : v)
        if (contains(value) && (link == nullptr || *link < value))
            link = &value;
    return link;
}
 
bool IsPerfectSquare(const int64_t n)
{
    if (n < 0)
        return false;
 
    const int64_t x = static_cast<int64_t>(sqrt(n * 1.0) + 0.5);
    return (x * x == n);
}
 
bool IsFibonacci(const int64_t n)
{
    const int64_t pos = 5 * n * n + 4;
    const int64_t neg = 5 * n * n - 4;
 
    return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
}
 
bool isFib(int64_t n)
{
    if (n < 0)
        return false;
    switch (n)
    {
    case 1:
    case 2:
    case 3:
    case 5:
    case 8:
    case 13:
    case 21:
    case 34:
    case 55:
    case 89:
    case 144:
    case 233:
    case 377:
    case 610:
    case 987:
    case 1597:
    case 2584:
    case 4181:
    case 6765:
    case 10946:
    case 17711:
    case 28657:
    case 46368:
    case 75025:
    case 121393:
    case 196418:
    case 317811:
    case 514229:
    case 832040:
    case 1346269:
    case 2178309:
    case 3524578:
    case 5702887:
    case 9227465:
    case 14930352:
    case 24157817:
    case 39088169:
    case 63245986:
    case 102334155:
    case 165580141:
    case 267914296:
    case 433494437:
    case 701408733:
    case 1134903170:
    case 1836311903:
    case 2971215073:
    case 4807526976:
    case 7778742049:
    case 12586269025:
    case 20365011074:
    case 32951280099:
    case 53316291173:
    case 86267571272:
    case 139583862445:
    case 225851433717:
    case 365435296162:
    case 591286729879:
    case 956722026041:
    case 1548008755920:
    case 2504730781961:
    case 4052739537881:
    case 6557470319842:
    case 10610209857723:
    case 17167680177565:
    case 27777890035288:
    case 44945570212853:
    case 72723460248141:
    case 117669030460994:
    case 190392490709135:
    case 308061521170129:
    case 498454011879264:
    case 806515533049393:
    case 1304969544928657:
    case 2111485077978050:
    case 3416454622906707:
    case 5527939700884757:
    case 8944394323791464:
    case 14472334024676221:
    case 23416728348467685:
    case 37889062373143906:
    case 61305790721611591:
    case 99194853094755497:
    case 160500643816367088:
    case 259695496911122585:
    case 420196140727489673:
    case 679891637638612258:
    case 1100087778366101931:
    case 1779979416004714189:
    case 2880067194370816120:
    case 4660046610375530309:
    case 7540113804746346429:
        return true;
    }
    return false;
}
Код
$ clang++ -Wall -fexceptions -O3 -std=c++11 -o run run.cpp 
$ ./run 
0.362689
0.227071
0.361598
Fixed value: 1
0.155653
0.123166
0.129878
Fixed value: 7540113804746346429
0.316709
0.140357
0.042689


У switch, по результатам, практически нет деградации. Также стабильно себя чувствует решение с std::set. А вот формула удивила. Почти в 3 раза быстрее считается если число является числом фибоначи и оно попадает в https://www.cyberforum.ru/cgi-bin/latex.cgi?5n^2+4. Иначе, я не пойму с чего, вдруг, такой скачек производительности.

Добавлено через 2 минуты
rossohin647, бери формулу в качестве решения, она самая крутая.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.02.2018, 17:47

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Разработать функцию, определяющую максимальное число, встречающееся в массиве больше одного раза
Дан одномерный массив.Разработать функцию, определяющую максимальное число, встречающееся в массиве...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.