7-1 寻找第k小的数 (20 分)
给定若干整数，请设计一个高效的算法，确定第k小的数。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数n，k（1≤k≤n≤1000000）。第2行输入n个整数，每个数据的取值范围在0到1000000之间。
输出格式:
对于每组测试，输出第k小的数。
输入样例:
5 3
1 2 2 2 1
9 3
1 2 3 4 5 6 9 8 7
输出样例:
2
3
提示:
如果提交后超时，请注意需要设计的是高效的算法！如果你初学《数据结构》，暂时设计不出来，请学完相关知识再回头来做。
也可以使用STL之sort、nth_element函数求解。
另外，由于输入数据特别多，为减少输入数据的耗时，建议使用以下的输入外挂函数：
void scan_d(int &num)
{
char in;
in=getchar();
while(in<'0'||in>'9') in=getchar();
num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}
}
调用方法如下：
int n;
scan_d(n);
解答：（简单sort）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
int a[1000000];
while(cin>>n){
scanf("%d",&k);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
printf("%d\n",a[k-1]);
}
return 0;
}
7-2 约瑟夫环 (20 分)
有n个人围成一圈（编号为1～n），从第1号开始进行1、2、3报数，凡报3者就退出，下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号?
输入格式:
测试数据有多组，处理到文件尾。每组测试输入一个整数n（5≤n≤100）。
输出格式:
对于每组测试，输出最后剩下那个人的编号。
输入样例:
10
28
69
输出样例:
4
23
68
解答：（#有点难）
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while ((scanf("%d", &n) != EOF)) {
if (n == 0)
break;
int sum = 0;
for (int i = 2; i < n + 1; i++) {
sum = (sum + 3) % i;
}
cout << sum + 1 << endl;
}
return 0;
}
7-3 英文单词排序 (20 分)
本题要求编写程序，输入若干英文单词，对这些单词按长度从小到大排序后输出。如果长度相同，按照输入的顺序不变。
输入格式：
输入为若干英文单词，每行一个，以#作为输入结束标志。其中英文单词总数不超过20个，英文单词为长度小于10的仅由小写英文字母组成的字符串。
输出格式：
输出为排序后的结果，每个单词后面都额外输出一个空格。
输入样例：
blue
red
yellow
green
purple
#
输出样例：
red blue green yellow purple
解答：(注意一定要用stable_sort) 感兴趣的同学可以在下面查查，这里就不赘述了。
#include <bits/stdc++.h>
using namespace std;
bool smp(string s, string b) {
return s.size() < b.size();
}
string s1[21];
int main() {
int i = 0;
string s;
cin >> s;
while (s != "#") {
s1[i] = s;
i++;
cin >> s;
}
stable_sort(s1, s1 + i, smp);
for ( int a = 0; a < i; a++) {
cout << s1[a] << " ";
}
return 0;
}
7-4 括号匹配 (20 分)
给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入格式:
输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。
输出格式:
如果括号配对，输出yes，否则输出no。
输入样例1:
sin(10+20)
输出样例1:
yes
输入样例2:
{[}]
输出样例2:
no
解答 （栈的使用）
#include <bits/stdc++.h>
using namespace std;
string solve(string str) {
stack<char> st;
int i = 0;
while (i < str.size()) {
if (str[i] == '(' || str[i] == '{' || str[i] == '[')
st.push(str[i]);
else if (str[i] == ')') {
if (st.size() == 0 || st.top() != '(') {
return "no";
}
st.pop();
} else if (str[i] == ']') {
if (st.size() == 0 || st.top() != '[') {
return "no";
}
st.pop();
} else if (str[i] == '}') {
if (st.size() == 0 || st.top() != '{') {
return "no";
}
st.pop();
}
i++;
}
if (st.size() == 0)
return "yes";
else
return "no";
}
int main() {
string str;
//cin >> str;
getline(cin, str);
cout << solve(str);
return 0;
}
7-5 函数的递归调用 (20 分)
有n个人坐在一起，第n个人比第n-1个人大2岁，第n-1个人比第n-2个人大2岁，以此类推，……，第1个人是10岁。请问第n个人年龄多大？
输入格式:
输入一个整数表示第几个人。
输出格式:
输出第n个人是m岁。
输入样例:
5
输出样例:
Number 5 is 18 age!
解答：（递归 找规律）
#include <bits/stdc++.h>
using namespace std;
int f(int n) {
if (n == 1)
return 10;
return f(n - 1) + 2;
}
int main() {
int n;
cin >> n;
cout << "Number " << n << " is " << f(n) << " age!";
return 0;
}```
