作者gba356 (瑪利歐)
看板C_and_CPP
標題Re: [問題] C語言1^1+2^2+3^3+....+n^n
時間Tue Mar 31 16:15:17 2009
※ 引述《azure532 (當紅炸子機)》之銘言：
: 使用迴圈計算1^1+2^2+3^3+...+n^n的值
: n由使用者輸入(n為個位數的正整數)
: p.s 不得使用公式，也不得使用數學函式庫
你好~
計算指數的時候有個 O(lgN) 的演算法，
是利用 Divide and Conquer 的精神的，
它的想法是這樣：
若我們要計算 2 的 16 次方，
原本的作法需要連乘 15 次，
我們將時間浪費在很多次的相同乘法，
若以 pow( x, y ) 表示 x 的 y 次方的話，
我們可以將 pow( 2, 16 ) 分為 pow( 2, 8 ) * pow( 2, 8 )，
也就是說，
知道 2 的一次方相乘可以得到 2 的二次方，
知道 2 的二次方可以知道 2 的四次方，
知道 2 的四次方可以知道 2 的八次方，
最後得到 2 的十六次方，
花的計算成本只需要「四次分解」和「四次乘法」，
這個計算速度將會比十五次的連乘要快上許多的，
而這個演算法在次方數 N 非常大的時候會和 lgN 成漸進正比關係，
意思就是說，
計算 2 的 1024 次方大約和 lg(1024) = 10 次成正比而已，
和連乘的 1023 次乘法有著天差地遠的速度。
//lg 就是以二為底的對數~
這麼一來，
可以將演算法實作成原始碼：
int Pow( int base,int expo ) /* functioning same as pow() in <cmath> */
{
int temp;
if( expo==0 ) /* if y == 0, pow( x, y ) = 1 */
return 1;
else if( expo==1 ) /* pow( x, 1 ) = x */
return base;
else if( expo%2==0 ) /* Divide and Conquer */
{
temp = Pow( base,expo/2 ); /* Use variable "temp" to avoid */
return temp*temp; /* the recalculation of Pow() */
}
else
{
temp = Pow( base,expo/2 );
return temp*temp*base;
}
return 0; /* return zero when an error occurs */
}
至於怎麼將每一項相加就應該是你的功課了，
祝你順利！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.161.125.152
推 ledia:還可以改成用 loop, 不用遞迴 XD 03/31 16:23
→ gba356:精神比較重要 03/31 16:24
→ gba356:對了請不要跟我說「你應該做位元運算」那種無聊的話.. 03/31 16:26
推 adrianshum:推 無聊話 XD 03/31 17:52
推 TroyLee:不想聽無聊話 可以試著把 2^16 改成 3^16... 03/31 18:04
→ gba356:寫得短這麼重要？ 03/31 20:46
→ sunneo:重要啊 且overhead少多了 03/31 20:50
→ sunneo:我想你終有一天會遺憾自己想表達的東西被衝動的語氣給埋沒 03/31 20:52
→ gba356:也許你是對的，但是從原發問者的問題來看，我認為可能他 03/31 21:24
→ gba356:對這塊領域是比較不熟悉的，因此犧牲原始碼的可讀性追求 03/31 21:24
→ gba356:一點點運作上的效率是顯得較為無意義的。於是我去掉了 03/31 21:25
→ gba356:通常會有的優化和短碼使用，為的是讓原發問者更快理解原始 03/31 21:26
→ gba356:碼，而不是藉著一些機會炫耀自己的功力。 03/31 21:27
推 sunneo:你說的是 推你的教學精神 03/31 21:27
→ gba356:您仍然認為這邊該把原始碼縮到六行以下嗎？我不認為。 03/31 21:28
→ gba356:如果我的口氣是衝動的，我很抱歉:( 03/31 21:29
推 adrianshum:我贊同 gba 大所說的. 原 po 本身明顯只是初學者, 這 04/01 10:22
→ adrianshum:種程度的, 我會覺得寫清楚的 code 比追求各類壓搾速度 04/01 10:24
→ azure532:小弟對這塊領域還真的不熟悉 大家都這麼熱心回答感激不盡 04/01 10:25
→ adrianshum:的 trick 來得更重要. 我覺得對於絕大部份 developer 04/01 10:25
→ adrianshum:學懂怎麼思考不要讓電腦做無謂的事已經足夠了, 一味追 04/01 10:26
→ adrianshum:求 >>1 比 /2 快這類 trick, 只會弄巧反拙 04/01 10:26
→ azure532:小弟是想了解有沒有最佳的寫法 04/01 10:39