问题类型：字符串，有限状态自动机
03pie’s solution for [UVA-11945]
#include <iostream> #include <cstdio> #include <cstring> using namespace std; void output_result(char s[], char t[]) { int len = strlen(s); int i = len - 1, j=0; int state = 0, count; while(i >=0) { count++; t[j++] = s[i]; if(s[i] == '.') { state = 1; count = 0; } else if(s[i] == '$') state = 2; if(state == 1 && count == 3 && s[i-1] != '$') t[j++] = ','; i--; } j--; while(j >= 0) putchar(t[j--]); //输出到数组t里 } int main() { int t2; double val, sum; char s[128], t[128]; cin >> t2; for(int i=1; i<=t2; i++) { sum = 0; for(int j=1; j<=12; j++) { cin >> val; sum += val; } sprintf(s, "%d $%.2f\n", i, sum / 12); //输出到数字s中，并在其前面加入“i $ ”。 output_result(s, t); } return 0; } 帮助理解有限状态自动机。
//例如：有限状态自动机：输入串为3进制数，输出为模5的余数（0，1，2，3，4）
//模5的余数总共只有5个，这就是5个状态。初始状态为0，每个状态也都是最终状态。
//三进制每位数有3种可能，因此每种状态有3种跃迁可能。
//把3进制串理解成从高位到低位一个一个输入，每条输入就是一次跃迁，状态就是到当前输入为止的3进制数模5的余数。
//跃迁的函数如下：
//目标状态 = （当前状态 *进制数(此题为3) + 串的当前位）% 5。
//举例如下：
//三进制数 12112
//当前状态 输入 跃迁
//0 1 (0*3+1) % 5 = 1
//1 2 (1*3+2) % 5 = 0
//0 1 (0*3+1) % 5 = 1
//1 1 (1*3+1) % 5 = 4
//4 2 (4*3+2) % 5 = 4 (最终结果)
#include<iostream>
#include<cstring>
#include<cstdio>using namespace std;const int maxn=100;
int main(){char a[maxn];while(scanf("%s",a)){int status=0;for(int i=0;i<strlen(a);i++){status=((status*3+(a[i]-'0'))%5);cout<<"status="<<status<<endl;}}return 0;
}