编程题练习
一、黑色星期五
章节: 一维数组
问题描述
13号又是星期五是一个不寻常的日子吗? 13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13 日落在星期一,星期二……星期日的次数.这个测试从1900年1月1日到 1900+n-1年12月31日.n是一个非负数且不大于400.
这里有一些你要知道的: 1900年1月1日是星期一. 4,6,11和9月有30天.其他月份除了2月都有31天.闰年2月有29天,平年2月有28天.
输入说明
一个整数n（1<= n <= 400）.
输出说明
七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一…..星期五的次数.
输入范例
20
输出范例
36 33 34 33 35 35 34
问题作答
完整代码
#include <iostream>
using namespace std;
int getMonthDays(int year, int month)
{
switch(month)
{
case 2:
return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0) ? 29 : 28;
case 4:
case 6:
case 9:
case 11:
return 30;
default:
return 31;
}
}
int main()
{
int n;
cin >> n;
int result[7] = {0};
int currentDay = 6;
for(int year = 1900; year < 1900 + n; year++) {
for(int month = 1; month <= 12; month++) {
int index = (currentDay + 1) % 7;
result[index]++;
int daysInMonth = getMonthDays(year, month);
currentDay = (currentDay + daysInMonth) % 7;
}
}
for(int i = 0; i < 7; i++) {
cout << result[i];
if(i < 6) cout << " ";
}
}
运行范例
个人总结
1.本题要求统计从1900年1月1日（已知为星期一）开始的连续 n年（1 ≤ n ≤ 400）中，每个月的13号落在周六、周日、周一至周五的次数
2.1900年1月1日为星期一，则1月13日为星期六，设 currentDay表示当前月13号的星期数， 每月13号的星期数确定后，累加到统计数组 result[]，下个月13号的星期 = (当前月13号的星期 + 当前月的天数) % 7
3.外层循环年份（1900 ~ 1900+n-1），内层循环月份（1~12），每次内层循环更新 result[currentDay]++并计算下个月的 currentDay
二、树
章节: 一维数组
问题描述
明明是一家地铁建设公司的职员，他负责地铁线路的规划和设计。一次，明明要在一条长L的马路上建造若干个地铁车站。
这条马路有一个特点，马路上种了一排树，每两棵相邻的树之间的间隔都是一米。
如果把马路看成一个数轴，马路的一端在数轴0的位置，马路的另一端在L的位置，那么这些树都种在数轴的整数点上，即0，1，2，…，L上都种有一棵树。
由于要设计建造地铁站的缘故，所以需要把一些树移走，明明为了移树的方便，把地铁站的区域也建在了数轴上两个整数点之间，由于有多条地铁线路，地铁车站的区域可能会有部分的重合（重合的区域明明将来会设计成一个大型的车站，移树的时候不必考虑地铁站重合区域的问题）。
现在明明想请你帮一个忙，他把车站区域的位置告诉你，即告诉你数轴上的两个整数点，在这两个整数点之间是车站的区域，请你写一个程序，计算出把所有车站区域两点之间的树移走以后，这条马路上还剩多少棵树。
例如：马路长为10，要建造2个地铁车站，车站的区域分别是2到5和3到6，原先的马路上一共有11棵树，在2到5的位置上建车站后，需要移走4棵树，在3到6的位置上建车站后，也需要移走4棵树，但是3到6这个区域和2到5这个区域有部分重合，所以只需移走1棵树即可，这样总共移走的树是5棵，剩下的树就是6棵。
明明的问题可以归结为：给你一条马路的长度和若干个车站的位置，请你用程序计算出把树移走后，马路上还剩多少棵树。
输入说明
你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有多行，每组测试数据的第一行有两个整数L（1≤L≤10000）和M（0≤M≤100），分别表示马路的长度和地铁车站区域的个数。接下来有M行，每行有2个整数，分别表示每一座地铁车站区域的两个坐标的。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。
输出说明
对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即把树移走后，马路上还剩下多少棵树。每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。
输入范例
5 1
1 2
10 2
2 5
3 6
输出范例
4
6
问题作答
完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int calculateRemainingTrees(int L, int M, vector<pair<int, int>>& stations) {
int totalTrees = L + 1;
vector<pair<int, int>> merged;
sort(stations.begin(), stations.end());
for (const auto& station : stations) {
int left = min(station.first, station.second);
int right = max(station.first, station.second);
if (merged.empty() || merged.back().second < left) {
merged.push_back({left, right});
} else {
merged.back().second = max(merged.back().second, right);
}
}
int removedTrees = 0;
for (const auto& interval : merged) {
removedTrees += (interval.second – interval.first + 1);
}
return totalTrees – removedTrees;
}
int main() {
int L, M;
while (cin >> L >> M) {
vector<pair<int, int>> stations;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
stations.push_back({a, b});
}
int result = calculateRemainingTrees(L, M, stations);
cout << result << endl;
}
}
运行范例
个人总结
1.本题可以理解为在数轴0到L的每个整数点上都有一棵树，给出M个需要移走树木的区间（区间可能重叠），要求计算移走这些区间内的所有树木后，马路上剩余的树木数量
2.先将所有区间按左端点排序。然后遍历区间，将相互重叠的区间合并成一个大区间，如果当前遍历到的区间的左端点小于等于当前合并区间的右端点，说明两个区间有重叠。此时更新当前合并区间的右端点为两者右端点的最大值。如果当前遍历到的区间的左端点大于当前合并区间的右端点，说明区间不重叠。此时可以将之前的合并区间计入总移除量，然后开始新的合并区间。最后用树木总数减去所有合并后区间所覆盖的树木数
3.为了排序，导入#include<algorithm>，对车站区间进行排序（区间合并的前提）sort(stations.begin(), stations.end());处理区间端点，确保左小右大nt left = min(station.first, station.second);int right = max(station.first, station.second);在合并区间时比较右端点merged.back().second = max(merged.back().second, right);
三、约瑟夫环
章节: 一维数组
问题描述
有一次，明明的公司举行忘年会。忘年会的高潮部分是最后的抽大奖环节。公司为了增加活动的气氛，并没有按传统的抽奖方式来抽，而是进行了一个游戏：逐步逐步地淘汰人，而最后剩下的人，将会得到大奖。
这个游戏的方式如下：首先公司的全部职员围成一个圈，然后确定一个淘汰数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个整数，即淘汰人的编号的顺序，每个数之间用一个空格隔开。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。
输入范例
5 2
5 6
99 1
输出范例
2 4 1 5 3
1 3 2 5 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
问题作答
完整代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> josephus(int n, int k)
{
vector<int> result;
bool eliminated[100] = {false};
int current = 0;
int remaining = n;
while (remaining > 0) {
int count = 0;
while (count < k) {
if (!eliminated[current]) {
count++;
if (count == k) {
break;
}
}
current = (current + 1) % n;
}
eliminated[current] = true;
result.push_back(current + 1);
remaining–;
if (remaining > 0) {
int next = (current + 1) % n;
while (eliminated[next])
next = (next + 1) % n;
current = next;
}
}
return result;
}
int main()
{
int n, k;
while (cin >> n >> k)
{
vector<int> eliminationOrder = josephus(n, k);
for (size_t i = 0; i < eliminationOrder.size(); i++) {
if (i > 0)
cout << " ";
cout << eliminationOrder[i];
}
cout << endl;
}
}
运行范例
个人总结
1.本题和Day8的第一题约瑟夫环2比较接近，不过本题尝试通过数组模拟循环链表的方式实现淘汰
2.初始化所有人状态为未淘汰，从当前位置开始数k个人（跳过已淘汰的），淘汰第k个人，记录到结果数组，从下一个人开始重复上述过程，直到所有人被淘汰，通过(current + 1) % n实现循环遍历，由于N<100，可以使用固定大小的数组
翻译练习
第一段
原文
译文
最近的图灵测试“成功”的例子包括互联网病毒，它们与人类受害者进行“智能”对话，以欺骗人类放弃其恶意软件防御。此外，类似于图灵测试的现象发生在计算机游戏的背景下，例如下棋程序。虽然这些程序仅通过应用蛮力技术来选择移动，但与计算机竞争的人类经常体验到机器拥有创造力和甚至个性的感觉。类似的感觉也发生在机器人学中，其中机器被构建为具有物理属性，以投射智能特征。例如，玩具机器人狗仅仅通过倾斜头部或抬起耳朵来响应声音来投射可爱的个性。
第二段
原文
Section B
Augmented Reality and Its Applications
B部分增强现实及其应用
译文
虚拟现实（VR）越来越受欢迎，因为计算机图形学已经发展到一个阶段，图像往往与现实世界无法区分。然而，游戏、电影和其他媒体中呈现的计算机生成的图像与我们的物理环境是脱节的。这既是一种美德–一切皆有可能–也是一种局限。这种局限来自于我们对日常生活的主要兴趣，而不是指向某些虚拟世界，而是指向我们周围的现实世界。
第三段
原文
译文
从许多方面来看，增强移动计算，使与现实世界的联系自动发生，似乎是一个有吸引力的命题。增强现实（AR）有望在物理世界和电子信息之间建立直接、自动和可操作的链接。它提供了一个简单而直接的用户界面，以电子增强的物理世界。AR可以将计算机生成的信息叠加在现实世界的视图上，以显著的新方式放大人类的感知和认知。
