資訊專欄INFORMATION COLUMN
摘要：但如果數(shù)據(jù)不大，代碼跑的結(jié)果是沒有任何問題的。我只是隨便找了一個例子，當(dāng)然有人會說不是要比要好進行嘛，是的沒錯，我在這里先埋下一個伏筆，最后我會針對這個問題進行優(yōu)化指的是第三種方法的優(yōu)化通過這個圖片，大家應(yīng)該可以很好的理解這個遞歸。
?文章將以代碼+解析（簡單）的方式進行，歡迎大家的閱讀！
首先，任何一個問題都是有來源的，所以請先看題（我遇到的）：
?暴力解法（我第一次的想法）
代碼如下：
#include int main() { int n, m, i, num; scanf("%d", &num); while (num--) { scanf("%d %d", &n, &m); int N = 1; for (i = 1; i <= n; i++) { N *= i; } int M = 1; for (i = 1; i <= m; i++) { M *= i; } int N_M = 1; for (i = 1; i <= n - m; i++) { N_M *= i; } int f = N / (M * N_M); printf("%d/n", f); } return 0;} ?核心：數(shù)學(xué)公式：n!/(m!*(n-m)!)
所以我們只需要分別算三次階乘（對應(yīng)代碼N ,M ,N_M）就OK了，非常暴力，但最容易理解!
缺點：計算速度慢，當(dāng)數(shù)據(jù)大的時候，就報不過去了，因為已經(jīng)超過long long類型了（于是我進行了第二種方法——遞歸）。
但如果數(shù)據(jù)不大，代碼跑的結(jié)果是沒有任何問題的。
請看一下上述問題的測試數(shù)據(jù)：
?遞歸解法（進一步優(yōu)化）
代碼如下：（僅單次輸入）
#include long long f(int n, int m){ if (n < m) return 0;//分幾種情況 if (n == m) return 1; if (m == 0) return 1; return f(n - 1, m - 1) + f(n - 1, m);//實現(xiàn)遞歸}int main(){ int n, m; long long k = 0; scanf("%d %d", &n, &m); k = k + f(n, m); printf("%lld", k); return 0;} ?核心：遞歸
如果不好理解請看下面，我將用圖片來講解這個遞歸。
?我只是隨便找了一個例子，當(dāng)然有人會說C 6 2不是要比C 6 4要好進行嘛，是的沒錯，我在這里先埋下一個伏筆，最后我會針對這個問題進行優(yōu)化（指的是第三種方法的優(yōu)化）！
通過這個圖片，大家應(yīng)該可以很好的理解這個遞歸。
回歸數(shù)學(xué)方法（加優(yōu)化）
代碼如下（僅單次輸入）：
#includeint main(){ double n, m; scanf("%lf %lf", &n, &m); double sum = 1; double i; double q = m; for (i = 1; i <= q; i++) { sum *= (n--) / (m--); } printf("%.0lf", sum); return 0;} ?核心：數(shù)學(xué)方法
不知道怎么描述，所以直接暴力上圖(高中數(shù)學(xué)知識)：
?我再解釋一下我的代碼：
C n m， m就是我循環(huán)的次數(shù)，為了m的值在m--的時候不會丟失，我在這里用q存儲一下m的值，使得循環(huán)正常進行。
最后來到了優(yōu)化環(huán)節(jié)：
舉個例子C 6 4 與 C 6 2的值是一樣的，前者循環(huán)4次，后者循環(huán)2次，為了減少循環(huán)次數(shù)，只需加上一個判斷處理一下m的值，具體我直接上代碼：
int q; if (n - m < m) { q = n - m; m = q; } else q = m;?這樣就可以使代碼運行時，用最小的循環(huán)次數(shù)來進行！
在最后我附上最終代碼（C與C++）
C：
#includeint main(){ double n, m; int T; scanf("%d", &T); while (T--) { scanf("%lf %lf", &n, &m); int q; if (n - m < m) { q = n - m; m = q; } else q = m; double t = 1; for (int i = 1; i <= q; i++) t *= (n--) / (m--); printf("%.lf/n", t); } return 0;} C++(學(xué)長提供)：
?
?在文章最開頭我提到的問題，用最后一種代碼跑沒有一點問題。因為在乘的過程中 除也在進行，就可以保證內(nèi)存夠用。
此題花費我數(shù)小時來解決（我太菜了，滑稽保命！）
希望本篇文章可以很好為廣大老鐵們解疑答惑，同時也希望老鐵們留下寶貴的建議與指導(dǎo)。
最后再次感謝您的閱讀！
?
?
?
?
?
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/119400.html
摘要：有關(guān)排列組合的一道算法題一題目內(nèi)容廢話不多說，先上題目有一個的網(wǎng)格，左下角為，右上角為，規(guī)定每次只能走一步，并且方向只能是向上或者向右，求到共有多少種走法例如一個日字形的格子就是一個的網(wǎng)格，共有種走法并用寫出程序算法。 有關(guān)排列組合的一道算法題 一、題目內(nèi)容 廢話不多說，先上題目： 有一個 n × m 的網(wǎng)格，左下角為A，右上角為B，規(guī)定每次只能走一步，并且方向只能是向上或者向右，求A...
摘要：前言相信大家在面試或者工作中偶爾會遇到遞歸算法的提問或者編程，我們今天來聊一聊從數(shù)學(xué)歸納法到理解遞歸算法。這種廣義的數(shù)學(xué)歸納法應(yīng)用于數(shù)學(xué)邏輯和計算機科學(xué)領(lǐng)域，稱作結(jié)構(gòu)歸納法。 showImg(https://img-blog.csdnimg.cn/20190426221838971.gif);showImg(https://img-blog.csdnimg.cn/20190429222...
摘要：它真的是深度優(yōu)先搜索嗎是真的嗎是真的如果是的話，那它的搜索空間解空間是什么是向量組成的集合，而。既然深度優(yōu)先搜索剪枝回溯。 什么是全排列？從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當(dāng)m=n時所有的排列情況叫全排列。那么ABC的全排列有哪些？根據(jù)定義得到：ABCACBBACBCACABCBA 如何通過程序求解？方法一：暴力...
閱讀 3846·2021-11-24 09:39
閱讀 3766·2021-11-22 12:07
閱讀 1116·2021-11-04 16:10
閱讀 810·2021-09-07 09:59
閱讀 1908·2019-08-30 15:55
閱讀 948·2019-08-30 15:54
閱讀 735·2019-08-29 14:06
閱讀 2484·2019-08-27 10:54
