三支小程式

張貼者： surveyorK 於 上午8:53 2010年11月21日 星期日 標籤：

幫朋友寫的作業，題目不刁鑽，強調趣味性，但若要找出複雜度低的演算法，其實很具挑戰，我那時候接近期中考，時間不多，就每個都厚顏地暴力解了。聽說後來讓助教測試程式的時候，其中一題的進階測試數據跑了十分鐘還沒跑出結果，囧在當下，哈哈。

以下便列這幾個程式題目和我的跛腳實作。

III. 網路配線

電腦網路使得一組電腦可以經由網路 (如Ethernet網路) 而獲得聯繫，在此我們考慮「線性」網路配線問題，即除了兩端點電腦之外，其餘電腦均僅與其他兩電腦連結，典型之電腦網路範例如下：

clip_image002

其中，黑色頂點代表電腦在xy平面的座標位置 (本題以英呎feet為單位)，連結的邊則以兩端點之距離表示，在此，距離是根據其幾何距離Euclidean Distance計算。

為了節省網路配線的開銷，必須使得總配線長度最小，如下圖為其最佳解：

clip_image004

其中，兩端點不限，網路配線的總長度為 ：4 + 5 + 5.83 + 11.18 = 26.01 ft。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304

/*

輸入說明:
每組輸入為網路上的電腦總數n (原則上不超過8)，緊接每行為其座標值，
其編號自動依數字順序1, 2, …等。輸入電腦總數為0時結束。

輸出說明:
最小配線長度之電腦順序及其最佳解 (配線長度)。

輸入範例:
5
8 11
8 16
12 16
13 8
24 10
0

輸出範例:
32145
26.01

*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>

#define EQ ==

#define COUNT_OF_CORRDINATE 10
#define COUNT_OF_DIMENSION 2
#define MAX_COUNT_OF_PERMUTATION 10000 // 最多排列數

using namespace std;

typedef int Coordinate [COUNT_OF_CORRDINATE][COUNT_OF_DIMENSION];
typedef int Permutation [MAX_COUNT_OF_PERMUTATION];

enum value {
    InitialValue = 444,
    SeparatedValue = 666,
    A,
    B
};


int powTen( int n )
// 取得10^n的值
{
    int temp = 1;
    while ( n -- > 0 )
        temp *= 10;
    return temp;
}

double getDistance( Coordinate data, int a, int b )
// a座標到b座標之間的距離
{
    int differenceX = data[a][0] - data[b][0];
    int differenceY = data[a][1] - data[b][1];
    
    return sqrt( differenceX * differenceX +
                 differenceY * differenceY );
}

int getRandNumber( int n )
// 取得1~n之間的隨機數
{
    return rand() % n + 1;
}

bool noSingleRepetition( Permutation per, int temp, int n )
// 檢查在一個排列中是否有重複的數字
// per: 已有的排列數字
// temp: 即將要加入的排列數字
// n: 總共有幾個數字
{
    bool noRepetition = true;
    
    while ( -- n >= 0 ) {
        if ( per[n] EQ temp )
            noRepetition = false;
    }
    return noRepetition;
}


bool noGroupRepetition( Permutation per, int temp )
// 檢查是否有重複的排列
// per: 已有的排列
// temp: 即將要加入的排列
{
    bool noRepetition = true;

    int i = 0;
    while ( per[i] != InitialValue ) {
        if ( per[i++] EQ temp )
            noRepetition = false;
    }
    return noRepetition;
}

int getRandPermutation( int n )
// 取得隨機排列數字
{
    int permutation = 0;
    bool over = false;
    Permutation per = {0};

    for ( int i = n - 1; i >= 0; i -- ) {
        over = false;
        while ( !over ) {
            int temp = getRandNumber( n );

            if ( noSingleRepetition( per, temp, n ) ) {
                permutation += temp * powTen( i );
                
                per[i] = temp;
                
                over = true;
            }
        }
    }
    return permutation;
}


int getPermutationNumber( int n )
// 取得排列數
// ex. n = 3 -> get 6
//     n = 4 -> get 24
//     n = 5 -> get 120
{
    int temp = n ? 1 : 0; // 若n=0, 則回傳0
    
    while ( n > 0 ) {
        temp *= n;
        n --;
    }
    
    return temp;
}

void setPermutation( Permutation perMethod, int n )
// 總共有幾組排列方式就設置幾組
// perMethod: 存放排列方式(以純數字儲存)
// n: 總共幾個節點
{
    int count = getPermutationNumber( n );

    int permutation = 0;
    bool over = false;

    for ( int i = 0; i < count; i ++ ) {
        over = false;

        while ( !over ) {
            int temp = getRandPermutation( n );

            if ( noGroupRepetition( perMethod, temp ) ) {
                perMethod[i] = temp;
                over = true;
            }
        }
    }
}

double getMinDistance( Coordinate data, Permutation perMethod, int n, int & minRoute )
// 計算此排列方式須行經的距離，求出最小者
// data: 座標資料
// perMethod: 座標排列方式
// n: 有幾個座標
// minRoute: 最短路徑所經過座標的順序
{
    int count = getPermutationNumber( n );
    int temp = 0, single = 0;
    int turn = A, a = InitialValue, b = InitialValue;
    
    double distance = 0, minDistance = 99999;

    for ( int i = 0; i < count; i ++ ) { // 有幾種排列方式

        single = perMethod[i];
        distance = 0;
        
        for ( int j = n - 1; j >= 0; j -- ) { // 有幾個節點
            temp = single / powTen( j );
            single -= temp * powTen( j );
            
            if ( turn EQ A ) {
                a = temp;
                turn = B;
            }
            else {
                b = temp;
                turn = A;
            }
                
            if ( a != InitialValue &&
                 b != InitialValue ) {
                distance += getDistance( data, a - 1, b - 1 );
            }
        }
        if ( distance < minDistance ) {
            minDistance = distance;
            minRoute = perMethod[i];
        }
        a = b = InitialValue;
    }
    return minDistance;
}



void initialData( Coordinate data )
// 初始化資料
{
    for ( int i = 0; i < COUNT_OF_CORRDINATE; i ++ )
        for ( int j = 0; j < COUNT_OF_DIMENSION; j ++ )
            data[i][j] = InitialValue;
}


void showData( Coordinate data, int countOfCoordinate )
// 顯示節點資料(檢查用)
{
    cout << "\n----------------\n";
    
    for ( int i = 0; i < countOfCoordinate; i ++ ) {
        for ( int j = 0; j < COUNT_OF_DIMENSION; j ++ )
            cout << data[i][j] << ".";


        cout << endl;
    }
    cout << "----------------\n";
}

void inputData( Coordinate data, int & countOfCoordinate )
// 輸入座標
{
    int temp = 0;
    int x = 0, y = 0;
    bool over = false;

    while ( !over ) {
        cin >> temp;

        if ( temp EQ 0 ) {
            over = true;
        }
        else {
            for ( int i = 0; i < temp * COUNT_OF_DIMENSION; i ++ ) {
                cin >> data[x][y++];

                if ( y EQ COUNT_OF_DIMENSION ) {
                    x ++;
                    y = 0;
                }
            }
            //data[x++][0] = SeparatedValue;
        }
    }
    countOfCoordinate = x;
}

void run()
// 執行主函式
{
    Coordinate data = {0};
    int countOfCoordinate = 0; // 座標的數目

    Permutation perMethod = {0}; // 有幾種排列方式

    double minDistance = 0; // 最短路徑
    int minRoute = 0; // 最短路由

    initialData( data );

    inputData( data, countOfCoordinate );
    //showData( data, countOfCoordinate );

    setPermutation( perMethod, countOfCoordinate );

    minDistance = getMinDistance( data, perMethod, countOfCoordinate, minRoute );


    cout << "最短路由: " << minRoute << endl;
    cout << "最短路徑: " << minDistance << endl;
}

int main()
{
    srand( time( NULL ) );

    run();
    
    system( "PAUSE" );
    
    return 0;
}

IV. 最大子陣列問題

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

/*

IV. 最大子陣列問題

給定一任意陣列，最大子陣列問題 (Maximum-Subarray Problem)
的目的是找到一連續子陣列其總和最大。舉例說明，給定一陣列 如下：
-2, 1, -3, 4, -1, 2, 1, -5, 4
則最大子陣列為4, -1, 2, 1，其總和為6，其他子陣列的總和都比6小。
試寫一程式解決最大子陣列問題。

輸入說明:
每組輸入為陣列表列，輸入數字均為整數值，0代表結束。

輸出說明:
最大子陣列及其總和。

輸入範例:
-2 1 -3 4 -1 2 1 -5 4
13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
0

輸出範例:
4 -1 2 1
Maximum = 6
18 20 -7 12
Maximum = 43

*/

#include <iostream>
//#include <cstdio>
#include <cstdlib>

#define EQ ==
#define COUNT_OF_DATA 100
#define LENGTH_OF_DATA 1000
#define LENGTH_OF_INPUT_LINE 100

using namespace std;

typedef int Data [COUNT_OF_DATA][LENGTH_OF_DATA];
typedef char Line [LENGTH_OF_INPUT_LINE];


int getCountOfData( Data data, int order )
// 取得資料數目
{
    int i = 0;
    while ( data[order][i] )
        i ++;
        
    return i + 1;
}

void cleanLine( Line line )
// 將line字串清空
{
    for ( int i = 0; i < LENGTH_OF_INPUT_LINE; i ++ )
        line[i] = ' ';
}

void translateData( Data data, int order, Line line )
// 從一行字串轉為一筆資料
{
    Line temp = {0};
    int j = 0, no = 0;
    bool haveNumber = false; // 有無數字
    bool haveNegative = false; // 有無負數
    
    for ( int i = 0; i < LENGTH_OF_INPUT_LINE; i ++ ) {
        if ( line[i] EQ '-' ) { // 出現負數的符號
            haveNegative = true;
            j = 0;
        }
        else if ( line[i] <= '9' && line[i] >= '0' ) {
            temp[j++] = line[i];
            haveNumber = true;
        }
        else {
            if ( haveNumber ) {
                if ( haveNegative )
                    data[order][no++] = - atoi( temp );
                else
                    data[order][no++] = atoi( temp );
                
                cleanLine( temp ); // 清空temp
                haveNumber = haveNegative = false;
            }
        }
    }
}

int inputData( Data data )
// 輸入資料，並回傳共輸入幾組資料
{
    int temp = 0, count = 0;
    bool over = false;
    
    Line tempStr = {0};

    while ( !over ) {

        cin.getline( tempStr, 100 );
        translateData( data, count, tempStr );
        
        if ( tempStr[0] EQ '0' )
            over = true;
            
        count ++;
    }
    over = false;
    
    return count;
}

void printData( Data data )
// 印出資料
{
    for ( int i = 0; data[i][0]; i ++ ) {
        for ( int j = 0; data[i][j]; j ++ )
            cout << data[i][j] << " ";
        cout << endl;
    }
}

int getBiggestSubArrary( Data data, int order, int count, int & no )
// 取count個的情況，回傳最大的連續加成，
// 並把開始數的位置寫入no
{
    int biggest = 0;
    int temp = 0, k = 0;
    int length = getCountOfData( data, order );

    for ( int i = 0; i < ( length - count ); i ++ ) {
        for ( int j = 0, k = i; j < count; j ++ )
            temp += data[order][k++];

        if ( temp > biggest ) {
            biggest = temp;
            no = i;
        }
        temp = 0;
    }
    return biggest;
}

int getBiggestArrary( Data data, int order, int & biggestNo, int & biggestLength )
// 求得在任何情況下的連續數字相加最大值
// biggestNo: 最大連續相加值的起始位置
// biggestLength: 最大連續相加值的長度
{
    int length = getCountOfData( data, order );
    int temp = 0, no = 0;
    int biggestValue = 0; // 最大連續相加值
    
    for ( int i = 1; i <= length; i ++ ) {
        temp = getBiggestSubArrary( data, order, i, no );
        
        if ( temp > biggestValue ) {
            biggestValue = temp;
            biggestNo = no;
            biggestLength = i;
        }
    }
    return biggestValue;
}

void printAnswer( Data data, int order, int value, int no, int length )
// 印出答案
{
    cout << "最大連續數字總和: ";
    for ( int i = 0; i < length; i ++ ) {
        cout << data[order][no++];
        if ( i + 1 < length )
            cout << " + ";
    }
    cout << " = " << value << endl;
}

void run( Data data )
// 執行主函式
{
    int no = 0; // 最大連續相加值的起始位置
    int length = 0; // 最大連續相加值的長度
    int order = inputData( data );
    //printData( data );

    for ( int i = 0; i < order - 1; i ++ ) {
        int value = getBiggestArrary( data, i, no, length );

        printAnswer( data, i, value, no, length );
    }
}

int main()
{
    Data data = {0};

    run( data );
    
    system( "PAUSE" );

    return 0;
}

V. 水桶謎題

假設有兩個水桶及一個水池 (無限供應水)，兩個水桶的容量均為已知，但是都沒有刻度，所以你只能進行下列三種動作：

(1) Fill 將水桶的水裝滿

(2) Empty 將水桶的水倒光

(3) Pour 將其中一個水桶的水倒到另一個水桶

其中，第三種動作僅有兩種可能，即第一個水桶的水須全部倒光、或是第二個水桶已裝滿便算結束。舉例說明，假設水桶A及水桶B都可容納8公升，若此時水桶A有5公升，水桶B有6公升，第一種動作可將水桶A裝滿，第二種動作可將水桶A倒光，第三種動作可將水桶A的水倒入水桶B，但僅可將水桶B裝滿到8公升，使得水桶A剩下3公升。

水桶謎題的目的在使水桶B達到某給定的水量 (公升)，如圖所示為範例，若水桶A的容量為3公升，水桶B的容量為5公升，目標水量為4公升，則可達到目標的順序如下 ：

Fill A

Pour A B

Fill A

Pour A B

Empty B

Pour A B

Fill A

Pour A B

Success

其中，Pour A B表示將水桶A倒水倒水桶B中。

clip_image002[6]

水桶A 水桶B 目標 (水桶B)

注意：

1. 本題中你可以假設給定的謎題一定有解。

2. 水桶A與水桶B在剛開始時皆是空的。

● 本問題曾經出現在電影「終極警探3」中。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246

/*

輸入說明:
每組有三個數字，第一個數字為水桶A的容量，第二個數字為水桶B的容量，
第三個數字為目標容量，單位均為公升。輸入為0 0 0時則結束。

輸出說明:
列出達到目標的順序。

輸入範例:
5 7 3
3 5 4
0 0 0

輸出範例:
Fill A
Pour A B
Fill A
Pour A B
Empty B
Pour A B
Fill A
Pour A B
Success
Fill A
Pour A B
Fill A
Pour A B
Empty B
Pour A B
Success

*/

#include <iostream>
#include <string>
#include <cstdio>

#define MAX_COUNT_OF_DATA 100 // 可一次讀取幾筆題目
#define MAX_OF_TIMER 12 // 遞迴取幾次（若題目解不出來可調高此參數！）
#define EQ ==

using namespace std;

typedef struct data {
    int aMax;  // A最大容量
    int aNow;  // A目前容量
    int bMax;  // B最大容量
    int bNow;  // B目前容量
    int goal;  // B的目標容量
}Data;

enum { A, B };

void start( string trace, Data data, int timer ); // 開始倒水行為

bool gSuccess = false; // 告知其他遞迴已經找到解法，可以結束執行了


string intToString( int & i )
// int轉string（C的方法）
{
    int num = i;
    char temp[100];

    sprintf( temp, "%d", num);

    string str = temp;

    return str;
}

string nameToString( int name )
// 回傳"A"或"B"
{
    return name EQ A ? "A" : "B";
}

void fill( string trace, Data data, int name, int timer )
// 加滿
{
    bool noNeedFill = false; // 解決會多寫的bug
    
    if ( name EQ A ) {
        noNeedFill = data.aNow EQ data.aMax ? true : false;
        data.aNow = data.aMax;
    }
    else {
        noNeedFill = data.bNow EQ data.bMax ? true : false;
        data.bNow = data.bMax;
    }
        
    string temp = nameToString( name ) + "加滿\t" +
                  intToString( data.aNow ) + " " +
                  intToString( data.bNow ) + "\n";

    if ( !noNeedFill )
        trace += temp;
        
    if ( !gSuccess )
        start( trace, data, timer );
}

void empty( string trace, Data data, int name, int timer )
// 倒掉
{
    bool noNeedEmpty = false; // 解決會多寫的bug

    if ( name EQ A ) {
        noNeedEmpty = data.aNow EQ 0 ? true : false;
        data.aNow = 0;
    }
    else {
        noNeedEmpty = data.bNow EQ 0 ? true : false;
        data.bNow = 0;
    }
        
    string temp = nameToString( name ) + "倒光\t" +
                  intToString( data.aNow ) + " " +
                  intToString( data.bNow ) + "\n";

    if ( !noNeedEmpty )
        trace += temp;
    
    if ( !gSuccess )
        start( trace, data, timer );
}

bool pour( string trace, Data data, int from, int to, int timer )
// from加到to(加滿或加到from沒水為止)
{
    if ( from EQ A && data.aNow ) { // A倒給B
        int tolerable = data.bMax - data.bNow; // 目前B還能容納多少公升
        
        if ( tolerable > data.aMax ) { // 可容納的還比A目前水量多
            data.bNow += data.aNow;
            data.aNow = 0;
        }
        else { // A把B倒滿還會有剩
            data.bNow = data.bMax;
            data.aNow -= tolerable;
        }
    }
    else if ( from EQ B && data.bNow ) { // B倒給A
        int tolerable = data.aMax - data.aNow; // 目前A還能容納多少公升

        if ( tolerable > data.bMax ) { // 可容納的還比B目前水量多
            data.aNow += data.bNow;
            data.bNow = 0;
        }
        else { // B把A倒滿還會有剩
            data.aNow = data.aMax;
            data.bNow -= tolerable;
        }
    }
    
    string temp = nameToString( from ) + "分給" +
                  nameToString( to ) + "\t" +
                  intToString( data.aNow ) + " " +
                  intToString( data.bNow ) + "\n";

    trace += temp;
    
    if ( data.bNow EQ data.goal ) {
        cout << trace;
        
        gSuccess = true; // 告知其他遞迴可以結束了 
        return true; // 達到指定水量
    }
    else {
        start( trace, data, timer );
        return false;
    }
}


void start( string trace, Data data, int timer )
// 開始所有可能的倒水行為
{
    if ( timer < MAX_OF_TIMER ) { // 計數器機制，預防無限遞迴
        timer ++;
        
        fill( trace, data, A, timer );
        empty( trace, data, A, timer );

        if ( pour( trace, data, A, B, timer ) )
            cout << "Success !!\n";

        fill( trace, data, B, timer );
        empty( trace, data, B, timer );

        if ( pour( trace, data, B, A, timer ) )
            cout << "Success !!\n";
    }
}

void printData( Data *data )
// 印出所有資料（檢查用）
{
    cout << "\n-----------\n";

    for ( int i = 0; data[i].aMax; i ++ )
        cout << data[i].aMax << " "
             << data[i].bMax << " "
             << data[i].goal << endl;

    cout << "-----------\n";
}

void run( Data *data )
// 執行主函式
{
    int i = 0;
    bool over = false;

    while ( ! over ) {
        cin >> data[i].aMax >> data[i].bMax >> data[i].goal;
        
        data[i].aNow = data[i].bNow = 0;

        if ( !data[i].aMax && !data[i].bMax && !data[i].goal )
            over = true;
        else
            i ++;
    }
    //printData( data );

    for ( int j = 0; j < i; j ++ ) {
        string trace = "";
        int timer = 0;
        
        start( trace, data[j], timer );
        gSuccess = false; // 重新跑一個新的題目
    }
}

int main()
{
    Data *data = new Data [MAX_COUNT_OF_DATA];
    
    run( data );
    
    system( "PAUSE" );

    return 0;
}

One response to “三支小程式” ;

Unknown 提到...
2015年12月15日 凌晨12:11

可以私底下問一下程式嗎

張貼留言