PTT數位生活區 / C_and_CPP (C/C++)

[問題] 請教個國考題目

看板C_and_CPP (C/C++)作者 (Yes We Can!)時間16年前 (2010/01/26 23:57), 編輯推噓4(4推 0噓 9→)
留言13則, 6人參與, 最新討論串1/1
一題98年關務特考的資料結構題目 我想很久，但還是不知道怎麼寫 想請高手指教一下！感謝！ N為2的m次方，a為任意整數， 請寫一使用O(logN)次乘法運算的疊代(iterative)程式計算a的N次方 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.199.7
推
01/27 00:06, , 1F
想要求 2^n 就先求 2^(n/2)
01/27 00:06, 1F
推
01/27 00:40, , 2F
為啥題目我都看不懂 a的次方跟2^m又有啥關係
01/27 00:40, 2F
推
01/27 00:44, , 3F
出題的描述比較不好吧; 簡單的說要你用連乘寫個算某數的
01/27 00:44, 3F
→
01/27 00:45, , 4F
a次方/還是a的某數次方(推測是後者); 但是乘法的複雜度
01/27 00:45, 4F
→
01/27 00:46, , 5F
是O(logN)這樣; 解題的概念就像1F l大提示的那樣子吧;
01/27 00:46, 5F
推
01/27 00:48, , 6F
他題目何必提起2^M呢@@
01/27 00:48, 6F
→
01/27 00:48, , 7F
假如要算3^8 => (3^2)^4 => ((3^2)^2)^2; 次方數不是2的
01/27 00:48, 7F
→
01/27 00:49, , 8F
次方數的話就看怎麼缺怎麼補, 搞點瑣碎的判斷之類的??
01/27 00:49, 8F
→
01/27 09:04, , 9F
int f(int a, int m){for(int i=0;i<m;i++)a=a*a; return a;}
01/27 09:04, 9F
→
01/27 09:06, , 10F
假設m是非負整數
01/27 09:06, 10F
※ 編輯: fjf1980 來自: 140.126.73.155 (01/27 14:15)
→
01/27 15:05, , 11F
01/27 15:05, 11F
→
01/27 21:15, , 12F
謝謝大家的指教！
01/27 21:15, 12F
→
01/27 21:18, , 13F
也感謝DJWS的熱心！ 超感恩！
01/27 21:18, 13F
‣ 更多 fjf1980 的文章
文章代碼(AID): #1BNn3z7_ (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fjf1980 的文章
文章代碼(AID): #1BNn3z7_ (C_and_CPP)