算法竞赛--“传智杯”初赛C/C++本科组赛题

发表于 分类于 阅读次数：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

1.选取奇数个数的数字

输入一行数字，其中有且只有一个数字出现了奇数次，其余数字均出现偶数次，请找出该数字并输出

输入信息:

一串连续的数字，最长长度100个字符

输出信息:

出现奇数次的数

样例输入:

1
589698956

样例输出:

1
9

思路：更好的做法 使用^=对输入数据逐个处理。使偶数个数的值两两异或消除，剩余一个奇数个数的值，将其输出。0^a=a a^a^b=b

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <string.h>
int main()
{
	char buff[128] = "";
	fgets(buff, sizeof(buff), stdin);		//也可直接scanf输入 用strlen函数求长度
	int i = 0;
	int ret = 0;
	for (i = 0; i < strlen(buff)-1; i++)
	{
		ret ^= buff[i];
	}
	printf("%c\n", ret);
}

2.输入一个正整数，输出其平方根（不可用使用数学类算法库）

给出年分m和一年中的第n天，算出第n天是几月几号。

输入信息:

小于999999999的正整数

输出信息:

输入数据的平方根，只取整数部分

样例输入:

1
9

样例输出:

1
3

思路：二分法求解

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
int main()
{
	int x;
	scanf("%d",&x);
	int low=0,high=x,mid;
	while(1)
	{
		mid=low+high/2;
		if(mid*mid<=x&&(mid+1)*(mid+1)>x)
			break;
		else if(mid*mid<x)
			low=mid;
		else 
			high=mid;
	}
	printf("%d",mid);
	return 0;
}

3.有效的括号

输入一行只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

输入信息:

一行字符串，其中只有若干大括号，中括号和小括号

输出信息:

若输入括号匹配正确，则输出yes，否则输出no

样例输入:

1
({[}])

样例输出:

1
no

思路：堆栈求解

代码如下:

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
#include <string>
#include <cstdio>
#include <iostream> 
#include <stack>
using namespace std; 
bool isValid(string s) 
{
    if(s=="") 
		return true;
    if(s.length()%2!=0) 
		return false;
    stack<char> ss;
    for(auto i:s) 
	{
        if (i=='{' || i=='('|| i=='[') 
			ss.push(i);
        else 
		{
            if (ss.size() == 0 && (i == ']' || i == '}' || i == ')')) 
				return false;
            else if ((i == '}' && ss.top() != '{') || (i == ']' && ss.top() != '[') || (i == ')' && ss.top() != '(') )
                return false;
            else
                ss.pop();
        }
	}
    if (ss.size() != 0 ) 
		return false;
    return true;
}
int main()
{
    string x;
    cin >> x;
    if (isValid(x))
    {
        cout << "yes"<<endl;
    }
    else
    {
        cout <<"no"<<endl;
    }
}

4.求众数

输入一行若干数字组成的字符串，输出众数（即出现次数大于总个数一半的数）

输入信息:

一行字符串，包含若干数字，数字之间用空格隔开，总长度不超过128字节

输出信息:

找到的众数

样例输入:

1
5 9 6 5 6 5 5 4 5

样例输出:

1
5

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main()
{
    int input;
    int ret = 0;
    int count = 0;
    while(0 < scanf("%d", &input))
    {
        if (0== count)
        {
            ret = input;
        }
        if (ret == input)	//出现次数大于总个数一半
        {
            count++;
        }
        else
        {
            count--;
        }
    }
    printf("%d\n", ret);
}

5.中文读正整数

输入信息:

一个正整数，小于等于9位长度

输出信息:

中文读法

样例输入:

1
12345

样例输出:

1
一万二千三百四十五

代码如下:

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
60
61
62
#include <bits/stdc++.h>
void print_digit(char c)	//读数字
{
	if(c=='0')printf("零");
	if(c=='1')printf("一");
	if(c=='2')printf("二");
	if(c=='3')printf("三");
	if(c=='4')printf("四");
	if(c=='5')printf("五");
	if(c=='6')printf("六");
	if(c=='7')printf("七");
	if(c=='8')printf("八");
	if(c=='9')printf("九");	
}
void reverse(char a[])	//字符串逆置
{
	int len=strlen(a);
	for(int i=0;i<len/2;i++)
	{
		char c=a[i];
		a[i]=a[len-i-1];
		a[len-i-1]=c;
	}
}
void printf_chinese(char str[])
{
	int len=strlen(str);
	reverse(str);
	int flag;
	for(int i=len-1;i>=0;i--)
	{
		if(str[i]!='0')//注意该处不为0 
		{
			if(flag==1)		//输出0 包含多个连续的0 
			{
				print_digit('0');	
				flag=0;
			}
			print_digit(str[i]);
			if(i%4==3)printf("千");
			if(i%4==2)printf("百");
			if(i%4==1)printf("十"); 
		}
		else
		{
			flag=1;
		} 
		if(i==8)printf("亿");
		if(i==4)
		{
			if(len<=8||str[7]!='0'||str[6]!='0'||str[5]!='0'||str[4]!='0')
				printf("万"); 
		} 
	}
}
int main()
{
	char str[10];
	scanf("%s",str);
	printf_chinese(str);
	return 0;
}
小礼物走一个哟
0%