高中生程式解題系統：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;
}