###前提・実現したいこと
「限られた数字で作れる数の、まんなかの値」を求めたいです。
例えば,
0, 4, 5以外の数を使わずに作ることができる3桁以下の非負の整数は,
0, 4, 5, 40, 44, 45, 50, 54, 55, 400, 404, 405, 440, 444, 445, 450, 454, 455, 500, 504, 505, 540, 544, 545, 550, 554, 555
の27個です。
中央は14番目の数なので、求める値は444になります。
入力は,
3 045
(桁数␣使える数)
という感じです。
出力は,
444
のように,中央の値を出力します。
作れる数が偶数個の場合には、中央に近い数を2つ,小さい順にコンマ区切りで並べます。
なお,桁数の上限の最小値は1。最大値は15です。
不正な入力に対処する必要はありません。
入力 | 出力 |
---|---|
15 12345789 | 444444444444444,444444444444445 |
15 123456789 | 494949494949495 |
15 0123456789 | 499999999999999,500000000000000 |
ソースコードを提示していただければ自分で解読します。
アルゴリズムのヒントでもいいので教えていただけると幸いです。
###発生している問題・エラーメッセージ
処理に時間がかかりすぎて終わりません。
###該当のソースコード
C++
1#include <iostream> 2#include <string> 3#include <vector> 4void median(std::vector<std::string> *str, const std::string &number, const int &digit, const std::string &buffer = "", const bool &flag = false) { 5 if (digit > 0) { 6 if (flag == false && digit > 1 && number.front() > '0') { 7 median(str, number, digit - 1, buffer + '0'); 8 } 9 for (const char c : number) { 10 median(str, number, digit - 1, buffer + c, true); 11 } 12 } 13 else if (digit == 0) { 14 str->push_back(buffer); 15 } 16 return; 17} 18int main(void) { 19 int digit; 20 std::string number; 21 while (std::cin >> digit >> number) { 22 std::vector<std::string> str; 23 //m:組み合わせの数 24 /* 25 long long int m = 0; 26 if (number.front() > '0') { 27 for (int i = 1; i < digit; ++i) { 28 m += pow(number.size(), i); 29 } 30 } 31 m += pow(number.size(), digit); 32 */ 33 median(&str, number, digit); 34 if (str.size() % 2 == 0) { 35 std::vector<std::string>::const_iterator itr = str.cbegin(); 36 std::advance(itr, str.size() / 2 - 1); 37 std::cout << *itr << "," << *(itr + 1) << std::endl; 38 } 39 else { 40 std::cout << str.at(str.size() / 2) << std::endl; 41 } 42 } 43 return EXIT_SUCCESS; 44}
###試したこと
数を文字列として扱い,組み合わせをすべて探索して,そこからまんなかの値を求めました。
ソースコード中にあるように組み合わせの数は求めることができます。
この問題は自分も最初勘違いしていましたが,使用できる数に「0」がなくても空白は使用できるようです。
###補足情報(言語/FW/ツール等のバージョンなど)
言語:C++11
回答6件
あなたの回答
tips
プレビュー