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