不同方式求sum, gcd

2021-03-11
#code
筆記

前言

這在我高二就有做過了，不過舊的那篇只有放code，沒講實作細節跟原因，在這裡補上。

問題 1

請實作一函數，不得使用乘法、除法、for、while、goto、if-else、switch、case、條件運算子等，算出$\sum^n_{i = 1} i$。

思考

如果不能使用迴圈，就只能往遞迴的方向思考。

1
2
3
4
5
int sum(int n)
{
	if (n == 1) return n;
	return sum(n - 1) + n;
}

標準遞迴

但是遞迴受限於條件判斷來中止，若是有辦法替換條件判斷的語句才可以實現。
這個解答大概要看過才知道。
陣列可以存指標，而C++存在函式指標，利用這個就可以判斷終止條件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定義函式指標為"Func"
typedef int64_t(*Func)(int64_t x);

// 中止函式
int64_t stop(int64_t x)
{
	return 0;
}

// 遞迴函式
int64_t cal(int64_t x)
{
	static Func arr[2] = {stop, cal};
	return x + arr[!!x](x - 1);
}

函式指標解

如果懂一點物件導向，應該知道”多型”的概念。

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
class animal
{
public:
	virtual void eat()
	{
		// to be defined
		return;
	}
	
}

class cat : public animal
{
	void eat() override
	{
		// cat eat
		return;
	}
}
class dog : public animal
{
	void eat() override
	{
		// dog eat
		return;
	}
}

animal house[] = {dog, cat};

標準多型概念

同樣利用陣列也可以達成跟函式指標一樣的效果。

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
// 定義父類
class Base;

Base* arr[2];
 
class Base
{
public:
	// 中止函式
    virtual int64_t sum(int64_t x)
    {
        return 0;
    }
};

// 子類
class Cal : public Base
{
public:
	// 遞迴函式
    int64_t sum(int64_t x) override
    {
        return x + arr[!!x](x - 1);
    }
};

int64_t cal(int64_t x)
{
	arr[0] = new Base;
	arr[1] = new Cal;
	
	return arr[1]->sum(x);
}

多型解

問題 2

請實作一函數，不得使用乘法、除法、for、while、if-else、switch、case、條件運算子，算出$gcd(a, b)$。

思考

同樣利用上面的模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定義函式指標為"Func"
typedef int64_t(*Func)(int64_t a, int64_t b);

// 中止函式
int64_t stop(int64_t a, int64_t b)
{
	return a;
}

// 遞迴函式
int64_t cal(int64_t a, int64_t b)
{
	static Func arr[2] = {stop, cal};
	return arr[!!(a % b)]->gcd(b, a % b);
}

函式指標解

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
// 定義父類
class Base;

Base* arr[2];
 
class Base
{
public:
	// 中止函式
    virtual int64_t gcd(int64_t a, int64_t b)
    {
        return a;
    }
};

// 子類
class Cal : public Base
{
public:
	// 遞迴函式
    virtual int64_t gcd(int64_t a, int64_t b)
    {
        return arr[!!(a % b)]->gcd(b, a % b);
    }
};

int64_t cal(int64_t a, int64_t b)
{
	arr[0] = new A;
	arr[1] = new B;
	
	return arr[1]->gcd(a, b);
}

多型解