检查特定txt文件中的项目是否符合c ++中的约束-名称为USACO号

问题描述 投票:-3回答:2

在解决时,我有些疑惑-给那个数字命名。它是这样的-

在威斯康星州的大型牧场主中,习惯上用序列号给母牛打上烙印,以取悦会计部门。不过,牛郎们并不喜欢这种归档系统的优势,他们希望用一个讨人喜欢的名字称呼牧群成员,而不是说:“来吧,#4734,相处。”

通过编写将牛的品牌序列号转换为与该序列号唯一关联的可能名称的程序来帮助穷人。由于这些天的牛人都拥有蜂窝马鞍形电话,因此请使用标准的Touch-Tone(R)电话小键盘映射来将数字转换为字母(“ Q”和“ Z”除外):

      2: A,B,C     5: J,K,L    8: T,U,V
      3: D,E,F     6: M,N,O    9: W,X,Y
      4: G,H,I     7: P,R,S

牛的可接受名称会在名为“ dict.txt”的文件中提供给您,该文件包含少于5,000个可接受的牛名称的列表(所有字母均大写)。取得一头母牛的品牌编号,并报告给定词典中该编号对应的所有可能单词中的哪个单词,该单词在评分环境中以dict.txt的形式提供(并按升序排序)。

例如,品牌号4734产生以下所有名称:

[GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDIGREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEIGSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFIHRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDIHSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEIIPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFIISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧,有效名称列表中的这81个名称中只有一个是“ GREG”。

编写一个程序,该程序将被赋予一头母牛的品牌编号,并打印可以从该品牌编号生成的所有有效名称;如果没有有效名称,则打印“ NONE”。序列号可以长达十二位数。

这是我试图解决此问题的方法。只需遍历列表中的所有名称,然后检查是否满足给定的约束即可。

int numForChar(char c){
    if     (c=='A'||c=='B'||c=='C') return 2;
    else if(c=='D'||c=='E'||c=='F') return 3;
    else if(c=='G'||c=='H'||c=='I') return 4;
    else if(c=='J'||c=='K'||c=='L') return 5;
    else if(c=='M'||c=='N'||c=='O') return 6;
    else if(c=='P'||c=='R'||c=='S') return 7;
    else if(c=='T'||c=='U'||c=='V') return 8;
    else if(c=='W'||c=='X'||c=='Y') return 9;
    else return 0;

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("namenum.in","r",stdin);
    freopen("namenum.out","w",stdout);

    string S; cin >> S;
    int len = S.length();

    freopen("dict.txt","r",stdin);

    string x;

    while(cin >> x){
        string currName = x;
        if(currName.length() != S.length()) continue;
        string newString = x;
        for(int i=0;i<len;i++){
            //now encode the name as a number according to the rules
            int num = numForChar(currName[i]);
            currName[i] = (char)num;
        }
        if(currName == S){
            cout << newString << "\n";
        }
    }



    return 0;
}

[不幸的是,由于某种原因,我将其提交给法官时,它说没有产生输出,这是我的程序创建了一个空的输出文件。可能出了什么问题?

任何帮助将不胜感激。谢谢。

更新:我尝试了某些程序员Dude的建议,在不同的字母的情况下,在else return 0;函数的末尾添加了一个语句numOfChar。不幸的是,它没有用。

c++ algorithm c++14
2个回答
1
投票

我建议您使用c ++文件处理。覆盖stdin和stdout似乎不合适。

[添加这些,

std::ifstream dict ("dict.txt");
std::ofstream fout ("namenum.out");
std::ifstream fin ("namenum.in");

根据变化,

cin >> S  --to-->  fin >> S;
cin >> x  --to-->  dict >> x
cout << newString  --to--> fout << newString


1
投票

因此,在进一步研究问题并探索了“以该号码命名”的信息之后,我意识到这不是当前的比赛,而只是练习上的挑战。因此,我更新了答案,并给了我成功提交的版本。尽管如此,这是一个破坏者,并且会在您的代码不起作用的原因之后发布。

首先,您在声明数字函数后忘记了}。次要的,您没有实现任何检查输入是否无法产生有效名称的功能。第三,当对currName字符使用numForChar()时,该函数产生一个整数值。那不是问题,问题在于它不是ASCII代码,而是原始数字。然后,将其与输入字符串的字符进行比较。其中,是ASCII的数字值。因此,您的代码永远无法找到匹配项。要解决此问题,您可以仅将48添加到numForChar()函数的返回值,或者将numForChar()返回的值添加为48。

您的方法走对了。但是有一些提示。如果您觉得无聊,可以随时跳到扰流板。您不需要使用numForChar()函数即可从字符中实际获取数字值。您可以只使用一个常量数组。一个常数数组比许多if循环要快。

例如,您知道A,B,C会产生2,而A的ASCII码是65,B的是66,C等于67。对于那3,您可以拥有3个索引的数组,分别为0、1, 2,并且它们全部存储一个2。因此,如果得到B,则减去B的ASCII码65将得出1。这就是从中获取值的索引。

为了将数字转换为字符,您可以使用char的矩阵数组。跳过前两个索引0和1。每个第一级索引包含3个3个字符的数组,这些数组适合其位置。

对于字典比较,如果长度不相等,我们实际上不需要看这个单词是正确的。但是,除此之外,由于对字典中的单词进行了排序,因此如果单词的首字母小于输入的首字母范围,我们可以跳过该单词。另一方面,如果单词的第一个字母现在高于输入的第一个字母的最大值,则继续搜索没有意义。请注意,除非我大量记录,否则用于代码注释的英语几乎总是很糟糕。

您的代码(固定):

#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int numForChar(char c){
    if     (c=='A'||c=='B'||c=='C') return 2;
    else if(c=='D'||c=='E'||c=='F') return 3;
    else if(c=='G'||c=='H'||c=='I') return 4;
    else if(c=='J'||c=='K'||c=='L') return 5;
    else if(c=='M'||c=='N'||c=='O') return 6;
    else if(c=='P'||c=='R'||c=='S') return 7;
    else if(c=='T'||c=='U'||c=='V') return 8;
    else if(c=='W'||c=='X'||c=='Y') return 9;
    else return 0;
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    ifstream fin("namenum.in");
    ifstream dict("dict.txt");
    ofstream fout("namenum.out");

    string S; 
    fin >> S;
    int len = S.length();
    bool match = false;

    string x;

    while(dict >> x){
        string currName = x;
        if(currName.length() != S.length()) continue;
        string newString = x;
        for(int i=0;i<len;i++){
            //now encode the name as a number according to the rules
            int num = numForChar(currName[i]) ^ 48;
            currName[i] = (char)num;
        }
        if(currName == S){
            fout << newString << "\n";
            match = true;
        }
    }

    if ( match == false ){
        fout << "NONE" << endl;
    }

    return 0;
}

剧透代码:

#include <fstream>
#include <string>

using namespace std;

// A = 65
// 65 - 0 = 65
const int wToN[] = {
//  A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S
    2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,
//  T,U,V,W,X,Y,Z
    8,8,8,9,9,9,9     
};
// 2 = {A, B, C} = 2[0] = A, 2[1] = B, 2[2] C
const char nToW[10][3] = {
    {}, // 0 skip
    {}, // 1
    {'A','B','C'},
    {'D','E','F'},
    {'G','H','I'},
    {'J','K','L'},
    {'M','N','O'},
    {'P','R','S'},
    {'T','U','V'},
    {'W','X','Y'}
};

int main(){

    ifstream fin("namenum.in");
    ifstream dict("dict.txt");
    ofstream fout("namenum.out");

    string S; 
    fin >> S;

    // Since this will not change
    // make this a const to make it 
    // run faster.
    const int len = S.length();
    // lastlen is last Index of length
    // We calculate this value here,
    // So we do not have to calculate 
    // it for every loop.
    const int lastLen = len - 1;
    int i = 0;
    unsigned char digits[len];
    unsigned char firstLetter[3];
    // If not match print None
    bool match = false;

    // Convert to number to match faster
    for (  ; i < len; i++ ){
      digits[i] = S[i] ^ 48;
      // Digits that are  2 or less are invalid.
      if ( digits[i] < 2 ) {
        fout << "NONE" << endl;
        return 0;
      }
    }

    // There are 3 set of first letter.
    // We get them by converting digits[0]'s
    // value using the nToW array.
    firstLetter[0] = nToW[digits[0]][0];
    firstLetter[1] = nToW[digits[0]][1];
    firstLetter[2] = nToW[digits[0]][2];

    string dictStr;

    while(dict >> dictStr){
      i = 0;
      // Skip if first character is lower
      // than our range. or If they are not equal in length
      if ( dictStr[0] < firstLetter[0] || dictStr.length() != len ) continue;

      // If it is higher than our range 
      // then there is no point continuing.
      if ( dictStr[0] > firstLetter[2] ) break;
      // If we are in the letter range
      // we always check the second letter
      // not the first, since we skip the first
      i = 1;
      for ( int j = 1; j < len; j++ ){
        // We convert each letter in the word
        // to the corresponding int value
        // by subtracting the word ASCII value 
        // to 65 and use it again our wToN array.
        // if it does not match the digits at 
        // this current position we end the loop.
        if ( wToN[dictStr[i] - 65] != digits[j] ) goto endwhile;

        // if we get here and there isn't an unmatch then it is a match.
        if ( j == lastLen ) {
            match = 1;
            fout << dictStr << endl;
            goto endwhile;
        }
        i++;
      }


      endwhile:;
    }
    // No match print none.

    if ( match == false ){
        fout << "NONE" << endl;
    }

    return 0;
}
© www.soinside.com 2019 - 2024. All rights reserved.