题目94：求字符串的起始位置

作者: SunCiHai

时间限制: 10s

章节: 字符串

问题描述

在程序设计中，对字符串的处理是经常遇到的一个问题。

例如，将字符串中所有的英文字母变成大写，或者将一个字符串与另一个字符串连接构成一个新的字符串。

由于此类的操作非常普遍，因此，在设计程序语言的时候，设计者就已经把这类操作的代码写好了，如果编程人员要使用这些代码，只需把该类代码的头文件包含到自己的程序中，编程人员就可以很简单的调用，这样使编程节省了不少时间。

明明是一名项目经理，他现在负责一种新的程序设计语言的开发，现在需要预先实现大量的和处理字符串有关的功能方法，以后这些方法会包含到程序设计语言中，方便程序语言使用者的开发。你是明明手下的一名软件工程师，明明分配给你一个任务，在两个字符串中，找到一个字符串在另一个字符串中的起始位置。 例如，有两个字符串，一个字符串s= “abc”，另一个字符串subs=“bc”，现在就要找出“bc”在“abc”中的其实位置，在这个例子中，“bc”的起始位置为2。

明明的问题可以归结为：输入两串字符串s和subs，求s中subs的起始位置。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据两行，每组测试数据的第一行为字符串s，s的长度小于100，每组测试数据的第二行为字符串subs，subs的长度小于100，s和subs中仅包含小写字母和数字。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数m，即subs在s中的起始位置，如果在s中找不到subs这个子串，则m=0。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

输入范例

abc
bc
aaa
bbb

输出范例

2
0
代码

#include <iostream>
#include <cstdio>
using namespace std;

 int main()
 {
	string s, subs;
	while(cin >> s >> subs)
	{
		int index = 0;
		int flag = 0;
		for(int i = 0; i < s.size(); i ++)
		{
			int cnt = 0;
			while(cnt < subs.size())
			{
				if(s[i + cnt] != subs[cnt])
				{
					break;
				}
				cnt ++;
				if(cnt == subs.size())
				{
					index = i + 1;
					flag = 1;
					break;
				}
			}
			if(flag)	break;//在s中第一次找到subs就退出循环
		}
		cout << index << endl;
	}
	return 0;
 }

题目95：最长的单词

作者: ZhuKai

时间限制: 10s

章节: 字符串

问题描述

明明刚开始学习英语的时候，对英语有浓厚的兴趣，但是随着时间的推移，英语单词量的增加，明明越来越觉得背单词是一件相当痛苦的事情。于是他想出各种各样的方法来增加背单词的乐趣。

这次他想出的方法是把所有要背的英语单词排成一行，找出其中最长的一个单词来先背，然后划去这个单词，在剩下的单词中再找出一个最长的单词来背，以此类推，直到把所有单词都背完。如果有多个长度相同的单词，则先背一行中靠前的那个单词。这样做的好处是：背到越后面，单词越短，越容易背，越能增加背单词的信心。

例如有这么一行单词： one two three four five 明明会首先挑出three来背，因为它是最长的一个单词，由5个字母组成；然后明明会选择four这个单词，虽然five这个单词的长度和four这个单词的长度一样，但是four在five的前面，所以明明会先背four这个单词，然后再背five，等明明把five这个单词背完以后，接着背one这个单词，最后背的是two这个单词。

但是在这样背单词之中，明明又发现了另一个问题，当要背非常多的单词时，寻找最长的单词会花很多时间，他想让你帮助他写一个程序，找出一行单词中最长的那个，节约明明背单词所花的时间，与此同时，明明希望你能告诉他这个英文单词有多少个字母组成，那他可以做到心里有数。

明明的问题可以归结为：在一行英文单词中，找出其中最长的单词（若有多个最长，找出第一个出现的），并输出这个单词的长度。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行包括许多个英语单词和空格，单词和单词之间可能有多个空格，每行的长度不会超过1000个字符。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数和一个英语单词，整数表示该英文单词的长度，整数和单词之间用一个空格隔开。输出时，每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

输入范例

a bc def ghijk lmn
abc def ghi

输出范例

5 ghijk
3 abc

个人总结

自定义的结构体node不能直接通过sort（）函数进行排序，需要额外通过编写排序逻辑cmp来搭配使用。

方法一（常规方法）

#include <iostream>
#include <string>

using namespace std;


int main() {

	string s;
	while(getline(cin , s))
	{
		int max = -1; //最长单词的长度
		string res = "";//用于存放最长的单词

		for(int i = 0; i < s.size(); i ++)
		{
			if(s[i] != ' ')
			{
				int begin = i; //一个单词第一个字母的索引
				while(s[i] != ' ' && i < s.size())
				{
					i ++;
				}

				if(max < i - begin)
				{
					max = i - begin;
					res = s.substr(begin , max);//截取开始的索引，截取长度
				}
			}
		}
		cout << max << ' ' << res << endl;
	}
    return 0;
}

方法二（使用结构体）

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
	string s;
	int len;
	int index;	
};

int cmp(struct node a, struct node b)
{
	if(a.index == b.index)	return a.index < b.index;
	return a.len > b.len;
}
	
 int main()
 {
	string s;
	while(getline(cin , s))
	{
		int cur = 0;
		vector<struct node> v;
		for(int i = 0; i < s.size(); i ++)
		{
			if(s[i] != ' ')
			{
				int j;
				struct node x;
				x.len = 0;
				x.index = i;
				for(j = i; s[j] != ' ' && j < s.size(); j ++)
				{
					x.s += s[j];
					x.len ++;
				}
				v.push_back(x);
				i = j;
				cur ++;
			}
		}
		sort(v.begin() , v.end(), cmp);
		cout << v[0].len << ' ' << v[0].s << endl;
	}
	return 0;
 }

题目96：奖学金

作者: ZhuKai

时间限制: 10s

章节: 字符串

问题描述

明明所在学校的惯例是在每学期的期末考试之后发放奖学金。

发放的奖学金共有五种，获取的条件各不相同：

1. 院士奖学金：每人8000元，期末平均成绩高于80分，并且在本学期内发表1篇或1篇以上论文的学生均可获得。

2. 五四奖学金：每人4000元，期末平均成绩高于85分，并且班级评议成绩高于80分的学生均可获得。

3. 成绩优秀奖：每人2000元，期末平均成绩高于90分的学生均可获得。

4. 西部奖学金：每人1000元，期末平均成绩高于85分的西部省份学生均可获得。

5. 班级贡献奖：每人850元，班级评议成绩高于80分的学生干部均可获得。

只要符合条件就可以得奖。 每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。

例如明明的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。

由于老师在学期末的时候很忙，所以，他把奖学金统计的事情交给明明做。老师把考试的相关数据给了明明，让他统计出以下数据：

1） 哪位同学获得的奖学金最多；

2） 获得最多奖学金的同学一共获得了多少奖学金；

3） 所有获得奖学金的同学一共获得了多少奖学金；

明明虽然很愿意帮老师这个忙，但是他发现，同学的数量很多，统计起来很麻烦，经常有统计出错的情况发生。于是明明就想请你帮一个忙，帮他写一个统计程序，统计出以上三项内容。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有多行，每组测试数据的第一行有一个整数N（1≤N≤100），表示学生的总数。接下来的N行，每行是一位学生的数据，一行中从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格），期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100），是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是，发表的论文数是0到10的一个整数（包括0和10），每两个相邻数据项之间用一个空格分隔。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。

每组运算结果有三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。 如果有不止一名学生获得的奖学金最多，输出他们之中出现最早的学生姓名，第三行是这N个学生获得的奖学金的总数。输出时，每组运算结果其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间有一个空行，最后一组运算结果后面没有空行。 注：通常，显示屏为标准输出设备。

输入范例

1
Peter 87 82 Y N 0
2
Peter 85 85 Y Y 1
Mary 90 90 N N 0

输出范例

Peter
4850
4850

Peter
8850
12850
代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
	string name;
	int sum;
	int index;
};

int cmp(struct node a, struct node b)
{
	if(a.sum == b.sum)	return a.index < b.index;
	return a.sum > b.sum;
}
	
 int main()
 {
	int n;
	while(cin >> n)
	{
		int cnt = 0;
		vector<struct node> v;
		while(n --)
		{
			string s;
			int q, b, l;
			char g, x;
			cin >> s >> q >> b >> g >> x >> l;
			cnt ++;
			struct node nn;
			nn.index = cnt;
			nn.name = s;
			nn.sum = 0;
			if(q > 80 && l >= 1)	nn.sum += 8000;//院士奖学金
			if(q > 85 && b > 80)	nn.sum += 4000;//五四奖学金
			if(q > 90)	nn.sum += 2000;//成绩优秀奖
			if(q > 85 && x == 'Y')	nn.sum += 1000;//西部奖学金
			if(b  > 80 && g == 'Y')	nn.sum += 850;//班级贡献奖
			v.push_back(nn);
		}
			sort(v.begin() , v.end(), cmp);
			cout << v[0].name << endl << v[0].sum << endl;
			int total = 0;
			for(int i = 0; i < cnt; i ++)
			{
				total += v[i].sum;
			}
			cout << total << endl <<endl;
	}
	return 0;
 }

英语翻译

III. Theory and Experiment理论与实验

        Computer science is a combination of theory, engineering, and experimentation. In some cases, a computer scientist develops a theory, then engineers a combination of computer hardware and software based on that theory, and experimentally tests it. An example of such a theory-driven approach is the development of new software engineering tools that are then evaluated in actual use. In other cases, experimentation may result in new theory, such as the discovery that an artificial neural network exhibits behavior similar to neurons in the brain, leading to a new theory in neurophysiology.

        计算机科学是理论、工程与实验的结合。在某些情况下，计算机科学家提出一种理论，然后基于该理论设计一种软硬件的结合，并用实验对其进行测试。这种理论驱动方法的一个例子就是新的软件工程工具的开发，随后在实际使用中被评估。在一些其他的情况，实验可能会催生新理论，比如人工智能神经网络表现行为与大脑中的神经元相似，从而引领神经生理学中的新理论。

neural network 神经网络

neuron /'njuərɔn/n. 神经元，神经细胞

neurophysiology /'njuərəu,fizi'ɔlədʒi/n. 神经生理学

        It might seem that the predictable nature of computers makes experimentation unnecessary because the outcome of experiments should be known in advance. But when computer systems and their interactions with the natural world become sufficiently complex, unforeseen behavior can result. Experimentation and the traditional scientific method are thus key parts of computer science.

        似乎看起来是计算机的可预测特性让实验变得不必要，因为实验的结果应该提前被知道。但当计算机系统和它们与自然世界的交互变得足够复杂，不可预见的行为就会出现。因此，实验和传统的科学方法都是计算机科学的关键组成部分。

unforeseen /ˌʌnfɔ:'si:n/a. 未预见到的；意料之外的

IV. Major Branches of Computer Science计算机科学的主要分支

        Computer science can be divided into four main fields: software development, computer architecture (hardware), human-computer interfacing (the design of the most efficient ways for humans to use computers), and artificial intelligence (the attempt to make computers behave intelligently). Software development is concerned with creating computer programs that perform efficiently. Computer architecture is concerned with developing optimal hardware for specific computational needs. The areas of artificial intelligence (AI) and human-computer interfacing often involve the development of both software and hardware to solve specific problems.

        计算机科学可以被分为四个主要领域：软件开发、计算机体系机构（硬件），人机接口技术（为人类设计最高效的方式来使用电脑），以及人工智能（尝试让计算机表现得智能）。软件开发与创建高效表现的计算机程序有关。计算机体系结构与为特定的计算机需求开发最优的硬件有关。人工智能领域和人机接口技术领域通常涉及为解决特定问题的软硬件开发。

architecture /'ɑ:kitektʃə/n. 体系结构

interfacing /'intə,feisin/n. 接口技术

optimal /'ɔptiməl/a. 最优的，最佳的

computational /ˌkɔmpju:'teiʃənəl/a. 计算（机）的

单词打卡