C++ Primer Plus章节编程练习第十六章
1
题目
回文指的是顺读和逆读都一样的字符串。例如，“tot” 和“otto" 都是简短的回文。编写一个程序，让用户输入字符串，并将字符串引用传递给一个bool函数。如果字符串是回文，该函数将返回true,否则返回false。此时，不要担心诸如大小写、空格和标点符号这些复杂的问题。即这个简单的版本将拒绝“Otto."和“Madam, I'm Adam"。请查看附录F中的字符串方法列表，以简化这项任务。
题解
#include<iostream>
#include<string>
using namespace std;
bool isPalindrome(const string& s);
int main(){
cout<<"Please enter a string for check if it is palindrome <quit to quit>: ";
string str;
while(cin>>str&&str!="quit"){
puts(isPalindrome(str)?"Yes!":"NO!");
cout<<"Please enter next string for check <quit to quit>: ";
}
cout<<"Bye!"<<endl;
return 0;
}
bool isPalindrome(const string& s){
int low=0,high=s.size()-1;
while(low<high){
if(s[low]!=s[high])
return false;
low++,high--;
}
return true;
}2
题目
与编程练习1中给出的问题相同，但要考忠诸如大小写、空格和标点符号这样的复杂问题。即“Madam, 'm Adam"将作为回文来测试。例如，测试函数可能会将字符串缩略为“madamimadam", 然后测试倒过来是否一样。不要忘了有用的cctype库，您可能从中找到几个有用的STL函数，尽管不一定非要使用它们。
题解
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
void stringFilter(string &s);
bool isPalindrome(const string& s);
int main(){
cout<<"Please enter a string for check if it is palindrome <quit to quit>: ";
string str;
while(getline(cin,str)&&str!="quit"){
stringFilter(str);
puts(isPalindrome(str)?"Yes!":"NO!");
cout<<"Please enter next string for check <quit to quit>: ";
}
cout<<"Bye!"<<endl;
return 0;
}
void stringFilter(string &s){ //过滤字符串
int index=0;
for(auto ch:s)
if(isalpha(ch))
s[index++]=tolower(ch);
s=s.substr(0,index);
}
bool isPalindrome(const string& s){
int low=0,high=s.size()-1;
while(low<high){
if(s[low]!=s[high])
return false;
low++,high--;
}
return true;
}3
题目
修改程序清单16.3, 使之从文件中读取单词。一种方案是，使用vector
题解
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<cstdlib>
#include<ctime>
#include<cctype>
using namespace std;
int main(){
fstream input("3.txt"); //改为从文件中读取构建wordlist
string word;
vector<string> wordlist;
while(input>>word) wordlist.push_back(word);
int NUM=wordlist.size();
srand(time(0));
char play;
cout<<"Will yor play a word game? <y/n> ";
cin>>play;
play=tolower(play);
while(play=='y'){
string target = wordlist[rand()%NUM];
int length=target.length();
string attempt(length,'-'); //玩家猜测的占位符
string badchars;
int guesses=6;
//输出提示信息，包括随机的单词长度和玩家允许错误的次数
cout<<"Guess my secret word. It has "<<length<<" letters, and you guess\n"
<<"one letter at a time. You get "<<guesses<<" wrong guess.\n";
cout<<"Your word: "<<attempt<<endl;
//进行猜测
while(guesses>0&&attempt!=target){
char letter;
cout<<"Guess a letter: ";
//如何是已经猜测过的则输出提示信息
cin>>letter;
if(badchars.find(letter)!=string::npos||attempt.find(letter)!=string::npos){
cout<<"You already guessed that. Try again.\n";
continue;
}
int loc=target.find(letter);
if(loc==string::npos){ //如果不是目标答案中的字符，则保存为错误字符
cout<<"Oh, bad guess!\n";
guesses--;
badchars+=letter;
}
else{ //如果猜中了，则讲临时占位符中的该字符全部替换为正确的字符
cout<<"Good guess!\n";
attempt[loc]=letter;
loc=target.find(letter,loc+1);
while(loc!=string::npos){
attempt[loc]=letter;
loc=target.find(letter,loc+1);
}
}
cout<<"Your word: "<<attempt<<endl;
if(attempt!=target){ //输出错误字符
if(badchars.length()>0)
cout<<"Bad choices: "<<badchars<<endl;
cout<<guesses<<" bad guesses left\n";
}
}
if(guesses>0) //输出最终的猜测结果
cout<<"That's right!\n";
else
cout<<"Sorry the word is "<<target<<".\n";
cout<<"Will you play anoter? <y/n> ";
cin>>play;
play=tolower(play);
}
input.close();
cout<<"Bye\n";
return 0;
}4
题目
编写一个具有老式风格接口的函数，其原型如下:
int reduce(long ar[],int n);实参应是数组名和数组中的元素个数。该函数对数组进行排序，删除重复的值，返回缩减后数组中的元素数目。请使用STL函数编写该函数(如果决定使用通用的unique()函数，请注意它将返回结果区间的结尾)。使用一个小程序测试该函数。
题解
#include<bits/stdc++.h>
using namespace std;
int reduce(long ar[],int n);
int main(){
long ar[]={19,9,9,4,20,4,5,6,8,3,11,22,11,0,43,0};
int size=16;
int num=reduce(ar,size);
for(int i=0;i<num;i++){
if(i) putchar(' ');
cout<<ar[i];
}
return 0;
}
int reduce(long ar[],int n){
int index=0;
sort(ar,ar+n);
for(int i=1;i<n;i++){
if(ar[i]!=ar[index]){
index++;
ar[index]=ar[i];
}
}
return index+1;
}5
题目
问题与编程练习4相同，但要编写一个模板函数:
template <class T>
int reduce(T ar[], int n);在一个使用long实例和string实例的小程序中测试该函数。
题解
#include<bits/stdc++.h>
using namespace std;
template<class T>
int reduce(T ar[],int n);
int main(){
long ar[]={19,9,9,4,20,4,5,6,8,3,11,22,11,0,43,0};
string words[]={"tom","cat","tim","tom","dog"};
int size=16;
int num=reduce(ar,size);
for(int i=0;i<num;i++){
if(i) putchar(' ');
cout<<ar[i];
}
cout<<endl;
num=reduce(words,5);
for(int i=0;i<num;i++){
if(i) putchar(' ');
cout<<words[i];
}
cout<<endl;
return 0;
}
template<class T>
int reduce(T ar[],int n){
int index=0;
sort(ar,ar+n);
for(int i=1;i<n;i++){
if(ar[i]!=ar[index]){
index++;
ar[index]=ar[i];
}
}
return index+1;
}6
题目
使用STL queue模板类而不是第12章的Queue类，重新编写程序清单12.12所示的示例。
题解
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
using namespace std;
//******************************Customer定义******************************
class Customer{
private:
long arrive;
int processtime;
public:
Customer(){arrive=processtime=0;}
void set(long when); //设置顾客的相关时间
long when()const{return arrive;} //读取到达时间
int ptime()const{return processtime;} //读取服务处理时间
};
//******************************Customer实现******************************
void Customer::set(long when){ //设置到达时间，服务处理时间为随机生成
processtime=rand()%3+1;
arrive=when;
}
//********************************Queue定义*******************************
typedef Customer Item;
const int MIN_PER_HR=60;
bool newcustomer(double x); //判断是否为新的顾客
int main(){
srand(time(0)); //初始化随机数
cout<<"Case Studay: Bank of Heather Automatic Teller\n";
cout<<"Enter maximum size of queue: ";
int qs;
cin>>qs;
queue<Item> line; //队列
cout<<"Enter the number of simulation hours: ";
int hours;
cin>>hours; //模拟时长
long cyclelimmit=MIN_PER_HR*hours;
cout<<"Enter the average number of customers per hour: ";
double perhour; //每小时顾客人数
cin>>perhour;
double min_per_cust; //每个顾客最短的花费
min_per_cust=MIN_PER_HR/perhour;
Item temp; //存储一个用户信息
long turnaways=0; //表示离开的人数
long customers=0; //业务人数数量
long served=0; //被服务的人数
long sum_line=0; //计算队长
long wait_time=0; //当前到下一个人的等待时间
long line_wait=0; //队伍等待时间
//开始模拟
for(int cycle=0;cycle<cyclelimmit;cycle++){
if(newcustomer(min_per_cust)){ //如果有新顾客
if(line.size()>=qs)
turnaways++; //因为队伍过长离开的人数累加
else{
customers++; //业务人数计数
temp.set(cycle); //初始化信息并入队
line.push(temp);
}
}
//如果不需要等待且队伍非空，则出队
if(wait_time<=0&&!line.empty()){
temp=line.front();
line.pop();
wait_time=temp.ptime();//更新到下个人所需的等待时间
line_wait+=cycle-temp.when();
served++; //被服务的人数计数
}
if(wait_time>0) //如果等待时间大于0，则随着cycle自动递减
wait_time--;
sum_line+=line.size();//累加每一时刻的队长
}
//输出结果
if(customers>0){
cout<<"customers accepted: "<<customers<<endl;
cout<<" customers served: "<<served<<endl;
cout<<" turnaways: "<<turnaways<<endl;
cout<<"average queue size: ";
cout.precision(2);
cout.setf(ios_base::fixed,ios_base::floatfield);
cout<<(double)sum_line/cyclelimmit<<endl;
cout<<" average wait time: "
<<(double)line_wait/served<<" minutes\n";
}
else
cout<<"No customers!\n";
cout<<"Done!\n";
return 0;
}
bool newcustomer(double x){
return rand()*x/RAND_MAX<1;
}7
题目
彩票卡是一个常见的游戏。卡片上是带编号的圆点，其中一些圆点被随机选中。编写一个lotto()函数，它接受两个参数。第一个参数是彩票卡上圆点的个数，第二个参数是随机选择的圆点个数。该函数返回一个vector
vector<int> winners;
winners = Lotto(51,6);这样将把一个矢量赋给winner,该矢量包含1~51中随机选定的6个数字。注意，仅仅使用rand()无法完成这项任务，因它会生成重复的值。提示: 让函数创建一个包含所有可能值的矢量，使用random_shuffle(),然后通过打乱后的矢量的第一个值来获取值。编写一个小程序来测试这个函数。
题解
#include<bits/stdc++.h>
using namespace std;
vector<int> Lotto(int t,int c);
int main(){
int total,choice;
cout<<"Enter the total number: ";
cin>>total;
cout<<"Enter the number of choice (no more than "<<total<<"): ";
cin>>choice;
vector<int> winners=Lotto(total,choice);
for(int i=0;i<winners.size();i++){
if(i) putchar(' ');
cout<<winners[i];
}
cout<<"Bye!\n";
return 0;
}
vector<int> Lotto(int t,int c){
srand(time(0));
vector<int> result;
for(int i=0;i<c;i++)
result.push_back(rand()%t+1);
random_shuffle(result.begin(),result.end());
return result;
}8
题目
Mat和Pat希望邀请他们的朋友来参加派对。他们要编写一个程序完成下面的任务。
● 让Mat输入他朋友的姓名列表。姓名存储在一个容器中，然后按排列后的顺序显示出来。
● 让Pat输入她朋友的姓名列表。姓名存储在另一个容器中，然后按排列后的顺序显示出来。
● 创建第三个容器，将两个列表合并，删除重复的部分，并显示这个容器的内容。
题解
#include<set>
#include<string>
#include<iostream>
using namespace std;
void getName(set<string> &s,string str){
cout<<str<<", Please enter the name of your friends <quit with quit>: ";
string name;
while(getline(cin,name)&&name!="quit"){
s.insert(name);
cout<<str<<", Please enter next name of your friends <quit with quit>: ";
}
}
int main(){
set<string> MatFriend,PatFriend;
string name;
getName(MatFriend,"Mat");
getName(PatFriend,"Pat");
set<string> finallist(MatFriend);
finallist.insert(PatFriend.begin(),PatFriend.end());
cout<<"All friend of you as following: "<<endl;
for(auto &name: finallist)
cout<<name<<" ";
return 0;
}9
题目
相对于数组，在链表中添加和删除元素更容易，但排序速度更慢。这就引出了一种可能性:相对于使用链表算法进行排序，将链表复制到数组中，对数组进行排序，再将排序后的结果复制到链表中的速度可能更快；但这也可能占用更多的内存。请使用如下方法检验上述假设。
a. 创建大型vector
b. 创建vector
c. 计算使用STL算法sort()对vi进行排序所需的时间，再计算使用list的方法sort()对li进行排序所需的时间。
d. 将li重置为排序的vi0的内容，并计算执行如下操作所需的时间:将li的内容复制到vi中，对vi进行排序，并将结果复制到li中。
要计算这些操作所需的时间，可使用ctime库中的clock()。正如程序清单5.14演示的，可使用下面的语句来获取开始时间：
clock_t start=clock();再在操作结束后使用下面的语句获取经过了多长时间：
clock_t end=clock();
cout<<(double)(end-start)/CLOCKS_PRE_SEC;这种测试并非绝对可靠，因为结果取决于很多因素，如可用内存量、是否支持多处理以及数组(列表)的长度(随着要排序的元素数增加，数组相对于列表的效率将更明显)。另外，如果编译器提供了默认生成方式和发布生成方式，请使用发布生成方式。鉴于当今计算机的速度非常快，要获得有意义的结果，可能需要使用尽可能大的数组。例如，可尝试包含100000、1000000和10000000个元素。
题解
#include<bits/stdc++.h>
using namespace std;
void getTime(int size){
const int MAXSIZE=size;
vector<int> vi0(MAXSIZE);
srand(time(0));
for(auto& item:vi0) item=rand();
vector<int> vi(vi0);
list<int> li(vi0.begin(),vi0.end());
clock_t start,end;
start=clock();
sort(vi.begin(),vi.end());
end=clock();
cout<<"Algorithm sort() with vi costs time: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
start=clock();
li.sort();
end=clock();
cout<<"sort() of list costs time: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
start=clock();
li.assign(vi0.begin(),vi0.end());
int index=0;
for(auto item:li) //把li复制到vi中
vi[index++]=item;
sort(vi.begin(),vi.end()); //vi排序
index=0;
for(auto& item:li) //把li复制到vi中
item=vi[index++];
end=clock();
cout<<"Copy li to vi and use sort() of algorithm costs time: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}
int main(){
int numbers[]={100000,1000000,10000000};
for(int i=0;i<3;i++){
cout<<"When number is "<<numbers[i]<<endl;
getTime(numbers[i]);
cout<<endl;
}
return 0;
}10
题目
请按如下方式修改程序清单16.9 (vect3.cpp)。
a.在结构Review中添加成员price。
b.不使用vector
c.在输入阶段结束后，使用一个循环让用户选择如下方式之一显示书籍:按原始顺序显示、按字母表顺序显示、按评级升序显示、按评级降序显示、按价格升序显示、按价格降序显示、退出。
下面是一种可能的解决方案:获取输入后，再创建一个shared_ptr矢量，并用原始数组初始化它。定义一个对指向结构的指针进行比较的operator<()函数，并使用它对第二个矢量进行排序，让其中的shared_ptr按其指向的对象中的书名排序。重复上述过程，创建按rating和price排序的shared_ptr矢量。请注意，通过使用rbegin()和rend()，可避免创建按相反的顺序排列的shared_ptr矢量。
题解
#include<iostream>
#include<string>
#include<vector>
#include<memory>
#include<algorithm>
using namespace std;
struct Review{
std::string title;
int rating;
double price;
};
bool operator<(shared_ptr<Review>& r1,shared_ptr<Review>& r2);
bool sortByRating(shared_ptr<Review>& r1,shared_ptr<Review>& r2);
bool sortByPrice(shared_ptr<Review>& r1,shared_ptr<Review>& r2);
shared_ptr<Review> FillReview();
void ShowReview(shared_ptr<Review>& rr);
int main(){
vector<shared_ptr<Review>> books;
shared_ptr<Review> temp;
while(temp=FillReview())
books.push_back(temp);
if(books.size()==0) cout<<"No entries.";
else{
cout<<"Please enter the rule of sort <5 for quit>:"<<endl
<<"1) Default 2) Title"<<endl
<<"3) Rating 4) Price"<<endl
<<"5) Quit"<<endl;
int choice=-1;
while(cin>>choice&&choice!=5){
vector<shared_ptr<Review>> ttemp(books);
switch(choice){
case 1: cout<<"Origin order:\nBook\tRating\tPrice\n";
break;
case 2: cout<<"Sorted by title:\nBook\tRating\tPrice\n";
sort(ttemp.begin(),ttemp.end());break;
case 3: cout<<"Sorted by rating:\nBook\tRating\tPrice\n";
sort(ttemp.begin(),ttemp.end(),sortByRating);break;
case 4: cout<<"Sorted by price:\nBook\tRating\tPrice\n";
sort(ttemp.begin(),ttemp.end(),sortByPrice);break;
}
for_each(ttemp.begin(),ttemp.end(),ShowReview);
cout<<"Please enter the rule of sort <5 for quit>:"<<endl
<<"1) Default 2) Title"<<endl
<<"3) Rating 4) Price"<<endl
<<"5) Quit"<<endl;
}
}
cout<<"Bye.\n";
return 0;
}
bool operator<(shared_ptr<Review>& r1,shared_ptr<Review>& r2){
return r1->title<r2->title;
}
bool sortByRating(shared_ptr<Review>& r1,shared_ptr<Review>& r2){
return r1->rating<r2->rating;
}
bool sortByPrice(shared_ptr<Review>& r1,shared_ptr<Review>& r2){
return r1->rating<r2->price;
}
shared_ptr<Review> FillReview(){
std::cout<<"Enter book title (quit to quit): ";
shared_ptr<Review> onebook(new Review);
std::getline(std::cin,onebook->title);
if(onebook->title=="quit")
return nullptr;
std::cout<<"Enter the book rating: ";
std::cin>>onebook->rating;
if(!std::cin) //如果没有读到符合要求的数据则返回false
return nullptr;
std::cout<<"Enter the book price: ";
std::cin>>onebook->price;
if(!std::cin)
return nullptr;
while(std::cin.get()!='\n') //吸收多余字符
continue;
return onebook;
}
void ShowReview(shared_ptr<Review>& rr){
std::cout<<rr->title<<"\t"<<rr->rating<<"\t"<<rr->price<<std::endl;
}
Comments | NOTHING