我怎样才能创建一个数组达到某个整数n的斐波那契数组？

因此，对于一个赋值，我被要求创建一个函数来生成一个斐波那契数组，然后用户将提供一个随机数组。然后，我的函数必须检查用户输入的数组是否包含任何斐波那契数，然后该函数将输出true，否则它将输出false。我已经能够创建Fib的数字数组，并检查它针对阵列但用户输入的是有限的，因为我的Fib阵列具有100我怎样才能创建一个数组达到某个整数n的斐波那契数组？

bool hasFibNum (int arr[], int size){ 

int fibarray[100]; 
fibarray[0] = 0; 
fibarray[1] = 1; 
bool result = false; 
for (int i = 2; i < 100; i++) 
{ 
    fibarray[i] = fibarray[i-1] + fibarray[i-2]; 

} 

for (int i = 0; i < size; i++) 
{ 
    for(int j = 0; j < 100; j++){ 
     if (fibarray[j] == arr[i]) 
      result = true; 
    } 
} 

return result; 
}

一个最大尺寸所以基本上我怎样才能使这样我就不必使用int fibarray [100]，而是可以生成一些特定点的fib数。这一点是用户数组中的最大数量。

因此，例如，如果用户输入数组{4,2,1,8,21}，我需要生成一个最大数目为21的纤维芯片{1,1,2,3,5,8,13 ，21}。如果用户输入数组{1,4,10}，我需要生成一个{1,1,2,3,5,8,13}的纤维阵列

很新的编程，所以任何帮助将不胜感激！对不起，如果我的代码是可怕的。

来源

2014-09-23 user3684741

循环遍历用户的数组以查找最大数字，然后创建最大为该数字的fib数字。你需要这种解决方案吗？我无法理解您的问题 – Michael 2014-09-23 18:32:58

是的，如果我的措辞使得理解有点复杂，我很抱歉。但这正是我需要做的。 – user3684741 2014-09-23 18:37:25

如果用户输入'{1,4,10}'，你是不是指你必须生成一个最大为10的fib数组，因为'10'是最大的？当我认为它会上升到'8'时，你的阵列上升到'13'。 – 0x499602D2 2014-09-23 18:54:06

这可能是我还是不明白你的问题，但如果我这样做，那么我会实现你想要的是这样的：

bool hasFibNum (int arr[], int size){ 
    if (size == 0) return false; 
    int maxValue = arr[0]; 
    for (int i = 1; i < size; i++) 
    { 
     if (arr[i] > maxValue) maxValue = arr[i]; 
    } 
    int first = 0; 
    int second = 1; 
    while (second < maxValue) 
    { 
     for (int i = 0; i < size; i++) 
     { 
      if (arr[i] == first) return true; 
      if (arr[i] == second) return true; 
     } 
     first = first + second; 
     second = second + first; 
    } 

    return false; 
}

来源

2014-09-23 18:35:06

我们只允许使用。可能有很多其他方法可以更高效地完成此操作，但我们尚未引入矢量库。 – user3684741 2014-09-23 18:36:46

请参阅最新的答案。 – 2014-09-23 18:52:46

是的！太棒了！非常感谢你的帮助，非常感谢。希望我能以某种方式回报你的青睐。 – user3684741 2014-09-23 19:04:59

这里是返回一个动态数组的所有功能斐波那契数高达并包括max（假设max > 0）

std::vector<size_t> make_fibs(size_t max) { 
    std::vector<size_t> retval = {1,1}; 
    while(retval.back() < max) { 
    retval.push_back(retval.back()+*(retval.end()-2)); 
    } 
    return retval; 
}

我与2个元素而不是保持最后2的轨道分别预填充它。

请注意，根据一些定义，0和-1是斐波纳契数。如果你正在使用它，请使用{-1, 0, 1}（这不是它们的顺序，它实际上是-1, 1, 0, 1，但通过将它们保留在升序中，我们可以在下面binary_search）开始数组。如果这样做，请将类型更改为int而不是size_t。

下，实现对has_fibs草图：

template<class T, size_t N> 
bool has_fibs(T(&array)[N]) { 
    // bring `begin` and `end` into view, one of the good uses of `using`: 
    using std::begin; using std::end; 
    // guaranteed array is nonempty, so 
    T m = *std::max_element(begin(array), end(array)); will have a max, so * is safe. 
    if (m < 0) m = 0; // deal with the possibility the `array` is all negative 

    // use `auto` to not repeat a type, and `const` because we aren't going to alter it: 
    const auto fibs = make_fibs(m); 

    // d-d-d-ouble `std` algorithm: 
    return std::find_if(begin(array), end(array), [&fibs](T v)->bool { 
    return std::binary_search(begin(fibs), end(fibs), v); 
    }) != end(array); 
}

这里我创建一个模板函数，它的（固定大小）阵列作为参考。这具有基于范围的循环可以工作的优点。

接下来，我使用std算法max_element来查找最大元素。

最后，我用两个std算法，find_if和binary_search，加上lambda来粘合在一起，找到了两个容器之间的交叉点。

我在这里宽松地使用C++ 11功能和大量的抽象。如果你不明白一个功能，我鼓励你重写你不明白的部分，而不是盲目地复制。

此代码的运行时间O(n lg lg n)这可能是矫枉过正。（纤维以指数形式增长，建造它们需要lg n时间，搜索它们需要lg lg n时间，然后我们搜索然后n次）。

来源

2014-09-23 19:07:22 Yakk

我怎样才能创建一个数组达到某个整数n的斐波那契数组？

回答

相关问题