最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

【僅供測試】快速冪與龜速乘

2023-08-16 20:49 作者:Mount256  | 我要投稿

1. 快速冪2. 龜速乘3. 快速冪取模4. 龜速乘取模5. 快速冪取模優(yōu)化6. 矩陣乘7. 矩陣快速冪8. 矩陣快速冪用于遞推式斐波那契數(shù)列遞推式的一些套路參考資料

1. 快速冪

算法原理：

  • 計算：
  • 僅需計算 3 次，而非 11 次
  • 計算 ：
  • 僅需計算 3 次，而非 10 次

算法思路：

  • 若指數(shù)是偶數(shù)，則將底數(shù)平方，指數(shù)除以 2。
  • 若指數(shù)是奇數(shù)，則將底數(shù)平方，指數(shù)除以 2，再乘上底數(shù)。

算法代碼：

typedef?unsigned?long?long?uLL;

//?快速冪?a^b
uLL?power?(uLL?a,?uLL?b){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?r?*?a;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?a?*?a;
????}
????return?r;
}

舉例：

  • 初始值：a = 3，b = 11
  • 第 1 輪：（11 % 2 == 1）r=1x3=3，b=5，a==9
  • 第 2 輪：（5 % 2 == 1）r=3x==27，b=2，a===81
  • 第 3 輪：（2 % 2 == 0）r 不變，b=1，a==
  • 第 4 輪：（1 % 2 == 1）r=x=，b=0，a==
  • 得到 r = =

2. 龜速乘

算法原理：將其中一個乘數(shù)分解成 2 的冪次相加。

算法代碼：

typedef?unsigned?long?long?uLL;

//?龜速乘?a*b
uLL?mul?(uLL?a,?uLL?b){
????uLL?r?=?0;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?r?+?a;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?a?+?a;
????}
????return?r;
}

3. 快速冪取模

初等數(shù)論中有如下公式：

(a × b) % m = ((a % m) × (b % m)) % m

推廣：

(a × b × c...) % m = ((a % m) × (b % m) × (c % m) × ... ) % m

(a^b) % m = (a × a × a...) % m = ((a % m) × (a % m) × (a % m) × ... ) % m

算法代碼：

typedef?unsigned?long?long?uLL;

//?快速冪取模?(a^b)?%?p
uLL?powerMod?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?(r?*?a)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?(a?*?a)?%?p;
????}
????return?r;
}

4. 龜速乘取模

算法原理：(a × b) % m = ((a % m) × (b % m)) % m

算法代碼：

//?龜速乘取模?(a*b)?%?p
uLL?mulMod?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?0;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?(r?+?a)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?(a?+?a)?%?p;
????}
????return?r;
}

5. 快速冪取模優(yōu)化

算法原理：注意到快速冪取模算法中的相乘操作可能會超出數(shù)據(jù)范圍，因此可以將相乘操作轉(zhuǎn)化為龜速乘取模。

原理依然是此公式：(a × b) % m = ((a % m) × (b % m)) % m，其中((a % m) × (b % m))即為龜速乘取模。

算法思路：快速冪 + 龜速乘結(jié)合。

//?快速冪取模防止爆炸?(a^b)?%?p
uLL?powerModBig?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?mulMod(a,?b,?p)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?mulMod(a,?a,?p)?%?p;
????}
????return?r;
}

6. 矩陣乘

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)，此時不能使用typedef！?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

int?main(){
????int?r,?c;

????printf("請輸入第一個矩陣的行和列：\n");
????scanf("%d?%d",?&r,?&c);
????Martix?x(r,?c);
????printf("請輸入%d行%d列的矩陣：\n",?r,?c);
????for?(int?i?=?0;?i?<?x.row;?i++)
????????for?(int?j?=?0;?j?<?x.col;?j++)
????????????scanf("%d",?&x.martix[i][j]);

????printf("請輸入第二個矩陣的行和列：\n");
????scanf("%d?%d",?&r,?&c);
????Martix?y(r,?c);
????printf("請輸入%d行%d列的矩陣：\n",?r,?c);
????for?(int?i?=?0;?i?<?y.row;?i++)
????????for?(int?j?=?0;?j?<?y.col;?j++)
????????????scanf("%d",?&y.martix[i][j]);

????Martix?result?=?Multiply(x,?y);

????printf("結(jié)果是：\n");
????for?(int?i?=?0;?i?<?result.row;?i++){
????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????printf("%d?",?result.martix[i][j]);
????????printf("\n");
????}

????return?0;
}

7. 矩陣快速冪

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

Martix?Power?(Martix?x,?int?k){
????Martix?r(x.row,?x.col);

????//?單位矩陣構(gòu)建?
????for?(int?i?=?0;?i?<?r.row;?i++){
????????for?(int?j?=?0;?j?<?r.col;?j++){
????????????if?(i?==?j)
????????????????r.martix[i][j]?=?1;
????????????else
????????????????r.martix[i][j]?=?0;
????????}
????}

????//?矩陣快速冪?
????while?(k?!=?0){
????????if?(k?&?1)
????????????r?=?Multiply(x,?r);
????????k?=?k?>>?1;
????????x?=?Multiply(x,?x);
????}

????return?r;
}

int?main(){
????int?r,?k;

????printf("請輸入行（列）：\n");
????scanf("%d",?&r);
????Martix?x(r,?r);
????printf("請輸入%d行%d列的矩陣：\n",?r,?r);
????for?(int?i?=?0;?i?<?x.row;?i++)
????????for?(int?j?=?0;?j?<?x.col;?j++)
????????????scanf("%d",?&x.martix[i][j]);

????printf("請輸入指數(shù)k：\n");
????scanf("%d",?&k);

????Martix?result?=?Power(x,?k);

????printf("結(jié)果是：\n");
????for?(int?i?=?0;?i?<?result.row;?i++){
????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????printf("%d?",?result.martix[i][j]);
????????printf("\n");
????}

????return?0;
}

8. 矩陣快速冪用于遞推式

斐波那契數(shù)列

數(shù)列遞推式：

矩陣遞推式：

矩陣公式：

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

Martix?Power?(Martix?x,?int?k){
????Martix?r(x.row,?x.col);

????//?單位矩陣構(gòu)建?
????for?(int?i?=?0;?i?<?r.row;?i++){
????????for?(int?j?=?0;?j?<?r.col;?j++){
????????????if?(i?==?j)
????????????????r.martix[i][j]?=?1;
????????????else
????????????????r.martix[i][j]?=?0;
????????}
????}

????//?矩陣快速冪?
????while?(k?!=?0){
????????if?(k?&?1)
????????????r?=?Multiply(x,?r);
????????k?=?k?>>?1;
????????x?=?Multiply(x,?x);
????}

????return?r;
}

int?main(){
????int?k;

????while?(scanf("%d",?&k)?!=?EOF){?
????????//?斐波那契數(shù)列的遞推矩陣構(gòu)建?
????????//?[1,?1]
????????//?[1,?0]
????????Martix?e(2,?2);
????????e.martix[0][0]?=?1;?e.martix[0][1]?=?1;
????????e.martix[1][0]?=?1;?e.martix[1][1]?=?0;

????????Martix?result?=?Power(e,?k);

????????for?(int?i?=?0;?i?<?result.row;?i++){
????????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????????printf("%d?",?result.martix[i][j]);
????????????printf("\n");
????????}
????}

????return?0;
}

輸入和輸出：

1
1?1
1?0
2
2?1
1?1
3
3?2
2?1
4
5?3
3?2
5
8?5
5?3
6
13?8
8?5
7
21?13
13?8
8
34?21
21?13
9
55?34
34?21
10
89?55
55?34

相關(guān)題目：（POJ3070）斐波那契數(shù)列f(n)，輸入n，求f(n) % 10000，n <= 1e9。

解題思路：僅需在快速冪函數(shù)中添加% 10000即可。

遞推式的一些套路

（1）數(shù)列遞推式：

矩陣遞推式：

（2）數(shù)列遞推式：

矩陣遞推式：

（3）數(shù)列遞推式：

矩陣遞推式：

參考資料

基礎(chǔ)算法—快速冪詳解

矩陣快速冪（原理+模板）

KY21 遞推數(shù)列

標(biāo)簽：

【僅供測試】快速冪與龜速乘的評論 (共 條)

分享到微博請遵守國家法律
皋兰县| 乌兰浩特市| 红原县| 宁陕县| 怀化市| 蒙自县| 大荔县| 麻城市| 太谷县| 新密市| 嘉义县| 金华市| 都昌县| 湖口县| 云浮市| 屯留县| 丰县| 民权县| 北海市| 阿图什市| 通榆县| 上饶市| 永泰县| 将乐县| 卢氏县| 台山市| 红安县| 准格尔旗| 双鸭山市| 固原市| 霍山县| 河曲县| 泽普县| 饶河县| 峨眉山市| 二连浩特市| 乐业县| 井陉县| 云和县| 抚远县| 禹州市|