Re: [問題] 快速-九九乘法表
最簡單的方法, 沒有人想到嗎?
首先, i*j = j*i, 所以幾乎有一半不用算.
其次, i*(j+1) = i*j + i, 所以只要拿前一項 i*j 加上 i, 就得到 i*(j+1).
同理, (i+1)*j = i*j + j.
所以周圍的項目都可以用加法算出來, 而且只用 "一次" 加法.
依此類推擴展.
※ 引述《TKyo (暗黑貴公子)》之銘言:
: ※ 引述《kbslave (ITer)》之銘言:
: : 最近朋友問我一個問題『要如何寫一個快速的 N N乘法表』,
: : 也就是要計算出一個Array[n][n],其中array[i][j]等於ixj,
: : 且全部紀錄此array中,當然最簡單的做法就是用雙for-loop去跑,
: : for
: : for
: : array[i][j]=i*j;
: : 我也想到另一個方法http://blog.kbslave.com/2008/05/1.html,
: : 但感覺效果其實沒有很好,不知道有沒有人有更快的解法呢?
: 1.以 2^x 為底, 對被乘數做因式拆解
: ps.不知道這 "解釋名詞" 是否有誤?? @@
: ex. 100 = 2^6 + 2^5 + 2^2 = 64 + 32 + 4
: 17 = 2^4 + 2^0 = 16 + 1
: 2.使用被乘數 "位移和加法" 的方法來加快速度, 減少乘法消耗的大量 clock
: ex. 假設乘數為 n
: n * 100 = n * (64 + 32 + 4) = n << 6 + n << 5 + n << 2
: n * 17 = n * (16 + 1) = n << 4 + n
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.87.245
推
05/27 06:08, , 1F
05/27 06:08, 1F
討論串 (同標題文章)