Есть задача, не могу сформировать ход решения, подскажите пожалуйста куда двигаться
Задание 1 Дан массив [3279, 920, 4181, 8, 337, 13, 918, 4923, 4448, 8, 4756, 4012, 7467, 89, 21, 2400, 4409, 6005, 3172, 55, 5, 6367, 8, 9970, 144, 1, 4360, 407, 7010, 9160, 7149, 9038, 9196, 8625, 662, 1597, 21, 2592, 1597, 5424, 2584, 2937, 1597, 9835, 7960, 2254, 3531, 8034, 9393, 807, 3225, 6765, 399, 3230, 34, 153, 2, 3980, 2093, 9238, 2326, 6453, 89, 4606, 3413, 3, 9950, 2098, 8579, 4914, 7204, 8875]. Среди его ячеек некоторые числа являются числами Фибоначчи (числами, учавствующимив последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21). Найдите сумму чисел Фибоначчи в этом массиве.
Ответы (1 шт):
Для первых 10000 (так как чисел больше 10000 в массиве нет) предпосчитай, являются ли они числами фибоначчи. Для этого можно создать массив а размера 10000, все элементы которого изначально false. Теперь считаешь все элементы фибоначчи, меньшие 10000, и меняешь a[i] на true для каждого нового числа. Теперь идешь по всем элементам данного тебе массива и если a от текущего элемента массива - true, добавляем текущий элемент к ответу.