d103 - NOIP 2008 1.ISBN号码
題目描述
題目要求驗證 ISBN 編號的有效性，並在無效時提供正確的 ISBN 編號。ISBN 編號由 9 位數字和 1 位檢查碼組成，檢查碼的計算方式是將前 9 位數字按權重（1 到 9）加權求和，然後對 11 取模。如果餘數為 10，則檢查碼為 'X'；否則，檢查碼為餘數的字元表示。
解題思路
程式碼首先讀取 ISBN 編號字串。然後，它提取前 9 位數字，計算加權和，並計算檢查碼。最後，它將計算出的檢查碼與輸入的檢查碼進行比較。如果它們匹配，則輸出 "Right"。否則，它會將輸入字串的最後一個字元替換為正確的檢查碼，並輸出修改後的 ISBN 編號。
複雜度分析
- 時間複雜度: O(n)，其中 n 是 ISBN 編號的長度。主要時間花在遍歷字串和計算加權和上。
- 空間複雜度: O(1)，因為程式碼只使用固定數量的額外空間。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a;
while(cin >> a){
string b;
int sum=0;
for(int i=0;i<a.length()-1;i++)
if(a[i]>='0'&&a[i]<='9')
b+=a[i];
for(int i=0;i<9;i++){
sum+=(b[i]-48)*(i+1);
}
sum%=11;
if(sum==10){
if(a[a.length()-1]=='X')
cout << "Right\n";
else{
a[a.length()-1]='X';
cout << a << "\n";
}
}
else{
if(a[a.length()-1]-48==sum)
cout << "Right\n";
else{
a[a.length()-1]=sum+48;
cout << a << "\n";
}
}
}
}