close

標題:

C++語言題目完整解法

發問:

有一個數(x)加上111(X+111)會是一個完平方數，若再加1647(X+111+1647)，又會是另一個完全平方數，請問x=?(不只有檔案，需有完整的C++語言寫法) 更新: (答案) 更新 2: 剛剛寫錯了

aa.jpg

 

此文章來自奇摩知識+如有不便請留言告知

最佳解答:

#include #include #include #define LOW 111 #define HIGH (1647+LOW) int main(void) { int a, root, square; for (a=40; ++a
其他解答:

對意見007： 1647 = 3^3 * 61 於是找到因數為1, 3, 9, 27, 61, 183, 549, 1647 也就是b可能的數 俺略加幾句： 因 b(2a+b) = 1647 故 b a^2 為 X+111, b 為 a 加上一個數後的平方等於a平方加1647 最後可得 b(2a + b) = 1647 2010-06-13 11:42:32 補充： OK, 再來已知a,b均為整數, 所以做法就是找出1647的因數, 先將1647給因數分解 1647 = 3^3 * 61 於是找到因數為1, 3, 9, 27, 61, 183, 549, 1647 也就是b可能的數 再帶回求a值, a^2值, x=a^2 - 111值 過濾掉重覆的結果值即求出 因為我是用java做的, 所以不貼答案 (也不便踼館啦....XD) 2010-06-13 11:43:07 補充： 111,1647 -> 這組數值我的程式執行為43次 111,760625775->這組數值我的程式執行為69次 111,760625773->這組數值執行為18702次 至於有沒有更快的? 有 從因數分解的演算法下手 如果有高手願意補充的話 2010-06-13 20:08:41 補充： 當然以企業角度而言, 求的是考慮到每項因素的最適合解而不是單考慮到演算法次數的最佳解 再以development time及維護的角度而言, 如果再考慮到平均工程師的程度及目標只是區區的4位數字 我上述的那些演算法一定是不及格的, 但我上述的回答也儘限於演算法次數, 需不需要採用真的要看是否會發生數字過大造成程式過慢的情況可能. 2010-06-13 20:09:07 補充： 不過既然被點名了, 那code不貼出來還真的說不過去 (順便感謝一下, 已加了009意見) http://tw.myblog.yahoo.com/tristezza-dolor/article?mid=12&prev=-1&next=-1 2010-06-13 20:13:51 補充： 至於次數的話, 已說明最差的狀況為Sqrt(N) (實際上會多加一點點), RAM使用量最差狀況為 N=2^n development 狀況最差狀況為-工程師看不懂在寫"尛"|||||To 發問者： 這兩位回答者的解法都正確，也都有說明。 程式的長短、速度的快慢，已說明其好壞。 知識+ 的定義是：最佳解答。 請給予符合定義的選擇，讓 好的回答者得到應得的 後人看到這題，很容易看到好的做法。 如果你把最佳解答給了較差的， 要是引起公憤，來了一堆負評， 你 和 較差的最佳解答，都會被扣點！！ 你希望這樣嗎？ ＝＝＝＝ 2010-06-13 06:01:01 補充： To 回答者 001 根據你之前問過的二題： http://knowledge.yahoo.com.tw/question/question?qid=1010060602064 http://knowledge.yahoo.com.tw/question/question?qid=1010052303237 你今年國二，學了C語言的一點皮毛。 能有這樣的本領，已算不錯！ 你應該有點印象： 『國一數學明顯比小六的難！』吧？ 告訴你： 1. 高一數學明顯比國三的難！ 2. 高二數學明顯比高一的難！ 2. 大一數學明顯比高三的難！（問題較簡單，觀念較難） 3. 大二數學明顯比大一的難！ 2010-06-13 06:01:44 補充： 而， 大二的數學，在數學的領域裡，是小小小小兒科！ 1960年代，大家還在考慮的是： 資工該不該獨立成為一個系？ 還是它仍應該只是數學系的一個組？ 也就是說： 沒有數學，就沒有好的程式！ 你才國二，數學再好都不可能真的很好！ 程式上能有這樣的表現，勇氣可佳！ 最後能認輸，再次證明你勇氣可佳！ 但，中間數落了人，就不應該了！！ 尤其是：國二，約14歲，口氣這麼大，真的不好！！ 希望你從這題，可以〝再〞學到： 1. 對別人的尊重。 2. 人外有人，天外有天！ 在知識+ 確定有比我強的程式師！ 而台灣最強的程式師，應該沒在知識+ 活動！ 世界最強的程式師，應該不在台灣！ 2010-06-13 06:01:59 補充： 3. 演算法的重要！ 你的程式花了半小時，他的程式花了不到一秒！ 看起來約是 0.5 * 60 * 60 / 1 = 1800 倍！ 你可知，要是這題改成 1111 和 16477（長大約10倍）， 我估 002 會是你的 1800 * 10^2 * 1.5 = 25萬 倍快！甚至更多！ 因此，建議你： 1. 好好顧好功課！才能學到更多！ 2. 好好學尊重人！才有更多高手願意教你！ 我高一時，程式還沒才國二的你強呢！ 加油！ ^_^ 2010-06-13 17:03:47 補充： 個人〝認為〞〝目前為止〞，〝這題〞最好的演算法是原始人法。 而這題也沒指名：要最好〝演算法〞！ 也就是說：應該是要：最好程式。 關於 Time Complexity， 回答 001 的是 O(n^2) with a large hidden constant, but not very large 回答 002 的是 O(n^0.5) with a small hidden constant 意見 5~8 的 Big-O 不易〝看〞出，可能要找一下課本對照。估約 O(n^0.15) ＝＝＝＝ 2010-06-13 17:05:09 補充： 問：為何 002 是 O(n^0.5)？ 答：輸入範圍是1~n，用了 a*a 的 a 當 loop index，且沒有 inner loop！ 當然是 O(n^0.5) 問：那，為何 001 是 O(n^2)？ 答：輸入範圍是1~n，用了 1 ~ n 當 loop index，己經是 n 它有 inner loop！是 1~x！簡言之，又是個 n 所以，是個 O(n^2) 裡面還有 loop 呢！ 所以，判它 O(n^2) 已是低估！！ 說它是 O(n^2.5)、甚至 O(n^3) 都不為過！ 問：怎知 001 的 hidden constant 不小？ 答：有了一堆除法（及 if）怎會小？ 2010-06-13 17:06:44 補充： 問：怎知 002 的 hidden constant 很小？ 答：每個 iteration 〝只〞有 一個 inc、乘法、減法，sqrt 二個 assign, cmp、cast 怎會大？ 問：5~8 的 Big-O 為何看不出？ 答：要先找到 N的因數個數 與 N的〝漸近〞曲線！ 而這〝曲線〞本身是個折幅不小的折線！（參意見008的數據） 這漸近曲線絕對不是 根號 N！而是比根號 N小不少的東西。 ＝＝＝＝ 2010-06-13 17:09:05 補充： 問：0.15

arrow
arrow
    文章標籤
    意思 旅遊 時間 世界 人法
    全站熱搜
    創作者介紹
    創作者 ddhdxb5 的頭像
    ddhdxb5

    百科全書

    ddhdxb5 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄