实验五 一. 7-1 部分排序 对于一组数据，我们可以只对原先处在中间位置的那些元素进行排序。 输入格式: 在一行内输入n r a1 a2 ... an 其中，不大于200的正整数n表示该组数据的个数；不大于200的非负整数r表示该组数据两端各自留有r个数不参与排序，若r+r>=n，则该组数据无需排序。 整数a1 a2 ... an是该组的n个数据，且都在8位以内。 输出格式: 排序之后的序列，元素之间用一个空格间隔，最后一个元素之后不加空格。 输入样例: 5 1 6 5 4 3 2 输出样例: 6 3 4 5 2 参考答案： #include<iostream> #include<vector> using namespace std; int main(){ int n,r; cin>>n>>r; vector<int>ivec; int num; for(int i=0;i<n;i++){ cin>>num; ivec.push_back(num); } if(r+r<n){ sort(ivec.begin()+r,ivec.begin()+n-r); } bool isHead = true; for(auto &c:ivec){ if(isHead){ cout<<c; isHead = !isHead; } else{ cout<<" "<<c; } } cout<<endl; return 0; } 二. 7-2 组最大数 设有n个正整数，将他们连接成一排，组成一个最大的多位整数。 如:n=3时，3个整数13,312,343连成的最大整数为34331213。 如:n=4时，4个整数7,13,4,246连接成的最大整数为7424613。 输入格式: 有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。 输出格式: 每组数据输出一个表示最大的整数。 输入样例: 2 12 123 4 7 13 4 246 输出样例: 12312 7424613 参考答案： #include<iostream> #include<vector> using namespace std; bool compare(int a,int b){ string sa = to_string(a); string sb = to_string(b); return sa + sb > sb + sa; } int main(){ int n; while(cin>>n){ vector<int>ivec; int num; for(int i=0;i<n;i++){ cin>>num; ivec.push_back(num); } sort(ivec.begin(),ivec.end(),compare); for(auto &s:ivec){ cout<<s; } ivec.clear(); cout<<endl; } return 0; } 三. 7-3 办事大厅排队 在郑州大学综合办事大厅，每天陆陆续续有很多人来排队办事。现在你能否写程序帮助老师时刻了解当前办理业务的情况。 请同学们学习C++ STL中 list相关内容后，编程实践。 输入格式: 第一行一个数字N，表示排队信息或者查询信息条目的数量。 以下N行，每行的内容有以下3种情况 (1) in name 表示名字为name的人员新来到办事大厅，排在队伍的最后。（in和name间存在一个空格，name是名字对应字符串，长度不超过10）。 (2) out 表示当前排在最前面的人已经办理完业务，离开了。 (3) q 表示一次查询，请输出当前正在办理业务的人，也就是队伍的第1个人。如果当前无人办理业务，则输出“NULL”，不包括引号。 输出格式: 请根据以上信息，每次遇到查询时，对应一行输出。如果这时队伍有人，则输出第一个人的姓名，否则输出NULL。 输入样例: 5 in A out q in B q 输出样例: 在这里给出相应的输出。例如： NULL B 参考答案： #include<iostream> #include<vector> #include<deque> using namespace std; int main(){ int n; cin>>n; deque<string>person; string op,name; while(n-->0){ cin>>op; if(op=="q"){ if(person.size()>0){ cout<<person.front()<<endl; } else{ cout<<"NULL"<<endl; } } else if(op=="out"){ person.pop_front(); } else{ cin>>name; person.push_back(name); } } return 0; } 四. 7-4 括号匹配 给定仅包含“()[]{}”六种括号的字符串，请你判断该字符串中，括号的匹配是否是合法的，也就是对应括号的数量、嵌套顺序完全正确。 输入格式: 第一行一个整数T（T<=10） 其后T行每行一个字符串只包含[{()}]六种字符（字符串长度2e5以内） 输出格式: 对于每个字符串，匹配输出Yes,否则输出No 输入样例: 2 {()[]} ([)] 输出样例: Yes No 参考答案： #include<iostream> #include<stack> using namespace std; int main(){ stack<char>st; int n; cin>>n; string s; while(n-->0){ cin>>s; bool flag = false; for(auto &c:s){ if(c=='{'||c=='['||c=='('){ st.push(c); } else if(c=='}'){ if(st.empty()||st.top()!='{'){ cout<<"No"<<endl; flag = true; break; } if(!st.empty())st.pop(); } else if(c==']'){ if(st.empty()||st.top()!='['){ cout<<"No"<<endl; flag = true; break; } if(!st.empty())st.pop(); } else if(c==')'){ if(st.empty()||st.top()!='('){ cout<<"No"<<endl; flag = true; break; } if(!st.empty())st.pop(); } } if(!flag&&st.size()>0){ cout<<"No"<<endl; } else if(!flag){ cout<<"Yes"<<endl; } while(!st.empty()){ st.pop(); } } return 0; } 五. 7-5 找出不是两个数组共有的元素 给定两个整型数组，本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组，每行先给出正整数N（≤20），随后是N个整数，其间以空格分隔。 输出格式: 在一行中按照数字给出的顺序输出不是两数组共有的元素，数字间以空格分隔，但行末不得有多余的空格。题目保证至少存在一个这样的数字。同一数字不重复输出。 输入样例: 10 3 -5 2 8 0 3 5 -15 9 100 11 6 4 8 2 6 -5 9 0 100 8 1 输出样例: 3 5 -15 6 4 1 参考答案： #include<iostream> #include<unordered_map> #include<deque> using namespace std; int main(){ int n1,n2; unordered_map<int,int>imap; deque<int>row2; cin>>n1; int num; while(n1-->0){ cin>>num; imap[num] = 1; } cin>>n2; while(n2-->0){ cin>>num; if(imap.count(num)){ imap[num] = 0; } else{ if(find(row2.begin(),row2.end(),num)==row2.end()){ row2.push_back(num); } } } for(const auto& pair:imap){ if(pair.second==1){ if(find(row2.begin(),row2.end(),pair.first)==row2.end()){ row2.push_front(pair.first); } } } bool head = true; for(auto& c:row2){ if(head){ cout<<c; head = false; } else{ cout<<" "<<c; } } return 0; }
实验四 一. 7-1 简单求阶乘问题 本题要求编写程序，计算N的阶乘。 输入格式: 输入在一行中给出一个不超过12的正整数N。 输出格式: 在一行中输出阶乘的值。 输入样例: 4 输出样例: 24 参考答案： #include<iostream> using namespace std; int f(int n){ if(n==1||n==0){ return 1; } return n*f(n-1); } int main(){ int n; cin>>n; cout<<f(n); return 0; } 二. 7-2 出生年 以上是新浪微博中一奇葩贴：“我出生于1988年，直到25岁才遇到4个数字都不相同的年份。”也就是说，直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求，自动填充“我出生于y年，直到x岁才遇到n个数字都不相同的年份”这句话。 输入格式： 输入在一行中给出出生年份y和目标年份中不同数字的个数n，其中y在[1, 3000]之间，n可以是2、或3、或4。注意不足4位的年份要在前面补零，例如公元1年被认为是0001年，有2个不同的数字0和1。 输出格式： 根据输入，输出x和能达到要求的年份。数字间以1个空格分隔，行首尾不得有多余空格。年份要按4位输出。注意：所谓“n个数字都不相同”是指不同的数字正好是n个。如“2013”被视为满足“4位数字都不同”的条件，但不被视为满足2位或3位数字不同的条件。 输入样例1： 1988 4 输出样例1： 25 2013 输入样例2： 1 2 输出样例2： 0 0001 参考答案： #include<iostream> #include<set> using namespace std; bool isValid(int Y,int num){ string s = to_string(Y); set<char>mySet; if(s.size()<4){ for(char c:s){ mySet.insert(c); } mySet.insert('0'); return mySet.size()==num; } for(char c:s){ mySet.insert(c); } return mySet.size()==num; } string toString(int num){ string s = "0000"; string origin = to_string(num); int i = origin.size()-1; int j = s.size()-1; while(i>=0){ s[j--] = origin[i--]; } return s; } int main(){ int Y,num; cin>>Y>>num; int index = 0; while(true){ if(isValid(Y+index,num)){ cout<<index<<" "<<toString(Y+index); return 0; } index++; } return 0; } 三. 7-3 验证“哥德巴赫猜想” 数学领域著名的“哥德巴赫猜想”的大致意思是：任何一个大于2的偶数总能表示为两个素数之和。比如：24=5+19，其中5和19都是素数。本实验的任务是设计一个程序，验证20亿以内的偶数都可以分解成两个素数之和。 输入格式： 输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。 输出格式： 在一行中按照格式“N = p + q”输出N的素数分解，其中p ≤ q均为素数。又因为这样的分解不唯一（例如24还可以分解为7+17），要求必须输出所有解中p最小的解。 输入样例： 24 输出样例： 24 = 5 + 19 参考答案： #include<iostream> #include<cmath> using namespace std; bool isValid(long long n){ if(n<2)return false; for(long long i=2;i*i<=n;i++){ if(n%i==0)return false; } return true; } int main(){ long long n; cin>>n; for(long long i=2;i<=n/2;i++){ if(isValid(i)&&isValid(n-i)){ cout<<n<<" = "<<i<<" + "<<n-i; return 0; } } return 0; } 四. 7-4 谷歌的招聘 2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。 自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921... 其中粗体标出的 10 位数就是答案。 本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。 输入格式： 输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数 N。 输出格式： 在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。 输入样例 1： 20 5 23654987725541023819 输出样例 1： 49877 输入样例 2： 10 3 2468001680 输出样例 2： 404 参考答案： #include<iostream> using namespace std; bool isValid(long long n){ if(n<2)return false; for(long long i=2;i*i<=n;i++){ if(n%i==0)return false; } return true; } int main(){ int L,N; cin>>L>>N; if(L<N){ cout<<"404"; return 0; } string s; cin>>s; int pos = 0; while(pos<=s.size()-N){ string sub = s.substr(pos++,N); if(isValid(stol(sub))){ cout<<sub; return 0; } } cout<<"404"; return 0; } 五. 7-5 估值一亿的AI核心代码 以上图片来自新浪微博。 本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是： 无论用户说什么，首先把对方说的话在一行中原样打印出来； 消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉； 把原文中所有大写英文字母变成小写，除了 I； 把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词； 把原文中所有独立的 I 和 me 换成 you； 把原文中所有的问号 ? 换成惊叹号 !； 在一行中输出替换后的句子作为 AI 的回答。 输入格式： 输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。 输出格式： 按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。 输入样例： 6 Hello ? Good to chat with you can you speak Chinese? Really? Could you show me 5 What Is this prime? I,don 't know 输出样例： Hello ? AI: hello! Good to chat with you AI: good to chat with you can you speak Chinese? AI: I can speak chinese! Really? AI: really! Could you show me 5 AI: I could show you 5 What Is this prime? I,don 't know AI: what Is this prime! you,don't know 参考答案： #include<iostream> using namespace std; string process(string s){ while(s[0]==' ') s.erase(s.begin());//去掉句首的空格 while(s.back()==' ') s.erase(s.end()-1);//去掉句尾的空格 for(int i=0;i<s.size();i++) { if(s[i]==' ') { while(s[i+1]==' ') s.erase(s.begin()+i+1);//句中多个空格，只保留一个 if(!isalnum(s[i+1])) s.erase(s.begin()+i);//去掉符号前面的空格 } } for(auto &x:s) { if(x>='A'&&x<='Z'&&x!='I') x=x-'A'+'a';//大写转化为小写 } for(int i=0;;i++) { i=s.find("can you",i);//查找"can you"出现的位置 if(i==-1) break;//没有找到 //位置为0或者当前位置前不能为字母或者数字，并且后面一个字符也不能是字母或者数字 if((i==0||!isalnum(s[i-1]))&&(i==s.size()-7||!isalnum(s[i+7]))) s.replace(i,7,"@ can");//将i后7个位置替换成"@ can" } for(int i=0;;i++) { i=s.find("could you",i); if(i==-1) break; if((i==0||!isalnum(s[i-1]))&&(i==s.size()-9||!isalnum(s[i+9]))) s.replace(i,9,"@ could"); } for(int i=0;;i++) { i=s.find("I",i); if(i==-1) break; if((i==0||!isalnum(s[i-1]))&&(i==s.size()-1||!isalnum(s[i+1]))) s.replace(i,1,"you"); } for(int i=0;;i++) { i=s.find("me",i); if(i==-1) break; if((i==0||!isalnum(s[i-1]))&&(i==s.size()-2||!isalnum(s[i+2]))) s.replace(i,2,"you"); } for(auto &x:s) { if(x=='@') x='I';//因为I会换成you所以先换成@然后再换回来 if(x=='?') x='!'; } return s; } int main(){ int n; cin>>n; getchar(); while(n-->0){ string s; getline(cin,s); cout<<s<<endl; cout<<"AI: "<<process(s)<<endl; } return 0; }
实验三 一. 7-1 求最大值及其下标 本题要求编写程序，找出给定的n个数中的最大值及其对应的最小下标（下标从0开始）。 输入格式: 输入在第一行中给出一个正整数n（1<n≤10）。第二行输入n个整数，用空格分开。 输出格式: 在一行中输出最大值及最大值的最小下标，中间用一个空格分开。 输入样例: 6 2 8 10 1 9 10 输出样例: 10 2 参考答案： #include<iostream> #include<climits> using namespace std; int main(){ int n; int index = 0; cin>>n; int max = INT_MIN; for(int i=0;i<n;i++){ int num; cin>>num; if(num>max){ index = i; max = num; } } cout<<max<<" "<<index; return 0; } 二. 7-2 统计字符出现次数 本题要求编写程序，统计并输出某给定字符在给定字符串中出现的次数。 输入格式： 输入第一行给出一个以回车结束的字符串（少于80个字符）；第二行输入一个字符。 输出格式： 在一行中输出给定字符在给定字符串中出现的次数。 输入样例： programming is More fun! m 输出样例： 2 参考答案： #include<stdio.h> #include<string.h> int main() { int i,len,count=0; char str[80]; char ch; gets(str);//输入str ch=getchar();//输入ch len=strlen(str);//str字符串的长度 for(i=0;i<len;i++) { if(str[i]==ch) count++; } printf("%d",count); return 0; } 三. 7-3 出租 下面是新浪微博上曾经很火的一张图： 一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。 本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。 输入格式： 输入在一行中给出一个由11位数字组成的手机号码。 输出格式： 为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。 输入样例： 18013820100 输出样例： int[] arr = new int[]{8,3,2,1,0}; int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4}; 参考答案： #include<iostream> #include<climits> #include<vector> #include<set> using namespace std; void print(vector<int>vec){ std::for_each(vec.begin(), vec.end(), [](int val) { std::cout << val << " "; }); cout<<endl; } int main(){ string tel; cin>>tel; set<int,greater<int>>mySet; for(char c:tel){ mySet.insert(c-'0'); } vector<int>index(10,0); int pos = 0; for(int val:mySet){ index[val] = pos; pos++; } vector<int>ivec; for(char c:tel){ ivec.push_back(index[c-'0']); } cout<<"int[] arr = new int[]{"; bool isHead = true; for(auto i:mySet){ if(isHead){ cout<<i; isHead = !isHead; } else{ cout<<","<<i; } } cout<<"};"<<endl; cout<<"int[] index = new int[]{"; isHead = true; for(auto i:ivec){ if(isHead){ cout<<i; isHead = !isHead; } else{ cout<<","<<i; } } cout<<"};"; return 0; } 四. 7-4 找鞍点 一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。 本题要求编写程序，求一个给定的n阶方阵的鞍点。 输入格式： 输入第一行给出一个正整数n（1≤n≤6）。随后n行，每行给出n个整数，其间以空格分隔。 输出格式： 输出在一行中按照“行下标 列下标”（下标从0开始）的格式输出鞍点的位置。如果鞍点不存在，则输出“NONE”。题目保证给出的矩阵至多存在一个鞍点。 输入样例1： 4 1 7 4 1 4 8 3 6 1 6 6 2 0 7 8 9 输出样例1： 2 1 输入样例2： 2 1 7 4 1 输出样例2： NONE 参考答案： #include<iostream> #include<climits> #include<vector> using namespace std; int main(){ int n; cin>>n; vector<int>rowMax(n,INT_MIN); vector<int>colMin(n,INT_MAX); vector<vector<int>>arr(n,vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int num; cin>>num; arr[i][j] = num; rowMax[i] = num>rowMax[i]?num:rowMax[i]; colMin[j] = num<colMin[j]?num:colMin[j]; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(arr[i][j]==rowMax[i]&&arr[i][j]==colMin[j]){ cout<<i<<" "<<j; return 0; } } } cout<<"NONE"; return 0; } 五. 7-5 小偷踩点 俗话说不怕贼偷，就怕贼惦记。 小偷在作案前有时会在居民家的门、墙上做一些标记，每一种记号代表一个含义，一般人看不懂，但同行一看便知道这个家庭的情况。不过派出所干警也不是吃素的，很快破译了这些记号的含义（如上图），并且在辖区内广为张贴，告知居民。 随后小偷们又改变了方法，将这些记号从 1 到 N 编号，然后将这些编号按照某种规则重新打乱再做标记，标记变成了一串数字。不过这种新的编号方法又被破译了！干警们发现这些数字的规律可以用一个二维矩阵来表示：矩阵有 10 列，顺序对应数字 0 到 9；矩阵一般不超过 10 行，每行对应一个 0 到 9 之间的数字，这些数字保证不重复。小偷的新标记由若干个两位数组成，每个数字的十位对应行、个位对应列，而对应位置上的数字就是原始标记的编号。 如上图 40 种标记从上到下、从左到右顺序编号后，按下图所示的规律打乱，则如果我们看到标记“71”，就是行标记为 7，列标记为 1 的单元格对应的数字 11，对应原始标记中第 11 个，即“很有钱”。那么标记“71 78 57”就表示原始标记的第 11、8、7 号，意思是“很有钱”、“没有防范”、“计划行动”。 本题就请你编写程序，自动破译小偷的新标记。 输入格式： 输入第一行给出 2 个正整数：N（≤100）为小偷的原始标记个数，M（≤10）为新标记对照矩阵的行数。 随后 N 行，第 i 行给出第 i 个标记的解释，由不超过 100 个英文字母和空格组成。 接下来一行给出 M 个数字，为 0 到 9 之间的数字，保证不重复，其中第 i 个数对应矩阵第 i 行。 接下来 M 行，每行给出 10 个数字，或者是 1 到 N 之间的一个编号，或者是 −1 表示没有对应的编号。 最后一行给出小偷留在墙上的数字标记，格式为： k t[1] ... t[k] 其中 k 是数字个数（不超过 N），后面跟着 k 个数字。 输出格式： 对小偷留下的每个数字，在一行中输出其对应的意义，顺序与输入顺序相同。如果没有对应的意义，则在对应行中输出 ?。 输入样例： 10 2 jia li you ren kong fang zi jia you e gou dan shen hen you qian xiao xin lin ju you bao jing qi jin kuai dong shou xia ci zai lai bu bi jin ru 6 2 -1 6 5 1 -1 10 3 4 -1 9 2 4 7 -1 3 -1 5 -1 8 2 5 20 64 61 22 13 输出样例： kong fang zi ? xiao xin lin ju you bao jing qi ? 参考答案： #include<iostream> #include<climits> #include<vector> using namespace std; int main(){ int N,M; cin>>N>>M; getchar(); vector<string>original; string line; for(int i=0;i<N;i++){ getline(cin,line); original.push_back(line); } vector<int>index(10,-1); for(int i=0;i<M;i++){ int num; cin>>num; index[num] = i; } vector<vector<int>>arr(M,vector<int>(10)); for(int i=0;i<M;i++){ for(int j=0;j<10;j++){ cin>>arr[i][j]; } } int k; cin>>k; for(int i=0;i<k;i++){ int sign; cin>>sign; int row = sign/10; int col = sign%10; if(index[row]==-1){ cout<<"?"<<endl; continue; } if(arr[index[row]][col]==-1){ cout<<"?"<<endl; } else{ cout<<original[arr[index[row]][col]-1]<<endl; } } return 0; }
实验二 一. 7-1 奇偶分家 给定N个正整数，请统计奇数和偶数各有多少个？ 输入格式： 输入第一行给出一个正整N（≤1000）；第2行给出N个非负整数，以空格分隔。 输出格式： 在一行中先后输出奇数的个数、偶数的个数。中间以1个空格分隔。 输入样例： 9 88 74 101 26 15 0 34 22 77 输出样例： 3 6 参考答案： #include<iostream> using namespace std; int main(){ int n; int odd = 0; //奇数 int even = 0; //偶数 cin>>n; for(int i=0;i<n;i++){ int num; cin>>num; if(num%2==0){ even++; } else{ odd++; } } cout<<odd<<" "<<even; return 0; } 二. 7-1 水仙花数 水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。 输入格式: 输入在一行中给出一个正整数N（3≤N≤7）。 输出格式: 按递增顺序输出所有N位水仙花数，每个数字占一行。 输入样例: 3 输出样例: 153 370 371 407 参考答案: #include<iostream> #include<cmath> using namespace std; bool isValid(int num,int N){ int sum = 0; int tmp = num; while(tmp!=0){ int left = tmp%10; sum+=pow(left,N); tmp/=10; } return sum == num; } int main(){ int N; cin>>N; for(int i=pow(10,N-1);i<pow(10,N);i++){ if(isValid(i,N)){ cout<<i<<endl; } } return 0; } 三. 7-2 猜数字游戏 猜数字游戏是令游戏机随机产生一个100以内的正整数，用户输入一个数对其进行猜测，需要你编写程序自动对其与随机产生的被猜数进行比较，并提示大了（“Too big”），还是小了（“Too small”），相等表示猜到了。如果猜到，则结束程序。程序还要求统计猜的次数，如果1次猜出该数，提示“Bingo!”；如果3次以内猜到该数，则提示“Lucky You!”；如果超过3次但是在N（>3）次以内（包括第N次）猜到该数，则提示“Good Guess!”；如果超过N次都没有猜到，则提示“Game Over”，并结束程序。如果在到达N次之前，用户输入了一个负数，也输出“Game Over”，并结束程序。 输入格式: 输入第一行中给出两个不超过100的正整数，分别是游戏机产生的随机数、以及猜测的最大次数N。最后每行给出一个用户的输入，直到出现负数为止。 输出格式: 在一行中输出每次猜测相应的结果，直到输出猜对的结果或“Game Over”则结束。 输入样例: 58 4 70 50 56 58 60 -2 输出样例: Too big Too small Too small Good Guess! 参考答案： #include<iostream> using namespace std; int main(){ int target,N; cin>>target>>N; int num; cin>>num; int cnt = 1; while(num>=0){ if(cnt>N){ cout<<"Game Over"; return 0; } if(num==target){ if(cnt == 1){ cout<<"Bingo!"; return 0; } else if(cnt<=3){ cout<<"Lucky You!"; return 0; } else if(cnt<=N){ cout<<"Good Guess!"; return 0; } } else if(num>target){ cout<<"Too big"<<endl; cnt++; }else { cout<<"Too small"<<endl; cnt++; } cin>>num; } cout<<"Game Over"; return 0; } 四. 7-4 阶梯电价 为了提倡居民节约用电，某省电力公司执行“阶梯电价”，安装一户一表的居民用户电价分为两个“阶梯”：月用电量50千瓦时（含50千瓦时）以内的，电价为0.53元/千瓦时；超过50千瓦时的，超出部分的用电量，电价上调0.05元/千瓦时。请编写程序计算电费。 输入格式: 输入在一行中给出某用户的月用电量（单位：千瓦时）。 输出格式: 在一行中输出该用户应支付的电费（元），结果保留两位小数，格式如：“cost = 应付电费值”；若用电量小于0，则输出"Invalid Value!"。 输入样例1: 10 输出样例1: cost = 5.30 输入样例2: 100 输出样例2: cost = 55.50 参考答案： #include<iostream> #include<iomanip> using namespace std; int main(){ int elec; cin>>elec; double cost = 0; if(elec<0){ cout<<"Invalid Value!"; return 0; } if(elec<=50){ cost+=elec*0.53; } else{ cost+=0.53*50; cost+=(elec-50)*0.58; } cout<<fixed<<setprecision(2)<<"cost = "<<cost; return 0; } 五. 7-5 阅览室 天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。 注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。 输入格式： 输入在第一行给出一个正整数N（≤10），随后给出N天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为： 书号（[1, 1000]内的整数） 键值（S或E） 发生时间（hh:mm，其中hh是[0,23]内的整数，mm是[0, 59]内整数） 每一天的纪录保证按时间递增的顺序给出。 输出格式： 对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。 输入样例： 3 1 S 08:10 2 S 08:35 1 E 10:00 2 E 13:16 0 S 17:00 0 S 17:00 3 E 08:10 1 S 08:20 2 S 09:00 1 E 09:20 0 E 17:00 输出样例： 2 196 0 0 1 60 参考答案： #include<iostream> #include<cmath> using namespace std; int parseTime(string time){ int res = 0; int tmp = 0; for(char c:time){ if(c==':'){ res = tmp*60; tmp = 0; } else{ tmp = tmp*10+c-'0'; } } return res+tmp; } void clear(int arr[1001][2]){ for(int i=0;i<1001;i++){ for(int j=0;j<2;j++){ arr[i][j] = 0; } } } int main(){ int N; cin>>N; int days = 1; int homeNum; char op; string time; int chs[1001][2]; // 清空数组 clear(chs); int cnt = 0; int totalM = 0; while(days<=N){ cin>>homeNum>>op>>time; // 当前输入转换后的分钟数; int curM = parseTime(time); // cout<<"curM = "<<curM<<endl; // 设S为1，E为2 if(op=='S'){ chs[homeNum][0]=1; chs[homeNum][1] = curM; } else{ if(chs[homeNum][0]==1){ cnt++; totalM += curM - chs[homeNum][1]; chs[homeNum][0]=0; chs[homeNum][1]=0; } } // 结束一天的标志，开始统计并输出结果; if(homeNum == 0){ days++; cout<<cnt<<" "<<(cnt==0?0:round(totalM*1.0/cnt))<<endl; // 清除数据 cnt = 0; totalM = 0; clear(chs); } } return 0; }
实验一 一. 7-1 3人分糖果 幼儿园里，有3个小朋友编号分别是1、2、3，他们按自己的编号顺序围坐在一张圆桌旁，每个小朋友的面前分别有8、9、10颗糖果。现在做一个分糖果游戏，从1号小朋友开始，将自己的糖果平均分成三份（如果有多余的糖果，则自己立刻吃掉），自己留一份，其余两份分给相邻座位的两个小朋友。接着，2号、3号小朋友也同样这么做。请问一轮后，每个小朋友面前分别有多少糖果？ 输入格式: 本题目没有输入。 输出格式: 在一行内显示以下结果。注意行末除了换行符不能有任何多余字符。 10 8 5 输入样例: 本题目没有输入。 输出样例: 10 8 5 参考答案： #include<iostream> using namespace std; int main(){ cout<<10<<" "<<8<<" "<<5; return 0; } 二. 什么是机器学习 什么是机器学习？上图展示了一段面试官与“机器学习程序”的对话： 面试官：9 + 10 等于多少？ 答：3 面试官：差远了，是19。 答：16 面试官：错了，是19。 答：18 面试官：不，是19。 答：19 本题就请你模仿这个“机器学习程序”的行为。 输入格式： 输入在一行中给出两个整数，绝对值都不超过 100，中间用一个空格分开，分别表示面试官给出的两个数字 A 和 B。 输出格式： 要求你输出 4 行，每行一个数字。第 1 行比正确结果少 16，第 2 行少 3，第 3 行少 1，最后一行才输出 A+B 的正确结果。 输入样例： 9 10 输出样例： 3 16 18 19 参考答案： #include<iostream> using namespace std; int main(){ int a,b; cin>>a>>b; int sum = a+b; cout<<sum-16<<endl; cout<<sum-3<<endl; cout<<sum-1<<endl; cout<<sum; return 0; } 三. 7-3 鸡兔同笼 《孙子算经》中记载了一个有趣的问题：“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”根据上述描述可列出如下形式的二元一次方程组。 {x+y=352x+4y=94​ 那么求解鸡兔同笼问题就转化成了二元一次方程组求解问题。本题要求编写程序对任意给定的头数和足数判断鸡和兔各有多少。 输入格式: 在一行中给出任意两个非负整数，整数之间用空格分开，第一个整数表示头数，第二个整数表示足数。 输出格式: 在一行中按照chickens = mm; rabbits = nn的格式输出解，如果无解则输出No solution! 。其中mm与nn都是非负整数。 输入样例1: 35 94 输出样例1: chickens = 23; rabbits = 12 输入样例2: 94 35 输出样例1: No solution! 参考答案 #include<iostream> using namespace std; int main(){ int head,foots; cin>>head>>foots; if((foots-head*2)%2!=0 || (head==0&&foots!=0)||(foots==0&&head!=0)||head<foots/4){ cout<<"No solution!"; return 0; } int rabbits = (foots-head*2)/2; int chickens = head - rabbits; cout<<"chickens = "<<chickens<<"; rabbits = "<<rabbits; return 0; } 四. 7-4 位数和 输入一个4位整数，求各个位上的数字之和。 输入格式: 一个四位数的整数。 输出格式: 一个整数，表示各位之和。 输入样例: 1234 输出样例: 10 样例解释：1+2+3+4=10 参考答案 #include<iostream> using namespace std; int main(){ int num; cin>>num; int sum = 0; while(num>0){ int left = num%10; num/=10; sum+=left; } cout<<sum; return 0; } 五. 7-5 逆序的三位数 程序每次读入一个正3位数，然后输出按位逆序的数字。注意：当输入的数字含有结尾的0时，输出不应带有前导的0。比如输入700，输出应该是7。 输入格式： 每个测试是一个3位的正整数。 输出格式： 输出按位逆序的数。 输入样例： 123 输出样例： 321 参考答案 #include<iostream> using namespace std; int main(){ int num; cin>>num; int sum = 0; while(num>0){ int left = num%10; sum = sum*10+left; num/=10; } cout<<sum; return 0; } 六. 7-6 算时间 夏老板在跑步机上锻炼身体。他低头一看，跑步机上记录的跑步时间是以秒为单位，屏幕上显示夏老板跑步的总时间是x秒。 夏老板想用“时分秒”的形式来表示跑步时间，他向你提问：x秒是多少个小时 多少分钟 多少秒？ 输入格式: 一行，一个整数x（0≤x≤2∗1012）。 输出格式: 一行，三个整数a,b,c分别表示时分秒，其间以":"作为间隔。 输入样例1: 8000 输出样例1: 2:13:20 输入样例2: 1234 输出样例2: 0:20:34 样例1说明：8000秒等于2小时13分20秒。 参考答案 #include<iostream> using namespace std; int main(){ long long time; cin>>time; long long hour = time/3600; time -=hour*3600; long long minite = time/60; time-=minite*60; long long second = time; cout<<hour<<":"<<minite<<":"<<second; return 0; }
1. vector 1. 概念 vector是标准库中常见的一种容器，使用起来非常方便，可以用来代替c++原本的数组。vector也可以称为动态数组，因为其大小是根据实时更新而变化的，正因为如此vector显得更加灵活易用。 2. 用法 2.1 vector初始化 vector vec1; 创建空的vector容器，里面不包含任何元素 vector vec2(3); 创建指定数量元素的容器，如果是数值类型，则填充为0；如果是char类型，则以ascii码为0的字符填充(无意义)； vector vec2({'a','b','c'}); 用数组也可以初始化；ps：不能使用变量定义的数组 vector vec3(3,'a'); 指定数量元素用来初始化 vector vec4(vec3); 使用vec3来初始化vec4 2.2 遍历vector vector<int> ivec; for (int i = 0; i < 10; i++) { ivec.push_back(i); } //1.利用迭代器 for (auto it = ivec.begin(); it != ivec.end(); ++it) { cout << *it << " "; } cout << endl; //2.利用下标操作符 for (auto i = 0; i < ivec.size(); i++) { cout << ivec[i] << " "; } cout << endl; //3.利用范围for循环 for (auto i : ivec) { cout << i << " "; } cout << endl; 2.3 vector中的常用操作 2.3.1 insert v.insert(pos,elem)； // 这里pos是一个迭代器，如v.begin() ,表示在pos处插入一个elem拷贝 v.insert(pos,n,elem); // 表示在pos处插入n个elem拷贝 v.insert(pos,beg,end); // 表示在pos位置插入在[beg, end) 区间的数据 2.3.2 erase v.erase(pos) // 删除pos位置的数据，这里依然是一个迭代器，传回下一个数据的位置 v.erase(beg,end) //删除[beg,end) 区间的数据，传回下一个数据的位置 除此之外，还可以用v.pop_back()删除尾部元素，用v.clear()清楚容器内容 2.3.3 front && back 顾名思义，返回容器开头或结尾元素 2.3.4 resize && size && capacity && reserve size指当前实际有多少元素，而capacity指该容器可以最多容纳多少个元素。由于vector是动态数组，因此，随着size增大，capacity也在不断增大 resize 代表重新调整大小，如果resize的值小于当前元素个数，则删掉尾巴的多出的部分；如果多于当前容器内元素的数量，则多出的默认为0 reserve代表设置capacity的值为多少，不常用，但是capacity的值不能小于size的值 2. deque deque与vector非常相似。它也采用动态数组管理元素提供随机存取，有着和vector几乎一样的接口。不同的是deque的动态数组头尾都是开放的，因此能在头尾两端进行快速安插和删除。deque通常是作为一组独立区块，第一区块朝某方向扩展，最后一个区块朝另一个方向扩展。 deque与vector的主要不同之处在于： 两端都能快速安插和删除元素，这些操作可以在分期摊还的常数时间内完成。 元素的存取和迭代器比vector稍慢。 迭代器需要在不同区块间跳转，所以它非一般指针。 因为deque使用不止一块内存（而vector必须使用一块连续的内存），所以deque的max_size() 可能更大。 不支持对容量和内存重新分配时机的控制。不过deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。 除了头尾两端，在任何地方安插或删除元素，都将导致指向deque元素的所有pointers、references、iterators失效。 deque的内存区块不再被使用时，会自动释放。deque的内存大小是可自动缩减的。 deque与vector组织内存的方式不一样。在底层，deque按“页”或“块”来分配存储器，每页包含固定数目的元素。而vector只分配一块连续的内存。例如，一个10M字节的vector使用的是一整块10M字节的内存，而deque可以使用一串更小的内存块，比如10块1M的内存。所以不能将deque的地址（如&deque[0]) 传递给传统的API，因为deque内部所使用的内存不一定会连续。 deque的下述特性与vector差不多： 在中部安插、删除元素的速度较慢。 迭代器属于 random access iterator (随机存取迭代器)。 优先使用vector还是deque？ c++标准建议：vector是应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时，应该选用deque。 使用deque还需注意： 除了at() ，其他成员函数均不会检查索引或迭代器是否有效。 任何插入或删除动作都会使所有指向deque元素的pointers、references、iterators失效，唯一例外的是在头部或尾部插入元素（此时pointers和references仍然有效，但iterators失效） 3. queue queue<Type, Container> (<数据类型，容器类型>） 初始化时必须要有数据类型，容器可省略，省略时则默认为deque 类型 还可以使用list类型，但是最好不要用vector作为底层容器，因为queue要求两端都有插入和删除，而vector只在尾部进行相关操作效率比较高。 常用函数 push() 在队尾插入一个元素 pop() 删除队列第一个元素 size() 返回队列中元素个数 empty() 如果队列空则返回true front() 返回队列中的第一个元素 back() 返回队列中最后一个元素 注意pop()没有返回值 4. list 直接见[C++中list详解_c++ list_愚蠢的土拨鼠。的博客-CSDN博客](https://blog.csdn.net/qq_44423388/article/details/126289452?ops_request_misc=%7B%22request%5Fid%22%3A%22168774933616800215057478%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168774933616800215057478&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-126289452-null-null.142^v88^insert_down28v1,239^v2^insert_chatgpt&utm_term=c%2B%2B list&spm=1018.2226.3001.4187)