存档

文章标签 ‘研究生’

上海交通大学08年研究生机试题B

2009年9月23日 没有评论

题目
Problem B. Simple Sorting
Input file: Standard Input
Output file: Standard Output
Time Limit: 1 Second

You are given an unsorted array of integer numbers. Your task is to sort this array and kill possible duplicated elements occurring in it.

Input
The first line of the input contains an integer number N representing the quantity of numbers in this array(1≤N≤1000). Next N lines contain N integer numbers(one number per each line) of the original array.

Output
Output file should contain at most N numbers sorted in ascending order. Every number in the output file should occur only once.

Sample input and output
Standard Input Standard Output
6 3
8 7
8 8
7
3
7
7

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_LEN 1000
 
int number_of_inputs;
int inputs[MAX_LEN];
 
void get_inputs()
{
	int i;
	cin >> number_of_inputs;
	for (i=0;i<number_of_inputs;++i)
	{
		cin >> inputs[i];
	}
}
 
void qsort(int left,int right)
{
	int i = left;
	int j = right;
	int pivot_index = (i + j) / 2;
	int pivot = inputs[pivot_index];
	while (i <= j)
	{
		while (inputs[i] < pivot)
			++i;
		while (inputs[j] > pivot)
			--j;
		if (i <= j)
		{
			int temp = inputs[i];
			inputs[i++] = inputs[j];
			inputs[j--] = temp;
		}
	}
	if (i > left)
		qsort(left,j);
	if (j < right)
		qsort(i,right);
}
int main()
{
	get_inputs();
 
	qsort(0,number_of_inputs-1);
	ofstream output_file;
	output_file.open("output.txt");
	for (int i =0;i<number_of_inputs-1;++i)
	{
		if (inputs[i] != inputs[i+1])
			output_file << inputs[i] << endl;
	}
	if (i == number_of_inputs -1)
		output_file << inputs[i] << endl;
	output_file.close();
	return 0;
}
分类: 算法 标签: , ,

上海交通大学08年研究生机试题A

2009年9月23日 没有评论

这两天在准备保送到交大软院,由于要考机试,这两天狂练C++中,把自己的代码贴出来吧,不能再懒了,再懒博客就要荒废了。

题目:
Problem A. Prime Number
Input file: Standard Input Page 1 of 2
Output file: Standard Output
Time Limit: 1 Second
Output the k-th prime number.

Input
k≤10000

Output
The k-th prime number.

Sample input and output
Standard Input Standard Output
3 5
7 17

C++代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cmath>
using namespace std;
 
int isPrime(int n)
{
	int i,flag = 1;
	for (i=2;i<=sqrt(n);++i)
	{
		if (n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}
 
int main()
{
	int i = 1,n = 2,k,result;
	cin >> k;
	while(i <= k)
	{
		result = n++;
		if (isPrime(result))
			++i;
	}
	cout << result;
}
分类: 算法 标签: , ,