我怎樣才能創建一個數組達到某個整數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的斐波那契數組？

回答

相關問題