如何爲斐波那契序列編寫一個C程序，而無需向量/遞歸？

我試圖實現的順序與Fibonacci類似，但是代替第N個號碼是N-1 + N-2，我們有K值，第N個號碼是N-1 + N-2 + ... + N-K。如何爲斐波那契序列編寫一個C程序，而無需向量/遞歸？

我想編寫一個C程序來編寫序列，直到第N個編號爲K和N作爲輸入。它不能使用向量或遞歸。

更新：

沒有可行的解決方案，這是一個運動來證明一個向量（數組）成一些問題的解決方案的必要性。

來源

2016-09-22 emiliopedrollo

什麼載體？ C中沒有矢量...使用循環。 –

@EugeneSh .:在上下文中，它很清楚（至少對我來說）「vector」被用作數組的另一個名稱。我的大多數老教授都擁有數學學位，並且在Fortran和C中爲1D數組使用了「矢量」一詞。基本上，問題陳述禁止將數組用作中間存儲。 –

這是否排除任何數組或僅存儲數組以存儲完整序列？也就是說，最後一個「K」值是否可以使用？ – LutzL

沒有真正的答案，因爲它是一個動態的問題。

來源

2016-09-27 18:19:18 emiliopedrollo

對於（至少）以前的K值，您需要某種類型的存儲空間，並且我認爲您的問題的癥結在於您可以使用哪種方式。

您不能使用調用堆棧/函數參數，因爲您不能遞歸。你不能使用「矢量」，我認爲你的意思是一個數組。使用單個局部變量會非常混亂，並且根本不可行，除非在數值上可能存在非常低的限制。我看到的唯一選擇是

鏈接列表的一些味道。（但要小心 - 鏈接列表可能被認爲是一個非常寬泛的術語「矢量」）。
一個外部文件。（Yuck！）

這個練習很可能與你在課堂上學習的東西有關，所以應該給你一些關於教師的想法的線索。

我離開實際的實施，因爲它是練習。

來源

2016-09-22 22:16:09

它不能是外部文件，因爲我們還沒有學習它。在第一個選項中，我不需要爲每個K值手動編寫一個列表？這不會工作，因爲K可以是任何整數。 – emiliopedrollo

@emiliopedrollo，不，你不必爲每個'K'值寫一個單獨的列表。具有靈活的長度是鏈接列表的主要特徵之一。如果你採用這種方法，你只需要一個列表實現 - 你只需要以適當的方式將它應用到你的問題。 –

所以，鏈表是一種使用指針的方法嗎？那麼，我們在課堂上還沒有看到，所以我認爲這不是預期的解決方案。現在我開始認爲沒有辦法做到這一點。 – emiliopedrollo

免責聲明 - 這是不，我再說一遍不你的教授正在尋找，但...

如果你知道如何解決recurrence relations，你可以找到的的封閉形式關係爲K的每個值，並簡單計算（無循環，不存儲中間值）。例如，^Ñ第斐波納契可以使用功能

long double fib_closed(unsigned int n) 
{ 
    long double sqrt_5 = sqrtl(5.0); 
    long double phi = (1 + sqrt_5)/2.0; 
    long double psi = (1 - sqrt_5)/2.0; 

    return floorl((powl(phi, n) - powl(psi, n))/sqrt_5); 
}

在你的情況來計算數，你就必須爲每個K不同的遞歸關係（即，用於N-遞推關係1 + N-2 + N-3將不同於N-1 + N-2 + N-3 + N-4等的遞歸關係），所以你需要編寫與K你想使用：

switch(K) 
{ 
    case 3: return f_closed_3(n); break; 
    case 4: return f_closed_4(n); break; 
    ... 
}

它，思考它，不會是TE非常實用。再次，這是而不是你的教授正在尋找什麼，但它可能會在未來一段時間內進行一個有趣的練習。

來源

2016-09-22 23:16:30

這樣我就必須爲每個K值找到/寫出一個關係，範圍從1到正無窮大。所以不可行。 – emiliopedrollo

如何爲斐波那契序列編寫一個C程序，而無需向量/遞歸？

回答

相關問題