Re: [問題] C語言1^1+2^2+3^3+....+n^n
※ 引述《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
推
03/31 16:23, , 1F
03/31 16:23, 1F
→
03/31 16:24, , 2F
03/31 16:24, 2F
→
03/31 16:26, , 3F
03/31 16:26, 3F
推
03/31 17:52, , 4F
03/31 17:52, 4F
推
03/31 18:04, , 5F
03/31 18:04, 5F
推
03/31 19:38, , 6F
03/31 19:38, 6F
→
03/31 20:46, , 7F
03/31 20:46, 7F
→
03/31 20:50, , 8F
03/31 20:50, 8F
→
03/31 20:52, , 9F
03/31 20:52, 9F
→
03/31 21:24, , 10F
03/31 21:24, 10F
→
03/31 21:24, , 11F
03/31 21:24, 11F
→
03/31 21:25, , 12F
03/31 21:25, 12F
→
03/31 21:26, , 13F
03/31 21:26, 13F
→
03/31 21:27, , 14F
03/31 21:27, 14F
推
03/31 21:27, , 15F
03/31 21:27, 15F
→
03/31 21:28, , 16F
03/31 21:28, 16F
→
03/31 21:29, , 17F
03/31 21:29, 17F
推
04/01 10:22, , 18F
04/01 10:22, 18F
→
04/01 10:24, , 19F
04/01 10:24, 19F
→
04/01 10:25, , 20F
04/01 10:25, 20F
→
04/01 10:25, , 21F
04/01 10:25, 21F
→
04/01 10:26, , 22F
04/01 10:26, 22F
→
04/01 10:26, , 23F
04/01 10:26, 23F
→
04/01 10:39, , 24F
04/01 10:39, 24F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
