河內塔遞迴&非遞迴解法

模組化(Modular)

這學期開始的Data Structure課程所要寫的程式架構勢必比上學期的Program Language課程大上很多，為了使得龐大的程式能夠被切割、分組成容易維護的小單位，模組化的概念顯的重要許多。C語言中，模組化的時候我們通常搭配header file來實作，下面做簡單講解。

模組化(Modular)

模組化本身是一種把實體抽象化的過程，把原本實際存在的東西轉換成概念、定義、模型、範本、架構的過程。

打個比方好了，我們常常在寫報告的時候會參考一些範本，我們會在範本當中找到一些寫報告的格式、必備內容等等通則。

像是普物實驗報告基本具備格式：Topic、Abstract、Introduction、Experimental Design、Data Analysis & Discussion、Conclusion

每一份普物實驗報告基本上都脫離不了這種格式，他們之間的差異只在於內容

若我們從程式的structure概念來看，他們都擁有屬性(資料)種類都一樣，差異在於屬性(資料)被設定的值(value)。

因此我們可以想成定義一個structure就好比先行建立好一個沒有內容的報告的格式。

我們可以把報告格式想成是一個模組，而定義structure就是在建立模組(Module)

報告格式本身是不具有任何意義的，我們最後所要交出去的是一份真正的報告，而不是報告的格式。

每當我們想要寫報告的時候，就依照格式把資訊填入，一份報告就完成了

同樣的，我們依照structure所規定的資料格式填入值，而產生一個實際真正儲存資料的結構變數，在程式的概念當中我們稱為實體(instance)。

程式語言課曾經提過，function是一種模組化的手段。不知道各位當時是否有完全體會到這句話的意思，這邊簡單說明一下：

試著回想一下，會被獨立成為function的程式碼，大部分都是具有一些固定且單一用途，例如資料排序、交換位置、計算平方、印出資料、搜尋重複等等。

獨立出來的function就點類似特定功能的SOP一般，呼叫function就會去執行特定的功能，而這樣建立function的行為也是一種模組化的表現。也因為是一種模組化表現，因此我們在建立function都會追求「功能單一化、簡單化」的目標，避免建立一個功能複雜的function。

模組化的實作

在C/C++當中，建立模組時通常都是 1個 header file(*.h) + 1個 Source file (*.cpp)。

一般狀況下這兩個檔案會取一樣的名稱，只有副檔名不同。而檔案名稱通常是模組的名字。

I.header file(*.h) 

通常在header file當中我們會寫下類似下列資訊：

1. struct的定義
   ex.
   

   struct Demo {
    int demoInt;
   };
   

2. 函式原型prototype
   ex.
   

   int add_function(int, int);

3. 定義常數
   ex.

   #define NUMBER_OF_STUDENT 5

4. library的載入
   ex.
   

   #include <stdio.h>

II.Source file (*.cpp)

在cpp的部分則是撰寫函式的定義(definition)，在這邊我們只把管方法怎麼做，不管實際資料如何。

ex.

int add_function (int a, int b) {
 return a+b;
}

寫完了.h和.cpp，到這邊為止模組就算完成建立了。

III.模組的套用

在一個新開的專案當中，我們要使用已經建立的模組時，只要遵循兩個步驟：

1. 將.h和.cpp加入到專案當中
2. 在要使用模組的原始碼最開頭利用「#include "header file名稱.h"」將他載入

例如這次的作業

做完了上述兩個動作，你就可以如往常使用function和structure的方式去使用已經被模組化的function和structure。

[C]大數乘法 - N階乘

實作一個計算 N階乘（N ! = N×(N-1) ×…×2×1）的程式。

(1) 請先試著看看，使用一般的 int 整數，最多可以實做到幾階乘？

(2) 實作一個支援大數運算（設定為可印出最高 1000位）的階乘程式，輸出 N!的值（N為一

輸入值，1<N<=200）。

[C]Perfect Number

Perfect Number

定義「A positive integer is a perfect number if it is equal to the sum of all its factors except itself.」。

例如：6 = 1 + 2 + 3；28 = 1 + 2 + 4 + 7 +14。

請以「隨機」的方式將 10000以內的 Perfect Number 印出。

[C]萬年曆實作

請設計一個萬年曆程式。程式需支援以下兩個功能：

(1) 輸入一個數字 Y表示年份、M表示月份，接著印出這個月份的日曆。

(2) 輸入一個數字 Y表示年份，接著印出該年各月的日曆。

(3)可選擇單欄印出 或者 雙欄印出的選項

每一個月的日曆中的星期次序為「日、一、二、三、四、五、六」，此外，請上網 Google 

查詢如何計算任一日屬於一星期中的哪一日。（關鍵字：「Zeller’s formula」或「蔡勒公式」）

[C]Chapter 8 Homework

I.

• 定義一個結構用來放個人通訊錄
• name: 10 char
• phone: 15 char
• email: 25 char
• age: int
• 首先輸入一個int 代表通訊錄要設多大 (至少4人)
• main()用 new 配置通訊錄的大小
• 將該通訊錄傳給一function 做輸入(Call by address)
• 將該通訊錄傳給一function 做輸出(列印通訊錄資料)
• 最後, 不用時要delete 該通訊錄

II.

• 寫一個function, 把副檔名”cpp”換成”c” (字串必須更改，不可以只有輸出更改)
• 輸入字串 “d:\vc\abc.cpp” 
• 輸出 “d:\vc\abc.c”

III.

• Displaying a Sentence with Its Words Reversed 
• strtok(), please google to find how to use strtok()
• e.g. input: I will go to school
•        Output: school to go will I

[C]20130611 class Project

n定義一個結構用來放全班個人成績

uenglish: int

uprogram: int

umath: int

uaverage: float

n首先輸入一個int 代表要放多少人的成績(>=4)

nmain()用 new 配置成績結構空間

n將該結構空間傳給一function 做輸入(scanf) (Call by address)

n將該結構空間傳給一function 做輸出(Call by value/address)

n將該結構空間傳給一function 算全班各科平均(Call by address)

n最後, 不用時要delete 該結構空間

[C]資料排序

當有一群數字資料要排列大小時，到底該怎麼做呢?

再這邊介紹兩種方法，氣泡排序法和插入排序法。

以下都介紹昇幕排序，若要做降幕排序只要更改一下比較條件即可，至於改法就請各為自行思考囉。

一、氣泡排序法

I.規則

1.將相鄰的兩筆資料比較大小，如果第一個資料比第二個資料小就交換(結果會是昇幕排序，由小到大)
2.針對每一個組合都比對，持續運作到結束後，第一個數字會是最小，最後一個數字最大。

II.寫法

以下利用function的方式寫

void bubble_sort(int data[],int size)
{
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(data[j]>data[i])
			{
				int temp=data[j];
				data[j]=data[i];
				data[i]=temp;
			}
		}
	}
}

III.實例

二、插入排序法

I.規則

1.從第二項開始取出
2.和前N-1項比較，如果比該項小，就把該項項後移一個位子
3.直到取出的項大於，當前比較的項，就停止
4.把取出的項插入
5.取下一項，重複2~5步驟
這樣講或許大家有聽沒有懂，這邊借一張wikipedia的圖片，讓大家了解實際運作規則

II.寫法

以下利用function的方式寫

void insertion_sort(int data_array[],int size)
{
	int temp;
	for(int i=1;i<size;i++)
	{
		temp=data_array[i];
		int j=i-1;
		while(j>=0 && data_array[j] > temp) // j>=0的條件是為了避免array的index為負值
		{
			data_array[j+1]=data_array[j];
			j--;
		}
		data_array[j+1]=temp;
	}
}

III.實例 

 temp相當於上面那張圖紅色框框所圈的數字

三、比較 

1. 氣泡排序法和插入排序法在完全散亂的資料上執行的時間是一樣的(因為行為都是做逐項比較)。
2. 插入排序法所需要的交換次數通常少於氣泡排序法。
3. 上面的例子，氣泡排列法交換6次，插入排列法交換5次

[C]Chapter 7 homework

n  (20%)輸入一個字元，輸出其ascii code number，並判斷此字元
u 若為數字，則輸出”number”
u 若為字母，則輸出”alphabet”
u 其他則輸出”others”
u 可重複輸入，直到輸入’!’離開
n  (20%)讀一個字串 scanf(“%s”, str); 計算字串長度並輸出
u 必須用function, array,傳陣列給function
u 用strlen() 去做驗證是否一樣
n  (20%) A 1-D array has these ten elements:
 4.4 3.3 2.2 5.5 1.1 6.6 7.7 10.0 9.9 8.8n  Write a program to sort the array in descending order.
n  Find the max number of  the 10 elements, swap this value with the first element in the array
    Then, find the max number of  the 9 elements (except first element), swap this value with the second element in the array    …

編輯紀錄

6/7
1.補上第一題可輸入無限次，直到輸入”!”表停止。
2.第三題改為float，以支援非整數

[C]猜數字遊戲

猜數字遊戲，電腦亂數產生不重複的四位數字，由使用者猜，如電腦亂數為5137，猜1234，則輸出1A1B，A代表數字與位置都對，B代表數字對，但位置不對。

[C]樂透機

題目：
電腦隨機產生樂透號碼

• 從01~49中任意產生6個號碼, 不能重複
• 必須用function,傳陣列給function
• (1)主程式中，輸入6個號碼(你買的號碼)
• (2)主程式中印出中獎號碼 (10%)
• (3)主程式中印出你猜中的號碼(10%)

[C]Midterm 2

答案供參考，完全憑印象中的題目去寫的@@

考試的時候我是一個程式一個cpp檔

不過剛剛重寫，索性就把他全部整合再一個程式了

我有標在各個function名稱旁寫註解，註明這個function的功用，哪一題不懂，可以直接去看那個function

main()裡面都只是引導語跟input/output而以

[C]function

function ? call by address? call by value ?

[C]猜數字參考解答

[C]reads an integer and return the reversing digits.

這邊提供兩總方法作為解決方案，第一種比較直觀直接印出餘數，第二種則採取真實將數值逆轉。
以下程式碼供大家參考
方法1

#include <stdio.h>
#include <stdlib.h>

int reversing(long int);

int reversing(long int number)
{
	while(number > 0)
	{
		printf("%d",number%10);
		number=number/10;
	}
	return 0;
}
void main (void)
{
	long int number;
	printf("please enter number > ");
	scanf("%d",&number);
	printf("The reversing of %d is ",number);
	reversing(number);
	printf("\n");
	system("pause");
}

方法2

#include <stdio.h>
#include <stdlib.h>

int reversing(long int);

int reversing(long int number)
{
	long int result=0,temp,ten_pow=1;
	int k=0;
	temp=number; //計算次數前先把數字存起來
	//--------計算最大是十的幾次方--------
	while(number > 0)
	{
		number=number/10;
		k++;
	}
	//--------計算剛剛的十的N次方是多少
	number=temp;
	for(int i=1;i<k;i++)
		ten_pow=ten_pow*10;
	//-------逐一取餘數，並乘上十的N次方或N-1次方等等
	while(number > 0)
	{
		result=result+((number%10)*ten_pow);
		number=number/10;
		ten_pow=ten_pow/10;
	}
	//傳回結果
	return result;
}
void main (void)
{
	long int number;
	printf("please enter number > ");
	scanf("%ld",&number);
	printf("The reversing of %ld is %d",number,reversing(number));
	printf("\n");
	system("pause");
}

[C]chapter 5- prj - function-06

1. write function increase_add()
   - with three integer parameter: a, b, c
   - a++; b++; c++;
   - return a+b+c
2. main:
   - enter 3 values: x, y, z
   - call increase_add()
    - print result, x, y, z
Write a function
參數 1:印出1的倍數
參數 2:印出2的倍數
…
參數 9:印出9的倍數
參數 0:印出全表

[C]Book page 217 Problem 3

[C]Midterm Solutions

[C]book page 199 problem 3 solution

[C]book page 203 problem 2&4 solution

[C]book page 203 problem 3 solution

[C語言]while、switch題目

上次的海龍公式教學，幫助到了很多人。所以又抽空寫了這篇，解題小教學，希望也能夠幫助到大家。這篇會詳細說明基本題、加分題及進階的奇數檢驗方法。

[C語言]計算三角形面積

還記得前幾天的程式語言課，除了那討人厭的Debug以外，還有一項令人很頭痛的題目是計算三角形面積的題目嗎?

iso檔案開啟、使用教學

最近大家都要開始學C語言，免不了要先安裝editor。不過似乎對電腦比較不熟的同學，從學校抓回來Microsoft Visual Studio 2010之後不知道怎麼開。

 

仔細看，他的副檔名是*.iso。iso是光碟映像檔的一種格式，簡單說這個檔案室把原版的Visual Studio 2010的光碟整份拷貝出來後所產生的檔案。所以當我們點開他的時候，Windows會跳出內建的燒錄程式。

可是當我們手邊沒有光碟或不想燒錄出來時該怎麼辦呢？這時候很簡單，只要透過工具軟體，在電腦裡面安裝一個"虛擬光碟機"，把iso檔載入之後，電腦就會像讀取一般光碟片一樣讀取這個檔案，此時就能夠順利安裝了。

可以產生虛擬光碟機的軟體很多，不過這邊介紹我習慣使用的軟體－－Virtual Clone Drive
首先先到官方網站下載。

該公司推出了很多跟光碟有關的軟體，往下找，看到Virtual CloneDrive的地方，按下綠色箭頭下載。

下載下來後就安裝他吧，安裝過程中會看到這個畫面

這邊可以保持預設勾選的，也可以把 .ccd 和 .dvd 的勾勾取消，畢竟我們這邊只是要開ISO檔案。

安裝完畢後，會在桌面上看到這個圖示，點兩下啟動他。

確定數量的部分(Number of Drives)是1之後，按下OK，關閉設定視窗。

接著我們對剛剛下載下來的Visual Studio 2010的ISO檔案按右鍵，選擇『Mount (Virtual CloneDrive X:』 (X: 是虛擬光碟機的代號，可能因電腦設定而有所不同)

接著就看到這個畫面啦，電腦已經成功把ISO檔案當作光碟來讀取了喔。點選『執行 autorun.exe』就會看到下面的安裝畫面囉。

如果沒有出現自動執行的畫面，就表示你的電腦關閉了自動執行的功能。這時候們只要到我電腦→剛剛新增的虛擬光碟機中執行autorun.exe就可以囉

這是小弟大概花30分鐘左右寫的簡單教學，希望大家都能夠順利安裝軟體交出程式語言作業喔(๑╹ڡ╹๑)

PS.如果有其他問題也可以在FB上問我(^_^;)

(經驗談)學測個人申請要點整理

1.若想在個人申請就要有學校不想指考，墊底志願學校往年第一階段錄取級分至少低於自己總級分5級(請至少比較兩年以上的往年級分)。

2.選擇校系時，篩選倍率越小的科目，自己的該科級分越高越有優勢。

3.勿局限於普通大學，台科、北科、高應大、雲科、虎科等科技大學都還不錯，也是可以選擇的。科大分數計算方法不同於普通大學，加權倍數越高的科目，自己該科級分越高越有優勢。

4.科技大學志願&普通大學志願是分開填寫，科大志願最多5個，普通大學志願最多6個。

5.注意是否面試，盡量不要選面試日期衝突的學校，若真的要填，請先洽電至該校確認是否能夠排開時間，即使是同校不同校系也最好洽電該校確認。

6.距離填寫志願還有一些時日，這期間除了選擇校系外，審查資料基本必備架構的自傳、讀書計畫先寫好基本版(因為之後要再針對校系作強化)，想附上的報告(小論文、實驗報告等)先排版整理好。

7.自傳、讀書計畫在決定校系後，請針對校系作內容強化，讓內容和校系之間產生關聯。

8.弄熟word功能，這樣可以加快備審資料製作速度，尤其可以節省許多排版時間，這樣你有更多時間去想內容(我那屆的同學很多人在做備審時，因為對word不熟，50%以上的時間都在搞排版。)

9.善用PDF輸出你的備審資料，PDF格是可以避免最後備審資料送到印刷店時因為店家OFFICE版本與自己的不同導致排版混亂以及字體遺失的問題。