更改方法C++中的'参数'字符串

Question

这是我的第一个问题，但我找不到一个好的解决方案，不是在线，也不是从我的大脑。 我有一大串数字（超过100位数字），我需要删除它的一些数字来创建一个可被8整除的数字。它非常简单... 但是，让我们说创建这个数字的唯一方法是以'2'结尾的数字。在这种情况下，我需要寻找合适的10位和100位数字，现在我找不到优雅的解决方案。 我有这样的：

bool ExistDigit(string & currentNumber, int look1) { 

int currentDigit; 
int length = currentNumber.length(); 
for (int i = length - 1; i >= 0; i--) { 
    currentDigit = -48;//0 in ASC II 
    currentDigit += currentNumber.back();//sum ASCII's value of char to current Digit 
    if (currentDigit == look1) { 
     return true; 
    } 
    else 
     currentNumber.pop_back; 
} 
return false; 

}

它修改字符串，但因为我检查8和0的第一个，到时候我去查2的，该字符串是空的了。我通过创建字符串的几个副本来解决这个问题，但我想知道是否有更好的方法，它是什么。
我知道，如果我使用ExistDigit（字符串CurrentNumber，int look1），字符串不会被修改，但在这种情况下，它不会帮助2，因为找到两个后我需要寻找1，5和9的后在原始字符串中的2。
这些问题的正确方法是什么？我的意思是，我应该坚持改变字符串，还是应该返回2（例如）位置的值并从那里开始工作？如果改变字符串是好的，我应该怎么做才能重用原始字符串？
我是C++的新手，一般编码（实际刚刚开始），所以，如果这是一个非常愚蠢的问题，很抱歉。提前致谢。


编辑：我的电话是这样的：

int main() { 
string originalNumber;//hold number. Must be string because number can be too long for ints 
cin >> originalNumber; 
string answer = "YES"; 
string strNumber; 
//look for 0's and 8's. they are solutions by their own 
strNumber = originalNumber; 
if (ExistDigit(strNumber, 0)) { 
    answer += "\n0"; 
} 
else { 
    strNumber = originalNumber; 
    if (ExistDigit(strNumber, 8)) { 
     answer += "\n8"; 
    } 
    else { 
     strNumber = originalNumber; 
     //look for 'even'32, 'even'72, 'odd'12, 'odd'52, 'odd'92 
     //these are the possibilities for multiples of 8 ended with 2 
     if (ExistDigit(strNumber, 2)) { 
      if (ExistDigit(strNumber, 1)) { 

      } 
     } 
     else { 

编辑2：如果你有同样的问题，检查功能find_last_of，真的很方便，解决了这个问题。

Answer 1

以下代码保留您的设计，并且至少应提供解决方案（如果存在）。嵌套的if和for可以通过使用递归函数在更优雅的解决方案中进行简化。有了这样的递归函数，你也可以枚举所有的解决方案。

您可以使用迭代器来定义搜索的开始，而不是有多个字符串的副本。在代码中，start变量是这个迭代器。

#include <string> 
#include <iostream> 
#include <sstream> 

using namespace std; 

bool ExistDigit(const string & currentNumber, int& start, int look1) { 
    int currentDigit; 
    int length = currentNumber.length(); 
    for (int i = length - 1 - start; i >= 0; i--) { 
     currentDigit = currentNumber[i] - '0'; 
     if (currentDigit == look1) { 
      start = length - i; 
      return true; 
     } 
    } 
    return false; 
} 

int main() { 
    string originalNumber;//hold number. Must be string because number can be too long for ints 
    cin >> originalNumber; 
    stringstream answer; 
    answer << "YES"; 
    //look for 0's and 8's. they are solutions by their own 
    int start = 0; 
    if (ExistDigit(originalNumber, start, 0)) { 
     answer << "\n0"; 
    } 
    else { 
     start = 0; 
     if (ExistDigit(originalNumber, start, 8)) { 
      answer << "\n8"; 
     } 
     else { 
      start = 0; 
      //look for 'even'32, 'even'72, 'odd'12, 'odd'52, 'odd'92 
      //these are the possibilities for multiples of 8 ended with 2 
      if (ExistDigit(originalNumber, start, 2)) { 
       for (int look2 = 1; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) { // 'odd' 
         for (int look3 = 1; look3 < 10; look3 += 2) { 
          int startAttempt2 = startAttempt1; 
          if (ExistDigit(originalNumber, startAttempt2, look3)) 
           answer << "\n" << look3 << look2 << "2"; 
         }; 
        } 
       }; 
       for (int look2 = 3; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) // 'even' 
         answer << "\n" << look2 << "2"; 
       }; 
      } 
      //look for 'odd'36, 'odd'76, 'even'12, 'even'52, 'even'92 
      //these are the possibilities for multiples of 8 ended with 2 
      else if (ExistDigit(originalNumber, start, 6)) { 
       for (int look2 = 3; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) { // 'odd' 
         for (int look3 = 1; look3 < 10; look3 += 2) { 
          int startAttempt2 = startAttempt1; 
          if (ExistDigit(originalNumber, startAttempt2, look3)) 
           answer << "\n" << look3 << look2 << "6"; 
         }; 
        } 
       }; 
       for (int look2 = 1; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) // 'even' 
         answer << "\n" << look2 << "6"; 
       }; 
      } 
      //look for 'even'24, 'even'64, 'odd'44, 'odd'84, 'odd'04 
      //these are the possibilities for multiples of 8 ended with 2 
      else if (ExistDigit(originalNumber, start, 6)) { 
       for (int look2 = 0; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) { // 'odd' 
         for (int look3 = 1; look3 < 10; look3 += 2) { 
          int startAttempt2 = startAttempt1; 
          if (ExistDigit(originalNumber, startAttempt2, look3)) 
           answer << "\n" << look3 << look2 << "4"; 
         }; 
        } 
       }; 
       for (int look2 = 2; look2 < 10; look2 += 4) { 
        int startAttempt1 = start; 
        if (ExistDigit(originalNumber, startAttempt1, look2)) // 'even' 
         answer << "\n" << look2 << "4"; 
       }; 
      } 
     } 
    } 
    cout << answer.str() << std::endl; 
    return 0; 
} 

下面是一个解决方案，当你正在寻找由十进制文本形式的连续字符组成的子字。

#include <string> 
#include <iostream> 

bool ExistDigit(const std::string& number, int look) { // look1 = 2**look 
    // look for a subword of size look that is divisible by 2**look = 1UL << look 
    for (int i = (int) number.size()-1; i >= 0; --i) { 
     bool hasFound = false; 
     unsigned long val = 0; 
     int shift = look-1; 
     if (i-shift <= 0) 
      shift = i; 
     for (; shift >= 0; --shift) { 
      val *= 10; 
      val += (number[i-shift] - '0'); 
     }; 
     if (val % (1UL << look) == 0) 
      return true; 
    }; 
    return false; 
} 

int main(int argc, char** argv) { 
    std::string val; 
    std::cin >> val; 
    if (ExistsDigit(val, 3) /* since 8 = 2**3 = (1 << 3) */) 
     std::cout << "have found a decimal subword divisible by 8" << std::endl; 
    else 
     std::cout << "have not found any decimal subword divisible by 8" << std::endl; 
    return 0; 
} 

如果你很可能会发现在数字的二进制形式连续位的子字，你需要你的电话号码转换成一个大的整数，然后做类似的搜索。

这是一个（最小测试）解决方案，不需要任何外部库的调用，如gmp就可以将大文本转换为文本。该解决方案利用按位运算（<<,&）。

#include <iostream> 
#include <string> 
#include <vector> 

int 
ExistDigit(const std::string & currentNumber, int look) { // look1 = 2^look 
    std::vector<unsigned> bigNumber; 
    int length = currentNumber.size(); 
    for (int i = 0; i < length; ++i) { 
     unsigned carry = currentNumber[i] - '0'; 
     // bigNumber = bigNumber * 10 + carry; 
     for (int index = 0; index < bigNumber.size(); ++index) { 
      unsigned lowPart = bigNumber[index] & ~(~0U << (sizeof(unsigned)*4)); 
      unsigned highPart = bigNumber[index] >> (sizeof(unsigned)*4); 
      lowPart *= 10; 
      lowPart += carry; 
      carry = lowPart >> (sizeof(unsigned)*4); 
      lowPart &= ~(~0U << (sizeof(unsigned)*4)); 
      highPart *= 10; 
      highPart += carry; 
      carry = highPart >> (sizeof(unsigned)*4); 
      highPart &= ~(~0U << (sizeof(unsigned)*4)); 
      bigNumber[index] = lowPart | (highPart << (sizeof(unsigned)*4)); 
     } 
     if (carry) 
      bigNumber.push_back(carry); 
    }; 
    // here bigNumber should be a biginteger = currentNumber 

    for (int i = 0; i < bigNumber.size()*8*sizeof(unsigned); ++i) { 
     // looks for look consective bits set to '0' 
     bool hasFound = true; 
     for (int shift = 0; hasFound && shift < look; ++shift) 
      if (bigNumber[(i+shift)/(8*sizeof(unsigned))] 
        & (1U << ((i+shift) % (8*sizeof(unsigned)))) != 0) 
       hasFound = false; 

     if (hasFound) { // ok, bigNumber has look consecutive bits set to 0 
      // test if we are at the end of the bigNumber 
      int index = (i+look)/(8*sizeof(unsigned)); 
      for (int j = ((i+look+8*sizeof(unsigned)-1) % (8*sizeof(unsigned)))+1; 
        j < (8*sizeof(unsigned)); j++) 
       if ((bigNumber[index] & (1U << j)) != 0) 
        return i; // the result is (currentNumber/(2^i)); 
      while (++index < bigNumber.size()) 
       if (bigNumber[index] != 0) 
        return i; // the result is (currentNumber/(2^i)); 
      return -1; 
     }; 
    }; 
    return -1; 
} 

int main(int argc, char** argv) { 
    std::string val; 
    std::cin >> val; 
    std::cout << val << " is divided by 8 after " << ExistDigit(val, 3) << " bits." << std::endl; 
    return 0; 
}