Измените строку 'parameter' внутри метода C++

Question

Это мой первый вопрос в SO, но я не могу найти подходящее решение для этого, а не онлайн и моего мозга. У меня есть большая строка номера (более 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 (string CurrentNumber, int look1), строка не будет изменена, но в этом случае это не поможет с 2, потому что после нахождения двух мне нужно искать 1, 5 и 9's после 2 в исходной строке.
Каков правильный подход к этим проблемам? Я имею в виду, должен ли я придерживаться изменения строки или мне нужно вернуть значение для позиции 2 (например) и работать оттуда? Если полезно изменить строку, как это сделать, чтобы иметь возможность повторно использовать исходную строку?
Я новичок в C++ и вообще кодирую (только что начал на самом деле), поэтому, извините, если это действительно глупый вопрос. Заранее спасибо.


EDIT: Мой призыв выглядеть следующим образом:

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 { 

EDIT 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; 
}