APCS 實作題 10603 第1題秘密差參考解法

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

 此題在高中生程式解題系統的題號為：c290: APCS 2017-0304-1秘密差。

筆者將解法依照子題組的給分方式分別解題：

第 1子題組 20 分： X 一定恰好四位數 。
只要用除法與餘數運算子，分別求出個位數字和百位數字的和以及十位數字與千位數字的和即可。

C 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <stdio.h>

int main(void) {
    int n;

    while(scanf("%d", &n))
    {
        int a = n %10 + n / 100 % 10;       // 個位數字與百位數字的和
        int b = n / 1000 + n / 10 % 10;     // 十位數字與千位數字的和

        printf("%d\n", (a > b? (a-b):(b-a)));
    }

    return 0;
}

第 2子題組 30分： X的位數不超過 9。
用除法與餘數運算子，分別求出奇數位數字的和以及偶數位數字的和即可。

Python 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
while True:
    try:
        n = int(input())
        a = 0
        b = 0
        while(n > 0):
            a = a + n % 10          # 奇數位數的和
            b = b + n // 10 % 10    # 偶數位數的和
            n = n // 100

        print(abs(a - b))
    except EOFError:
        break

 第 3子題組 50 分： X的位數不超過 1000 。
用字串來解。例如輸入的數字為 3217478967458012345689 時，而此數字的字串索引如下圖所所示：


Python 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import math

while True:
    try:
        n = input()
        a = 0
        b = 0
        i = 0
        for c in n:
            if i % 2 == 0:
                a = a + int(c)
            else:
                b = b + int(c)
            i = i + 1
        
        print(abs(a - b))
    except EOFError:
        break

C 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>

int main(void) {
  const int MAX = 1001;
  char num[MAX];
  int sLen = 0;
  int a, b, i;

  while(scanf("%s", num) != EOF) {
    sLen = strlen(num);
    a = 0, b = 0;

    for(i = 0; i < sLen; i += 2)
        a += (num[i] - '0');

    for(i = 1; i < sLen; i += 2)
        b += (num[i] - '0');

    printf("%d\n", a > b ? (a-b):(b-a));
  }

  return 0;
}

C++ 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>

using namespace std;

int main(void) {
  string n;
  int sLen = 0;
  int a, b, i;

  while(cin >> n) {
    sLen = n.length();
    a = 0, b = 0;

    for(i = 0; i < sLen; i += 2)
        a += (n[i] - '0');

    for(i = 1; i < sLen; i += 2)
        b += (n[i] - '0');

    cout << (a > b ? (a-b):(b-a)) << endl;
  }

  return 0;
}


滿分的解法會是哪一個呢？

Labels: , , ,

LeetCode OJ: 326. Power of Three 三次方判斷

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

題目連結 https://leetcode.com/problems/power-of-three/。題目需要判斷一個整數是不是 3 的某次方，例如：
1 是 3 的 0 次方；
3 是 3 的 1 次方；
9 是 3 的 2 次方；
27 是 3 的 3 次方；
0 不是 3 的 某次方；
12 不是 3 的 某次方；
24 不是 3 的 某次方；

此題 LeetCode 提供了四種解法：Loop Iteration、Base Conversion、Mathematics、Integer Limitations。

方法一： Loop Iteration
一個整數是 3 的某次方時(3^x)，可以寫成如下表示方式：
n = 3 ^ x
n = 3 * 3 * 3 * 3 ... * 3
也就是將 n 除以 3 做 x 次後，會得到整數 1 。於是可以用迴圈一直除以 3，直到餘數不是零。最後在判斷有沒有得到整數 1。

C++ 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 1)   return false;
        
        while(n % 3 == 0)   n /= 3;
        
        return n == 1;
    }
};

方法二： Base Conversion
十進制時，10 ^ 0 = 1；10 ^ 1 = 10；10 ^ 2 = 100 ... etc。只要是 10 ^ x 次方時，一定會是以 1 開頭，接著連續 0 的形式出現： 1 ... 0 。

那二進制時呢？ 2 ^ 0 = 1； 2 ^ 1 = 10；2 ^ 2 = 100 ... etc。也是 1 ... 0 形式。所以可以將數字 n 轉換成 三進制 的字串，在檢查數字 1 是否只有出現一次。

C++ 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    bool isPowerOfThree(int n) {
        string s = "";
        char c;

        // convert n into base 3 as string
        while(n / 3 > 0)
        {
            c = (n%3) + '0';
            s.append(string(1, c));
            n = n / 3;
        }

        // the last digit
        c = n + '0';
        s.append(string(1, c));
        
        // Check checking if the string contains only one 1.
        int cnt = 0;
        for(int i = s.length() - 1; i >= 0; i--)
        {
            if(s[i] == '2')
            {
                cnt += 2;
                break;
            }
            else if(s[i] == '1')
            {
                cnt++;
                if(cnt > 1)
                {
                    break;
                }
            }
        }

        return cnt == 1;
    }
};


方法三： Mathematics
若 n 為 3 的 x 次方，那麼以 3 為底，對 n 取對數會得到整數的結果。而C++ math 所提供的對數函數沒有以 3 為底。但可以使用換底公式(下圖取自Wikipedia)：
\log_\alpha\!x=\frac{\log_\beta\!x}{\log_\beta\!\alpha}
以十為底來計算。接著使用 floor() 函數來判斷計算結果是不是一個整數。

C++程式碼：
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        double r = (log10(n) / log10(3));
        int fr = floor(r);
        return fr == r;
    }
};

方法四： Integer Limitations
在程式語言中，整數會有最大值的限制，C++ 中可以使用 INT_MAX 來查詢到最大值為 2147483647。那麼找出小於 INT_MAX 的 3 ^ x 次方之數值，這個數值會是 3 ^ 19 = 1162261467。而其他的 3 ^ x 一定會是 3 ^ 19 的因數，所以就可以用求餘數的方式來判斷了。

C++ 程式碼：
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};


而針對這四種方法，LeetCode在解答部分有做了 Java 程式碼執行速度的比較：

Iterations10^610^710^810^9Maxint
Java Approach 1: (Naive)0.040.070.302.475.26
Java Approach 2: (Strings)0.684.0238.90409.16893.89
Java Approach 3: (Logarithms)0.090.504.5945.5397.50
Java Approach 4: (Fast)0.040.060.080.410.78


可以看出第四種方法是最快的。依上面的解法，讀者可以試著解這題：https://leetcode.com/problems/power-of-four/
沒有留言:
Labels: , ,

遊戲程式設計入門


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

前言
本文將介紹遊戲程式設計的工具及能力，標題已說明內文將著重在遊戲設計中的程式設計，所以對程式設計沒有興趣的人，請不要浪費自己寶貴的時間來閱讀本文。若對電腦遊戲設計有興趣但對程式設計不怎麼了解的人，請讀敝人另一篇文章：【電腦遊戲設計入門】。

程式語言的選擇
既然是程式設計，首先要選擇的就是程式語言了，那要怎麼考慮呢？程式語言所用的軟體工具：想用拖曳的方式設計使用介面(User Interface)，還是慢慢寫程式寫出來？工具是否免費？說明文件是否完善？除錯容易嗎？遊戲的執行環境：Windows？Linux？iPhone？Android？

哇！哇！哇！真的要考慮這麼多的問題嗎？？？其實先不用喔。
開始入門時，其實也不用考慮這麼多，先把想做的遊戲給訂出來，再來選擇要用的工具即可；若對做什麼遊戲還沒有想法時，建議可以看看 Making Games with Python & Pygame 這一本免費的電子書，會建議這一本是因為 Python 是目前很紅的程式語言，很多人都說學起來很容易。在學習的過程中，也可以玩玩 Hour of Code來建立自己的程式邏輯，用Hour of Code做一些小遊戲，例如：一小時玩 Flappy、編寫一個你自己的運動遊戲程式等。此外個人覺得使用視覺化的程式設計工具(如Scratch、Construct2、Clickteam Fusion、RPG Maker)來快速打造遊戲的原型，也是個不錯的選擇。

不過筆者比較建議使用Scratch，這是因為Scratch的中文網路資源相對較多(若讀者本身可以接受英文資源的話，還是看看英文的囉)，Scratch官方也有教學可以讓我們自己學習；以及Scratch官網上也有很多Scratcher所分享的專案，可以看看別人的想法，並從中得到不一樣的想法。此外，也需要常常練習做專案，等到累積一定的經驗後，就會發現Scratch有些地方不怎麼容易實現遊戲的功能，例如連線遊戲；而且積木程式一多，除錯起來很不容易。

學好Scratch後，我會建議學C#當第二個程式語言，這是因為C#是跨平台開發工具Unity所用的程式語言之一，而且 C# 在設計視窗相關的程式(學習資源可參考視窗程式設計 - 使用 C#)時，會比較方便。

遊戲引擎(Game engine)
開發一款遊戲時，程式設計者通常不會什麼都自己來，例如2D影像的繪圖就有很多種圖檔格式(bmp, png, jpg, ai...etc)，所以就會有 2D game engine 給程式開發人員來使用，除了 2D game engine 之外，還有 聲音引擎、物理引擎、人工智慧引擎等來幫助開發人員。

最重要的事：
「請先做出一個遊戲，
不論此遊戲的程式開發有多容易！」

沒有留言:
Labels: ,
訂閱： 文章 (Atom)