爬樓梯演算法
A. 爬樓梯約做多少功
這個...你體重多少？算你60kg吧...7樓..每層樓多高？...算他3米吧...（取10N/kg）那麼演算法如下
W=FS=Gh=60kg*10N/kg*(7-1)*3m
=600N*18m
=10800J
B. C語言 爬樓梯的問題
用遞歸解決比較方便：
#include<stdio.h>
int fibonacci (int n)
{
if (n > 2)
return fibonacci(n - 1) + fibonacci(n - 2);
else
return 1;
}
int main()
{
int data[20];
int t;
int i;
printf ("Please input T and the nums: \n");
scanf ("%d", &t);
for (i=0; i<t; i++)
{
scanf("%d", &data[i]);
}
printf("The output: \n");
for (i=0; i<t; i++)
{
printf("%d\n", fibonacci (data[i]+1));
}
return 0;
}
/* 這是斐波那契演算法的一個應用，你可以搜索一下 */
C. 幼兒園爬樓梯演算法什麼意思
爸爸媽媽要注意觀察，當寶寶練至身體微微出汗時就應該停止，以防止運動過度，讓寶寶厭倦並以後討厭走樓梯這個活動，同時也可以防止過度的訓練影響寶寶身體骨骼的發育。
D. leetcode演算法
*最近在做一些 leetcode 的演算法題，我會將自己做過的演算法題記錄下來以供大家參考，如果查找不方便請看 油猴插件實現網站左側目錄生成。
給定一個排序數組，你需要在 原地 刪除重復出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在 原地修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
示例：
解答：
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例：
提示：
解答：
給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。
示例：
說明:
解答：
給定一個整數數組，判斷是否存在重復元素。
如果任意一值在數組中出現至少兩次，函數返回 true 。如果數組中每個元素都不相同，則返回 false 。
示例：
解答：
給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。
說明：
你的演算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？
示例：
解答：
給定兩個數組，編寫一個函數來計算它們的交集。
示例：
說明：
進階:
解答：
給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。
最高位數字存放在數組的首位， 數組中每個元素只存儲單個數字。
你可以假設除了整數 0 之外，這個整數不會以零開頭。
示例：
解答：
給定一個數組 nums ，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:
說明:
給定一個整數數組 nums 和一個目標值 target ，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
示例：
解答：
判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。
數獨部分空格內已填入了數字，空白格用 '.' 表示。
示例：
說明:
解答：
給定一個 *n *× *n* 的二維矩陣表示一個圖像。
將圖像順時針旋轉 90 度。
說明：
你必須在 原地 旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。 請不要 使用另一個矩陣來旋轉圖像。
示例：
解答：
編寫一個函數，其作用是將輸入的字元串反轉過來。輸入字元串以字元數組 char[] 的形式給出。
不要給另外的數組分配額外的空間，你必須 原地修改輸入數組 、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字元都是 ASCII 碼表中的可列印字元。
示例：
解答：
給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉。
示例：
注意:
假設我們的環境只能存儲得下 32 位的有符號整數，則其數值范圍為 [−231, 231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就返回 0。
解答：
給定一個字元串，找到它的第一個不重復的字元，並返回它的索引。如果不存在，則返回 -1。
示例：
解答：
給定兩個字元串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
長度一樣，包含的字母都一樣，每個字元出現的頻率也一樣，只是順序不同而已，這就屬於異位詞，
示例：
說明:
你可以假設字元串只包含小寫字母。
進階:
如果輸入字元串包含 unicode 字元怎麼辦？你能否調整你的解法來應對這種情況？
解答：
給定一個字元串，驗證它是否是迴文串，只考慮字母和數字字元，可以忽略字母的大小寫。
說明 ：本題中，我們將空字元串定義為有效的迴文串。
示例：
解答：
請你來實現一個 atoi 函數，使其能將字元串轉換成整數。
首先，該函數會根據需要丟棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。接下來的轉化規則如下：
注意 ：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換，即無法進行有效轉換。
在任何情況下，若函數不能進行有效的轉換時，請返回 0 。
提示 ：
示例：
解答：
實現 strStr() 函數。
給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始) 。如果不存在，則返回 -1 。
示例：
說明:
當 needle 是空字元串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。
對於本題而言，當 needle 是空字元串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符
解答：
「外觀數列」是一個整數序列，從數字 1 開始，序列中的每一項都是對前一項的描述。前五項如下：
1 被讀作 "one 1" ("一個一") , 即 11 。
11 被讀作 "two 1s" ("兩個一") , 即 21 。
21 被讀作 "one 2", "one 1" ("一個二" , "一個一") , 即 1211 。
給定一個正整數 n（1 ≤ n ≤ 30），輸出外觀數列的第 n 項。
注意 ：整數序列中的每一項將表示為一個字元串。
示例：
解答：
編寫一個函數來查找字元串數組中的最長公共前綴。
如果不存在公共前綴，返回空字元串 "" 。
示例：
說明:
所有輸入只包含小寫字母 a-z 。
解答：
請編寫一個函數，使其可以刪除某個鏈表中給定的（非末尾）節點，你將只被給定要求被刪除的節點。
現有一個鏈表 -- head = [4,5,1,9]，它可以表示為:
示例：
說明：
解答：
給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。
示例：
說明：
給定的 n 保證是有效的。
進階：
你能嘗試使用一趟掃描實現嗎？
解答：
反轉一個單鏈表。
示例：
解答：
將兩個升序鏈表合並為一個新的升序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例：
解答：
請判斷一個鏈表是否為迴文鏈表。
示例：
解答：
給定一個鏈表，判斷鏈表中是否有環。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1 ，則在該鏈表中沒有環。
示例：
解答：
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明 : 葉子節點是指沒有子節點的節點。
示例：
給定二叉樹 [3,9,20,null,null,15,7] ，
返回它的最大深度 3 。
解答：
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特徵：
示例：
解答：
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
解答：
給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。 （即逐層地，從左到右訪問所有節點）。
示例：
二叉樹： [3,9,20,null,null,15,7] ,
返回其層次遍歷結果：
解答：
將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。
本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。
示例：
給定有序數組: [-10,-3,0,5,9] ,
一個可能的答案是: [0,-3,9,-10,null,5] ，它可以表示下面這個高度平衡二叉搜索樹：
解答：
給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合並到 nums1 中，使 nums1 成為一個有序數組。
說明:
示例:
解答：
你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由於每個版本都是基於之前的版本開發的，所以錯誤的版本之後的所有版本都是錯的。
假設你有 n 個版本 [1, 2, ..., n] ，你想找出導致之後所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。
示例：
解答：
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意 ：給定 n 是一個正整數。
示例：
解答：
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤。
注意 ：你不能在買入股票前賣出股票。
示例：
解答：
給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
示例:
解答：
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例：
解答：
打亂一個沒有重復元素的數組。
示例：
解答：
設計一個支持 push ， pop ， top 操作，並能在常數時間內檢索到最小元素的棧。
示例：
解答：
寫一個程序，輸出從 1 到 n 數字的字元串表示。
示例：
解答：
統計所有小於非負整數 n 的質數的數量。
示例：
解答：
給定一個整數，寫一個函數來判斷它是否是 3 的冪次方。
示例：
解答：
羅馬數字包含以下七種字元: I ， V ， X ， L ， C ， D 和 M 。
例如，羅馬數字 2 寫做 II ，即為兩個並列的 1 。 12 寫做 XII ，即為 X + II 。 27 寫做 XXVII , 即為 XX + V + II 。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII ，而是 IV 。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX 。這個特殊的規則只適用於以下六種情況：
示例：
解答：
編寫一個函數，輸入是一個無符號整數，返回其二進製表達式中數字位數為 『1』 的個數（也被稱為 漢明重量 ）。
示例：
提示：
E. 20個階梯，你一次可以上一階或兩階，走上去，共有多少種走法 把詳細的解答過程寫出來
這個題最簡單的做法就是分析法。共有10946種。
假設階梯有N層，則按N=1，2，3，4……逐步分析，推出一般規律，即走法a(n)=a(n-2)+a(n-1)可以看出這是一個遞推公式。同時也滿足菲波拉契數列的情況所以20級階梯的走法a(20)就為菲波拉契數列的第20項a(20)=fib(20)=10946。
另外一種就比較復雜，根據走2步的不同情況分析，最少一個2步都不走，最多為10個：
(1)一個2步都不走，為1種情況。
(2)走1個2步，總共步數為19，從19個中隨便選1個為2步的 C（19，1）
(3)走2個2步，總共步數18，從18個中隨便選2個為2步的。C（18，2）
依次類推為C（17，3）；C（16，4）；C（15，5）……C（10，10）
總走法=1+C（19，1）+C（18，2）+C（17，3）+……+C（10，10）
=1+19+153+ 680+1820+……+1=10946
(5)爬樓梯演算法擴展閱讀：
關於分析法：
1.從求解的問題出發，正確地選擇出兩個所需要的條件，依次推導，一直到問題得到解決的解題方法叫做分析法。
2.用分析法解題時如果解題所需要的兩個條件，（或其中一個條件）是未知的時候，就要分別求解找出這兩個（或一個）的條件，一直到問題都是已知的時候為止。
3.分析法指從要證的結論出發，逐步尋求使它成立的充分條件，直到歸結為判定一個顯然成立的條件（已知量、定義、公理、定理、性質、法則等）為止，從而證明論點的正確性、合理性的論證方法。也稱為因果分析、逆推證法或執果索因法。
F. 一自然數的各位數字之和是1784.該自然數是什麼
2021-06-18 修改回答
找到了高效率的演算法，直接計算出符合條件的自然數至少有多少個。
採用爬樓梯演算法。把問題轉換一下，一次可以爬1到9個台階，爬上1784級台階，一共有多少種方案？
遞歸公式，第n級的方案數量是f(n)，則：
f(n)=f(n-9)+n(n-8)+n(n-7)+n(n-6)+n(n-5)+n(n-4)+n(n-3)+n(n-2)+n(n-1)
類似的討論很多，證明就不列出了。這是斐波那契數列的一個擴展形式。
計算結果，不包含零的話，可以找到 9.46639556*10^535 個這樣的自然數。
如果包含零，那就有無窮多個。
附：計算結果和fortran代碼，結果是一個536位的大整數
2021-06-16 的回答
如果這個自然數的數字中可以包含0，那麼就有無窮多個解。
如果這個自然數的數字中不包含0，那麼：
它最少也要199位，也就是198個9和1個2的情形；最多可以是1784位的大整數，也就是都是1的情形。
沒有現成的演算法可以求解符合條件的大正整數的個數。可以估算一下達到何種規模。
123456789，九個數字的和是45。1784/45=39餘29。
因此，可以用1到9重復使用45次，剩下的29分拆為3個9，1個2。
這樣是：42個9，40個2，其它數字都是39個，一共是42+40+39*7=355位。
這個組合的全排列數量是：
355!/(39!)^7/42!/40! =4.*10^329
方案的數量達到了 10的330次方。極其巨大！
這還只是其中的一個組合的全排列情形。可以肯定，這個問題的解遠不止這個規模。
供參考。
G. 演算法設計 爬樓梯類型,共n階樓梯,一次最多爬m階，用JAVA或者C或者C++
循環，，，，，好多循環，，，，哇，，，，實現了
#include<string.h>
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int n = 0, m = 0, sum = 0, cnt = 0;
cout << "輸入階梯數：" << endl;
cin >> n;
cout << "輸入最多爬的階梯數：" << endl;
cin >> m;
if (n <= 0)
{
cout << "就一種，上去了!" << endl;
}
if (m <= 0)
{
cout << "你想上是不可能的！" << endl;
}
int i;
stack<int> sk;
do
{
if (sum <= n)
{
++cnt;
while (sum <= n)
{
sk.push(1);
++sum;
}
}
if (!sk.empty())
{
sum -= sk.top();
sk.pop();
}
else
{
cout << cnt << endl;
return 0;
}
HHH:
if (!sk.empty())
{
i = sk.top();
}
else
{
cout << cnt << endl;
return 0;
}
if (i < m)
{
++i;
}
else
{
if (!sk.empty())
{
sum -= sk.top();
sk.pop();
goto HHH;
}
else
{
cout << cnt << endl;
return 0;
}
}
if (!sk.empty())
{
sum -= sk.top();
sk.pop();
}
else
{
cout << cnt << endl;
return 0;
}
sk.push(i);
sum += i;
} while (1);
return 0;
}
H. 猴子爬樓梯十個台階不跳下可以爬一層,兩層,三層有幾種方法
相加組合等於10有下面14種基本可能
10個1，只有1種排列方式
5個2，只有1種排列方式
8個1,1個2，8個1排列，8個1之間7個位置，前後有2個位置，合計9個位置，9個位置選一個插入2，所以有9種排列方式
6個1,2個2，6個1之間和前後有7個位置。2個2如果是隔開的，7個位置選2個插入2，共有C(2,7)=21種可能；2個2如果在一起，則有7種可能，故共有21+7=28種排列方式
4個1,3個2，4個1之間和前後有5個位置，3個2如果是隔開的，4個位置選3個插入2，共有C(3,5)=10種可能；2個2在一起，另一個2單獨，那麼有A(2,5)=20種可能；3個2在一起，共有5種可能，故共有10+20+5=35種排列方式
2個1,4個2，4個2之間和前後有5個位置，2個1如果是隔開的，共有C(2,5)=10種可能；2個1在一起，那麼有5種可能，故共有10+5=15種排列方式
7個1,1個3，7個1之間和前後有8個位置，1個3選一個，共有8種排列方式
4個1,2個3，4個1之間和前後有5個位置，2個3如果隔開的，共有C(2,5)=10種可能；2個3在一起，那麼有5種可能，故共有10+5=15種排列方式
1個1,3個3，3個3之間和前後有4個位置，1個1選一個插入，共有4種排列方式
2個2,2個3，2個3之間和前後有3個位置，2個2如果隔開的，共有C(2,3)=3種可能，2個2如果在一起，那麼有3種可能，故共有3+3=6種排列方式
1個1,3個2,1個3，3個2之間和前後有4個位置，1個1先放入，有4種可能，放入1後，3個2和1個1之間有5個位置，選一個放入3，有5種可能，故共有4X5=20種排列方式
3個1,2個2,1個3，3個1之間和前後有4個位置，2個2先放入，如果2個2在一起，有4種可能；2個2分開，有C(2,4)=6種可能。3個1和2個2之間有6個位置，選1個放入3，有6種可能，故共有(4+6)X6=60種排列方式
5個1,1個2,1個3，5個1之間和前後有6個位置，1個2先放入，有6種可能；5個1和1個2之間和前後共7個位置，選1個放入3，有7種可能，故共有6X7=42種排列方式
2個1,1個2,2個3，2個1之間和前後有3個位置，2個3放入，如果2個3分開，有C(2,3)=3種可能；如果2個3在一起，有3種可能；2個1和2個3之間，有5個位置，選1個放入2，有5種可能，故共有(3+3)X5=30種排列方式
綜上所述：
猴子跳台階共計14種基本組合
共計1+1+9+28+35+15+8+15+4+6+20+60+42+30=274種跳法排列
I. 爬樓梯問題--有n階台階,上樓可以一步上1階,2階,3階,計算共有多少種不同的走法
簡單的dp問題：
#include
int step[2048];
int* p = step;
void foo(int n)
{
if(n > 0) {
if(n > 1) {
*p++ = 2;
foo(n-2);
--p;
}
*p++ = 1;
foo(n-1);
--p;
} else {
for(int* k = step; k != p; ++k)
printf("%d ",*k);
putchar('\n');
}
}
int main()
{
foo(5);
}
J. 使用python演算法如何解
解決方案
從一些測試案例開始總是好的做法。讓我們從小的案例開始，看看能否找到某種規律。
．N=1，1種爬樓方式：[1]
．N=2，2種爬樓方式：[1,1]，[2]
．N=3，3種爬樓方式：[1,2]，[1,1,1]，[2,1]
．N=4，5種爬樓方式：[1,1,2]，[2,2]，[1,2,1]，[1,1,1,1]，[2,1,1]
你有沒有注意到什麼？請看N=3時，爬完3階樓梯的方法數量是3，基於N=1和N=2。存在什麼關系？
爬完N=3的兩種方法是首先達到N=1，然後再往上爬2步，或達到N=2再向上爬1步。所以f(3)=f(2)+f(1)。
這對N=4是否成立呢？是的，這也是成立的。因為我們只能在達到第三個台階然後再爬一步，或者在到了第二個台階之後再爬兩步這兩種方式爬完4個台階。所以f(4)=f(3)+f(2)。
所以關系如下：f(n)=f(n–1)+f(n–2)，且f(1)=1和f(2)=2。這就是斐波那契數列。
deffibonacci(n):
ifn<=1:
return1
returnfibonacci(n-1)+fibonacci(n-2)
當然，這很慢（O(2^N)）——我們要做很多重復的計算！通過迭代計算，我們可以更快：
deffibonacci(n):
a,b=1,2
for_inrange(n-1):
a,b=b,a+b
returna
現在，讓我們嘗試概括我們學到的東西，看看是否可以應用到從集合X中取步數這個要求下的爬樓梯。類似的推理告訴我們，如果X={1,3,5}，那麼我們的演算法應該是f(n)=f(n–1)+f(n–3)+f(n–5)。如果n<0，那麼我們應該返回0，因為我們不能爬負數。
defstaircase(n,X):
ifn<0:
return0
elifn==0:
return1
elifninX:
return1+sum(staircase(n-x,X)forxinXifx<n)
else:
returnsum(staircase(n-x,X)forxinXifx<n)
這也很慢（O(|X|^N)），因為也重復計算了。我們可以使用動態編程來加快速度。
每次的輸入cache[i]將包含我們可以用集合X到達台階i的方法的數量。然後，我們將使用與之前相同的遞歸從零開始構建數組：
defstaircase(n,X):
cache=[0for_inrange(n+1)]
cache[0]=1
foriinrange(n+1):
cache[i]+=sum(cache[i-x]forxinXifi-x>0)
cache[i]+=1ifiinXelse0
returncache[-1]
現在時間復雜度為O(N*|X|)，空間復雜度為O(N)。