[程式設計] UVa 13178 - Is it multiple of 3? 以及工程師心態

題目說明

Is it multiple of 3 是 UVa 上的題目，算是簡單題，但要求在 1 秒內得到結果。

它的翻譯可以看一下 lucky 貓的說明。

乍看之下，這題蠻難的。

簡單來說，就是給一個數字，看看它是不是 3 的倍數。

這題難在於數字會很大，直覺看來，是不可能在 1 秒內得到結果。

我們先來看看這題數字的規則：

題目會給一個數字 n，然後你要湊出對應的數字 x，接著判斷 x 是不是 3 的倍數。

底下是範例

所以你可以推出來，當 n = 99 時，數字是有多大了 (如下圖囉)

n == 99 時，x 的值

暴力法解題

一開始沒有頭緒，所以先用暴力法試試看！

拆出一個數中的所有數字，然後加起來，看是不是3的倍數。

例如
123456，那就拆成 1+2+3+4+5+6 ==> 21

因為 21 可以被 3 整除，所以123456 是 3 的倍數。

程式碼如下。第8到12行是最關鍵的部分，就是將每一個位數拆出來，並加總。

	#include<iostream>
	using namespace std;
	int main()
	{
	int x = 123456;
	int s = 0;
	while (x != 0)
	{
	s = s + x % 10;
	x /= 10;
	}
	if (s % 3 == 0)
	cout << "YES" << endl;
	else
	cout << "NO" << endl;
	}

view raw multiple3.cpp hosted with ❤ by GitHub

但前述的程式碼中的 x 是給定好的。

這當然不符合題目要求。題目要的，是給一個 n 產生一個 x。

所以我們可以稍微修改一下，先讀入一個 n，然後由 1 開始走訪到 n，產生 x。程式碼如下囉。

	#include<iostream>
	using namespace std;
	int main()
	{
	int n;
	cin >> n;
	int s = 0;//做加總
	for (int i = 1; i <= n; i++)
	{
	int x = i;
	while (x != 0)
	{
	s = s + x % 10;
	x /= 10;
	}
	}
	if (s % 3 == 0)
	cout << "YES" << endl;
	else
	cout << "NO" << endl;
	}

view raw multiple3_2.cpp hosted with ❤ by GitHub

上面的程式碼中，第 7 - 16 行的部分，就是算 12345...n 的每一位數的加總。
如果 n 是 6，就會算 123456 的每一位數加總。

這基本上就算達到題目的要求了。

因為題目要求 n 小於等於 10 的 9 次方，所以我們就用這個極限值去測吧，測的結果會發現，要好久的時間。一定會超過一秒！

這表示題目中一定有什麼地方是我們沒有破解的。

尋找規律

那怎麼辦？就想法子找出這些數字有沒有存在什麼規律囉。

寫程式方便就在這兒，我們就直接改程式碼，模擬 n = 1, 2,...,10 時，所有數字的結果。程式碼如下：

	#include<iostream>
	using namespace std;
	int main()
	{
	//int n;
	//cin >> n;
	//底下程式碼模擬 1, 12, 123, 1234, 12345,...,12345678910
	//這些數字是否為 3 的倍數
	for (int n = 1; n <= 10; n++)
	{
	int s = 0;//做加總
	for (int i = 1; i <= n; i++)
	{
	int x = i;
	while (x != 0)
	{
	s = s + x % 10;
	x /= 10;
	}
	}
	if (s % 3 == 0)
	cout <<n<< " YES" << endl;
	else
	cout <<n<< " NO" << endl;
	}
	}

view raw multiple3_3.cpp hosted with ❤ by GitHub

程式碼的輸出如下圖

n = 1,2,3,...,10 時的結果

上圖一看就發出會心一笑啦，我們找到規律了！！

看圖就知道，結果是一個 NO，YES，YES 的循環。

所以給一個 n，我們只要判斷 (n-1) % 3 有沒有等於 0，那就知道對應的 x 值是否為 3 的倍數了。

	#include<iostream>
	using namespace std;
	int main()
	{
	int n;
	cin >> n;
	//n = 1, NO
	//n = 2, YES
	//n = 3, YES
	//n = 4, NO
	//n = 5, YES
	//n = 6, YES
	//依此循環
	if((n-1) % 3 == 0)
	cout << "NO" << endl;
	else
	cout << "YES" << endl;
	}

view raw multiple3_4.cpp hosted with ❤ by GitHub

這一定是對的嗎？

看到這兒，一定有人會問，你確定這樣的判斷一定是對的嗎？

嗯，事實上，我們可以跑 n = 1,2,...,10^9試試看。會發現一直存在這樣的規律，所以致少在題目要求的數值範圍內，這個規律都是存在的。

心得

最後說說心得。

這題是可以透過嚴謹的證明，證出不管數字到多大，都會存在「NO, YES, YES」這樣的規律。我們只要使用

「在整數序列中，每隔 3 個數字，就會出現一個 3 個倍數！」

這樣的想法來證明！

但其實解題不是證明，我們沒有必要那麼「搞剛」。

記得之前在網路上看到一則「工程師 VS 科學家」的文章，裏面有一句話我蠻喜歡的：

「科學家求的是真理。工程師追求的是現實」。

這意思是說，我們工程師只要「覺得是對的」，即使我們不知道「背後的真理」，捲起袖子「硬幹」下去就對了。

事實上好多的發明都是在這樣的心態下產生的。舉例來說，燈泡就是在這樣的想法下產生的。

愛迪生當初可不是全盤理解了「碳化的竹絲」的所有化學特性，才把它用來當燈泡的發光材料的。他當初就是不斷地實驗，直接硬幹下去，才找到了這個材料。致於為什麼碳化的竹絲很適合當發光材料，它的物理，以及化學特性為何？我想愛迪生應該不會很關心才對。

而解題，這種工程師心態蠻受用的！