Re: [問題] 找小於輸入值的最大質數的語法

看板C_and_CPP (C/C++)作者loveme00835 (最愛朴素妍)時間15年前 (2010/12/17 13:40)推噓5(5推 0噓 4→)

留言9則, 4人參與討論串4/4 (看更多)

※ 引述《kight (山中雜草一隻鹿)》之銘言： : 我是使用Dev C++而且是初學者.. : 最近寫到這個題目.. : 想了老半天想不出來...後來看到解答的Code..我有些疑問.. : 他的解答如下.. : #include <iostream> : #include <cstdlib> : using namespace std; : int main(void) : { : int i,n=45; : bool flag=false; : int prime=n-1; : while(!flag) : { : for(i=2;i<prime;i++) : if(prime%i==0) // not a prime : { : prime--; : continue; : } : flag=true; : } : cout << "小於" << n << "的最大質數為" << prime << endl; : system("pause"); : return 0; : } : 只是我想請問.. : 我發現有沒有While迴圈似乎對整個算出來的解答沒有影響 : 我自己有將這code改寫成沒有while回圈而且可以自己輸入任意數.. : 但隨便輸入一個數算出來的最大質數也都是正確的.... : 所以我一直在思考這個迴圈的存在意義.. : 因為看來他執行完裡面的for迴圈就會直接把flag改成true然後跳出while迴圈 : 那...它這邊為何要加一個While迴圈呢??? : 懇請高手幫忙解答..。非常感謝.... ──────────────────────────── 我會把他的語法結構放在一邊, 專心在其中的兩行: for(i=2;i<prime;i++) if(prime%i==0) →「大於等於2且小於prime的每一個整數, 假如他整除prime..」假如有一個整數整除prime, 那prime就不會是質數, 此時因為你是要找最大的質數, prime測試失敗下一個就要測prime - 1, 然後... →「大於等於2且小於prime - 1的每一個整數, 假如他整除 prime - 1...」測試prime - 1是不是質數, 如果不重新從 2 開始除, 當n = 36 時: prime : 35, i 跑到 5 └→ prime : 34, i 跑到 17 └→ prime : 33, i 跑到 34 (迴圈結束) 此時會判定33是質數, 而 while 可有可無, 因為: ┌不存在 i 可以整除 prime → for 迴圈會停止 └存在 i 可以整除 prime → for 迴圈還是會停止最後都會讓 flag 值為真 → while 還是跑一次就停 ──────────────────────────── 正確的演算法: ┌─────────────────┐ │1. for prime ← n - 1 down to 2 │ │2. for i ← 2 to prime - 1 │ │3. if prime divided by i │ │4. goto the step 1. │ │5. prime is the answer. │ └─────────────────┘ 可以用書上的解答的程式修改一下, 變成下面這模樣: http://nopaste.info/53dc75acd2.html 雖然這份程式碼不是你寫的, 但我還是建議你養成習慣: 1.變數在使用之前才定義隔了好幾行的定義, 或是重複使用的變數會讓許多不同程式區段的碼邏輯混在一起, 更難瞭解語義以及分開除錯. 2.旗標的命名要符合它的目的此例的旗標是用來標示是否已經找到最大質數, 把他叫做 find 也是可以的. 3.儘量別在迴圈內更改他的上下界這會讓看的人較難追蹤程式的執行情況, 當然就比較難驗證它的正確性, 甚至修改它. ──────────────────────────── 自己想清楚或跟別人討論一下演算法, 腦力激盪一下你的思路會更清晰, 而且這也沒有到需要翻解答的地步.. 去理解看不懂的程式, 有時候花的時間還比你自己重寫一個還要長. 試著寫多種版本的解法, 比較差異的過程你也更能了解他們的優劣. 不要太相信解答... -- ◢████ ◢█ ◢██◣ ◢█ ◢███ ◢█ T-ara版怎麼去 ████◤ ██ ◢██◣█ ██ ████ ██ s ~> T-ara █／███ ██ ██ ██ █／█ ◢███ █／█ 歡迎您的光臨 ████◤ ██ ██ ██ ██◤ ███◤ ██◤ 恩靜、智妍、孝敏 █／███ ██ █／██◤ ██ █／██ ██ 素妍、居麗、寶藍 ████◤ █◤ ◥██◤ █◤ ████◤█◤ 花英 ψmakigoto123 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.121.216.198

推

kight

12/17 13:59, , 1^F

12/17 13:59, 1^F

→

kight

12/17 14:00, , 2^F

12/17 14:00, 2^F

→

kight

12/17 14:01, , 3^F

12/17 14:01, 3^F