2014年4月8日 星期二

[UVA] Ones

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



沒有留言:

張貼留言