Это алгоритм, который подсчитывает количество сдвигов символов. Как я могу упростить это?
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define SIZE 20
int w[1 << (SIZE + 1)];
упростить для удобства чтения? Используйте осмысленные имена переменных
Добавьте в свой код документацию, объясняющую принцип работы алгоритма.
Добро пожаловать в StackOverflow. Пожалуйста, следуйте инструкциям по размещению сообщений в справочной документации, которые были предложены при создании этой учетной записи. Здесь применяются По теме, как спросить и ... идеальный вопрос. StackOverflow не является ресурсом для проектирования, кодирования, исследований или учебных пособий. Пожалуйста, проверьте Какой сайт? для общих вопросов.





Вы можете упростить функцию, используя алгоритмы, предоставляемые C++.
В приведенном ниже примере кода мы читаем 2 строки, затем поворачиваем одну и смотрим, равна ли она другой. Мы будем повторять операцию, пока не найдем совпадение или пока не обнаружим, что преобразование невозможно. Код прокомментирован и должен быть понятен. Если нет, то, пожалуйста, спросите.
#include <iostream>
#include <string>
#include <algorithm>
int main()
{
std::string string1{}; std::string string2{};
std::cout << "Enter 2 strings with same number of digits:\n";
std::cin >> string1 >> string2; // Read strings
// Strings must have same size
if (string1.size() == string2.size()) {
// Countes the number of rotations to the right
size_t rotateCounter{0};
do {
// If rotated string is equal to original, then we found something
if (string1 == string2) break;
// Rotate right
std::rotate(string1.rbegin(),string1.rbegin()+1,string1.rend());
// We have done one more rotation
++rotateCounter;
} while(rotateCounter < string1.size());
// CHeck, if we could find a solution
if ((rotateCounter == string1.size()) && (string1 != string2)) {
std::cout << "Total different strings. No rotation transformation possible\n";
} else {
std::cout << "Number of right shifts needed: " << rotateCounter << '\n';
}
} else {
std::cerr << "Size of strings not equal\n";
}
return 0;
}
Обновлено:
Я создал вторую версию с массивами. Я не могу представить себе причину, по которой кто-то хочет использовать массивы. Возможно, в образовательных целях. Но и здесь я бы нашел это контрпродуктивным. В любом случае. Пожалуйста, смотрите ниже.
Обратите внимание, что std::rotate работает и с простыми массивами, как и все алгоритмы.
Это не было скомпилировано и проверено мной!
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
int main()
{
std::cout << "Enter number of letters for a string: ";
size_t numberOfLetters{}; std::cin >> numberOfLetters;
if (numberOfLetters < 1000000)
{
// Create Array of char
char* charArray1 = new char[numberOfLetters];
char* charArray2 = new char[numberOfLetters];
// Read the strings
std::cout << "Enter s strings with excactly " << numberOfLetters << " digits:\n";
std::string s1{}, s2{}; std::cin >> s1 >> s2;
// Padding with spaces
s1.insert(0, numberOfLetters, ' ');s2.insert(0, numberOfLetters, ' ');
// Copy the char Array
s1.copy(charArray1, numberOfLetters);
s2.copy(charArray2, numberOfLetters);
// Countes the number of rotations to the right
size_t rotateCounter{0};
do {
// If rotated string is equal to original, then we found something
if (0 == std::memcmp(charArray1, charArray2, numberOfLetters)) break;
// Rotate right
std::rotate(charArray1,charArray1+numberOfLetters-1,charArray1+numberOfLetters);
// We have done one more rotation
++rotateCounter;
} while(rotateCounter < numberOfLetters);
// CHeck, if we could find a solution
if (std::memcmp(charArray1, charArray2, numberOfLetters)) {
std::cout << "Total different strings. No rotation transformation possible\n";
} else {
std::cout << "Number of right shifts needed: " << rotateCounter << '\n';
}
delete [] charArray1;
delete [] charArray2;
} else {
std::cerr << "To many letters\n";
}
return 0;
}
И последнее но не менее важное. Версия с простыми статическими массивами и ручным алгоритмом поворота.
Этого должно быть достаточно. Возможно, в следующий раз очень четкие требования будут полезны. Тогда мы сможем выбрать правильное решение.
#include <iostream>
#include <algorithm>
#include <iterator>
constexpr size_t MaxDigits = 1000000;
char LetterArray1[MaxDigits] {};
char LetterArray2[MaxDigits] {};
// Rotate array one char to the right
inline void rotateRight(char(&arrayToRotate)[MaxDigits], size_t numberOfLetters)
{
--numberOfLetters;
char temp = arrayToRotate[numberOfLetters];
for (size_t i = numberOfLetters; i > 0; --i) arrayToRotate[i] = arrayToRotate[i - 1];
arrayToRotate[0] = temp;
}
int main() {
// Get the number of letters that the user wants to use
std::cout << "Enter the number of letters: ";
size_t numberOfLetters{ 0 }; std::cin >> numberOfLetters;
// Check input for underflow or overflow
if (numberOfLetters <= MaxDigits)
{
// Now read to strings from the console
std::cout << "\nEnter 2 strings:\n";
std::string inputString1{}; std::string inputString2{};
// Read 2 strings
std::cin >> inputString1 >> inputString2;
// If user enters too short string, we would run into trouble. Therefore, pad string with spaces
inputString1 += std::string(numberOfLetters, ' ');
inputString2 += std::string(numberOfLetters, ' ');
// Copy strings to array
inputString1.copy(LetterArray1, numberOfLetters);
inputString2.copy(LetterArray2, numberOfLetters);
// So, now we have the 2 strings in our arrays
// We will rotate Array1 and compare the result with Array 2. And we count the number of shifts
bool matchFound{ false };
size_t rotateCounter{ 0 };
while (!matchFound && (rotateCounter < numberOfLetters))
{
if (0 == std::memcmp(LetterArray1, LetterArray2, numberOfLetters)) {
matchFound = true; break;
}
rotateRight(LetterArray1, numberOfLetters);
++rotateCounter;
}
if (matchFound) {
std::cout << "\nNecessary rotations: " << rotateCounter << '\n';
}
else {
std::cout << "\nNo Match Found\n";
}
}
else {
std::cerr << "***** Number of letters entered is to big. Max allowed: " << MaxDigits << '\n';
}
return 0;
}
Хорошо, но я должен использовать массив и переменную n (имеется в виду количество букв). n < 1000 000
FWIW, что максимальное значение, указанное в требованиях, предполагает, что учитель OP ожидает, что нет будет использовать динамическое распределение (но вместо этого статический массив хранения, подобный показанному в вопросе). Не то, чтобы я сделал это. Но эй.
О, вставляю n = 4, inputString1 = AACB and inputString2 = BACA. Результаты: «Не найдено», но должно быть output: 4.
Хм? Я не понимаю. Как мы можем преобразовать AACB в BACA с вращением? Какая будет логика? Пожалуйста, ss: AACB --> BAAC --> CBAA --> ACBA --> AACB
Если у вас есть работающая программа, и вы просто хотите получить советы по ее улучшению, то лучшим местом будет codereview.stackexchange.com.