C++: все n-значные числа, сумма цифр которых равна k
Ещё одна небольшая алгоритмическая программка на C++ (консоль Visual Studio 2015), показывающая не только, как решить задачу из заголовка, но и как простейшим способом измерить длительность вычислительного процесса средствами стандарта C++ 11.
Соответствующие операторы видны в коде с комментариями //0
, //1
, ..., //4
.
Алгоритм не оптимален по времени, а компилироваться программка будет только в достаточно новых средах, я выполнил в Visual Studfio 2015.
При значении n
, большем пяти-шести и разумном (то есть, не превышающем величины n*9
) значении k
, программа может выполняться уже достаточно долго, так как реализует просто перебор, правда, не совсем тупой, а с применением стандартного алгоритма accumulate
:)
//Только стандарт C++ 11 и выше ! #include <iostream> #include <string> #include <numeric> #include <vector> #include <cmath> #include <chrono> //0. подключить эту библиотеку для работы с таймером using namespace std; vector <string> *v; //используется функцией find_digits vector <string> *find_digits (size_t n, size_t k) { if (n < 1 || k > n*9) return 0; size_t cnt = 0; size_t first = pow(10, (n - 1)); string str; for (size_t i = first; i < first * 10; i++) { str = to_string(i); if ((accumulate(str.begin(), str.end(), 0) - str.length() * '0') == k) { ++cnt; v->push_back(str); } } return v; } int main() { v = new vector <string>(); //вектор для результатов auto start = std::chrono::high_resolution_clock::now(); //1. начать отсчёт find_digits(3, 12); //аргументы: количество цифр, нужная сумма auto finish = std::chrono::high_resolution_clock::now(); //2. завершить отсчёт std::chrono::duration<double> elapsed = finish - start; //3. узнать время for (auto i = v->begin(); i != v->end(); ++i) cout << *i << ' '; //вывести элементы вектора cout << endl << v->size() << " number(s) found in " << elapsed.count() << " s."; //4. вывести время в сек. delete v; cin.get(); return 0; }
07.03.2018, 13:13 [2560 просмотров]