题目39：约瑟夫环

有一次，明明的公司举行忘年会。忘年会的高潮部分是最后的抽大奖环节。公司为了增加活动的气氛，并没有按传统的抽奖方式来抽，而是进行了一个游戏：逐步逐步地淘汰人，而最后剩下的人，将会得到大奖。

这个游戏的方式如下：首先公司的全部职员围成一个圈，然后确定一个淘汰数X，接着就从其中的一个人开始，从1数数，当数到X时，那个人就被淘汰出局，接着下一个人再从1开始数数，一直这样重复下去，直到剩下最后一个人，那个人就是最后的大奖得主。

例如，公司有5个人，淘汰数定为2，则一开始五个人排成一圈，依次编号为：1、2、3、4、5； 首先从编号1的人开始数数，数到2后，编号2淘汰，这样只剩下4个人：1、3、4、5； 接着从编号3的人开始数，数到2后，编号4淘汰，这样只剩下3个人：1，3、5； 接着从编号5的人开始数，数到2后，编号1淘汰，这样只剩下2个人：3、5； 最后从编号为3的人开始数，数到2后，编号5淘汰，最后编号为3的那个人就获得了最终的大奖。 （注：以上的淘汰顺序为2 4 1 5 3。）

由于明明的运气十分地差，最后第二个被淘汰，与大奖失之交臂，十分郁闷。他想知道自己被淘汰的全过程，于是他想请你帮个忙，帮他写一个程序，明明把他公司的人数告诉你，并且把那个淘汰数也告诉你，你的程序能够根据这两个数计算出淘汰人的具体顺序，即把淘汰人的编号按顺序输出。

明明的问题可以归结为：给你一个公司的人数N和一个淘汰数X，你的程序模拟上面描述的淘汰方式，输出淘汰人的编号顺序。

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅一行，每组测试数据有两个整数N（1<N<100）和X（0<X<10），N表示公司的人数，X表示淘汰数，两个整数用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

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

总结：

1. people[] 记录淘汰状态，0表示未淘汰，1表示淘汰，初始时均为0

2. remaining记录当前未被淘汰的人数，每淘汰一个人remaining--

3. output_count记录已输出的人数，用于控制空格，除第一个淘汰的人外，以后每淘汰一个人之前输出一个空格

4. current记录当前位置，用于遍历所有人，初始时current = 0，代表第一轮从第一个人开始数，每数一个人后移一个，current = (current + 1) % n

5. count记录每一轮数到了第几个人，若count数到了第x个人则淘汰，输出这个人，然后令count = 0，开始下一轮淘汰

#include <stdio.h>
int main(){
    int n, x;
    while(scanf("%d %d", &n, &x) != EOF){
        int people[n];  //标记是否被淘汰
        int remaining = n, output_count = 0;
        int current = 0, count = 0;
        for(int i = 0; i < n; i++){
            people[i] = 0;
        }
        while(remaining > 0){
            if(people[current] == 0){
                count++;  //数到x则淘汰
                if (count == x) {
                    people[current] = 1;  //标记为淘汰
                    remaining--;         //剩余人数减1
                    //输出淘汰编号（编号是1-n，所以+1）
                    if (output_count > 0) {
                        printf(" ");
                    }
                    printf("%d", current + 1);
                    output_count++;
                    count = 0; //开始下一轮淘汰
                }
            }
        //移动到下一个人
            current = (current + 1) % n;
        }
        printf("\n");
    }
    return 0;
}

---

题目41：环

明明喜欢玩游戏，而明明的爸爸也乐意陪明明玩各种各样的小游戏。但是在游戏中，明明的爸爸又十分注意培养明明的智力，他希望通过游戏，不仅能让明明得到快乐，而且又能让明明学到一些知识，锻炼他的思维能力，为将来的发展打下基础。

一天，明明的爸爸和明明做起了一个叫“环”的游戏。游戏的内容很简单但却很有趣，就是有1到9九个整数，他们以任意的顺序排列成一个圆环，然后要在这个圆环中剪一刀，再分别按顺时针和逆时针次序排列成两个九位数。现在的要求是，得到的这两个九位数差的绝对值能被396整除，问一共有几种剪环的方法。 例如九个数的排列为：1、2、3、4、5、6、7、8、9，在1和9之间剪一刀（注意：因为是一个环，所以1和9是相邻的。），顺时针形成的数为：123456789，逆时针形成的数为：987654321，这两个数的差的绝对值为：864197532，这个数能被396整除，因此这是一种符合规则的剪法，更奇妙的是，这也是这种排序方式的唯一剪法。

明明显然对这个游戏非常感兴趣，高兴地做起来。但是玩了几次后，明明发现这个游戏又并不是那么容易了，因为对于这九个数来说，虽然一共只有九种剪法，但是每种方法都要试，且还要做加法再做除法，他觉得非常的麻烦，玩着玩着就失去了兴趣。明明的爸爸发现了这个问题，于是就找到了你，他请你来帮明明一把，写一个程序，计算出某个排序中符合条件的剪法共有几种，这样的话可以大大鼓励明明玩游戏的兴致。

明明爸爸的问题可以归结为：将1至9这九个数字，以任意顺序排成一个环，请在某两个数字之间剪开，分别按顺时针和逆时针次序排列成两个九位数，要求剪开后所得到的这两个九位数的差能被396整除，问共有几种剪法？

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，输入的第一行有一个整数n，表示一共有多少组测试数据，接下来有n行，为n个测试数据，每组测试数据有9个数字，表示一种环的排列顺序，每个数字之间用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

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

总结：

1. 长度为9的数组有九种分割方式，分割之后顺时针和逆时针次序排的数刚好为逆序，使用long long类型存储两个顺序得到的数，temp1 += arr[x] * pow(10, 8 - k); temp2 += arr[x] * pow(10, 8 - k);

2. abs() 取整数的绝对值，头文件中加上#include <stdlib.h>

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(){
    int n, m;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){//n种测试数据
        int count = 0;
        int arr[9];
        for(int j = 0; j < 9; j++){//将测试数组用数组存储
            scanf("%d", &m);
            arr[j] = m;
        }
        for(int j = 0; j < 9; j++){//九种分割方式
            long long temp1 = 0, temp2 = 0;
            for(int k = 0; k < 9; k++){
                int x = (j + k) % 9;
                temp1 += arr[x] * pow(10, 8 - k);
            }
            for(int k = 0; k < 9; k++){
                int x = (j + k) % 9;
                temp2 += arr[x] * pow(10, k);
            }
            int y = abs(temp1 - temp2);
            if(y % 396 == 0)
                count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

---

题目42：求数列项

数列是数学世界中一种非常有趣的数字排列规则，它使一串数字相互之间产生了某种联系，变幻无穷。很多数学家对数列产生了浓厚的兴趣，花了很多时间对其进行研究，明明就是其中的一位。一天，他又专注于一种新的数列排列规则，该排列规则满足以下条件：

1. 该数列的第一个数为1。

2. 该数列的第二个数为5。

3. 该数列的第i （其中i > 2）个数为第i - 1个数的数值加上(i - 3) × 3 + 7。

明明很快就推算出了这个数列的前三项数字：

1. 第一项为1。

2. 第二项为5。

3. 第三项为12。（第三项的数字为第二项的数字加上(3 - 3) × 3 + 7，即第三项的数为：5 + (3 - 3) × 3 + 7 = 12）

但是当明明还想继续把数列往下推算的时候，他发现计算量越来越大，计算难度越来越高，计算速度也越来越慢。于是，明明就求助于你这位程序设计专家，帮他写一个程序，计算出数列的前50项，然后当明明需要知道数列中的哪一项的数字时，你就把那一项的数字告诉明明。 明明的问题可以归结为：跟据一个正整数n，要求你输出题目中所描述的数列的第n项数值。

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

对于每一组测试数据，你写的程序需要计算出一组相应的运算结果，并将每组运算结果依次写入到标准输出设备（通常为启动该程序的文本终端，例如Windows中的命令行终端）中。每组运算结果为一个整数，即题目中所描述的数列的第n项数值。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。

总结：

使用for循环输出到第n项

#include <stdio.h>
int main(){
    int n, temp;//count:第几项  temp:第count项的值
    while(scanf("%d", &n) != EOF){
        temp = 1;//第一项的值
        for(int i = 2; i <= n; i++){
            temp += (i - 3) * 3 + 7;
        }
        printf("%d\n", temp);
    }
    return 0;
}

---

翻译：

II定义和范围
尽管AR将用户置在一个完全有电脑产生的环境中，AR的目的是展示直接注册到物理环境中的信息。AR超越了移动计算，因为它在空间上和认知上连接了虚拟世界和真实世界的间隙。通过AR，数字信息似乎成为真实世界的一部分，至少在用户的看法中。

到达这个连接是一个宏伟的目标，这个目标要利用计算机科学很多领域的知识，然而这会导致对AR到底是什么的误解。例如，很多人将虚拟和现实元素的视觉联系与例如侏罗纪公园和化身这种电影里的特殊效果联系起来。虽然用在电影里的计算机图形技术也可以应用在AR上，但是电影缺乏AR交互性这个关键方面。为了避免这种困惑，我们需要为讨论的主题设置一个范围。换句话说，我们需要回答一个关键问题：什么是AR？

最广泛被接受的AR的定义由阿祖玛在他1997年的调查论文中提出。依照阿祖玛所说，AR必须有以下三种特征：
·连接现实和虚拟
·实时交互
·3D显示