UVA 10127、CPE 10532 程式解題。
解題觀念 :
這題嘛......我想一下要怎麼解釋(笑)
主要就是去找出一個數可以被使用者所輸入的數字整除。
要找什麼數字呢? 全部都是1的數。 ((蛤?!
比如說,使用者輸入3。
好從1開始,1不能被3整除,繼續往下變11,11也不能被3整除,繼續往下變111。喔!111可以被3整除了!
讓我們來數一下總共有幾個1呢?
3個!答案就是3。
所以,這題主要是考,如何從1算到111的演算法。
解題步驟 :
因為心機測資問題(?),所以如果用 int 的話,會有溢位的狀況發生。
所以某K就直接用BigInteger來解題了。
用BigInteger宣告n,讓使用者輸入。
用BigInteger宣告sum=1,等一下用來計算1、11、111、1111...時要用的。
用 int 宣告count = 1,統計「1」的個數。
(將初始值設為1的原因,是因為我們開頭就從"1"開始算。)
我看過很多人會用字串輸入後,再把他轉成BigInteger,其實不用這麼麻煩。BigInteger是可以直接用Scanner掃描的,(.nextBigInteger())。
設定while迴圈,如果sum不能被n整除,則繼續計算。
好啦~終於寫到最重要的演算法了。 我是這樣寫的。
1 -> 11,(1x10)+1 = 11。
也就是說 :
將sum x10( .multiply(BigInteger.TEN) )後,加1(.add(BigInteger.ONE) )。
每計算一次就將count加1。
最後印出count。記得將所有值都初始化喔!
EX :
3
n = 3。
while(1.mod(3) != 0),符合,進入迴圈計算 :
sum = 1 x 10 + 1 = 11;count = 2。
while(11.mod(3) != 0),符合,繼續進入迴圈計算 :
sum = 11 x 10 + 1 = 111 ;count = 3。
while(111.mod(3) !=0),不符合,跳出迴圈。
印出 3。
By 小K
沒有留言:
張貼留言