a159 - 11743 - Credit Check

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作 Luhn 演算法，驗證輸入的 16 位信用卡號碼是否合法。Luhn 演算法的步驟如下：

1. 從倒數第二個位元開始，將它們放到後面，並將其他未移動的位元加倍。
2. 將列表中所有數字的位元加總 (n)，再將被移到後面的數字加總 (m)，然後將兩個數加起來 (n+m)。
3. 如果這個數字的結尾是 0，則信用卡號碼為合法的，反之則是不合法的。

解題思路

程式碼直接依照 Luhn 演算法的步驟進行計算。首先，將輸入的信用卡號碼分割成四組，每組四個數字。然後，對每個數字進行處理：

1. 對於未移動的位元，將其加倍，如果結果大於 9，則將十位數和個位數相加。
2. 對於移動的位元，直接將其加總。
3. 最後，將兩個加總結果相加，判斷結果是否以 0 結尾。

複雜度分析

• 時間複雜度: O(N)，其中 N 是測試案例的數量。對於每個測試案例，需要處理 16 個數字，因此處理每個案例的時間複雜度是 O(1)。
• 空間複雜度: O(1)，程式碼只使用了常數個變數來儲存中間結果，因此空間複雜度是常數級別。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int a,e,o,t,i;
	string b;
	cin >> a;
	while(a--){
		for(i=0,e=0,o=0;i<4;i++){
			cin >> b;
			t=(b[0]-48)*2;
			(t>9)?o+=t/10+t%10:o+=t;
			t=(b[2]-48)*2;
			(t>9)?o+=t/10+t%10:o+=t;	
			e+=b[1]+b[3];
		}
		e-=384;
		((o+e)%10==0)?cout << "Valid\n":cout << "Invalid\n";
	}
}