雲林SONG: 2月 2015

高中生程式解題系統：Print it all

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a147。

此題用題目給的條件來解即可。

程式碼：

#include <cmath>
#include <cstdio>

using namespace std;

int main(void){
 int num = 0;

    while(scanf("%d", &num) != EOF)
    {
  for(int i = 1; i < num; i++)
  {
   if( i % 7 == 0)
    continue;
   printf("%d ", i);
  }

  printf("\n");
    }

    return 0;
}

高中生程式解題系統：質數又來囉 (Prime Numbers in A Range)

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a121。

維基百科上質數的定義為：

「指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個因數的數）」

一個著名且有效率的方法Sieve of Eratosthenes(底下圖片取自https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

Sieve of Eratosthenes演算法(底下文字取自https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)：

 Input: an integer n > 1.
 
 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding  $\sqrt n$ :
   if A[i] is true:
     for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n:
       A[j] := false.
 
 Output: all i such that A[i] is true.

筆者先用Sieve of Eratosthenes演算法求出100000000以下的所有質數的對照表，接著再用迴圈檢查 [a,b] 範圍內有多少個質數。
程式碼：

#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

#define NUM 100000001
int main(int argc, char** argv) {
 vector<bool> isP;
 long cnt;
 long a, b;

    for(int i = 0; i < NUM; i++)
        isP.push_back(true);

    isP[0] = false;
    isP[1] = false;

    for(long i = 2; i <= 10000; i++)
    {
        if(isP[i])
        {
            for(long j = i * i; j < NUM; j += i)
                isP[j] = false;
        }
    }


 while(cin >> a >> b)
 {
  cnt = 0;

  for(long i = a; i <= b; i++)
  {
      if(isP[i]) cnt++;
  }

  cout << cnt << endl;
 }

 return 0;
}

高中生程式解題系統：排序 Sorting

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a104。

雖然排序演算法有很多種，C++也有內建的函數，所以直接用內建函數 sort 來解，其他排序演算法可參考 Python 排序演算法範例一文。

程式碼：

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char** argv) {
 int n;

 while(cin >> n) 
 {
  int data[n];
  for(int i = 0; i < n; i++)
   cin >> data[i];
  
  sort(data, data+n);
  
  for(int i = 0; i < n; i++)
   cout << data[i] << " ";
   
  cout << endl;
 }

 return 0;
}

高中生程式解題系統：麥哲倫的陰謀

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a095。

這題求出的公式如下：
當 m == n 時，結果為 m。
其餘結果均為 m + 1。

程式碼：

#include <iostream>

using namespace std;

int main(int argc, char** argv) {
 int n, m;

 while(cin >> n >> m) 
 {
  int ans = m + 1;
  if(n == m)
   ans = m;

  cout << ans << endl;
 }

 return 0;
}

高中生程式解題系統：You Cannot Pass?!

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a148。

此題根據題目給的條件即可。此外，為了避免 overflow，用了個計算的技巧 average += (score / num); ，但在此題似乎作用不大。

程式碼：

#include <cmath>
#include <cstdio>

using namespace std;

int main(void){
 int num = 0;
 float score = 0;
 double average = 0.0;

    while(scanf("%d", &num) != EOF)
    {
  average = 0.0;
  for(int i = 1; i <= num; i++)
  {
   scanf("%f", &score);
   average += (score / num);
   
   //printf("average:%lf\n", average);
  }

  if( average > 59)
   printf("no\n");
  else
   printf("yes\n");
    }

    return 0;
}