You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
68 lines
1.6 KiB
68 lines
1.6 KiB
/*
|
|
* Copyright 2002-2019 Intel Corporation.
|
|
*
|
|
* This software is provided to you as Sample Source Code as defined in the accompanying
|
|
* End User License Agreement for the Intel(R) Software Development Products ("Agreement")
|
|
* section 1.L.
|
|
*
|
|
* This software and the related documents are provided as is, with no express or implied
|
|
* warranties, other than those that are expressly stated in the License.
|
|
*/
|
|
|
|
#include <iostream>
|
|
#include <sstream>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
|
|
static unsigned long Fibonacci(unsigned long);
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
if (argc > 2)
|
|
{
|
|
std::cerr << "Usage: fibonacci [num]" << std::endl;
|
|
return 1;
|
|
}
|
|
|
|
unsigned long num = 1000;
|
|
if (argc == 2)
|
|
{
|
|
std::istringstream is;
|
|
is.str(argv[1]);
|
|
is >> num;
|
|
if (!is)
|
|
{
|
|
std::cerr << "Illegal number '" << argv[1] << "'" << std::endl;
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
unsigned long fib = Fibonacci(num);
|
|
std::cout << "Entry number " << num << " in the Fibonacci sequence is " << fib << std::endl;
|
|
return 0;
|
|
}
|
|
|
|
|
|
static unsigned long Fibonacci(unsigned long num)
|
|
{
|
|
static unsigned long *Cache = 0;
|
|
static unsigned long CacheLen = 0;
|
|
|
|
if (num < CacheLen && Cache[num])
|
|
return Cache[num];
|
|
|
|
unsigned result = 1;
|
|
if (num > 1)
|
|
result = Fibonacci(num-1) + Fibonacci(num-2);
|
|
|
|
if (num >= CacheLen)
|
|
{
|
|
size_t sz = 2*num;
|
|
Cache = static_cast<unsigned long *>(realloc(Cache, sz*sizeof(*Cache)));
|
|
memset(&Cache[CacheLen], 0, (sz - CacheLen)*sizeof(*Cache));
|
|
CacheLen = sz;
|
|
}
|
|
Cache[num] = result;
|
|
return result;
|
|
}
|