題意
根據四個條件,判斷車牌是否合法:
- 車牌有兩種,第一種是 $x_1x_2$-$x_3x_4x_5x_6$ ,第二種是 $x_1x_2x_3$-$x_4x_5x_6$
- $x_1$ ~ $x_6$ 都必須是大小寫字母或數字
- $x_1$ ~ $x_6$ 至少要包含一個數字,且所有數字的和不能被 $7$ 整除
- $x_1$ ~ $x_6$ 不能包含同一種字元超過兩次
- $x_1$ ~ $x_6$ 不能有連續的兩個 $4$。第一種車牌中,$x_2$ 和 $x_3$ 不算連續;第二種車牌中,$x_3$ 和 $x_4$ 不算連續
把合法的車牌按照 ASCII 大小排序後輸出,先輸出第一種車牌,再輸出第二種車牌。
實作技巧
每個條件判斷盡量寫成 function ,增加程式的易讀性。
如果有需要用到字母的 ASCII 值,可以用單引號。例如
'A' <= ch
, 而不是65 <= ch
。程式碼比較乾淨也不容易出錯。善用
ctype.h
裡的 function。例如判斷 ch 是不是數字,可以用isdigit(ch)
,不用自己寫成'0' <= ch && ch <= '9'
。ctype.h
裡還有isalpha(char)
及isalnum(char)
等 function。比較字串大小時 (根據 ASCII 碼的值),可以用
string.h
裡的strcmp(const char*, const char*)
幫助判斷。
實作注意事項
車牌都是七個字元,但是每個字串後面都會有 '\0' 字元代表結尾,所以陣列大小至少要是 $7 + 1 = 8$。如果拿 RE 可能是因為這個緣故。
關於
strcmp(str1, str2)
: 若str1
和str2
相同,會回傳 $0$;若str1 < str2
,則回傳一個負的值 (只保證是負的,不一定是 -1 !);若str1 > str2
,則回傳一個正的值 (只保證是正的,不一定是 1 !)。有同學判斷的時候寫strcmp(str1, str2) == -1
,這個寫法是錯的,應該改成strcmp(str1, str2) < 0
。 詳細的說明文件在這裡。關於
isdigit(ch)
: 若ch
是不是數字,會回傳 0;否則會回傳 非零的值(只保證不是零,不一定是 1)。其他類似的 function 包括isalnum(ch)
,isalpha(ch)
等等也一樣。 詳細的說明文件在這裡。老師上課有提過課本裡的 bubble-sort 程式碼 index 有錯誤,p99. i = m - 1 應該為 i = m - 2。課本勘誤表連結。
0 可以被 7 整除,所以
00-abcd
不是合法的車牌。
更多測資
提供同學另一筆容易錯的測資
Sample input
7
12-3456
44-ZejR
Gc4-4Oe
wJ--x20
3eM-nMM
K6-z-bB
00-abce
Sample output
Gc4-4Oe
程式碼
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980 #include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#define MAXN 30
#define L 7
char
license[MAXN][L+5];
int
getHyphen(
char
*str){
// get the position of the hyphen (2 or 3, else return -1)
if
(str[2] ==
'-'
)
return
2;
return
str[3] ==
'-'
? 3 : -1;
}
int
multipleSameChar(
char
*str){
// check if an alpha or digit appears more than twice
for
(
int
i = 0; i < L; i++){
int
cnt = 1;
for
(
int
j = i + 1; j < L; j++)
if
(str[i] == str[j]) cnt++;
if
(cnt >= 3)
return
1;
}
return
0;
}
int
validSum(
char
*str){
// check if the sum of all digits cannot be divided by 7
int
sum = 0;
for
(
int
i = 0; i < L; i++)
if
(
isdigit
(str[i])) sum += str[i] -
'0'
;
return
sum % 7 != 0;
// no need to check if has at least one digit, since if there are no digits, sum remains 0 and it is invalid
}
int
isValid(
char
*str){
// check if the string satisties all four constraints
int
sum = 0, haveNum = 0;
int
hyphen = getHyphen(str);
if
(hyphen == -1)
return
0;
// invalid (neither first nor second kind)
if
(!validSum(str))
return
0;
// invalid (constraint 2.)
if
(multipleSameChar(str))
return
0;
// invalid(constraint 3.)
for
(
int
i = 0; i < L; i++){
char
ch = str[i];
if
(i != hyphen && !
isalnum
(ch))
return
0;
// invalid (constraint 1.)
if
(ch ==
'4'
&& str[i+1] ==
'4'
)
return
0;
// invalid (constraint 4.)
}
return
1;
}
int
isSmaller(
char
*str1,
char
* str2){
// compare two strings
int
h1 = getHyphen(str1), h2 = getHyphen(str2);
return
h1 != h2 ? h1 < h2 :
strcmp
(str1, str2) < 0;
// first check the type, if same type, check ASCII code using strcmp()
}
int
sort(
int
*idx,
int
cnt){
// sort the index (selection sort)
int
tmp;
for
(
int
i = 0; i < cnt; i++){
for
(
int
j = i + 1; j < cnt; j++){
if
(isSmaller(license[idx[j]], license[idx[i]]))
tmp = idx[i], idx[i] = idx[j], idx[j] = tmp;
}
}
}
int
main(){
int
N, idx[MAXN], vcnt = 0;
assert
(
scanf
(
"%d"
, &N) == 1);
for
(
int
i = 0; i < N; i++){
assert
(
scanf
(
"%s"
, license[i]) == 1);
if
(isValid(license[i])) idx[vcnt++] = i;
// safe the indices of all valid strings
}
sort(idx, vcnt);
for
(
int
i = 0; i < vcnt; i++)
printf
(
"%s\n"
, license[idx[i]]);
return
0;
}