當前位置:首頁 » 操作系統 » 快遞冪演算法

快遞冪演算法

發布時間: 2022-07-21 11:00:08

『壹』 快速冪演算法原理

快速冪
顧名思義,快速冪就是快速算底數的n次冪。其時間復雜度為 O(log2N), 與樸素的O(N)相比效率有了極大的提高。

中文名
快速冪
外文名
Fast Power
時間復雜度
log(n)
性質
快速算底數的n次冪
快速
導航
實現

代碼比較
原理
快速冪演算法的核心思想就是每一步都把指數分成兩半,而相應的底數做平方運算。這樣不僅能把非常大的指數給不斷變小,所需要執行的循環次數也變小,而最後表示的結果卻一直不會變。
讓我們先來看一個簡單的例子:
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
9^5=(9^4)*(9^1)
9^5=(9^4)*(9^1)
9^5=(6561^1)*(9^1)
以下以求a的b次方來介紹[1]
把b轉換成二進制數。
該二進制數第i位的權為
例如

11的二進制是1011

因此,我們將a11轉化為算
實現
快速冪可以用位運算來實現
b and 1{也就是取b的二進制最低位(即第0位)判斷b是否為奇數,是則為1}
b shr 1{就是去掉b的二進制最低位(即第0位)}
C++實現為
b & 1//取b二進制的最低位,判斷和1是否相同,相同返回1,否則返回0,可用於判斷奇偶
b>>1//把b的二進制右移一位,即去掉其二進制位的最低位
以下為pascal的實現:
var a,b,n:int64;
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1; y:=a;
while b<>0 do begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;{這里用了一個技巧,y*y即求出了a^(2^(i-1))不知道這是什麼的看原理
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情況下a*b mod c =(a mod c)*(b mod c) mod c}
b:=b shr 1;{去掉已經處理過的一位}
end;
exit(t);
end;
begin
read(a,b,n);{n是模}
writeln(f(a,b,n));
end.
[1]
以下為C的實現,為了方便與pascal的對照,變數全部與上面相同.可以對照查看。
遞歸版:[2]
ll pow(ll a,ll i){
if (i==0) return 1;
int temp=pow(a,i>>1);
temp=temp*temp%MOD;
if (i&1) temp=(ll)temp*a%MOD;
return temp%MOD;
}
非遞歸版:
ll f(ll a,ll b,ll n){
int t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%n;
y=y*y%n; b=b>>1;
}
return t;
}

『貳』 用遞歸 快速冪怎麼寫

是求(a的b次冪)mod c的值吧?
#include<stdio.h>
int res(int a, int b, int c);
void main()
{int a,b,c;
scanf("%d %d %d",&a,&b,&c);
printf("%d\n",res(a,b,c));
}
int res(int a, int b, int c) {
if (b == 1) return a % c;
if (b % 2) return a * res (a, b / 2, c) * res (a, b / 2, c) % c;
else return res (a, b / 2, c) * res (a, b / 2, c) % c;
}

『叄』 快遞體積的重量計算公式是怎麼樣的

快遞體積的重量計算公式,以順豐為例,列舉如下:

1、【順豐即日/次晨/標快】

同城、省內件以及經濟區域內互寄,體積重量=長(CM)×寬(CM)×高(CM)÷12000;

省外跨經濟區域互寄,體積重量=長(CM)×寬(CM)×高(CM)÷6000;

(經濟區域包含:京津冀區域,江浙滬皖區域,,川渝區域,黑吉遼區域)

2、【順豐特惠】 體積重量=長(CM)×寬(CM)×高(CM)÷12000;

3、【重貨包裹/小票零擔/冷運到家】 體積重量=長(CM)×寬(CM)×高(CM)÷6000;

4、【冷運零擔】 體積重量=長(CM)×寬(CM)×高(CM)÷3000;

5、【港澳台(服務)】體積重量=長(CM)×寬(CM)×高(CM)÷6000

6、【國際快遞(服務)】體積重量=長(CM)×寬(CM)×高(CM) ÷5000

100KG以下,續重以0.5KG為計重單位,不足0.5kg,按0.5kg計;100KG及以上,四捨五入取整數。

『肆』 快遞怎麼算運費

快遞的運費計算公式:(總重量-首重重量)*續重價格+首重價格=快件的運費

較多情況下按重量計費,以毛重為總的重量,以KG為計量單位。不同的省份會收取不同的運費價格,會有首重價格和續重價格。比較少的情況會按體積重計價,快遞會對長、寬、高進行單邊限制,超出則會按長*寬*高/6000,算出來的體積重,然後再按照上面的公式進行計價算運費。

在實際工作過程中,對於快遞批量進行計價的,還可以通過運費計算插件,連接電子稱,進行自動計算。提高工作效率。運費計算插件一般需要將運費價格表的明細錄入,才能進行自動計算,所以一定要理解運費的計算。

國際快遞收費標准

國際快遞包裹重量分實際重量和體積重量兩種,快遞公司將以兩種重量中大的一項為計費依據運輸物品到國外,主要包括兩大類的費用,運費和當地國的稅費。

國際快遞包裹的貨物不足0.5公斤的,按0.5公斤計費,要了解目的地國家都要收哪些費用,因為各個國家都不一樣,所以要注意國際快遞出口價格資費變化較大,需發快遞郵包時,應先聯系客服人員確認價格。

『伍』 快遞費用演算法

首重就是不超過1公斤,續重是1公斤以上
比如首重10元/公斤,續重5元/公斤 有6公斤,那就是6公斤×5元+5元
加的5元是首重的10元-續重的5元
也可以用10元+5公斤×5元
希望對你有所幫助~~

『陸』 不理解矩陣快速冪如何用於求斐波那契數列第n項%m的余數,望大神講解,越詳細越好

按照正常的邏輯是只要求a[2][2]={1,1,1,0}這個矩陣的n次方就可以得到斐波那契數列的第n項(即a[0][1])的值。但是你忽略了一點,就是你在求a[0][1],a[1][0],a[1][1]的值的時候你的a[0][0]的值其實已經改變了,導致你求得的a[0][1]的值不正確,繼而影響到a[1][0]和a[1][1]的值。

因此,我們在遍歷這四個值的時候是不能改變其中任何一個的,只有改完之後才能去改變它的值。所以我們可以用幾個變數先將求得的新矩陣各值存起來,如下:

#include<stdio.h>

inta[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用兩個二維數組表示快速冪演算法要用到的矩陣

intmain()

{

intn,m,i,j,t,u;

inta1,a2,a3,a4;

while(scanf("%d%d",&n,&m)!=EOF)

{

if(m==-1&&n==-1)//當輸入的m.n值為-1時結束整個演算法

return0;

/*以下是對於第n項斐波那契數的計算*/

if(n==0)

a[0][0]=0;

elseif(n==1||n==2)

a[0][0]=1;

else

{

for(i=3;i<=n;i++)

{

a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];

a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];

  • a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];

  • a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];

a[0][0]=a1;

a[0][1]=a2;

a[1][0]=a3;

a[1][1]=a4;

}

}

t=a[0][0];

a[0][0]=1;//重置矩陣

a[0][1]=1;

a[1][0]=1;

a[1][1]=0;

if(m==0)

a[0][0]=0;

elseif(m==1||m==2)

a[0][0]=1;

else

{

for(j=3;j<=m;j++)

{

a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];

a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];

  • a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];

  • a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];

a[0][0]=a1;

a[0][1]=a2;

a[1][0]=a3;

a[1][1]=a4;

}

}

u=a[0][0];

a[0][0]=1;//重置矩陣

a[0][1]=1;

a[1][0]=1;

a[1][1]=0;

t=t%u;

printf("%d ",t);

}

return0;

}

還有一點,就是你的矩陣相乘後兩項寫錯了,自己對比一下改過來吧。

這樣就能得到你想要的結果了。

『柒』 快速冪是什麼

解釋一下a^b mod c:
a^b mod c=a^(f[0]*2^0+f[1]*2^1+f[2]*2^2...f[t]*2^t)
因為 a*b mod c= ((a mod c) *b) mod c
所以
a^b mod c=(((f[0]*2^0 mod c)*f[1]*2^1 mod c)......*f[t]*2^t mod c)
用這種方法解決a^b mod c 時間復雜度
2^t<=b<2^(t+1)
t<=log(2)b<t+1
因為 b是個整數 所以
t=log(2)b
時間復雜度比直接循環求a^b大大的降低了

模取冪運算

事實上,m^e mod n可以直接計算,沒有必要先算m^e。
m^e mod n叫做模取冪運算,根據簡單的數論知識,很容易設計一個分治演算法。具體如下:

設<b[k], b[k-1],...,b[1],b[0]>是整數b的二進製表示(即b的二進制有k+1位,b[k]是最
高位),下列過程隨著c的值從0到b成倍增加,最終計算出a^c mod n

Molar-Exponentiation(a, b, n)
1. c ← 0
2. d ← 1
3. 設<b[k],b[k-1],..b[0]>是b的二進製表示
4. for i←k downto 0
5. do c ← 2c
6. d ← (d*d) mod n
7. if b[i] = 1
8. then c ← c + 1
9. d ← (d*a) mod n
10. return d

首先說明一下,上述偽代碼中用縮緊表示語句之間的層次關系,例如第5~9行都是for循環體
內的語句,第8~9行都是then裡面的語句。這是我比較喜歡的一種表示方法 ;)

上述偽代碼依次計算出的每個冪或者是前一個冪的兩倍,或者比前一個冪大1。過程依次從
右到左逐個讀入b的二進製表示已控制執行哪一種操作。循環中的每次迭代都用到了下面的
兩個恆等式中的一個:
a^(2c) mod n = (a^c mod n)^2
a^(2c+1) mod n = a * (a^c mod n)^2
用哪一個恆等式取決於b[i]=0還是1。由於平方在每次迭代中起著關鍵作用,所以這種方法
叫做「反復平方法(repeated squaring)」。在讀入b[i]位並進行相應處理後,c的值與b的
二進製表示<b[k],b[k-1],..b[0]>的前綴的值相同。事實上,演算法中並不真正需要變數c,
只是為了說明演算法才設置了變數c:當c成倍增加時,演算法保持條件d = a^c mod n 不變,直
至c=b。

如果輸入a,b,n是k位的數,則演算法總共需要執行的算術運算次數為O(k),總共需要執行的位
操作次數為O(k^3)。

『捌』 如何計算快速冪,比如 x^100000000次方,直接循環很慢。。謝謝了

因為 x^n = (x^(n/2))^2
根據這個公式,可以在 log2N時間內算出乘法冪

遞歸演算法:
int pow(int x,int n)
{
if(n==1) return x;
else if(n&1) //n is odd
{
return x*pow(x,n/2);

}
else
{
return pow(x,n/2);
}

}

非遞歸演算法:

int pow(int x,int n)
{
int temp(x),res(1);
while(n)
{
if(n&1)
{
res *= temp;
}
temp *= temp;
n>>=1;
}
return res;
}

『玖』 次方的快速演算法

次方有兩種快速演算法:

第一種是直接用乘法計算,例:3⁴=3×3×3×3=81。

第二種則是用次方階級下的數相乘,例:3⁴=9×9=81

次方最基本的定義是:設a為某數,n為正整數,a的n次方表示為aⁿ,表示n個a連乘所得之結果,如2⁴=2×2×2×2=16。次方的定義還可以擴展到0次方和負數次方等等。

負數次方

由5的0次方繼續除以5就可以得出5的負數次方。

例如: 5的0次方是1 (任何非零數的0次方都等於1。)

5的-1次方是0.2 1÷ 5 =0.2

5的-2次方是0.04 0.2÷5 =0.04

因為5的-1次方是0.2 ,所以5的-2次方也可以表示為0.2×0.2=0.04

5的-3次方則是0.2×0.2×0.2=0.008

由此可見,一個非零數的-n次方=這個數的倒數的n次方。

(9)快遞冪演算法擴展閱讀:

0的次方

0的任何正數次方都是0,例:0⁵=0×0×0×0×0=0

0的0次方無意義。

一個數的0次方

任何非零數的0次方都等於1。原因如下:

通常代表3次方

5的3次方是125,即5×5×5=125

5的2次方是25,即5×5=25

5的1次方是5,即5×1=5

由此可見,n≧0時,將5的(n+1)次方變為5的n次方需除以一個5,所以可定義5的0次方為:

5 ÷ 5 = 1。

熱點內容
安卓系統的哪個平板吃雞好 發布:2025-01-20 20:13:24 瀏覽:555
go語言編譯模式 發布:2025-01-20 19:57:25 瀏覽:405
超能編程 發布:2025-01-20 19:56:26 瀏覽:1000
安卓手機怎麼連藍牙汽車 發布:2025-01-20 19:39:05 瀏覽:253
保定軍工存儲廠家 發布:2025-01-20 19:38:53 瀏覽:795
雲伺服器ecs服務條款 發布:2025-01-20 19:19:36 瀏覽:47
安卓系統顯示屏怎麼設置屏保 發布:2025-01-20 19:18:53 瀏覽:896
有鎖機和配置鎖哪個好 發布:2025-01-20 19:18:05 瀏覽:767
安卓版軟體如何設置 發布:2025-01-20 18:58:53 瀏覽:58
java中級項目案例 發布:2025-01-20 18:58:52 瀏覽:913