Ежедневный бит (е) C ++, Общая проблема интервью C ++: английские числа
Сегодня мы рассмотрим распространенную задачу на собеседовании в C++: английские числа.
Учитывая целое число без знака, преобразуйте его в текстовое представление на английском языке.
Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/vY3463hKd.
Решение
В этой задаче нет никаких хитростей или сложных алгоритмов. Единственная цель этой задачи — проверить усердие.
Таким образом, стоит сначала записать полную спецификацию.
Преобразование является периодическим, с периодом 1000, ненулевые периоды формируют вывод в виде «X Magnitude», например. «42 миллиона». X — это преобразование значения 0–999 в текстовую форму.
Числа 0–99 имеют полурегулярный формат:
- 0..14 неправильные: «Ноль», «Один», «Два», «Три», «Четыре», «Пять», «Шесть», «Семь», «Восемь», «Девять», «Десять» , «Одиннадцать», «Двенадцать», «Тринадцать», «Четырнадцать».
- 15..19 и 20–99 являются обычными, с использованием общих префиксов: «Twen», «Thir», «For», «Fif», «Six», «Seven», «Eight» и «Nine».
- 15..19 префикс основан на второй цифре, за которой следует «teen».
- 20..99, префикс основан на первой цифре, за которой следует «ty». Вторая цифра основана на нерегулярном диапазоне 0..9 (без нуля).
Мы можем преобразовать это непосредственно в код:
constexpr std::string_view prefixes[] = {
"", "", "Twen", "Thir", "For", "Fif", "Six",
"Seven", "Eigh", "Nine"
};
constexpr std::string_view tenths[] = {
"Zero", "One", "Two", "Three", "Four",
"Five", "Six", "Seven", "Eight", "Nine",
"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen"
};
// 0..99
struct Tenths {
unsigned value;
friend std::ostream& operator<<(std::ostream& s, Tenths v) {
// 0..14
if (v.value <= 14)
return s << tenths[v.value];
// 15..19 (e.g. Fif-teen)
if (v.value <= 19)
return s << prefixes[v.value%10] << "teen";
// First digit of 20..99 (e.g. Eigh-ty)
s << prefixes[v.value/10] << "ty";
// Second digit of 20..99 (e.g. For-ty Two)
if (v.value%10 != 0)
s << " " << Tenths{v.value%10};
return s;
}
};
Сотни представлены однозначным числом, основанным на нерегулярном диапазоне от 0 до 9 (полностью опуская ноль).
// 0..999
struct Hundreds {
unsigned value;
friend std::ostream& operator<<(std::ostream& s, Hundreds v) {
// Skip over Zero
if (v.value == 0) return s;
std::string delim = "";
// Number of hundreds, omit if zero
if (v.value >= 100)
s << std::exchange(delim, " ") <<
tenths[v.value / 100] << " Hundred";
// 0..99, only add delimiter if we also
// have hundreds, e.g. One Hundred Forty Two
if (v.value % 100 != 0)
s << delim << Tenths{v.value % 100};
return s;
}
};
Наконец, мы можем обработать число, по три младших десятичных разряда за раз, добавив соответствующий дескриптор величины.
constexpr std::string_view ranks[] = {
"", " Thousand", " Million", " Billion", " Trillions"
};
std::string toEnglish(unsigned number) {
// Zero
if (number == 0)
return std::string(tenths[0]);
std::string result;
unsigned rank = 0;
while (number != 0) {
unsigned rem = number % 1000; // current 0..999
// Skip over zeroes
if (rem != 0) {
std::stringstream s;
// Format the 0..999 and append the rank
s << Hundreds{rem} << ranks[rank];
// If we already have some formatted text
// add it with a delimiter.
if (!result.empty())
s << " " << result;
result = s.str();
}
++rank;
number /= 1000;
}
return result;
}
