БлогNot. C++: все n-значные числа, сумма цифр которых равна k

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 [2351 просмотр]


теги: c++ числа алгоритм время

показать комментарии (3)