2008年(884)
分类: C/C++
2008-08-06 10:03:05
int i,j,count=0; for ( i = 100; i<=899; i ) { for ( j = 100; j <= 999-i; j ) { if ( 匹配成功) { count ; } } }这么一来需要判断的组合数量变成 800 799 ...... 1 =320400(种) 比原先减少了近一半。但数量依旧庞大。
void init(string **pStr) { int i,j; memset(m_linePattern,0,sizeof(m_linePattern)); for ( i = 0 ; i< 3; i ) { char ch[3]; for ( j = 0; j<3; j ) { ch[j] = (*pStr[i])[j]; } if ( ch[0]==ch[1]) m_linePattern[i][0]=1;//比较0,1位置 if ( ch[0]==ch[2]) m_linePattern[i][1]=1;//比较0,2位置 if ( ch[1]==ch[2]) m_linePattern[i][2]=1;//比较1,2位置 } }我又添加了成员函数int IfNumOk(int idx, int num)来比较num是否符合索引为idx的字符串.匹配成功返回1,失败返回0.代码如下:
int IfNumOk(int idx, int num) { char temp[4]; int com[3]={0}; sprintf(temp,"%d",num);//将num转换成字符串 //计算传入数字的匹配结果 if (temp[0] == temp[1] ) com[0]=1; if (temp[0] == temp[2] ) com[1]=1; if (temp[2] == temp[1] ) com[2]=1; //与索引为idx的字符串匹配结果比较 for ( int i=0; i< 3; i ) if ( com[i] != m_linePattern[idx][i]) return 0; return 1; }这样同时通过了IfNumOk筛选的数字才正式进入最后的比较.我添加了函数int IfMatch(int *maybe)来做判断,符合要求时返回1,不符合返回0.至此函数countPossible的代码已可全部确定下来了,代码如下:
int countPossible(string num1, string num2, string result) { string *pStr[]={&num1,&num2,&result}; init(pStr); int i,j,count=0; for ( i = 100; i<=899; i ) { if ( ! IfNumOk(0, i)) continue; for ( j = 100; j <= 999-i; j ) { if ( ! IfNumOk(1, j)) continue; int maybe[]={i,j,i j}; if ( ! IfNumOk(2, maybe[2])) continue; if ( IfMatch (maybe)) { count ; } } } return count; }通过上述方法筛选出的3个候选数时,当字符串中相同字母越多,则符合的数越少.例如当三个字母都相等时,通过筛选的num1,num2的数各只有8个,显然计算速度大大加快.即使最糟糕的情况下num1,num2和result中三个字母各不相同,则通过筛选的组合有166176种,还是远少于优化前的320400(种)了.
typedef struct{ int dim1; int dim2; }POS;其中dim1表示一个字母(数字)的第1维下标值。同理,dim2表示一个字母(数字)的第2维下标值。一个字母可能在多个位置出现,所以我添加了个成员变量来保存每个字母在矩阵中出现的位置:
typedef vector其中m_letterPos[0]保存字母A出现的位置,m_letterPos[1]保存字母B出现的位置,以此类推m_letterPos[25]保存字母Z出现的位置。在字母矩阵中显然许多字母的位置向量为空,空向量对接下去的筛选判断根本没有用处,所以我又添加了个成员变量,来保存不为空的字母位置向量的指针POSVEC; POSVEC m_letterPos[26]; //保存每个字母的出现位置向量的数组
typedef vector显然上述2个成员变量同样需要在循环筛选前初始化,代码同样添加到成员函数init中。添加后init代码如下:POSPTRVEC; POSPTRVEC m_posptrVec; //保存出现的字母向量的指针
void init(string **pStr) { int i,j; memset(m_linePattern,0,sizeof(m_linePattern)); for ( i = 0 ; i< 3; i ) { char ch[3]; for ( j = 0; j<3; j ) { ch[j] = (*pStr[i])[j]; POS ps={i,j}; m_letterPos[ch[j]-''A''].push_back(ps);//将坐标保存到相应向量中 } //计算各个字母的匹配矩阵 if ( ch[0]==ch[1]) m_linePattern[i][0]=1; if ( ch[0]==ch[2]) m_linePattern[i][1]=1; if ( ch[1]==ch[2]) m_linePattern[i][2]=1; } for ( i = 0; i<26; i ) { if (m_letterPos[i].size()>0) m_posptrVec.push_back(&m_letterPos[i]);//将所有出现的字母向量指针保存起来 } }具体判断候选的3个数字是否匹配时,先将这3个数字转换到3个字符串数组中去,这个转换可以使用sprintf函数。然后遍历m_posptrVec中非空的位置向量,判断每个保存在相同字母的位置向量中的位置,在相应的候选数字矩阵的相应位置的数是否相等,若相等则设置该数字以被使用,具体的IfMatch代码如下:
int IfMatch(int *maybe) { char numChar[3][4]; int bUse[10]={0}; int i,j; for ( i = 0 ; i <3; i ) sprintf(numChar[i],"%d",maybe[i]);//将数字转换成字符串 for ( i = 0; i < m_posptrVec.size(); i )//遍历所有出现的字母 { POSVEC &ps= (*m_posptrVec[i]); int ch = numChar[ps[0].dim1][ps[0].dim2]-''0'';//取得该字母第一个位置处的数字 if ( bUse[ch] ) return 0; //如果数字已被使用就返回0 //逐一比较其他位置出的数字是否都相同 j=1; while( j < ps.size() ) { int ch2 = numChar[ps[j].dim1][ps[j].dim2]-''0''; if (ch != ch2 ) return 0; j ; } bUse[ch] = 1;//将该数字设置为已被使用 } return 1; }
#include三、小结#include #include #include using namespace std; //**************************************************************** //类名:SecretSum //作者:roc(txqc4@sohu.com) //日期:2005-12-26 //用途: 本代码为实现上述竞赛题所作。 //注意事项:如欲转载,敬请保持本段说明。 //**************************************************************** class SecretSum{ typedef struct{ int dim1; int dim2; }POS; typedef vector POSVEC; typedef vector POSPTRVEC; public : int countPossible(string num1, string num2, string result) { string *pStr[]={&num1,&num2,&result}; init(pStr); int i,j,count=0; for ( i = 100; i<=899; i ) { if ( ! IfNumOk(0, i)) continue; for ( j = 100; j <= 999-i; j ) { if ( ! IfNumOk(1, j)) continue; int maybe[]={i,j,i j}; if ( ! IfNumOk(2, maybe[2])) continue; if ( IfMatch (maybe)) { count ; } } } return count; } void init(string **pStr) { int i,j; memset(m_linePattern,0,sizeof(m_linePattern)); for ( i = 0 ; i< 3; i ) { char ch[3]; for ( j = 0; j<3; j ) { ch[j] = (*pStr[i])[j]; POS ps={i,j}; m_letterPos[ch[j]-''A''].push_back(ps);//将坐标保存到相应向量中 } //计算各个字母的匹配矩阵 if ( ch[0]==ch[1]) m_linePattern[i][0]=1; if ( ch[0]==ch[2]) m_linePattern[i][1]=1; if ( ch[1]==ch[2]) m_linePattern[i][2]=1; } for ( i = 0; i<26; i ) { if (m_letterPos[i].size()>0) m_posptrVec.push_back(&m_letterPos[i]);//将所有出现的字母向量指针保存起来 } } int IfMatch(int *maybe) { char numChar[3][4]; int bUse[10]={0}; int i,j; for ( i = 0 ; i <3; i ) sprintf(numChar[i],"%d",maybe[i]);//将数字转换成字符串 for ( i = 0; i < m_posptrVec.size(); i )//遍历所有出现的字母 { POSVEC &ps= (*m_posptrVec[i]); int ch = numChar[ps[0].dim1][ps[0].dim2]-''0'';//取得该字母第一个位置处的数字 if ( bUse[ch] ) return 0; //如果数字已被使用就返回0 //逐一比较其他位置出的数字是否都相同 j=1; while( j < ps.size() ) { int ch2 = numChar[ps[j].dim1][ps[j].dim2]-''0''; if (ch != ch2 ) return 0; j ; } bUse[ch] = 1;//将该数字设置为已被使用 } return 1; } int IfNumOk(int idx, int num) { char temp[4]; int com[3]={0}; sprintf(temp,"%d",num);//将数字转换成字符串 //计算传入数字的匹配结果 if (temp[0] == temp[1] ) com[0]=1; if (temp[0] == temp[2] ) com[1]=1; if (temp[2] == temp[1] ) com[2]=1; //与索引为idx的字符串匹配结果比较 for ( int i=0; i< 3; i ) if ( com[i] != m_linePattern[idx][i]) return 0; return 1; } protected: POSVEC m_letterPos[26]; //保存每个字母的出现位置向量的数组 POSPTRVEC m_posptrVec; //保存出现的字母向量的指针 int m_linePattern[3][3];//保存每个字符串匹配类型的数组 };