34. 繁殖问题

题目

问题描述

有一家生化所，一月份引入一对新生的小白鼠。这对小白鼠生长两个月后，在第三、第四、第五个月各繁殖一对新小白鼠，在第六个月停止繁殖，在第七个月则死亡。新生的小白鼠也如此繁殖。问在第N个月时，活的小白鼠有多少对？

输入说明

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组输入数据由一行组成，其中只有一个整数N（0 < N ≤ 50）。两组输入数据间无空行。

输出说明

对于每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的文本终端）输出一行，其中只有一个整数，即第N个月时活的小白鼠有几对，所有数据前后没有多余的空行，两组数据之间也没有多余的空行。

个人总结

思路

使用数组模拟老鼠的年龄分布。定义一个数组a[8]，下标1到6分别代表1个月大到6个月大的活老鼠数量，下标7代表第7个月（刚死亡）的老鼠。
初始时a[1]=1，其余为0。
模拟每个月变化时包含两步：首先是生长，通过循环从后往前将老鼠年龄加1（例如把a[6]移到a[7]，a[1]移到a[2]），倒着循环是为了防止数据还没用就被覆盖；其次是繁殖，新的a[1]由当前的a[3]、a[4]、a[5]之和决定。
循环计算N-1次后，将a[1]到a[6]累加即为结果。

易错点

1. N=50时老鼠总数非常巨大，会超过int范围，因此统计总和的变量sum必须定义为long long类型，否则会发生溢出错误。
2. 每次读取新N值后必须清空数组并重新初始化
3. 不用统计a[7]因为题目要求计算活的老鼠。
4. 计算的月份数量应该比输入的少1，因为第一个月就是初始状态。

知识点

1. 数组的定义与初始化

在 OJ 中，通常把数组的大小开得比题目要求的稍大一点（比如题目说 N≤1000N \le 1000N≤1000，就开 1005）。

方式一：定义在 main 函数外面（全局变量）—— 最推荐

#include <iostream>
using namespace std;

// 推荐：使用 const 定义最大范围，方便修改
const int N = 100005; 

// 定义在全局，有两个好处：
// 1. 默认初始化为 0（不用动手清空）。
// 2. 内存存在堆/静态区，空间很大，开几百万的数组也不会爆栈。
int a[N]; 

int main() {
    // 此时 a[0] 到 a[100004] 全是 0
    return 0;
}

方式二：定义在 main 函数里面（局部变量）

int main() {
    // 危险：默认是随机垃圾值！必须手动初始化。
    int b[10]; 
    
    // 写法 A：全部初始化为 0（最常用）
    int c[10] = {0}; 
    
    // 写法 B：部分初始化，剩下的自动补 0
    // d[0]=1, d[1]=2, 后面全是 0
    int d[10] = {1, 2}; 
    
    // 警告：局部数组开太大（比如超过 10^5 int）会导致 Stack Overflow（爆栈/段错误）。
    // 所以大数组一定要放在 main 外面。
    return 0;
}

方式三：使用 memset 清空/赋值

在“多组测试数据”的题目中，每次处理下一组数据前需要重置数组，常用 memset。需包含 <cstring> 头文件。

#include <cstring> // 必须头文件

int a[1005];

int main() {
    // 将 a 数组全部清零
    memset(a, 0, sizeof(a));
    
    // 将 a 数组全部变为 -1 (图论题常用，表示未访问)
    memset(a, -1, sizeof(a));
    
    // 警告：memset 是按字节赋值的。
    // 除了 0 和 -1，赋其他整数（如 1）会得到奇怪的值，别乱用。
    return 0;
}

2. 常见的“坑”与注意事项

1. 数组下标从 0 开始

• 如果不习惯，可以开大一点，从下标 1 开始用。
• 比如 int a[105];，你就可以放心地用 a[1] 到 a[100]，把 a[0] 空着不用即可，很多算法（如前缀和）这样做更方便。

2. 不要用变量定义数组大小 (VLA)

虽然部分编译器支持下列写法，但标准 C++ 不推荐，且在某些 OJ（如使用 MSVC 编译器）会报错 CE。

// 错误示范（虽然有时能跑通）：
int n;
cin >> n;
int a[n]; // 不要这样写！

正确做法：看题目数据范围，比如 N≤1000，就直接 const int N = 1010; 然后开 int a[N];不管输入多少，反正开到最大够用就行。

3. 越界（Runtime Error / Segmentation Fault）

这是新手最常犯的错误。

int a[10];
// 合法下标是 0 到 9
a[10] = 5; // 越界！a[10] 已经超出范围了。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	// 用数组储存储当前处于每个月的小白鼠数量，
	// 多开一格把第0个位置空出来，好让月份和数组下标一一对应
	long long a[8]; 
	while (cin >> N){
		// 初始化数据
		memset(a, 0, sizeof(a)); 
		a[1] = 1;
		
		// 开始逐个月份向后推
		for (int i = 1; i < N; i++){ // 从 1 而不是 0 开始
			// 所有小白鼠年龄向后一个月，7月小白鼠数量覆盖不保留
			for (int j = 6; j > 0; j--){
				a[j+1] = a[j];
			}
			// 增加新生的小白鼠
			a[1] = a[3] + a[4] + a[5];
		}
		
		// 计算并输出活着的小白鼠，第 7个月的不算
		int sum = 0;
		for (int i = 1; i < 7; i++){
			sum += a[i];
		}
		cout << sum <<"\n";
		
	}
	
	return 0;
}

35. 奇妙的数字

题目

问题描述

有一种自然数，它的各位数字之和能被17整除。这个数的后继数（即这个数加1）的各位数字之和也能被17整除。求所有自然数中，从小到大第n个这样的数。

输入说明

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组输入数据占一行，其中仅有一个整数n（1≤n≤10）。在行首和行尾没有多余的空格。所有数据前后没有多余的空行，两组数据之间也没有多余的空行。

输出说明

对每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的终端）依次输出一组对应的答案。每组答案占一行，每行中仅有一个整数，即题目描述中的第n个数。在行首和行尾不要输出多余的空格。在所有数据的前后，以及两组数据之间不要输出多余的空行。

个人总结

1. 预处理策略：题目有多组输入但N的范围很小（1到10），采用“打表”的思想，在读取输入前先通过循环算出前10个结果存入数组，之后直接输出，避免重复计算。
2. 暴力枚举逻辑：从1开始逐个增加数字num，通过编写辅助函数判断其“各位数字之和”能否被17整除。
3. 连续性判断：使用变量last记录上一个符合条件的数。如果当前数num符合条件，且num等于last+1，说明找到了两个连续的数，此时last即为所求的一个解。
4. 数据类型陷阱：int类型最大值约为21亿，本题这类数字增长非常快，第10个数极大概率超出int范围，循环变量num和结果数组必须使用long long，否则会发生溢出导致死循环或错误。
5. 时间复杂度：逐个加1枚举效率很低，如果题目要求的N稍大一点就会超时（TLE），这种解法仅适用于本题特例的小数据范围。不过即使出现 n 很大的题目，这题的代码也不是完全没用。可以通过这段代码暴力打表，找出前面的几十个数字。找规律会发现，符合条件的数字都是以 99 结尾的。

代码

#include <bits/stdc++.h>
using namespace std;

bool div17(int n){
	// 求各位和
	int a;
	int sum = 0;
	
	while (n != 0){
		a = n % 10;
		sum += a;
		n /= 10;
	}
	
	// 返回是否能整除
	return sum % 17 == 0;
}



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	// 算出前10个数
	long long res[11] = {0};
	int cnt = 0;
	int num = 1; // 从1开始逐个判断
	int last = 0; // 上一个符合条件的数字，初始为0
	while (cnt < 10){
		if (div17(num)){ // 本数符合
			if (num == last + 1){ // 上一个数也符合
				cnt++;
				res[cnt] = last; // 储存
			}
			// 不管它是不是，都更新上一个
			last = num;
		}
		// 更新数字
		num++;
	}
	
	int n;
	while(cin >> n){
		cout << res[n] << "\n"; // 直接输出对应结果
	}
	
	return 0;
}

36. 整除的尾数

题目

问题描述

一个整数，只知道前几位为a，不知道末二位，被另一个整数b除尽了(即没有余数)，那么该数的末二位该是什么呢？

程序已完成主体框架,请完成以下函数getResult的函数体。

getResult的功能为：

    根据传入的参数a和b，求出所有符合条件的末二位（尾数）放入数组weishu中，数组weishu按升序排列。函数返回符合条件的尾数个数。

部分代码如下

prog_re.zip)：

//以下代码可自行修改成C++代码

#include <stdio.h>

int getResult(int a, int b, int weishu[])

{

    //请完成此函数

}

int main()

{

    int a, b, weishu[100],count,i;

    scanf("%d%d", &a, &b);

    count=getResult(a,b,weishu);

    for(i=0; i<count; i++)

    {

        if (i>0)

            printf(" ");

        printf("%02d", weishu[i]);

    }

    printf("\n");

    return 0;

}

个人总结

1. 这道题目整体思路在之前的题目中已经做过，主要考察的就是封装成函数。
2. 要格外注意的是，main 中隐含了需要函数返回数字个数的条件，因此需要 return cnt。如果返回的是其他内容，比如 return 0,会导致后续的输出无法正常执行。

代码

#include <bits/stdc++.h>
using namespace std;

int getResult(int a, int b, int weishu[])

{

    //请完成此函数
    int cnt = 0;
    for (int i = 0; i < 100; i++){
    	if ((a * 100 + i) % b == 0){
    		weishu[cnt] = i;
    		cnt++;
		}
	}
	
	return cnt;
}


int main(){
	int a, b, weishu[100],count,i;

    scanf("%d%d", &a, &b);

    count=getResult(a,b,weishu);

    for(i=0; i<count; i++)

    {

        if (i>0)

            printf(" ");

        printf("%02d", weishu[i]);

    }

    printf("\n");

    return 0;
}

计算机英语翻译练习

Ill. The Turing Test

In the past the Turing test (proposed by Alan Turing in 1950) has served as a benchmark in measuring progress in the field of artificial intelligence. Today the significance of the Turing test has faded although it remains an important part of the artificial intelligence folklore. Turing's proposal was to allow a human, whom we call the interrogator, to communicate with a test subject by means of a typewriter system without being told whether the test subject was a human or a machine. In this environment, a machine would be declared to behave intelligently if the interrogator was not able to distinguish it from a human. Turing predicted that by the year 2000 machines would have a 30 percent chance of passing a five-minute Turing test-—a conjecture that turned out to be surprisingly accurate.

在过去，图灵测试（1905 年由 Alan Turing 提出）是衡量人工智能进展的基准测试。

时至今日，图灵测试的重要性已经逐渐淡化，但它仍然是人工智能民间传说中的重要组成部分。

图灵的提案是，让一个我们称之为“询问者”的人类，在不知道测试对象是人类还是机器的情况下，通过打字机系统与测试对象沟通。

在这种情况下，如果询问者无法区分对方是机器还是人类，则该机器就被判定为表现出了智能。

图灵预测到 2000 年，机器会有 30%的概率通过 5 分钟的图灵测试，这一猜测惊人的准确。

One reason that the Turing test is no longer considered to be a meaningful measure of intelligence is that an eerie appearance of intelligence can be produced with relative ease. A well-known example arose as a result of the program DOCTOR (a version of the more general system called ELIZA) developed by Joseph Weizenbaum in the mid1960s. This interactive program was designed to project the image of a Rogerian analyst conducting a psychological interview; the computer played the role of the analyst while the user played the patient. Internally, all that DOCTOR did was restructure the statements made by the patient according to some well-defined rules and direct them back to the patient. For example, in response to the statement "I am tired today," DOCTOR might have replied with "Why do you think you're tired today?" If DOCTOR was unable to recognize the sentence structure, it merely responded with something like "Go on" or "That's very interesting."

图灵测试不再被当做一种衡量智能的有意义标准的原因之一，是一种可以轻易制造智能表现的诡异方法。

一个著名的例子是 Joseph Weizenbaum 在 20 世纪 60 年代中期开发的 DOCTOR 程序（它是通用系统 ELIZA 的一个版本）的结果。

这个交互式程序旨在模拟一位进行心理访谈的罗杰斯式分析师。电脑扮演分析师的角色，而用户扮演病人。

在内部，DOCTOR 所做的一切，只不过是根据一些精心制定的规则，把病人的叙述重组一遍，然后再把这句话直接返回给病人。

例如当回应“我今天很累”这句话时，DOCTOR 也许会回复说：“你为什么会觉得今天很累？”如果 DOCTOR 无法识别句子结构，它仅仅会回复像“继续“或”这很有趣”这类的话语。

Weizenbaum's purpose in developing DOCTOR dealt with the study of natural language communication. The subject of psychotherapy merely provided an environment in which the program could "communicate." To Weizenbaum's dismay, however, several psychologists proposed using the program for actual psychotherapy. (The Rogerian thesis is that the patient,not the analyst, should lead the discussion during the therapeutic session, and thus, they argued, a computer could possibly conduct a discussion as well as a therapist could.) Moreover, DOCTOR projected the image of comprehension so strongly that many who "communicated" with it became subservient to the machine's question-and-answer dialogue. In a sense, DOCTOR passed the Turing test. The result was that ethical,as well as technical,issues were raised,and Weizenbaum became an advocate for maintaining human dignity in a world of advancing technology.

Weizenbaum 开发 DOCTOR 程序的初衷是为了研究自然语言交流。心理治疗项目仅仅是用来给程序提供交流环境的。然而让他失望的是，几位心理学家竟然提议将该程序用于实际的心理治疗。

（罗杰斯理论认为，在心理治疗过程中，应该由病人而不是分析者来引领话题，因此这些心理学家认为，计算机或许能像治疗师一样引导讨论）

此外，DOCTOR 营造出的理解力假象如此强烈，以至于许多与之“交流”的人在机器的问答对话中变得唯命是从。

从某种意义上讲， DOCTOR 通过了图灵测试。但它也引发了伦理及技术层面的双重问题。而 Weizenbaum 也由此成为在技术飞速发展的世界中维护人类尊严的倡导者。