题目67：三角形的个数

问题描述

明明的爸爸常用玩游戏的方法来激发明明对几何学的兴趣。这天明明的爸爸和明明又玩起了有关三角形的游戏。

明明爸爸对明明说：“我们能不能构造一个周长为15的三角形？” “太简单了，”明明说道：“三条边长都是5的三角形，它的周长不就是15吗？” “明明真聪明，算得真快。”明明爸爸接着说：“可是，我不想要三条边都相等的三角形哪！” 明明大眼睛一转，说道：“那也好办啊，我只要对这个等边三角形的一条边减去一个数，再把这个数加到另一条边上就可以得到一个新的周长为15的三角形。例如，在第一条边上减去1，在第二条边上加上1，这样不就可以得到一个周长为15的新的三角形了吗？” “哇，明明太聪明了”爸爸称赞道。“对，如果把第一条边上减去的1加到第三条边上去不就又可以得到周长为15的另外一个新三角形了吗？”爸爸模仿着明明的方法和语气。 “不对呀，爸爸。你构造的三角形和我构造的三角形是同样的三角形。爸爸你看，我的三角形三条边分别长为4、6、5，而你的三角形三条边分别长为4、5、6，将三条边按其边长排序后都得到4、5、6，所以它们是同一个三角形，不是两个不同的三角形。” “啊，还是明明聪明。那还有没有其他周长为15的三角形吗？” “当然有啦。三条边边长分别为4、4、7的三角形，它的周长就是15，不过你可能不喜欢它，因为它有两条边的边长相等。” 明明和爸爸玩了一下午这样的三角形游戏，明明一共又构造了另外两个他认为他爸爸喜欢的三角形，即边长分别为2、6、7的三角形和边长分别为3、5、7的三角形。

晚上，明明躺在床上还在思考：如果周长不是15，而是90，那么爸爸喜欢的三角形有多少个呢？

明明的问题可以归结为：根据一个正整数n（3 ≤ n ≤ 100），要求统计出同时满足下列条件的三角形的个数：

1. 边长都是整数。

2. 周长为n。

3. 边长两两不相等。

之所以有上述第一个条件，那是因为明明只知道正整数，没有学过分数和实数，因此他构造出的三角形的边长均为正整数。 请你写一个程序来帮助明明计算出他认为他爸爸喜欢的三角形的个数。

输入说明

你写的程序需要从标准输入设备（通常为键盘）中读入多组测试数据，每组测试数据仅占一行，每行仅包括一个正整数n（3 ≤ n ≤ 100），代表需要被统计的三角形的周长，n的前后都没有任何空格。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果依次写入到标准输出设备（通常为启动该程序的文本终端，例如Windows中的命令行终端）中。每组运算结果为一个大于等于0的整数构成，即满足条件的三角形的个数。例如：测试数据n为15时，运算结果应为3。输出时，每组运算结果占一行，其行首和行尾都没有任何空格或其他字符，每组运算结果与其后一组运算结果之间没有任何空行或其他字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他字符。

输入范例

15
30

输出范例

3
12
代码

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

 int main()
 {
	int n;
	while(cin >> n)
	{
		int cnt = 0;
		for(int i = 1; i < n; i ++)
		{
			for(int j = i + 1; j < n; j ++)
			{
				for(int k = j + 1; k < n; k ++)
				{
					if(i + j + k == n && i != j && i != k && j != k)
					{
						if(i + j > k && j + k > i && i + k > j)	cnt ++;
					}
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
 }

题目68：素数

问题描述

明明的爸爸是一位数学家，明明受他爸爸的影响从小就喜欢数学，经常向他爸爸学习或请教数学问题。一天，明明问他爸爸什么是素数，明明的爸爸回答说：“首先，素数都是大于1的自然数；其次，素数是只能被1和其本身整除的数。例如‘3’这个数，它只能被1和3这两个整数整除，因此‘3’就是素数；但是‘4’就不是素数，因为4除了能被1和4整除外，还能被2整除，因此‘4’就不是一个素数。”明明对于爸爸的回答很满意，也很快明白了素数的定义。于是明明的爸爸就问明明：“明明，你现在知道了什么是素数，那我现在给你一个整数区间，你能告诉我在这个区间里，一共有多少个素数吗？” 例如：一个区间为[1，10]，则在这个区间里一共有2、3、5、7，总共4个素数。 明明想了想，觉得这很简单，就说：“没问题。”于是明明爸爸就给了明明一个很大的区间，这下明明有点犯难了，由于区间太大，一个一个算过了会很花时间。聪明的明明想到了你，你总是乐于助人。明明想让你帮他写一个程序，用来计算在某一个整数区间内一共有多少个素数。 明明的问题可以归结为：给你一个整数区间，求出在这个区间里共有多少个素数。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅有一行，每组测试数据有两个正整数M，N(0 < M ≤ N ≤ 1000000)，表示一个整数区间。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即区间[M, N]内一共有多少个素数。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

输入范例

1 10
10 30

输出范例

4
6

代码

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

bool IsPrime(int x)
{
	if(x == 1)	return false;
	for(int i = 2; i <= sqrt(x); i ++)
	{
		if(x % i == 0)	return false;
	}
	return true;
}

 int main()
 {
	int m, n;
	while(cin >> m >> n)
	{
		int cnt = 0;
		for(int i = m; i <= n; i ++)
		{
			if(IsPrime(i))	cnt ++;
		}
		cout << cnt << endl;
	}
    return 0;
 }

题目69：杨辉三角

问题描述

还记得中学时候学过的杨辉三角吗？

基本的特征是：

前提：端点的数为1.

1. 每个数等于它上方两数之和。

2. 每行数字左右对称，由1开始逐渐变大。

3. 第n行的数字有n项。

你可以参考以下的图形：

输入说明

输入数据首先包含一个正整数T ( T < 10 )，表示有 T 组测试数据, 每组测试数据只包含一个正整数n（1 <= n <= 20），表示将要输出的杨辉三角的层数。

输出说明

对应于每一个输入，请输出相应层数的杨辉三角，输出的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。

输出时，每一行的开头的“1”前面不需要空格，结尾的“1”后面也没有空格。

输入范例

2
5
8

输出范例

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

个人总结

虽然1 <= n <= 20，但是仍然需要将数组设置为int a[21][21] = {0};
 数组 a[20][20] 的合法下标范围是 0 <= 行/列 <= 19（C 语言数组下标从 0 开始），当 i=20、j=20 时，访问 a[20][20] 属于数组下标越界。

代码

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

 int main()
 {
	int t;
	cin >> t;
	while(t --)
	{
		int n;
		cin >> n;
		int a[21][21] = {0};
		for(int i = 1; i <= n; i ++)//i行j列
		{
			for(int j = 1; j <= i; j ++)
			{
				if(i == j || j == 1)	a[i][j] = 1;
				else if(i > j && j > 1)
				{
					a[i][j] = a[i - 1] [j] + a[i - 1][j - 1];
				}
			}
		}
		for(int i = 1; i <= n; i ++)
		{
			int flag = 0;
			for(int j = 1; j <= i; j ++)
			{
				if(a[i][j] != 0)
				{
					if(flag)	cout << ' ';
					flag = 1;
					cout << a[i][j];
				}
			}
			cout << endl;
		}
		cout << endl;
	}
    return 0;
 }

英语翻译

As an emerging technology, the IoT will become more mature and more sophisticated. Figure 12C-1 shows the major technology advances and key applications that may benefit from the IoT. For example, supply chains are now better supported than before. Vertical market applications may represent the next wave of advances. Ubiquitous positioning is expected to become a reality as we move toward 2020. Beyond that, a physical IoT may be in place in a global scale. These advances will significantly upgrade human abilities, societal outcomes, national productivity, and quality of life.

作为一项新兴技术，物联网将变得更加成熟和精密。图12C-1展示了可能受益于物联网的主要技术进展和关键应用领域。例如，如今供应链比之前的供应能力更好。垂直行业应用可能代表下一波技术进步浪潮。随着我们迈向 2020 年，泛在定位有望成为现实。在此之后，一个覆盖全球的实体物联网或将建成。这些进步将显著提升人类能力、社会成果、国家生产力以及生活质量。

supply chain 供应链

societal /sə'saiətəl/ a. 社会的

Figure 12C-1: Technology Road Map of the IoT

图12C-1：物联网技术路线图

III. Architecture of the Internet of Things物联网的体系结构

The IoT system is likely to have an event-driven architecture. In Figure 12C-2, IoT development is shown with a three-layer architecture. The top layer is formed by driven applications. The application space of the IoT is huge. The bottom layers represent various types of sensing devices: namely RFID tags, ZigBee or other types of sensors, and road-mapping GPS navigators. The sensing devices are locally or wide-area-connected in the form of RFID networks, sensor networks, and GPSs. Signals or information collected at these sensing devices are linked to the applications through the cloud computing platforms at the middle layer.

物联网系统很可能采用事件驱动型架构。图12C-2展示了物联网发展所采用的三层架构。最上层由各类驱动型应用构成。物联网的应用空间很广。底层代表各种类型的感知设备，包括RFID标签、ZigBee或其他类型的传感器，以及用于路径规划的GPS导航设备。这些感知设备通过RFID网络、传感器网络和GPS系统以本地或广域方式相互连接。在这些感知设备上采集到的信号或信息，通过中间层的云计算平台与上层应用相连接。

navigator /'næviɡeitə/ n. 导航仪，导航系统；航海者

The signal processing clouds are built over the mobile networks, the Internet backbone, and various information networks at the middle layer. In the IoT, the meaning of a sensing event does not follow a deterministic or syntactic model. In fact, the service-oriented architecture (SOA) model is adoptable here. A large number of sensors and filters are used to collect the raw data. Various compute and storage clouds and grids are used to process the data and transform it into information and knowledge formats. The sensed information is used to put together a decision-making system for intelligence applications. The middle layer is also considered as a Semantic Web or Grid. Some actors (services, components, avatars) are self-referenced.

信号处理云平台构建于中间层的移动通信网络、互联网骨干网以及各类信息网络之上。在物联网中，感知事件的含义并不遵循确定性或纯语法模型。事实上，此处可采用面向服务的架构模型。大量传感器和滤波器被用于采集原始数据。各种计算云、存储云以及网格系统被用来处理这些数据，并将其转化为信息乃至知识的形式。所获取的感知信息被集中用于构建面向智能应用的决策系统。中间层也被视为语义网或语义网格。其中一些参与者（如服务、组件、虚拟化身等）具有自引用特性。

deterministic /diˌtəːmi'nistik/ a. 决定论的；确定性的

semantic /si'mæntik/ a. 语义（学）的

Semantic Web 语义网

Semantic Grid 语义网格

Figure 12C-2: The architecture of an IoT consisting of sensing devices that are connected tovarious applications via mobile networks, the Internet, and processing clouds

图 12C-2：一种物联网架构，其中感知设备通过移动网络、互联网和处理云平台连接到各类应用。

单词打卡