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

[loveme00835 (最愛朴素妍)]

※ 引述《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:其實是因為他的題目指定要用continue去寫,所以我才想不出來.
→ kight:我自己是有用break就寫出來了,只是我想是否有continue的寫法
→ kight:但我怎麼想都想不出來如何用continue去寫....
→ kight:非常感謝你給的建議....
推 kight:也感謝大家給的想法...我大概明白了...^^
continue 只能略過該迴圈後面的部分, 如果硬要把 continue放
進來, 就要變成兩個迴圈要合在一起, 使得計數器值的上下界在
迴圈內動態被修改. 就像你那篇的推文: if內把 i「賦值」為 2
, 雖然一樣可以達成目的, 但卻是不好的寫法.
推 Yshuan:推這篇 我也在想給psudo code對原po會不會比較好
→ Yshuan:另外 為了練習某個syntax語法而去硬寫得作法 我覺得很怪...
推 cutecpu:推
※ 編輯: loveme00835     來自: 140.121.216.198      (12/17 15:07)
推 walker2009:推這篇的coding style