uva :185 - Roman Numerals（dfs）

本文主要是介绍uva :185 - Roman Numerals（dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：uva :185 - Roman Numerals

题目大意：给出一个字符串的等式，问这个字符串是否是罗马等式吗？有符合的阿拉伯等式吗？前者是就输出correct or incorrect ，后者就得分情况：

ambiguous 能组成阿拉伯等式的字母组合大于等于2， 
valid     能组成阿拉伯等式的字母组合只有1种
impossible 没有符合阿拉伯等式的字母组合。
解题思路：
1、能不能组成罗马等式的规则：每个当前的字母（i）的左边的字母（（i-1）所对应的值如果比i所对应的值小的话，i-1的值就取负值，否则就取正值。最后判断是否等是式左右成立。
2、能不能组成阿拉伯等式的话，就是每个字母都可以用 0 - 9 之间的数字去替代，看是否有是左右两边等式成立的。
注意：
0单独出现，和出现前导0的情况，都是不要的，需要排除。然后相同的字母表示一样的值。这里就将每个字母的情况都枚举出来，然后去掉0出现错误的情况，dfs（）找出符合的组合。

代码：
#include <stdio.h>
#include <string.h>const int N = 10;char str[N * N], s1[3][N];
int s[N * N];
char vis[N * N], head[N * N];
const char *letter = "IVXLCDM";
int	count, size;void init () {s['I'] = 1;s['X'] = 10;s['C'] = 100;s['M'] = 1000;s['V'] = 5;s['L'] = 50;s['D'] = 500;size = 0;
}int trans (char * a) {int num = 0, i;for (i = 1; i <= strlen (a); i++) {if (s[a[i - 1]] >= s[a[i]])num += s[a[i- 1]];elsenum -= s[a[i - 1]];}return num;
}bool is_roman () {int n1 = trans(s1[0]);int n2 = trans(s1[1]);int n3 = trans(s1[2]);if (n1 + n2 == n3)return true;return false;
}int tran_num (char * a) {int num = 0;for (int i = 0; i < strlen (a); i++)num = num * 10 + s[a[i]];return num;
}void is_numerals (int n, int v) {if (n == size) {int n1 = tran_num (s1[0]);int n2 = tran_num (s1[1]);int n3 = tran_num (s1[2]);if (n1 + n2 == n3) 	count++;return ;}if (v >= 7)return;while(!vis[letter[v]]) v++;if (v < 7) {for (int j = 0; j < 10; j++) {if (j == 0 && head[letter[v]])continue;s[letter[v]] = j;is_numerals (n + 1, v + 1);if (count >= 2)return;}} 
}int main () {int k, j;while (scanf ("%s", str) , str[0] != '#') {init();k = j = 0;memset (vis, 0, sizeof (vis));memset (head, 0, sizeof (head));for (int i = 0; i < strlen (str); i++) {if (str[i] != '+' && str[i] != '=' ) {s1[k][j++] = str[i];if (!vis[str[i]])size++;vis[str[i]] = 1;if (j == 1)head[str[i]] = 1;} else {s1[k][j] = '\0';k++;j = 0;}}s1[2][j] = '\0';printf ("%s ", is_roman() ?"Correct":"Incorrect");count = 0;is_numerals(0, 0);if (!count)printf ("impossible\n");else {if (count == 1)printf ("valid\n");elseprintf ("ambiguous\n");}}return 0;
}

这篇关于uva :185 - Roman Numerals（dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---