查找在第100行帕斯卡三角形中不能被X整除的位數

我需要找出在第100行帕斯卡三角形中不能被數字x整除的位數。查找在第100行帕斯卡三角形中不能被X整除的位數

我爲了找到它而應用的算法是：由於Pascal的三角形是從第二行開始的11次冪，第n行可以通過11 ^（n-1）找到並且可以容易地檢查哪些數字不能被x整除。

當n等於99或100時，我怎樣才能找到大數字？有沒有其他的算法可以用來找到它？

2012-03-07 Jay

這是功課嗎？ – 2012-03-07 19:39:34

你的第二句話很難理解，你應該把它分成多個句子，或者至少加上一些標點符號 – phoog 2012-03-07 19:41:40

你可以寫一個算法來手動計算帕斯卡三角形而不是使用數字11 ^（n-1），那麼你可以遍歷每個數字而不是使用大在內存中溢出的數字。 – jzworkman 2012-03-07 19:43:08

您可以使用階乘（n！/（n-k + 1）！（k-1）！第n行，第k個值）直接計算帕斯卡三角形的值。您可以從k = 1開始，逐步計算二項式係數，並在n/2步中找到不能被x整除的數字。（n，k + 1）=（n，k）*（n-k + 1）/ k其中選擇（n，k）=（n！/（nk + 1）！ k-1）！

2012-03-07 19:43:43 ElKamina

第二行的第一個值是1，但是使用上面提到的公式n！/（n-k）！k！給出2這是錯誤的 – Jay 2012-03-07 19:52:02

@Jay索引問題。通常k以0開頭。請參閱我的更新答案，k從1開始。 – ElKamina 2012-03-07 19:56:41

仍然不起作用......第三排帕斯卡三角形是1 2 1.現在根據您的公式，找出第二個元素第三行，n = 3，k = 2，所以3！/（3-2 + 1）！（2-1）！給3但它的2 – Jay 2012-03-08 13:36:43

你不需要三角形第100行的精確值，可以計算value mod x，只需要像往常一樣建立三角形，但是隨處可以應用模數運算 - 你不需要大數字

2013-03-11 20:10:01 maxim1000

回答