C++第3版 17章 練習問題解答
-
17.1 , 17.2 , 17.3 ,
17.4 , 17.5 , 17.6 ,
17.7 , 17.8 , 17.9 ,
17.10 , 17.11 , 17.12 ,
17.13 , 17.14 , 17.15 ,
17.16 , 17.17 , 17.18 ,
17.19 , 17.20 , 17.21 ,
17.22 , 17.23 , 17.24 ,
17.25 , 17.26 , 17.27 ,
17.28 , 17.29 , 17.30 ,
17.31 , 17.32 , 17.33 ,
17.34 , 17.35
目次へ戻る
次のプログラムで、nth_element について計測してみた。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
// v[i] = i; を生成
struct FGen {
int count;
FGen(int i = 0){count = i;}
int operator()(){return ++count;}
};
// 比較回数計測用
namespace test {
int count;
bool Less(int i,int j){++count; return i < j;}
}
// 簡易版統計収集クラス
struct CStatCount {
int count;
double max,min,sum,sum2;
CStatCount(){max = -numeric_limits<double>::max();
min = numeric_limits<double>::max(); sum = sum2 = count = 0;}
void operator=(double d){++count; if (max < d) max = d;
if (min > d) min = d; sum += d; sum2 += d*d;}
int Count()const{return count;}
double Max()const{return max;}
double Min()const{return min;}
double Ave()const{return sum / (count ? count : 1);}
double Std()const{double d = Ave(),v;
return count > 0 && (v = sum2 / count - d*d) > 0. ? sqrt(v) : 0.;}
};
int main(int argc,char** argv)
{
int n = argc > 1 ? atoi(argv[1]) : 3, m = n < 3 ? n : 3;
vector<int> v(n),vv(n);
generate(v.begin(),v.end(),FGen());
CStatCount s;
do {
vv = v;
test::count = 0;
nth_element(vv.begin(),vv.begin()+m,vv.end(),test::Less);
s = test::count;
} while (next_permutation(v.begin(),v.end()));
cout << s.Min() << " " << s.Max() << " " << s.Ave() << endl;
}
|
さて、VC++5 での結果(比較回数)を示すと、
| N = 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 |
| 最小 | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
| 最大 | 0 | 2 | 5 | 9 | 14 |
20 | 27 | 35 | 44 | 54 |
| 平均 | 0 | 1.5 | 3.5 | 6 | 9 |
12.5 | 16.5 | 21 | 26 | 31.5 |
となる。g++ でもやってみると、
| N = 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 |
| 最小 | 0 | 1 | 2 | 9 | 11 |
12 | 19 | 20 | 21 | 23 |
| 最大 | 0 | 2 | 5 | 12 | 22 |
33 | 45 | 57 | 71 | 86 |
| 平均 | 0 | 1.5 | 3.5 | 10.6 | 13.9 |
18.8 | 23.9 | 26.8 | 30.0 | 33.0 |
となる。（但し、プログラムは少し直した。）
気づいたことを挙げてみよう。
- VC++ の方が g++ より比較回数が（最小、最大、平均とも）少ない。
- 最小は O(N)、最大は O(N^2)、平均も O(N^2) のようである。（VC++の平均は、n(n+3)/4-1 回である。）
STL の本やヘルプによると、「比較回数は、平均で線形、最悪で二次」となっている。
しかし、結果は平均で二次である。追加実験でいろいろやってみると
他にもふに落ちない点が出てくる。
- VC++ では、nth_element の n 番目を変えても比較回数が変わらない。（g++ では変わる。）
- nth_element でなく sort にしてみると、VC++ の比較回数は変わらない。
g++ の比較回数は VC++ と同じになる。ちなみに sort の比較回数も本では「O(N Log N)」となっている。
どう考えても STL の実装か本の説明がおかしい。
#include <string>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4786)
class phone_number {
int m_n1,m_n2,m_n3;
public:
phone_number(const char* p = "0(0)0")
{sscanf(p,"%d(%d)%d",&m_n1,&m_n2,&m_n3);}
string Str()const{char buf[20];
sprintf(buf,"0%d(%d)%.4d",m_n1,m_n2,m_n3); return buf;}
bool operator<(const phone_number& p)const
{return m_n1 < p.m_n1 || (m_n1 == p.m_n1 &&
m_n2 < p.m_n2 || (m_n2 == p.m_n2 && m_n3 < p.m_n3));}
static bool Less1(const phone_number& p1,const phone_number& p2)
{return p1.m_n1 < p2.m_n1;}
};
ostream& operator<<(ostream& o,const phone_number& p)
{return o << p.Str();}
int main()
{
set<phone_number> s;
s.insert(phone_number("03(777)0001"));
s.insert(phone_number("045(678)0101"));
s.insert(phone_number("03(234)5678"));
s.insert(phone_number("01(111)2222"));
ostream_iterator<phone_number> o(cout,"\n");
copy(s.begin(),s.end(),o);
typedef set<phone_number>::iterator SIter;
pair<SIter,SIter> pr = equal_range(s.begin(),s.end(),
phone_number("03(0)0"),phone_number::Less1);
cout << "\nStart at 03\n";
copy(pr.first,pr.second,o);
}
|
文字列から初期化できるようにした。phone_number(045,678,0101) というように数字を
引数にするコンストラクタを用意しても良かったのだが、紛らわしいので止めにした。
何故なら、プログラム中で 0 で始まる数字は8進数と解釈され、045 は 10進数の 37 に
なるからである。
map や set で使えるように、operator< を用意した。また、ostream に出力できるようにもした。
さらに、市外局番が 0XX のものを equal_range で取出せるように Less1 を用意した。
#include <string>
#include <set>
#include <fstream>
#include <iostream>
using namespace std;
#pragma warning(disable : 4786)
bool getalpha(istream& i,string& s)
{
s = "";
if (i.eof()) return false;
char c;
while (i.get(c)) if (isalpha(c)) break;
if (i.eof()) return false;
while (true) {
s += c;
if (i.peek() == char_traits<char>::eof()) break;
i.get(c);
if (!isalpha(c)) {
i.putback(c);
break;
}
}
return true;
}
static void Show(set<string>& tbl)
{
set<string>::iterator i;
for (i=tbl.begin();i!=tbl.end();++i)
cout << "[" << *i << "]" << endl;
}
int main()
{
ifstream fi("test.txt");
if (!fi.is_open()) return 1;
string s;
set<string> tbl;
while (fi >> s) tbl.insert(s);
Show(tbl);
tbl.clear(); fi.clear(); fi.seekg(0);
while (getalpha(fi,s)) tbl.insert(s);
Show(tbl);
return 0;
}
|
パス。
IsKaibunS は汎用的な IsKaibun を使って実装されている。
IsKaibunC も IsKainbun を使って簡単に実装できる。
#include <cstring>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
#pragma warning(disable : 4786)
bool IsKaibunC(const char* s)
{
const char* t = s+strlen(s)-1;
while (s < t) if (*s++ != *t--) return false;
return true;
}
bool IsKaibunI(unsigned int i)
{
string s;
while (i) {
int j = i%10;
i /= 10;
s += static_cast<char>('0'+j);
}
return IsKaibunC(s.c_str());
}
template <typename T>
bool IsKaibun(T i, T j)
{
if (i == j) return true;
while (i != --j) {
if (*i != *j) return false;
if (++i == j) break;
}
return true;
}
bool IsKaibunS(const char* p)
{
istringstream ss(p);
string s;
vector<string> v;
while (ss >> s) v.push_back(s);
return IsKaibun(v.begin(),v.end());
}
int main()
{
cout << IsKaibunC("abccba") << endl;
cout << IsKaibunI(1234321) << endl;
cout << IsKaibunS("abc de de abc") << endl;
}
|
メンバには、stack を１つしか持っていない。
２つ持てば、push（または pop）の連続でも非効率にならずに、できるであろう。
２つめの stack は、push で使っている。最後の要素として入れるために、
一度、別の stack に逆順で入れ直している。
#include <string>
#include <stack>
#include <iostream>
using namespace std;
#pragma warning(disable : 4786)
template <typename T>
class Queue { // 先入れ先出し
stack<T> m_stack; // 後入れ先出し
static void Move(stack<T>& s,stack<T>& t)
{while (!t.empty()) {s.push(t.top()); t.pop();}}
public:
void push(const T& t)
{stack<T> s; Move(s,m_stack); s.push(t); Move(m_stack,s);}
T pop(){T t = m_stack.top(); m_stack.pop(); return t;}
};
int main()
{
Queue<string> q;
q.push("apple");
q.push("orange");
q.push("pine");
cout << q.pop() << endl;
cout << q.pop() << endl;
cout << q.pop() << endl;
}
|
問題の意味が不明なのでパス。
やったことないのでパス。
#include <cstring>
#include <string>
#include <set>
#include <sstream>
#include <iostream>
using namespace std;
#pragma warning(disable : 4786)
class Date {
int m_year;
int m_month;
int m_day;
string m_str;
public:
Date(string s);
bool operator<(const Date& d)const
{return m_year < d.m_year || (m_year == d.m_year &&
(m_month < d.m_month || (m_month == d.m_month && m_day < d.m_day)));}
string Str()const{return m_str;}
};
Date::Date(string s) : m_month(1),m_day(1),m_str(s)
{
static char* m[] = {"Jan","Feb","Mar","Apr","May",
"Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
m_year = atoi(s.c_str()+3);
if (m_year < 100) m_year += 1900;
// for 17.10
string t = s.substr(0,3);
int i;
for (i=0;i<12;++i) if (t == m[i]) break;
if (i == 12) return; // 例外をスローした方がよいかも
m_month = i+1;
}
int main()
{
stringstream ss("Dec85 Dec50 Jan76");
string s;
multiset<Date> v;
while (ss >> s) v.insert(Date(s));
multiset<Date>::reverse_iterator i;
for (i=v.rbegin();i!=v.rend();++i)
cout << i->Str() << endl;
}
|
前問の解の「for 17.10」と書いてある所に以下を追加する。
if (isdigit(s[0])) {
sscanf(s.c_str(),"%d/%d/%d",&m_month,&m_day,&m_year);
return;
} else if (s[0] == '(') {
if (char* p = strchr(s.c_str(),','))
sscanf(p+1,"%d,%d",&m_day,&m_year);
else return;
s = s.substr(1);
}
|
bitset は意外と便利かもしれない。
#include <limits>
#include <bitset>
#include <iostream>
using namespace std;
int main()
{
int dat[] = {0,1,-1,18,-18,numeric_limits<int>::max()};
int i, n = sizeof(dat) / sizeof(*dat);
for (i=0;i<n;++i)
cout << bitset<sizeof(int)*8>(dat[i]) << endl;
}
|
#include <string>
#include <bitset>
#include <sstream>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
const n = 5; // 生徒数
const m = 12; // 日数
bitset<n> b[m]; // 右から1番
stringstream ss("01010 00111 10010 11111 11111"
" 11111 11011 01110 01110 00011 00011 11111");
string s;
int j, i = 0;
while (ss >> s) b[i++] = bitset<n>(s);
// 縦横変換
bitset<m> rb[n];
for (j=0;j<n;++j) for (i=0;i<m;++i) rb[j][i] = b[i][j];
for (j=0;j<n;++j)
if (rb[j].count() == 12)
cout << "毎日出席 " << j+1 << "番" << endl;
else if (rb[j].count() >= 8)
cout << "8日以上出席 " << j+1 << "番" << endl;
}
|
パス。
#include <iostream>
#include <stack>
using namespace std;
namespace {
void Show(const stack<int>& s0)
{
stack<int> s = s0;
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
}
}
int main()
{
stack<int> s;
s.push(3); s.push(2); s.push(1);
Show(s);
}
|
パス。
パス。
パス。
パス。
#include <list>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
template <typename I1,typename I2,typename O>
void cont_cat(I1 f1,I1 l1,I2 f2,I2 l2,O o)
{
while (f1 != l1) *o++ = *f1++;
while (f2 != l2) *o++ = *f2++;
}
int main()
{
int x[] = {1,2,3,4}, y[] = {5,6,7};
vector<int> v(x,x+4), w(y,y+3);
list<int> l;
cont_cat(v.begin(),v.end(),w.begin(),w.end(),back_inserter(l));
copy(l.begin(),l.end(),ostream_iterator<int>(cout));
cout << endl;
}
|
17.5を参照のこと。
正確な中央値は、(データを全て持たないで)一度走査しただけでは、
わからない。ここでは、CStatHistEx というヒストグラムの統計量を
求めるクラスを使って、近似値で求めている。
以下の解答をコンパイルするには、
sim.h と
sim.cpp
が必要である。
#include <string>
#include <map>
#include <sstream>
#include <iostream>
#include "sim.h"
using namespace std;
#pragma warning(disable : 4786)
int main()
{
stringstream ss("a 3 b -1 b 6 a 8 b 1 a 2 a 5 a 2");
string s;
int i;
map<string,CStatHistEx> m;
while (ss >> s >> i) m[s] = i;
map<string,CStatHistEx>::iterator it;
for (it=m.begin();it!=m.end();++it) {
CStatHistEx& h = it->second;
double d = h.Ave();
cout << it->first << " " << h.Count() * d <<
" " << d << " " << h.Percentile(.5) << endl;
}
}
|
パス。
パス。
パス。
パス。
パス。
パス。
パス。
パス。
パス。
パス。
例えば、文字列をキーにしたとき、最初の数文字しか見ないようにするなどが、考えられる。
キーの一部を無視する時は、無視してもあまり影響がない時であろう。
理由は、無視する方が、値の計算が速くなるからである。
意味が良く分からないが、適当に書いてみる。
size_t res = 0;
while (size_t v = hash(key)) res = ((res<<7)|(res>>25))^v;
|
パス。
int Hash(unsigned int i)
{
return i % 1024;
}
|
当然、i*1024+n は、全て同じハッシュ値になる。
前章へ
目次へ
次章へ