Re: [其他] 尋找更快的方法算這個題目嗎？
※ 引述《lily4 (lily)》之銘言：
: 這是一個很簡單理解的algorithm,
: 計算不複雜但就是"煩"
: 加上考試的時候時間一逼下來，
: 很容易就亂了陣腳
: 考試的時候花了快半小時在算這題
: 雖然拿到了分數 但我想在考試的設計上，
: 最多最多五分鐘就應該要估得出來。
: 所以我想請教大家這一題是不是有非土法大煉鋼的方式
: 他是要跑兩個loops,
: 大loop是a, 小loop是b.
: 一開始a=0, b=0,
: a先固定住，b從0開始變動
: 如果a^2+b^2<2500,
: 就維持a=0, 但b要加1,
: 若符合a^2+b^2<2500, b再加1,
: 這樣一直重複到不符合a^2+b^2<2500才停止，
: 然後Ci=count,紀錄這個process重複的次數，
: 比如說a=0, b可以從0一直到49, 所以C0=50,
: a=1, b可以從0一直到49, C1=50,
: a=2,3,....,9, b都是可以從0一直到49.
: 題目最後的問題是總count大約是多少?
: 概數以千為單位, 1000,2000,3000,etc.
: 我當時把這題留到最後，告訴自己靜下心算就有繡花針了，
: 從a=0,1,....一直算平方算減法算到a=35,b=35,
: 然後a=36以上時就利用先前算a=0~35的結果去反推Ci,
: 然後再逐個加起來。
: 最後答案雖然對了，但自己把以上programming的時候，
: 得到的數字是2006, 我當時考試算1939.
: 所以我想問大家，集思廣益一下是不是有什麼good idea,
: 像高斯算1加到100的那種巧算法~~
: 謝謝大家!!
換個概念來看 把 (a,b) 看成座標的話
那這題在算的就是有多少格子點在 x^2+y^2=50^2 在第一象限中的 1/4 圓裡
其中座標軸上的要算, 圓上的不算
圖一畫出來想必你應該就可以看出來確實有一個稍微快些的方法:
在 1/4 圓中切一塊儘量大 邊跟座標軸平行的正方形
正方形裡的一口氣算完之後剩下的再慢慢數
這塊正方形正如你所算的裡面包含了 (0,0) 到 (34,34) 的格子點
((35,35) 在圓外 XD)
所以格子點數至少該有 35^2 = 1225 個
而剩下的部份用個很粗糙的估計法是兩個長 35 寬 15 的三角形
裡面至少有 35*15 = 525 個點 合計是 1750 個
考慮到這個結果是有少許低估的話就能夠選擇 2000 做為答案了
---
不過既然都畫出圖了 那其實有一個更有趣的做法
直接求出這個 1/4 圓的面積為 (1/4)(50)(50)(π) = 625π
因為π稍大於 3 所以 625π 就大約是 2000 所以就選 2000 XD
之所以這個做法可行的原因是
如果把座標平面上舖滿單位方格的話 上面的格子點其實就可以看成是方格的左下角點
這樣一來 格子點數就會大約跟方格數相同 (邊界會有少許誤差, 不過反正這題問估計)
於是要求的格子點數就大約跟 1/4 圓面積相等了
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.39.63
推
10/05 02:50, , 1F
10/05 02:50, 1F
→
10/05 02:50, , 2F
10/05 02:50, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：