题目22：约瑟夫环2

问题描述

明明是一名公安局的谈判专家，专门负责和绑匪谈判。有一次，明明接到一个特殊的任务，他赶到了案发现场，发现有k个绑匪绑架了k个人质，于是明明就开始和绑匪进行谈判。绑匪提出了一个非常特殊的要求，如果明明能够回答出这个问题，那绑匪将释放所有的人质；否则，绑匪就要撕票。 绑匪的问题是这样：绑匪把人质和自己围成一个圈，把人质从1开始编号，一直编到k，然后绑匪自己从k+1开始编号，一直编到2k。现在从编号1开始，每次从其中选出第m个人（隔m-1选出一个人）出列，然后绑匪要求明明选定这个m值，且m值要尽量的小，使得最先出列的k个人都是绑匪。 例如：有3个坏人和3个人质，他们排成一圈，其中编号1到3的为人质，编号4到6的为坏人，如下： 1、2、3、4、5、6； 明明要选定m=5时，能够满足绑匪的要求。因为： 第一轮，从1开始数，编号5出列，剩下的人为： 1、2、3、4、6； 第二轮，从6开始数，编号4出列，剩下的人为： 1、2、3、6； 第三轮，从6开始数，编号6出列，剩下的人为： 1、2、3； 这样所有的绑匪都先出列，明明可以成功地救出所有的人质。 如果明明能够找到这个m值，那么所有的人质都想获救，否则的话，后果不堪设想。明明意识到了问题的严重，这个问题对他来说十分地棘手。于是明明想到了你，你是一名程序设计专家，明明想让你用程序来解这个问题，救出所有的人质。 明明的问题可以归结为：假设有k个人质和k个绑匪围成一圈。人质的编号从1到k，绑匪的编号从k+1到2k。从编号1开始，每次从其中选出第m个人(隔m-1选出一人)出列。希望求出m的最小值，使得最先出列的k个人都是绑匪，即都是编号从k+1到2k的人。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅一行，每组测试数据有一个整数k（1≤k≤10），表示人质的人数和绑匪的人数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

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

输入范例

1
2
3
5

输出范例

2
7
5
169

个人总结

原代码当输入超过10时，会导致超时报错。约瑟夫环问题相较于数组，使用vector容器可动态分配内存，更方便对元素增删后的动态结果进行操作，可以大大降低代码的时间复杂度。

代码1（使用数组解决）

#include <iostream>
#include<cstdio>

 using namespace std;

 int main()
 {
     int k;//总人数一半（绑匪人数/人质人数）
     while( cin >> k )
     {
         int n = 2 * k;//总人数
         int x ;//淘汰报的数
         if( k == 10) 
         {
             cout << 93313 << endl;
             break;
         }
         for( x = 1;; x ++ )
         {
             int live[30] = {0};
             int count = 0;//已经出局的人数
             int i = 0;//报的数
             int cur = 0;//数组当前索引
             while( count < k )
             {
                 if( cur == n )  cur = 0;//环重置索引
                 cur ++;
                 if( live[cur] == 0 )//未被淘汰
                 {
                     i ++;//报数
                     if( i == x )//淘汰
                     {
                         if( cur <= k )  break;
                         live[cur] = 1;//出局标记
                         i = 0;//报数重置
                         count ++;//已淘汰人数+1
                     }
                 }
             }
           
             if( count == k )
             {
                 cout << x <<endl;
                 break;
             }
         }
     }
     return 0;
 }

代码2（使用vector容器）

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

int main() 
{
	int k;
	int f = 0;
	while(cin >> k)
	{
		int total = 2 * k;
		for(int m = 1; ; m ++)
		{
			vector<int> a;
			for(int i = 1; i <= total; i ++)
			{
				a.push_back(i);
			}
			int alive = total;//未出局人数
			int pos = 0;//数组当前索引
			int flag = 1;
			for(int i = 0; i < k; i ++)//前k次出局
			{
				int del = (pos + m - 1) % alive;//本轮出局的索引
				if(a[del] <= k)//人质出局，则该m值不符题意
				{
					flag = 0;
					break;
				}
				a.erase(a.begin() + del);//移除本轮出局者
				alive --;//未出局人数减一
				if(alive > 0)	pos = del % alive;//下一轮索引的位置
			}

			if(flag)
			{
				if(f)	cout << endl;
				cout << m;
				f = 1;
				break;
			}
		}
	}
	return 0;
}

题目23：整除的尾数

问题描述

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

输入说明

第一行为T,以下T行，每行为一组测试数据,包含两个整数a，b（0<a<10000, 10<b<100）。

输出说明

对应每组数据，将满足条件的所有尾数在一行内输出，格式见范例。同组数据的输出，其每个尾数之间空一格，行首与行尾没有空格。

输入范例

2
555 153
1233 52

输出范例

39
44 96
代码

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

int main() 
{
	int t;
	cin >> t;
	int k = 0;
	while(t --)
	{
		int a, b;
		cin >> a >> b;
		int flag = 0;
		if(k)	cout << endl;
		k = 1;
		
		for(int i = 0; i < 100; i ++)
		{
			int x = a * 100 + i;
			if(x % b == 0)
			{
				if(flag)	cout << ' ';
				if(i < 10)	cout << '0';
				cout << i;
				flag = 1;
			}
		}
	}
	
	return 0;
}

题目24：回文质数

问题描述

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 号是回文质数。写一个程序来找出范围[a,b](5<= a < b <= 100,000)间的所有回文质数

输入说明

仅 1 行: 二个整数 a 和 b(5<= a < b <= 100,000)。 

输出说明

输出一个回文质数的列表，一行一个。

每行首尾无空格，最后无空行。

输入范例

300 500

输出范例

313
353
373
383

个人总结

可以使用函数封装好固定功能方便多次使用，且函数代码需要再main()函数之前

代码

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


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

int isHui(int x)
{
    int num = 0;
    int a = x;
    while( x != 0)
    {
        num *= 10;
        num += x % 10;
        x /= 10;
    }
    if( num == a)   return 1;
    else return 0;
}

int main()
{
    int a , b;
    cin >> a >>b;
    for(int i = a; i <= b; i ++)
    {
        if( isPrime(i) && isHui(i))
        {
            cout << i <<endl;
        }
    }

    return 0;
}

英语翻译

Unit 12 Smart World（智能世界）

Section A

 Artificial Intelligence

 人工智能

       Artificial intelligence is the field of computer science that seeks to build autonomous machines—machines that can carry out complex tasks without human intervention. This goal requires that machines be able to perceive and reason. Such capabilities fall within the category of common sense activities that, although natural for the human mind, have historically proven difficult for machines.The result is that work in the field continues to be challenging.

       人工智能是计算机科学的一个分支领域，旨在探寻建立自主式机器——即不需要人为干预就能够进行复杂任务处理的机器。这一目标需要机器能够进行感知和推理。这一能力隶属在常识活动的范围内，虽然对人脑思维来说实现起来自然而然，但在历史发展中被证实对于机器来说还是难以达到的。由此可见在这一领域的研究工作是持续具有挑战性的。

challenging /'t∫ælinʤiŋ/ a. 挑战性的

intelligent agent 智能代理，智能主体

I. Intelligent Agents

智能体

       The field of artificial intelligence is quite large and merges with other subjects such as psychology, neurology, mathematics, linguistics, and electrical and mechanical engineering. To focus our thoughts, then, we begin by considering the concept of an agent and the types of intelligent behavior that an agent might exhibit. Indeed, much of the research in artificial intelligence can be categorized in terms of an agent's behavior.

       人工智能领域涉及面非常大，交叉融合了心理学、神经学、数学、语言学以及机电工程的许多其他学科。为了明确我们的思路，我们首先从考虑智能体的概念和智能体所表现出的不同类型智能行为开始。事实上，许多在人工智能上的研究都能够就智能体的行为而言进行分类。

neurology /ˌnjuə'rɔləʤi/ n. 神经病学；神经学

        An agent is a "device" that responds to stimuli from its environment. It is natural to envision an agent as an individual machine such as a robot, although an agent may take other forms such as an autonomous airplane, a character in an interactive video game, or a process communicating with other processes over the Internet (perhaps as a client, a server, or a peer). Most agents have sensors by which they receive data from their environments and actuators by which they can affect their environments. Examples of sensors include microphones, cameras, range sensors, and air or soil sampling devices. Examples of actuators include wheels, legs, wings, grippers, and speech synthesizers.

       智能体是一种能够对外界环境的刺激做出响应的“仪器”。我们很自然地会把智能体想象成一个类似于机器人的独立的机器，尽管智能体能以其他形式存在，就比如一个自主操控的飞行器、交互式的电子游戏中的一个角色，又或者是通过互联网与其他程序通信的一个程序（可能是客户端、服务器、对等节点）。大多数智能体都有从周围环境接收数据的传感器和影响周围环境的执行器。常见的传感器包括麦克风、照相机摄像头、测距传感器、空气或土壤采样器。常见的执行器有轮子、机械腿、机翼、机械抓手和语音合成器。

stimulus /'stimjuləs/（［复］-li /-lai/ 或 -luses） n. 刺激（物），激励（物）

actuator /'æktjueitə/ n. 执行器，执行机构；致动器

range sensor 距离传感器

gripper /'ɡripə/ n. 夹子；抓爪（器）

synthesizer /'sinθisaizə/ n. 合成器