高中生程式解題系統：d709: 判断质数（一）

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

題目連結 https://zerojudge.tw/ShowProblem?problemid=d709。

想法是：「目前要判斷的整數 N，用已知的質數 prime 去除。」

程式碼：

#include <stdio.h>
#include <cmath>

using namespace std;

const long long int limitValue = 1000000;

const int num = 78500;

bool primeFlag[limitValue + 1];

int prime[num+1] = {2, 3, 5, 7, 11, 13};
int cnt = 0;

void genPrimeArray()
{
    int index = 6;

    for(int i = 0; i < index; i++)
        primeFlag[prime[i]] = 1;

 bool isPrime;
 for(int i = 15; i <= limitValue; i += 2)
 {
  isPrime = true;
  int k = 1;
  int terminal = sqrt(i);
  for(int c = prime[k]; c <= terminal; k++, c = prime[k])
  {
   if( i % c == 0)
   {
    isPrime = false;
    break;
   }
  }

  if(isPrime == true)
  {
   prime[index] = i;
   primeFlag[prime[index]] = 1;
   index++;
  }
 }
}

int main(void) {
 genPrimeArray();

 int p ;
 while(scanf("%d",&p)&& p!=0){
  printf("%d\n", 1 - primeFlag[p]);
 }

 return 0;
}

高中生程式解題系統：a227: 三龍杯 -> 河內之塔

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

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

以兩盤子個為例：

• 讓竿子一叫做 A，竿子二叫做B ，竿子三叫做C 
• 步驟一：從 A 移動 盤子1 到 B。
• 步驟二：從 A 移動 盤子2 到 C。
• 步驟三：從 B 移動 盤子1 到 C。

可看出規律：

• 從 A 移動 n-1個盤子 到 B。
• 從 A 移動 第 n個盤子 到 C。
• 從 B 移動 n-1個盤子 到 C。

程式碼：

#include <cstdio>

using namespace std;

void hanoi(int i, char from, char axu, char to)
{
 if(i == 1)
 {
  printf("Move ring %d from %c to %c\n", i, from, to);
 }
 else
 {
  hanoi(i-1, from, to, axu);
  printf("Move ring %d from %c to %c\n", i, from, to);
  hanoi(i-1, axu, from, to);
 }
}

int main(void)
{
 int n;
 while(scanf("%d", &n) == 1)
 {
  hanoi(n, 'A', 'B', 'C');
 }
}

高中生程式解題系統：c121: 00495 - Fibonacci Freeze

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

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

此題需要用到大數運算的做法，程式碼是用字串來處理。

程式碼：

#include <iostream>
#include <string>

// Fibonacci

using namespace std;

string addition(string s, string s2)                    // 加法
{
    int len, lenS, MaxL, i, a, b, c = 0;
    string BNstr(s2);

    // 去掉多餘的數字０
    len = BNstr.length();                // 讀取被加數的長度
    lenS = s.length();                    // 讀取加數的長度
    for (i = 0; i < len-1; i++)
       if (BNstr[0] == '0')
           BNstr.erase(BNstr.begin());
       else
           break;
    for (i = 0; i < lenS-1; i++)
       if (s[0] == '0')
           s.erase(s.begin());
       else
           break;

    len = BNstr.length();
    lenS = s.length();
    MaxL = (len > lenS)?len:lenS;

    for (i = 0; i < MaxL; i++) {
       if (i < len) a = BNstr[len-1-i]-'0';
               else a = 0;
       if (i < lenS) b = s[lenS-1-i]-'0';
                else b = 0;
       if (i < len) BNstr[len-1-i] = (a+b+c)%10+'0';
               else BNstr.insert(BNstr.begin(),(a+b+c)%10+'0');
       c = (a+b+c)/10;
    }
    BNstr.insert(BNstr.begin(),c+'0');

    // 去掉多餘的數字０
    len = BNstr.length();
    for (i = 0; i < len-1; i++)
       if (BNstr[0] == '0')
           BNstr.erase(BNstr.begin());
       else
           break;

    return BNstr;
}

int main(void){
    const int SIZE = 5001;
    string Fibonaccinum[SIZE] = { "0", "1" };

    for( int i = 2; i < SIZE; i++ )
    {
        Fibonaccinum[i] = addition(Fibonaccinum[i-1], Fibonaccinum[i-2]);
    }


    int n;
    while( cin >> n )
    {
        cout << "The Fibonacci number for " << n << " is " << Fibonaccinum[n] << endl;
    }

    return 0;
}

高中生程式解題系統：c119: 10220 - I Love Big Numbers

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

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

用陣列來處理，此部分可參考 超長整數運算（大數運算）一文。

程式碼：

#include<stdio.h>
int val[1001], p[10000], psize = 0;

int main(){
  int i, j, n;

  p[0] = 1;
  val[0] = 1;
  for(i = 1; i <= 1000; i++){
    for(j = 0; j <= psize; j++){
      p[j] *= i;
    }
    for(j = 0; j <= psize; j++){
      p[j+1] += p[j]/10;
      p[j] %= 10;
      val[i] += p[j];
    }
    while(p[psize+1]){
      psize++;
      p[psize+1] += p[psize]/10;
      p[psize] %= 10;
      val[i] += p[psize];
    }
  }
  while(scanf("%d", &n)==1){
    printf("%d\n", val[n]);
  }
  return 0;
}

高中生程式解題系統：c039: 00100 - The 3n + 1 problem

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

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

程式碼是用迴圈一直更新 num 的數值，直到 num == 1為止。
但可用動態規劃加速。

while(num != 1)
{
    num = (num % 2 == 0 ? num / 2: (num*3) + 1);
    cycleLength++;
}

程式碼：

#include <iostream>

using namespace std;

int get_cycle_length(int num);

int main(void)
{
    int i, j, k, start, end;
    int maximum = 1;
    int cycleLength;

    while( cin >> i >> j )
    {
        maximum = 1;
        start = i;
        end = j;
        if( i > j )  // ensure "start" is less than "end"
        {
            start = j;
            end = i;
        }

        for(k = start; k <= end; k++)
        {
            cycleLength = get_cycle_length(k);
            if(maximum < cycleLength)
                maximum = cycleLength;
        }

        cout << i << " " << j << " " << maximum << endl;
    }

    return 0;
}

int get_cycle_length(int num)
{
    int cycleLength = 1;
    while(num != 1)
    {
        num = (num % 2 == 0 ? num / 2: (num*3) + 1);
        cycleLength++;
    }

    return cycleLength;
}

高中生程式解題系統：c032: 00382 - Perfection

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

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

此題用迴圈從判斷1到 N/2 是否為 N 的因數，若是則加總(s)。接著比較加總結果與 N的大小關係來輸出對應的訊息。(那有沒有更好的演算法呢？)

C++程式碼：

#include <iostream>
#include <iomanip>

using namespace std;

/*

15 28 6 56 60000 22 496 0

   15  DEFICIENT
   28  PERFECT
    6  PERFECT
   56  ABUNDANT
60000  ABUNDANT
   22  DEFICIENT
  496  PERFECT

*/

short checkPerfection(int n)
{
    int sum = 0;
    for( int i = 1; i <= n/2; i++ )
        if( n % i == 0 )
            sum += i;

    if( n == sum )
        return 0;       // perfect
    else if( n > sum )
        return -1;      // deficient
    else if( n < sum )
        return 1;       // abundant

}

void prnMsg(short choice)
{
    switch( choice )
    {
        case 0:
            cout << "PERFECT";
            break;
        case 1:
            cout << "ABUNDANT";
            break;
        case -1:
            cout << "DEFICIENT";
            break;
        default:
            break;
    }

    cout << endl;
}

int main()
{
    int input[100];
    int size = 0;

    while( cin >> input[size] )
    {
        if( input[size] == 0 )
            break;

        size++;
    }

    cout << "PERFECTION OUTPUT" << endl;

    for( int i = 0; i < size; i++ )
    {
        cout.width(5);
        cout << input[i] << "  ";
        prnMsg(checkPerfection(input[i]));
    }

    cout << "END OF OUTPUT";

    return 0;
}

Python程式碼：

import sys
    
msg = {0:"PERFECT", 1:"ABUNDANT", -1:"DEFICIENT"}
  
def checkPerfection(n):
    sum = 0
    for i in range(1, (n // 2) + 1, 1):
        if( n % i == 0 ):
            sum += i

    if( n == sum ):
        return 0
    elif( n > sum ):
        return -1
    elif( n < sum ):
        return 1

num = []
n = 1
for s in sys.stdin:
    tn = list(map(int,s.split()))
    for n in tn:
        if n == 0:
            break
        num.append(n)

    if n == 0:
        break
    
print('PERFECTION OUTPUT')

for n in num:
    ret = checkPerfection(n)
    print("%5d  %s" % (n, msg[ret]))

print('END OF OUTPUT')

高中生程式解題系統：c013: 00488 - Triangle Wave

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

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

用2D座標(Cartesian coordinate system)的方式來解題。這樣的解法也可以畫出如下的圖形(可參考：Python 金字塔圖案、Python 巴斯卡三角形)：

程式碼：

#include <iostream>

using namespace std;

void prtTriangle(short a, int f)
{
    short start = -a + 1;
    short end = a - 1;
    for( int times = 0; times < f - 1; times++ )
    {
        for(short n = start; n <= end; n++)
        {
            int out = a - abs(n);
            for(int k = abs(n); k < a; k++)
                cout << out;
            cout << endl;
        }

        cout << endl;
    }

    for(short n = start; n <= end; n++)
    {
        int out = a - abs(n);
        for(int k = abs(n); k < a; k++)
            cout << out;
        cout << endl;
    }
}

int main()
{
    int n, a, f;

    cin >> n;

    while( cin >> a >> f )
    {

        prtTriangle(a, f);
        n--;

        if( n <= 0 )
            break;
    }

    return 0;
}

高中生程式解題系統：集合運算 Set Operations

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

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

直接用 C++ STL algorithm 裡的 set_union、set_intersection、set_difference、includes來寫。

程式碼：

#include <iterator>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int n;
    int count = 0;

    while( cin >> n )
    {
        count = count + 1;

        if( n == 0 ) break;

        vector<char> *dataSet = new vector<char>[n];

        for( int i = 0; i < n; i++ )
        {
            string input;
            cin >> input;

            for( unsigned j = 0; j < input.length(); j++ )
                input[j] = tolower(input[j]);

            for( unsigned j = 0; j < input.length(); j++ )
                dataSet[i].push_back(input[j]);

            sort(dataSet[i].begin(), dataSet[i].end());
        }

        cout << "Test Case " << count << ":\n";

        for( int i = 0; i < n; i++ )
        {
            char name = 'A' + i;

            cout << name << ": {";
            copy(dataSet[i].begin(), dataSet[i].end(), ostream_iterator<char>(cout, ""));
            cout << "}" << endl;
        }

        // Union and intersection
        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = i + 1; j < n; j++ )
            {
                char name = 'A' + j;
                vector<char> setUnion( dataSet[i].size() + dataSet[j].size() );
                vector<char>::iterator iter = set_union( dataSet[i].begin(), dataSet[i].end(),
                           dataSet[j].begin(), dataSet[j].end(), setUnion.begin());

                cout << setName << "+" << name << ": {";
                copy(setUnion.begin(), iter, ostream_iterator<char>(cout, ""));
                cout << "}" << endl;

                vector<char> setIntersection( min(dataSet[i].size(), dataSet[j].size()) );
                iter = set_intersection( dataSet[i].begin(), dataSet[i].end(),
                           dataSet[j].begin(), dataSet[j].end(), setIntersection.begin());

                cout << setName << "*" << name << ": {";
                copy(setIntersection.begin(), iter, ostream_iterator<char>(cout, ""));
                cout << "}" << endl;

            }
        }

        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = 0; j < n; j++ )
            {
                char name = 'A' + j;
                if( i != j )
                {
                    vector<char> difference( max(dataSet[i].size(), dataSet[j].size()) );
                    vector<char>::iterator iter = set_difference( dataSet[i].begin(), dataSet[i].end(),
                                    dataSet[j].begin(), dataSet[j].end(), difference.begin());

                    cout << setName << "-" << name << ": {";
                    copy(difference.begin(), iter, ostream_iterator<char>(cout, ""));
                    cout << "}" << endl;
                }
            }
        }

        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = 0; j < n; j++ )
            {
                char name = 'A' + j;
                if( i != j )
                {
                    if(includes( dataSet[i].begin(), dataSet[i].end(),
                                 dataSet[j].begin(), dataSet[j].end()) == true)
                    {
                        cout << setName << " contains " << name << endl;
                    }
                    else
                    {
                        cout << setName << " does not contain " << name << endl;
                    }
                }
            }
        }

        delete [] dataSet;
    }
}